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 2
Luego estipula que , , lo que produce una desigualdad basada en el trabajo previo del artículo. b i = z 2
También estipula que , , lo que produce una desigualdad similar pero diferente basada en el trabajo previo del artículo. b i = z 1
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 2
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 i , por ejemplo, P i ( v ′ i ) ≤ P i ( v i ) . Vale, eso tiene sentido.
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.
fuente
Creo que lo que quieres es la siguiente propuesta.
Proposición. Deje y A ser conjuntos. Deje f : V n → A y p 1 , ... , p n : V n → R . Suponga que para todo i , x i , y i , v - i tenemos x i ( f ( x i , v - i ) ) - p i ( xV UNA F: Vnorte→ A pags1, ... , pnorte: Vnorte→ R i , xyo, yyo, v- yo
Entonces para todo i , v i , v ′ i , v - i tenemos
v i ( f ( v i , v - i ) )
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 ( vXyo= vyo yyo= v′yo
Poniendoxi=vieyi=v ′ i tenemos
v ′ i (f(v ′ i ,v-i))-pi(v ′ i ,v-i)≥v ′ i (f(vi,v
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.
fuente