We study the second-price auction in which bidders have asymmetric information regarding the item’s value. Each bidder’s value for the item depends on a private component and a public component. While each bidder observes their own private component, they hold different and asymmetric information about the public component. We characterize the equilibrium of this auction game and study how the asymmetric bidder information affects their equilibrium bidding strategies. We also discover multiple surprisingly counter-intuitive equilibrium phenomena. For instance, a bidder may be better off if she is less informed regarding the public component. Conversely, a bidder may sometimes be worse off if she obtains more accurate estimation about the auctioned item. Our results suggest that efforts devoted by bidders to improve their value estimations, as widely seen in today’s online advertising auctions, may not always be to their benefit.

Unit demand auctions power today's search and native ad marketplaces. Traditional implementations make an extreme "separability" assumption: the relative value of any two ad slots is the same for all advertisers. Under this assumption, the optimal assignment problem can be conveniently solved simply by sorting; without it, efficient allocation requires solving a full-blown weighted matching problem. Motivated by prior work and our own empirical evidence against separability, we abandon that assumption and tackle the algorithmic problems of assignment and pricing for general unit demand ad auctions. Instead of computing prices directly, we take a novel approach and compute bidders' full allocation curves---complete mappings from each agent's bid space to their allocation under the optimal assignment function---from which it is trivial to compute most prices of interest, like those of the Generalized Second Price (GSP) or Vickrey-Clarke-Groves (VCG) auctions. Remarkably, we show that these full allocation curves (and therefore prices) can be computed in the same asymptotic runtime required to compute the optimal matching alone.

The generalized second price (GSP) auction has served as the core selling mechanism for sponsored search ads for over a decade. However, recent trends expanding the set of allowed ad formats---to include a variety of sizes, decorations, and other distinguishing features---have raised critical problems for GSP-based platforms. Alternatives such as the Vickrey-Clarke-Groves (VCG) auction raise different complications because they fundamentally change the way prices are computed. In this paper we report on our efforts to redesign a search ad selling system from the ground up in this new context, proposing a mechanism that optimizes an entire slate of ads globally and computes prices that achieve properties analogous to those held by GSP in the original, simpler setting of uniform ads. A careful algorithmic coupling of allocation-optimization and pricing-computation allows our auction to operate within the strict timing constraints inherent in real-time ad auctions. We report performance results of the auction in Yahoo's Gemini Search platform.

Nearly fifteen years ago, Google unveiled the generalized second price (GSP) auction. By all theoretical accounts including their own [Varian 14], this was the wrong auction --- the Vickrey-Clarke-Groves (VCG) auction would have been the proper choice --- yet GSP has succeeded spectacularly.

We study winner-take-all contests for crowdsourcing procurement in a model of costly effort and stochastic production. The principal announces a prize value P, agents simultaneously select a level of costly effort to exert towards production, yielding stochastic quality results, and then the agent who produces the highest quality good is paid P by the principal. We derive conditions on the probabilistic mapping from effort to quality under which this contest paradigm yields efficient equilibrium outcomes, and demonstrate that the conditions are satisfied in a range of canonical settings.

We join the goals of two giant and related fields of research in group decision-making that have historically had little contact: fair division, and efficient mechanism design with monetary payments. To do this we adopt the standard mechanism design paradigm where utility is assumed to be quasilinear and thus transferable across agents. We generalize the traditional binary criteria of envy-freeness, proportionality, and efficiency (welfare) to measures of degree that range between 0 and 1. We demonstrate that in the canonical fair division settings under any allocatively-efficient mechanism the worst-case welfare rate is 0 and disproportionality rate is 1; in other words, the worst-case results are as bad as possible. This strongly motivates an average-case analysis. We then set as the goal identification of a mechanism that achieves high welfare, low envy, and low disproportionality in expectation across a spectrum of fair division settings. We establish that the VCG mechanism is not a satisfactory candidate, but the redistribution mechanism of [Bailey, 1997; Cavallo, 2006] is.

The emerging area of dynamic mechanism design seeks to achieve desirable equilibrium outcomes in multi-agent sequential decision-making problems with self-interest. Here we take the goal of maximizing social welfare. We start by extending the characterization result of Green & Laffont [1977] to a dynamic setting, defining the dynamic-Groves class of dynamic mechanisms and showing that it exactly corresponds to the set of mechanisms that are efficient (social welfare maximizing) and incentive compatible in an ex post equilibrium. The dynamic-VCG mechanism of Bergemann & Valimaki [2006] is a dynamic analogue of the static VCG mechanism and is efficient, incentive compatible, and individual rational in an ex post equilibrium; we use our characterization result to show here that it is also revenue maximizing among all dynamic mechanisms with these properties. In other words, dynamic-VCG maximizes the payments required of the agents and thus, while perhaps desirable for an auctioneer seeking high revenue, is in fact worst when maximizing agent utility is the goal. We then build on recent work on static redistribution mechanisms (see [Cavallo, 2006]) to design a dynamic redistribution mechanism for multi-armed bandit settings (e.g., the repeated allocation of a single good) that returns much of the revenue under dynamic-VCG back to the agents, while maintaining the same efficiency, incentive compatibility, individual rationality, and no-deficit properties. We conclude with a numerical analysis, demonstrating empirically that this redistribution mechanism typically comes close to perfect budget balance.

We present the design and analysis of the first fully expressive, iterative combinatorial exchange (ICE). The exchange incorporates a tree-based bidding language (TBBL) that is concise and expressive for CEs. Bidders specify lower and upper bounds in TBBL on their value for different trades and refine these bounds across rounds. These bounds allow price discovery and useful preference elicitation in early rounds, and allow termination with an efficient trade despite partial information on bidder valuations. All computation in the exchange is carefully optimized to exploit the structure of the bid-trees and to avoid enumerating trades. A proxied interpretation of a revealed-preference activity rule, coupled with simple linear prices, ensures progress across rounds. The exchange is fully implemented, and we give results demonstrating several aspects of its scalability and economic properties with simulated bidding strategies.

We present the first design for a fully expressive iterative combinatorial exchange (ICE). The exchange incorporates a tree-based bidding language that is concise and expressive for CEs. Bidders specify lower and upper bounds on their value for different trades. These bounds allow price discovery and useful preference elicitation in early rounds, and allow termination with an efficient trade despite partial information on bidder valuations. All computation in the exchange is carefully optimized to exploit the structure of the bid-trees and to avoid enumerating trades. A proxied interpretation of a revealed-preference activity rule ensures progress across rounds. A VCG-based payment scheme that has been shown to mitigate opportunities for bargaining and strategic behavior is used to determine final payments. The exchange is fully implemented and in a validation phase.