Mechanisms for position auctions are often used across very different instances of the same problem. In sponsored search, for example, the same mechanism is used for frequent keywords and rare keywords. While assuming complete information among agents may be reasonable for the former, it seems to be more appropriate to assume incomplete information for the latter. Motivated by this we ask the following robustness question: Is there a mechanism for position auctions that guarantees at least the truthful VCG revenue in every efficient equilibrium under both complete and incomplete information? We isolate a variant of the GFP mechanism in which the agents are allowed to place multi-dimensional bids as the only standard mechanism that achieves this goal. Our work thus shows that expressiveness is both necessary and sufficient for robustness against informational assumptions. This presents an interesting counterpoint to previous work on position auctions which highlighted the benefits of simplicity. Technically, our positive results are interesting as the respective equilibria are constructed for a multi-dimensional bid space. The structure of the equilibrium bids moreover provides an intuitive explanation why first-price payment rules may be able to support equilibria in a wider range than second-price payment rules.
Joint work with Felix Fischer and David C. Parkes