Invited Session Wed.2.MA 043

Wednesday, 13:15 - 14:45 h, Room: MA 043

Cluster 8: Game theory [...]

Analysis of auction mechanisms


Chair: Vangelis Markakis



Wednesday, 13:15 - 13:40 h, Room: MA 043, Talk 1

Renato Paes Leme
Polyhedral clinching auctions and the AdWords polytope

Coauthors: Gagan Goel, Vahab Mirrokni


A central issue in applying auction theory in practice is the problem of dealing with budget-constrained agents. A desirable goal in practice is to design incentive compatible, individually rational, and Pareto optimal auctions while respecting the budget constraints. Achieving this goal is particularly challenging in the presence of nontrivial combinatorial constraints over the set of feasible allocations.
Toward this goal and motivated by AdWords auctions, we present an auction for polymatroidal environments satisfying the above properties. Our auction employs a novel clinching technique with a clean geometric description and only needs an oracle access to the submodular function defining the polymatroid. As a result, this auction not only simplifies and generalizes all previous results, it applies to several new applications including AdWords Auctions, bandwidth markets, and video on demand. In particular, our characterization of the AdWords auction as polymatroidal constraints might be of independent interest. This allows us to design the first mechanism for Ad Auctions taking into account simultaneously budgets, multiple keywords and multiple slots.



Wednesday, 13:45 - 14:10 h, Room: MA 043, Talk 2

Ioannis Caragiannis
Welfare and revenue guarantees in sponsored search auctions

Coauthors: , Christos Kaklamanis, Panagiotis Kanellopoulos, Maria Kyropoulou, Renato Paes Leme, Brendan Lucier, Eva Tardos


In sponsored search auctions, advertisers compete for a number of available advertisement slots of different quality. The auctioneer decides the allocation of advertisers to slots using bids provided by them. Since the advertisers may act strategically and submit their bids in order to maximize their individual objectives, such an auction naturally defines a strategic game among the advertisers. We consider generalized second price and generalized first price auctions in settings where the advertisers have incomplete information and present bounds on the social welfare over Bayes-Nash equilibria compared to the optimal social welfare. We also consider auctions that use a single reserve price and provide similar bounds on the revenue. Even though the above auctions are inferior to variations of the well-known VCG auction mechanism both in terms of welfare and revenue, our results provide explanations for their adoption by the sponsored search industry.
% The talk is based on joint works with Christos Kaklamanis, Panagiotis Kanellopoulos, Maria Kyropoulou, Brendan Lucier, Renato Paes Leme, and Eva Tardos.



Wednesday, 14:15 - 14:40 h, Room: MA 043, Talk 3

Vasilis Syrgkanis
Efficiency in sequential auctions

Coauthors: Renato Paes Leme, Eva Tardos


In many settings agents participate in multiple different auctions that are not necessarily implemented simultaneously. Future opportunities affect strategic considerations of the players in each auction, introducing externalities. Motivated by this consideration, we study a setting of a market of buyers and sellers, where each seller holds one item, bidders have combinatorial valuations and sellers hold item auctions sequentially. We examine both the complete and incomplete information version of the setting.
For the complete information setting we prove that if sellers hold sequential first price auctions then for unit-demand bidders (matching market) every subgame perfect equilibrium achieves at least half of the optimal social welfare, while for submodular bidders or when second price auctions are used, the social welfare can be arbitrarily worse than the optimal. For the incomplete information setting we prove that for the case of unit-demand bidders any Bayesian equilibrium achieves at least 1⁄3 of the optimal welfare.


  There are three major facts that should be watched out for in all payday loans in the United States. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.