Comprender una prueba de diseño de mecanismo

9

He estado luchando con los detalles técnicos de una prueba sobre la teoría de subastas en este documento: http://users.eecs.northwestern.edu/~hartline/omd.pdf

Específicamente, Teorema 2.5: Las condiciones necesarias y suficientes para un mecanismo veraz.

Incluso más específicamente, la dirección hacia adelante de la prueba, dada en la página 6. Al definir un valor verdadero como , y un valor general, posiblemente falso (por ejemplo, una oferta) como , el autor postula dos cantidades adicionales, y .b i z 1 z 2vibiz1z2

Luego estipula que , , lo que produce una desigualdad basada en el trabajo previo del artículo. b i = z 2vi=z1bi=z2

También estipula que , , lo que produce una desigualdad similar pero diferente basada en el trabajo previo del artículo. b i = z 1vi=z2bi=z1

De acuerdo, bastante justo. Luego resta una desigualdad de la otra y procede a obtener el resultado deseado sobre la base del álgebra consecuente. No entiendo por qué esa sustracción está justificada: parece estar restando dos desigualdades que se basan en suposiciones completamente diferentes (de hecho, opuestas), y cada vez que lo veo me arrojan violentamente del tren del pensamiento.

Estoy bastante seguro de que he visto este enfoque básico (¿el libro de Shoham y Leyton-Brown? No lo tengo a mano para verificar), por lo que parece ser una idea común, pero no puedo superarlo. ¿Alguien puede ayudarme a comprender por qué eso es válido o explicarme lo que me falta?

(He intentado demostrar el resultado deseado asumiendo tres values-- un valor verdadero , y dos ofertas, y - para conseguir su resultado deseado, pero también fracasó Por lo tanto, no sólo puede ser común, pero. Necesarias para hazlo a la manera del autor. Pero todavía no lo entiendo).b 1 b 2vib1b2

Actualización: Sabía que había visto algo similar en el libro de Shoham y Leyton-Brown . No es exactamente lo mismo, pero es muy similar y trata con la misma ecuación y el mismo tema. Es el caso 1 del teorema 10.4.3.

Partiendo del contexto de mecanismos veraces, primero asumen una veraz y una falsa y deducen que el pago basado en es menor o igual que el pago basado en v i , por ejemplo, P i ( v i ) P i ( v i ) . Luego suponen lo contrario, una v i verdadera y una v i falsa , y obtienen el resultado opuesto, que el pago basado en v i es menor que el pago basado env i v iviviviviPi(vi)Pi(vi)vivivi , por ejemplo, P i ( v i ) P i ( v i ) . Vale, eso tiene sentido. viPi(vi)Pi(vi)

Luego sostienen que los pagos basados ​​en y v i deben ser iguales, como si estuvieran diciendo que P i ( v i ) P i ( v i ) y P i ( v i ) P i ( v i ) son simultáneamente verdaderas, a pesar de que son el resultado no solo de supuestos diferentes, sino opuestos.viviPi(vi)Pi(vi)Pi(vi)Pi(vi)

Novak
fuente

Respuestas:

11

La respuesta es que el mecanismo debe ser veraz para cada conjunto de tipos posibles: el mecanismo no sabe cuáles son los tipos verdaderos de antemano. Entonces, para un par de tipos y v i , el mecanismo debe ser veraz si el tipo verdadero de un agente es v i : es decir, su utilidad debe ser mayor si ofrece v i que si ofrece v i . ¡Pero el mecanismo también debe ser veraz si el tipo verdadero del agente es v i ! Después de todo, en lo que respecta al mecanismo, ¡podría serlo! Entonces, en este caso, la utilidad de un agente debe ser mayor si ofrece v 'vivivivivivi en comparación convi.vivi

El punto es que la veracidad impone muchas desigualdades diferentes en el mismo mecanismo simultáneamente: uno para cada tipo que un agente pueda tener, y para cada desviación que pueda considerar. Todos ellos aguantan. Esta prueba usa solo dos de estas desigualdades

Aaron Roth
fuente
Creo que finalmente estoy empezando a entender eso. De hecho, saber que la prueba es correcta (y por qué) me impresiona aún más cuán estricto y poderoso es el concepto de "veracidad". Gracias.
Novak
4

Creo que lo que quieres es la siguiente propuesta.

Proposición. Deje y A ser conjuntos. Deje f : V nA y p 1 , ... , p n : V nR . Suponga que para todo i , x i , y i , v - i tenemos x i ( f ( x i , v - i ) ) - p i ( xVAf:VnAp1,,pn:VnRi,xi,yi,vi Entonces para todo i , v i , v i , v - i tenemos v i ( f ( v i , v - i ) )

xi(f(xi,vi))pi(xi,vi)xi(f(yi,vi))pi(yi,vi).
i,vi,vi,vi
vi(f(vi,vi))vi(f(vi,vi))vi(f(vi,vi))vi(f(vi,vi)).

Prueba. Poniendo e y i = v i tenemos v i ( f ( v i , v - i ) ) - p i ( v i , v - i ) v i ( f ( v i , v - i ) ) - p i ( vxi=viyi=vi Poniendoxi=vieyi=vi tenemos vi (f(vi ,v-i))-pi(vi ,v-i)vi (f(vi,v

vi(f(vi,vi))pi(vi,vi)vi(f(vi,vi))pi(vi,vi).
xi=viyi=vi El resultado sigue agregando estas desigualdades y reorganizando.
vyo(F(vyo,v-yo))-pagsyo(vyo,v-yo)vyo(F(vyo,v-yo))-pagsyo(vyo,v-yo).

La interpretación del diseño del mecanismo de esta propuesta es que cada mecanismo compatible con incentivos (es decir, a prueba de estrategia, es decir, veraz) tiene una "monotonicidad débil".

Por alguna razón, es convencional discutir al referirse a verdaderas ofertas y mentiras. En este contexto, "verdadero" y "mentira" son solo nombres de variables, como "x" e "y". Está bien usar el mismo nombre para referirse a diferentes cosas en argumentos separados, porque no hay una diferencia formal entre una oferta verdadera y una mentira.

Colin McQuillan
fuente
Esa es la propuesta en cuestión. (Aunque creo que tiene un error tipográfico en la tercera línea de su prueba, las asignaciones de v_i deben intercambiarse desde la primera línea). Todavía tengo dudas sobre por qué es aceptable agregar las dos desigualdades cuando resultan de suposiciones diferentes. Sí, no hay una diferencia formal entre una oferta verdadera y una falsa; Ambos son números. Pero son (o para ser precisos, pueden ser) números diferentes .
Novak
g(a,b)=1a,bg(x,y)g(y,x)=0x,y
Si. Pero déjenme masticar eso en el contexto del diseño del mecanismo por un momento. (Y al mismo tiempo, actualice mi publicación original en Mathjax y agregue el caso similar que extraje de Shoham y Leyton-Brown.)
Novak
Xyoyyo
sol(una,si)=1unasisol(X,y)-sol(y,X)=0 0Xy