Memahami Bukti Desain Mekanisme

Saya telah berjuang dengan rincian teknis bukti tentang teori lelang dalam makalah ini: http://users.eecs.northwestern.edu/~hartline/omd.pdf

Secara khusus, Teorema 2.5: Kondisi yang diperlukan dan cukup untuk mekanisme yang benar.

Bahkan lebih spesifik, arah maju buktinya, diberikan pada halaman 6. Mendefinisikan nilai benar sebagai , dan umum, mungkin palsu, nilai (misalnya, tawaran) sebagai , penulis melanjutkan dengan postulat dua tambahan jumlah, dan . $v_i$ $b_i$ $z_1$ $z_2$

Dia kemudian menetapkan bahwa , , yang menghasilkan ketidaksetaraan berdasarkan karya sebelumnya dari makalah ini. $v_i = z_1$ $b_i = z_2$

Dia juga menetapkan bahwa , , yang menghasilkan ketimpangan yang serupa tetapi berbeda berdasarkan karya sebelumnya dari makalah ini. $v_i = z_2$ $b_i = z_1$

Oke, cukup adil. Dia kemudian mengurangi satu ketidaksamaan dari yang lain dan hasil untuk mendapatkan hasil yang diinginkan berdasarkan aljabar konsekuen. Saya tidak mengerti mengapa pengurangan itu dibenarkan - ia tampaknya mengurangi dua ketidaksetaraan yang didasarkan pada asumsi yang sama sekali berbeda (pada kenyataannya, berlawanan), dan setiap kali saya melihatnya saya dilempar dengan keras keluar dari jalur pemikiran.

Saya cukup yakin saya telah melihat pendekatan dasar ini yang lain (buku Shoham dan Leyton-Brown? Saya tidak punya cukup dekat untuk memeriksa) jadi sepertinya itu adalah ide yang umum, tetapi saya tidak bisa melewatinya. Adakah yang bisa membantu saya untuk memahami mengapa itu valid, atau menjelaskan kepada saya apa yang saya lewatkan?

(Saya sudah mencoba membuktikan hasil yang diinginkan dengan mengasumsikan tiga nilai - nilai benar , dan dua tawaran, dan - untuk mendapatkan hasil yang diinginkan, tetapi juga gagal. Jadi mungkin tidak hanya umum, tetapi perlu untuk melakukannya dengan cara penulis. Tapi saya masih belum memahaminya.) $v_i$ $b_1$ $b_2$

Pembaruan: Saya tahu saya telah melihat sesuatu yang serupa dalam buku Shoham dan Leyton-Brown . Ini tidak persis sama, tetapi sangat mirip dan berkaitan dengan persamaan dan materi pelajaran yang sama. Ini adalah Kasus 1 dari Teorema 10.4.3.

Mulai dari konteks mekanisme yang benar, mereka pertama kali menganggap jujur dan palsu dan berasal bahwa pembayaran berdasarkan adalah lebih rendah dari atau sama dengan pembayaran berdasarkan , misalnya, . Mereka kemudian menganggap berlawanan, sebuah jujur dan palsu , dan menurunkan hasil yang berlawanan, bahwa pembayaran berdasarkan $v_i$ $v_i'$ $v_i$ $v_i'$ $P_i(v_i) \leq P_i(v_i')$ $v_i'$ $v_i$ $v_i'$ kurang dari pembayaran berdasarkan , mis. . Oke, itu masuk akal. $v_i$ $P_i(v_i') \leq P_i(v_i)$

Mereka kemudian berpendapat bahwa pembayaran berdasarkan dan harus sama, seolah-olah mereka mengatakan bahwa dan secara simultan benar, meskipun mereka bukan hanya hasil dari asumsi yang berbeda, tetapi berbeda. $v_i$ $v_i'$ $P_i(v_i) \leq P_i(v_i')$ $P_i(v_i') \leq P_i(v_i)$

gt.game-theory Novak
sumber

Jawaban:

$v_i$ $v_i'$ $v_i$ $v_i$ $v_i'$ $v_i'$ $v_i'$ $v_i$

Intinya adalah bahwa kejujuran memaksakan banyak ketidaksetaraan yang berbeda pada mekanisme yang sama secara bersamaan: satu untuk setiap jenis agen mungkin miliki, dan untuk setiap penyimpangan yang mungkin dia pertimbangkan. Mereka semua memegang. Bukti ini hanya menggunakan dua dari ketidaksetaraan ini

Aaron Roth
sumber

Saya pikir saya akhirnya mulai mengerti itu. Kenyataannya, mengetahui bahwa buktinya benar (dan mengapa) membuat saya terkesan lebih kuat dan kuat tentang konsep "kejujuran". Terima kasih.

Novak

Saya pikir yang Anda inginkan adalah proposisi berikut.

$V$ $A$ $f:V^n\to A$ $p_1,\dots,p_n:V^n\to\mathbb{R}$ $i,x_i,y_i,v_{−i}$

x_{i} (f (x_{i}, v_{- i})) - p_{i} (x_{i}, v_{- i}) \geq x_{i} (f (y_{i}, v_{- i})) - p_{i} (y_{i}, v_{- i}) .

$x_i (f(x_i , v_{−i})) − p_i (x_i , v_{−i}) \geq x_i (f(y_i , v_{−i})) − p_i (y_i , v_{−i}).$

i, v_{i}, v_{i}^{'}, v_{- i}

$i,v_i,v'_i,v_{-i}$

v_{i} (f (v_{i}, v_{- i})) - v_{i} (f (v_{i}^{'}, v_{- i})) \geq v_{i}^{'} (f (v_{i}, v_{- i})) - v_{i}^{'} (f (v_{i}^{'}, v_{- i})) .

$v_i(f(v_i,v_{-i}))-v_i(f(v'_i,v_{-i}))\geq v'_i(f(v_i,v_{-i}))-v'_i(f(v'_i,v_{-i})).$

$x_i=v_i$ $y_i=v'_i$

v_{i} (f (v_{i}, v_{- i})) - p_{i} (v_{i}, v_{- i}) \geq v_{i} (f (v_{i}^{'}, v_{- i})) - p_{i} (v_{i}^{'}, v_{- i}) .

$v_i (f(v_i , v_{−i})) − p_i (v_i , v_{−i}) \geq v_i (f(v'_i , v_{−i})) − p_i (v'_i , v_{−i}).$

x_{i} = v_{i}

$x_i=v_i$

y_{i} = v_{i}^{'}

$y_i=v'_i$

v_{i}^{'} (f (v_{i}^{'}, v_{- i})) - p_{i} (v_{i}^{'}, v_{- i}) \geq v_{i}^{'} (f (v_{i}, v_{- i})) - p_{i} (v_{i}, v_{- i}) .

$v'_i (f(v'_i , v_{−i})) − p_i (v'_i , v_{−i}) \geq v'_i (f(v_i , v_{−i})) − p_i (v_i , v_{−i}).$

Interpretasi desain mekanisme dari proposisi ini adalah bahwa setiap mekanisme yang kompatibel (yaitu bukti strategi, yaitu jujur) memiliki "monotonitas yang lemah".

Untuk beberapa alasan, adalah konvensional untuk berdebat dengan merujuk pada tawaran dan kebohongan sejati. Dalam konteks ini, "true" dan "lie" hanyalah nama variabel, seperti "x" dan "y". Boleh saja menggunakan nama yang sama untuk merujuk pada hal-hal yang berbeda dalam argumen yang terpisah, karena tidak ada perbedaan resmi antara tawaran yang benar dan dusta.

Colin McQuillan
sumber

Itulah proposisi yang dipertanyakan. (Meskipun saya pikir Anda memiliki kesalahan ketik pada baris ketiga bukti Anda - penugasan v_i harus ditukar dari baris pertama.) Saya masih bingung mengapa menambahkan dua ketidaksetaraan ketika mereka dihasilkan dari asumsi yang berbeda. Ya, tidak ada perbedaan resmi antara tawaran benar dan salah; keduanya adalah angka. Tetapi mereka (atau tepatnya, mereka bisa) angka yang berbeda .

Novak

g (a, b) = 1

$g(a,b)=1$

a, b

$a,b$

g (x, y) - g (y, x) = 0

$g(x,y)-g(y,x)=0$

x, y

$x,y$

Iya. Tetapi izinkan saya mengunyahnya dalam konteks desain mekanisme sebentar. (Dan pada saat yang sama memperbarui posting asli saya di Mathjax, dan menambahkan case serupa yang saya gali dari Shoham dan Leyton-Brown.)

Novak

x_{i}

$x_i$

y_{i}

$y_i$

g (a, b) = 1

$g(a,b) = 1$

a

$a$

b

$b$

g (x, y) - g (y, x) = 0

$g(x,y) - g(y,x) = 0$

x

$x$

y

$y$