Tutorial by Brendan Lucier
Brendan Lucier, Microsoft Research, New England, USA.
Abstract:Prophet inequalities capture a natural class of online selection problems. In the traditional prophet inequality setup, a protagonist is presented a sequence of rewards drawn from independent distributions. Whenever a reward is revealed it must either be rejected and lost forever, or accepted irrevocably. The goal is to maximize the expected reward. Originally studied in the 70s, prophet inequalities have enjoyed a resurgence in algorithmic game theory due to their connection to pricing problems. In the pricing analogy, the rewards are buyers who arrive sequentially, and the protagonist is a seller who must decide whether to trade with each buyer as he or she arrives.
Recent work has extended prophet inequalities to multiple-choice scenarios, such as accepting many rewards subject to a feasibility constraint (cardinality, matroid, etc.), and choosing among multiple rewards each round (as in matching and combinatorial auctions). These extensions have led to exciting developments in mechanism design for increasingly complex allocation problems. In this tutorial, I will survey this line of work, emphasizing recent developments and applications to pricing. The tutorial will be self-contained, and aims to develop a useable framework for designing new prophet inequalities and posted-price mechanisms.
Tutorial by Hu Fu
Hu Fu, University of British Columbia, Canada.
Title: The Lookahead Auction: a Simple Auction and its Several Lives
Abstract:The Lookahead Auction was designed by Amir Ronen to extract approximately optimal revenue in a single item auction with correlated bidders. It focuses on the highest bidder while bounding the total revenue that lower bidders may contribute. This idea proves powerful in various other settings: auctions with independent bidders, unit demand bidders, and interdependent bidders. Its elegance leads to nontrivial results, albeit with transparent proofs, in each of these domains. This survey discusses the Lookahead auction and its applications, and, towards the end, glimpses at recent developments in multi-dimensional revenue optimal auction design that bear formal resemblance.
Tutorial by Thomas Kesselheim
Thomas Kesselheim, Max-Planck-Institut für Informatik, Germany.
Abstract:In a combinatorial auction with item bidding, agents participate in multiple single-item second-price auctions at once. As some items might be substitutes, agents need to strategize in order to maximize their utilities. In the first part of this tutorial, we give an overview of positive results for this setting regarding the welfare at equilibrium. These are complemented by negative results that equilibria are hard to compute and therefore unlikely to be attained. In the second part, we study simple best-response dynamics, in which agents myopically react to the other agents’ behavior. As we show, these dynamics reach and remain in states of good welfare reasonably fast despite the fact that it may take exponentially long before they converge or they may not converge at all.