Compreendendo uma prova de design de mecanismo

9

Tenho lutado com os detalhes técnicos de uma prova relativa à teoria dos leilões neste artigo: http://users.eecs.northwestern.edu/~hartline/omd.pdf

Teorema 2.5: As condições necessárias e suficientes para um mecanismo verdadeiro.

Ainda mais especificamente, a direção para a frente da prova, dada na página 6. Definindo um valor verdadeiro como , e um valor geral, possivelmente falso, (por exemplo, uma oferta) como b i , o autor continua postulando dois quantidades, z 1 e z 2 .vibiz1z2

Ele então estipula que , b i = z 2 , o que gera uma desigualdade com base no trabalho anterior do artigo. vi=z1bi=z2

Ele também estipula que , b i = z 1 , que gera uma desigualdade semelhante, mas diferente, com base no trabalho anterior do artigo. vi=z2bi=z1

Ok, é justo. Ele então subtrai uma desigualdade da outra e passa a derivar o resultado desejado com base na álgebra conseqüente. Não entendo por que essa subtração é justificada - ele parece estar subtraindo duas desigualdades que se baseiam em suposições totalmente diferentes (de fato, opostas), e toda vez que a vejo, sou expulso violentamente da linha de pensamento.

Tenho certeza de que já vi essa abordagem básica (o livro de Shoham e Leyton-Brown? Não a tenho à mão para checar), por isso parece ser uma ideia comum, mas não consigo superar isso. Alguém pode me ajudar a entender por que isso é válido ou me explicar o que está faltando?

(Eu tentei provar o resultado desejado, assumindo três values-- um verdadeiro valor , e duas propostas, b 1 e b 2 -. Para obter o seu resultado desejado, mas também falhou Por isso, não só pode ser comum, mas necessário fazê-lo da maneira do autor. Mas ainda não o entendo.)vib1b2

Atualização: Eu sabia que tinha visto algo semelhante no livro de Shoham e Leyton-Brown . Não é exatamente o mesmo, mas é muito semelhante e lida com a mesma equação e assunto. É o caso 1 do teorema 10.4.3.

A partir do contexto dos mecanismos verdadeiras, eles primeiro assumir um verdadeiro e um falso v ' i e derivar que o pagamento com base em v i é menor ou igual ao pagamento baseado em v ' i , por exemplo, P i ( v i ) P i ( v i ) . Eles então assumem o oposto, um verdadeiro v i e um falso v i , e obtêm o resultado oposto, que o pagamento baseado em v iviviviviPi(vi)Pi(vi)vivivié menor que o pagamento com base em , por exemplo, P i ( v i ) P i ( v i ) . Ok, isso faz sentido. viPi(vi)Pi(vi)

Eles então sustentam que os pagamentos baseados em e v i devem ser iguais, como se estivessem dizendo que P i ( v i ) P i ( v i ) e P i ( v i ) P i ( v i ) são simultaneamente verdadeiras, mesmo que sejam o resultado não apenas de suposições diferentes, mas opostas.viviPi(vi)Pi(vi)Pi(vi)Pi(vi)

Novak
fonte

Respostas:

11

A resposta é que o mecanismo deve ser verdadeiro para cada conjunto de tipos possíveis: o mecanismo não sabe quais são os tipos verdadeiros antes do tempo. Portanto, para um par de tipos e v i , o mecanismo deve ser verdadeiro se o tipo verdadeiro de um agente for v i : ou seja, sua utilidade deve ser maior se ele oferecer v i do que se ele oferecer v i . Mas o mecanismo também deve ser verdadeiro se o tipo verdadeiro do agente for v i ! Afinal, no que diz respeito ao mecanismo, pode ser! Portanto, neste caso, a utilidade de um agente deve ser maior se ele oferecer v vivivivivivi em comparação comvi.vivi

O ponto é que a veracidade impõe muitas desigualdades diferentes no mesmo mecanismo simultaneamente: uma para cada tipo que um agente possa ter e para cada desvio que ele possa considerar. Todos eles se sustentam. Essa prova usa apenas duas dessas desigualdades

Aaron Roth
fonte
Acho que finalmente estou começando a entender isso. De fato, saber que a prova está correta (e por que) me impressiona ainda mais quão rigoroso e poderoso é o conceito de "veracidade". Obrigado.
Nov12
4

Eu acho que o que você quer é a seguinte proposição.

VAf:VnAp1,,pn:VnRi,xi,yi,vi

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)).

xi=viyi=vi

vi(f(vi,vi))pi(vi,vi)vi(f(vi,vi))pi(vi,vi).
xi=viyi=vi
vi(f(vi,vi))pi(vi,vi)vi(f(vi,vi))pi(vi,vi).

A interpretação do mecanismo de design dessa proposição é que todo mecanismo compatível com incentivos (isto é, prova de estratégia, ou seja, verdadeiro) tem "monotonicidade fraca".

Por alguma razão, é convencional argumentar referindo-se a verdadeiras ofertas e mentiras. Nesse contexto, "true" e "lie" são apenas nomes de variáveis, como "x" e "y". É bom usar o mesmo nome para se referir a coisas diferentes em argumentos separados, porque não há diferença formal entre uma oferta verdadeira e uma mentira.

Colin McQuillan
fonte
Essa é a proposição em questão. (Embora eu ache que você tenha um erro de digitação na terceira linha de sua prova - as atribuições v_i devem ser trocadas da primeira linha.) Ainda estou confuso sobre o porquê de ser aceitável adicionar as duas desigualdades quando elas resultam de suposições diferentes. Sim, não há diferença formal entre uma oferta verdadeira e uma falsa; ambos são números. Mas eles são (ou para ser mais preciso, podem ser) números diferentes .
Novak
g(a,b)=1a,bg(x,y)g(y,x)=0x,y
Sim. Mas deixe-me analisar isso no contexto do design do mecanismo por um tempo. (E, ao mesmo tempo, atualize minha postagem original no Mathjax e adicione o caso semelhante que eu peguei de Shoham e Leyton-Brown.) #
1100 Novak
xiyi
g(a,b)=1abg(x,y)g(y,x)=0xy