Skip to content
Kembali ke hasil pencarian

Mekanisme VCG

Diperkenalkan oleh
William Vickrey, Edward Clarke, Theodore Groves
Tahun
1961
Jenis
algorithm
Keluarga
Game-theoretic

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Mekanisme Vickrey-Clarke-Groves (VCG) adalah solusi desain mekanisme yang jujur yang mengalokasikan sumber daya dan menentukan pembayaran untuk mendorong peserta mengungkapkan penilaian sebenarnya.

Dibangun di atas karya lelang amplop tertutup William Vickrey tahun 1961 dan diperluas oleh Clarke dan Groves, VCG memastikan bahwa melaporkan kebenaran adalah strategi dominan bagi semua peserta, mencapai efisiensi alokatif sambil memaksimalkan surplus total.

Intuisi di balik metode

Mekanisme VCG memecahkan masalah mendasar dalam lelang dan alokasi: bagaimana mendapatkan penilaian jujur dari peserta yang mungkin sebaliknya salah merepresentasikan preferensi mereka untuk mendapatkan keuntungan. Wawasan kuncinya adalah mengenakan biaya kepada setiap peserta sebesar eksternalitas yang mereka timbulkan pada orang lain: apa yang akan diperoleh orang lain jika mereka tidak berpartisipasi. Desain ini membuat kebohongan tidak menguntungkan—penawar memaksimalkan surplus mereka sendiri dengan menawar secara jujur.

Sejarah

William Vickrey memperkenalkan lelang harga kedua amplop tertutup (lelang Vickrey) pada tahun 1961, membuktikan bahwa itu mendorong penawaran jujur. Edward Clarke dan Theodore Groves secara independen memperluas prinsip ini ke mekanisme alokasi yang lebih umum dengan pembayaran berdasarkan eksternalitas. Kontribusi mereka membentuk dasar teori desain mekanisme modern, membuat Vickrey memenangkan Hadiah Nobel Ekonomi pada tahun 1996 (anumerta) dan sangat memengaruhi desain lelang dalam praktik, terutama lelang spektrum dan pasar periklanan online.

Kapan digunakan

Terapkan VCG saat merancang mekanisme untuk alokasi sumber daya, lelang, atau penyediaan barang publik di mana pengungkapan preferensi yang jujur sangat penting. Ideal untuk lelang kombinatorial (beberapa item dengan nilai yang saling bergantung), alokasi spektrum, dan pengadaan. Gunakan ketika mencapai kompatibilitas insentif dan efisiensi alokatif adalah prioritas, bahkan jika total pembayaran mungkin lebih tinggi daripada desain alternatif.

Batasan dan pertimbangan

  • Secara komputasi tidak dapat diatasi untuk jumlah item atau peserta yang besar, membuat penentuan pemenang menjadi NP-hard
  • Sering menghasilkan defisit (pembayaran melebihi pendapatan), memerlukan subsidi dalam beberapa aplikasi
  • Rentan terhadap kolusi atau masuk/keluar penawar jika tidak dipantau dengan cermat
  • Mungkin tidak intuitif bagi peserta, mengurangi adopsi dalam pengaturan praktis

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Kejujuran strategi dominan: penawar memaksimalkan surplus dengan menawar penilaian sebenarnya mereka
  • Efisien secara alokatif: mengalokasikan sumber daya untuk memaksimalkan surplus total
  • Generalitas: berlaku untuk skenario multi-item yang kompleks dengan struktur nilai arbitrer
  • Kesederhanaan: prinsip desain mekanisme jelas dan secara teoritis elegan

Penerapan

  • Lelang spektrum: mengalokasikan spektrum radio kepada perusahaan telekomunikasi sambil mendorong penilaian jujur
  • Periklanan online: lelang iklan Google menggabungkan elemen VCG untuk mengalokasikan slot iklan berdasarkan nilai penawar
  • Pengadaan: pengadaan pemerintah dan swasta menggunakan lelang VCG terbalik untuk mendapatkan barang dengan harga kompetitif
  • Program pertukaran ginjal: mencocokkan donor dan penerima sambil mendorong pengungkapan kompatibilitas yang jujur

Cara kerjanya

Cara kerjanya

1

Meminta tawaran tertutup atau penilaian dari semua peserta tanpa mengungkapkan informasi kepada peserta lain.

2

Temukan alokasi yang efisien dengan memilih hasil yang memaksimalkan surplus total (jumlah penilaian semua peserta).

3

Tentukan pembayaran setiap peserta sama dengan kerugian yang mereka timbulkan pada orang lain: apa yang akan diperoleh orang lain jika peserta tidak hadir.

4

Konfirmasikan bahwa tidak ada peserta yang dapat meningkatkan surplus mereka dengan salah melaporkan penilaian mereka mengingat laporan jujur orang lain.

Kesalahan umum

  • Mengasumsikan kelayakan komputasi untuk masalah alokasi yang kompleks; menemukan alokasi yang efisien adalah NP-hard untuk lelang kombinatorial
  • Mencampuradukkan VCG dengan lelang harga pertama; VCG menggunakan penetapan harga berbasis keuntungan, bukan penetapan harga berbasis tawaran
  • Mengabaikan bahwa VCG mendorong kejujuran dalam penilaian tetapi tidak dalam dimensi strategis lainnya (masuk, kolusi)
  • Melupakan bahwa efisiensi bersifat global, bukan lokal; salah alokasi terjadi jika tawaran tidak mencerminkan penilaian sebenarnya

Pertanyaan yang sering diajukan

Mengapa mekanisme VCG mengenakan harga Vickrey (harga kedua) dalam lelang satu item?

Dalam lelang satu item, eksternalitas yang ditimbulkan oleh penawar tertinggi sama dengan apa yang akan dimenangkan oleh penawar tertinggi kedua, yaitu tawaran tertinggi kedua. Harga ini memastikan kejujuran sambil memaksimalkan surplus penawar yang menang.

Kapan mekanisme VCG tidak memaksimalkan pendapatan?

VCG memprioritaskan efisiensi alokatif dan kejujuran di atas maksimisasi pendapatan. Dalam beberapa kasus, itu menghasilkan defisit. Lelang harga pertama mungkin menghasilkan pendapatan lebih tinggi, tetapi dengan mengorbankan penawaran yang tidak jujur.

Bagaimana VCG menangani lelang kombinatorial dengan banyak item?

VCG mengalokasikan bundel untuk memaksimalkan surplus total, tetapi menghitung alokasi optimal adalah NP-hard. Implementasi praktis menggunakan algoritma perkiraan atau membatasi kompleksitas tawaran yang diizinkan (misalnya, menempatkan batasan pada ukuran bundel).

Metode terkait

Sumber

  1. Vickrey, W. (1961). Counterspeculation, auctions, and competitive sealed bids. The Journal of Finance, 16(1), 8-37.

    Buka referensi DOI
    Disalin.
  2. Clarke, E. H. (1971). Multipart pricing of public goods. Public Choice, 11(1), 17-33.

    Buka referensi DOI
    Disalin.