The area of mechanism design in economics is concerned with algorithms that produce good outcomes given inputs from self-interested individuals. One of the stars of mechanism design theory is the Vickrey-Clarke-Groves (VCG) mechanism, which makes it optimal for each individual to truthfully reveal its input. In practice the VCG mechanism is used with surprising rarity and the mechanisms we actually find are non-truthful. An example of this phenomenon are position auctions used by internet search engines to allocate space for advertisements displayed next to genuine search results. Here only non-truthful mechanisms have ever been used, and what in theory looks like a beginner's mistake was a huge commercial success. An obvious advantage of the non-truthful mechanisms is that they use simpler payments, and it has been known for some time why they do not produce chaos when participants decide strategically how to bid. We will see that the simplicity of payments also comes with a greater robustness to uncertainty on part of the search engines regarding the relative values of positions. This talk is based on joint work with Paul Dütting (LSE) and David C. Parkes (Harvard).
Truthful Outcomes from Non-Truthful Position Auctions
Felix Fischer (QMUL)
Fri, 24/11/2017 - 16:00
W316, Queens Building