Inbal Talgam-Cohen

Understanding when equilibria are guaranteed to exist is a central theme in economic theory, seemingly unrelated to computation. This paper shows that the existence of pricing equilibria is inextricably connected to the computational complexity of related optimization problems: demand oracles, revenue-maximization, and welfare-maximization. This relationship implies, under suitable complexity assumptions, a host of impossibility results. We also suggest a complexity-theoretic explanation for the lack of useful extensions of the Walrasian equilibrium concept: such extensions seem to require the invention of novel polynomial-time algorithms for welfare-maximization.

Designing double auctions is a complex problem, especially when there are restrictions on the sets of buyers and sellers that may trade with one another. The goal of this paper is to develop “black-box reductions” from double auction design to the exhaustively-studied problem of designing single-sided mechanisms. We consider several desirable properties of a double auction: feasibility, dominant-strategy incentive compatibility, the still stronger incentive constraints offered by a deferred-acceptance implementation, exact and approximate welfare maximization, and budget-balance. For each of these properties, we identify sufficient conditions on the two single-sided mechanisms – one for the buyers, one for the sellers – and on the method of composition, that guarantee the desired property of the double auction. Our framework also offers new insights into classic double auction designs, such as the VCG and McAfee auctions with unit-demand buyers and unit-supply sellers.

We study interdependent value settings [Milgrom and Weber, 1982], and extend several fundamental results from the well-studied independent private values model to these settings. For revenue-optimal mechanism design, we give conditions under which Myerson’s virtual value-based mechanism remains optimal with interdependent values. One of these conditions is robustness of the truthfulness and individual rationality guarantees, in the sense that they are required to hold ex post. We then consider an even more robust class of mechanisms called “prior independent” (a.k.a. “detail free”), and show that by simply using one of the bidders to set a reserve price, it is possible to extract near-optimal revenue in an interdependent values setting. This shows that a considerable level of robustness is achievable for interdependent values in single-parameter environments.

Most results in revenue-maximizing auction design hinge on “getting the price right” – offering goods to bidders at a price low enough to encourage a sale, but high enough to garner non-trivial revenue. Getting the price right can be hard work, especially when the seller has little or no a priori information about bidders’ valuations. A simple alternative approach is to “let the market do the work”, and have prices emerge from competition for scarce goods. The simplest-imaginable implementation of this idea is the following: first, if necessary, impose an artificial limit on the number of goods that can be sold; second, run the welfare-maximizing VCG mechanism subject to this limit. We prove that such “supply-limiting mechanisms” achieve near-optimal expected revenue in a range of single- and multi-parameter Bayesian settings. Indeed, despite their simplicity, we prove that they essentially match the state-of-the-art in prior-independent mechanism design.

We study equilibria of markets with m heterogeneous indivisible goods and n consumers with combinatorial preferences. It is well known that a competitive equilibrium is not guaranteed to exist when valuations are not gross substitutes. Given the widespread use of bundling in real-life markets, we study its role as a stabilizing and coordinating device by considering the notion of competitive bundling equilibrium: a competitive equilibrium over the market induced by partitioning the goods for sale into fixed bundles. Compared to other equilibrium concepts involving bundles, this notion has the advantage of simultaneous succinctness (at most m prices) and market clearance.
Our first set of results concerns welfare guarantees. We show that in markets with homogeneous goods, even in the presence of complementarities, there always exists a competitive bundling equilibrium that guarantees a logarithmic fraction of the optimal welfare, and this guarantee is tight. We also establish non-trivial welfare guarantees for general markets, twoconsumer markets, and markets where the consumer valuations are additive up to a fixed value (budget-additive).
Our second set of results concerns revenue guarantees. Motivated by the fact that the revenue extracted in a standard competitive equilibrium may be zero (even with simple unit-demand consumers), we show that for natural subclasses of gross substitutes valuations, there always exists a competitive bundling equilibrium that extracts a logarithmic fraction of the optimal welfare, and this guarantee is tight. The notion of competitive bundling equilibrium can thus be useful even in markets which possess a standard competitive equilibrium.

We study how standard auction objectives in sponsored search markets are affected by refinement in the prediction of ad relevance (click-through rates). As the prediction algorithm takes more features into account, its predictions become more refined; a natural question is whether this is desirable from the perspective of auction objectives. Our focus is on mechanisms that optimize for a convex combination of economic efficiency and revenue, and our starting point is the observation that the objective of such a mechanism can only improve with refined prediction, making refinement in the best interest of the search engine. We demonstrate that the impact of refinement on market efficiency is not always positive; nevertheless, we are able to identify natural – and to some extent necessary – conditions under which refinement is guaranteed to also improve economic efficiency. Our main technical contribution is in explaining how refinement changes the ranking of advertisers by value (efficiency-optimal ranking), moving it either towards or away from their ranking by virtual value (revenue-optimal ranking). These results are closely related to the literature on signaling in auctions.