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 .
Ele então estipula que , b i = z 2 , o que gera uma desigualdade com base no trabalho anterior do artigo.
Ele também estipula que , b i = z 1 , que gera uma desigualdade semelhante, mas diferente, com base no trabalho anterior do artigo.
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.)
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 ′ ié menor que o pagamento com base em , por exemplo, P i ( v ′ i ) ≤ P i ( v i ) . Ok, isso faz sentido.
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.
fonte
Eu acho que o que você quer é a seguinte proposição.
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.
fonte