More Like this

1. Pacing Equilibrium in First Price Auction Markets

   https://doi.org/10.1287/mnsc.2022.4310  

   Conitzer, Vincent; Kroer, Christian; Panigrahi, Debmalya; Schrijvers, Okke; Stier-Moses, Nicolas E.; Sodomka, Eric; Wilkens, Christopher A. (December 2022, Management Science)

   Mature internet advertising platforms offer high-level campaign management tools to help advertisers run their campaigns, often abstracting away the intricacies of how each ad is placed and focusing on aggregate metrics of interest to advertisers. On such platforms, advertisers often participate in auctions through a proxy bidder, so the standard incentive analyses that are common in the literature do not apply directly. In this paper, we take the perspective of a budget management system that surfaces aggregated incentives—instead of individual auctions—and compare first and second price auctions. We show that theory offers surprising endorsement for using a first price auction to sell individual impressions. In particular, first price auctions guarantee uniqueness of the steady-state equilibrium of the budget management system, monotonicity, and other desirable properties, as well as efficient computation through the solution to the well-studied Eisenberg–Gale convex program. Contrary to what one can expect from first price auctions, we show that incentives issues are not a barrier that undermines the system. Using realistic instances generated from data collected at real-world auction platforms, we show that bidders have small regret with respect to their optimal ex post strategy, and they do not have a big incentive to misreport when they can influence equilibria directly by giving inputs strategically. Finally, budget-constrained bidders, who have significant prevalence in real-world platforms, tend to have smaller regrets. Our computations indicate that bidder budgets, pacing multipliers, and regrets all have a positive association in statistical terms. This paper was accepted by Gabriel Weintraub, revenue management and market analytics. Funding: D. Panigrahi was supported in part by the National Science Foundation [Awards CCF 1535972, CCF 1750140, and CCF 1955703]. Supplemental Material: The data files are available at https://doi.org/10.1287/mnsc.2022.4310 . 

   more » « less
2. Contextual Standard Auctions with Budgets: Revenue Equivalence and Efficiency Guarantees

   https://doi.org/10.1287/mnsc.2023.4719  

   Balseiro, Santiago; Kroer, Christian; Kumar, Rachitesh (January 2023, Management Science)

   The internet advertising market is a multibillion dollar industry in which advertisers buy thousands of ad placements every day by repeatedly participating in auctions. An important and ubiquitous feature of these auctions is the presence of campaign budgets, which specify the maximum amount the advertisers are willing to pay over a specified time period. In this paper, we present a new model to study the equilibrium bidding strategies in standard auctions, a large class of auctions that includes first and second price auctions, for advertisers who satisfy budget constraints on average. Our model dispenses with the common yet unrealistic assumption that advertisers’ values are independent and instead assumes a contextual model in which advertisers determine their values using a common feature vector. We show the existence of a natural value pacing–based Bayes–Nash equilibrium under very mild assumptions. Furthermore, we prove a revenue equivalence showing that all standard auctions yield the same revenue even in the presence of budget constraints. Leveraging this equivalence, we prove price of anarchy bounds for liquid welfare and structural properties of pacing-based equilibria that hold for all standard auctions. In recent years, the internet advertising market has adopted first price auctions as the preferred paradigm for selling advertising slots. Our work, thus, takes an important step toward understanding the implications of the shift to first price auctions in internet advertising markets by studying how the choice of the selling mechanism impacts revenues, welfare, and advertisers’ bidding strategies. This paper was accepted by Itai Ashlagi, revenue management and market analytics. Supplemental Material: The online appendix is available at https://doi.org/10.1287/mnsc.2023.4719 . 

   more » « less
3. Simple, Credible, and Approximately-Optimal Auctions

   Daskalakis, C; Fishelson, M; Lucier, B; Syrgkanis, V; Velusamy, S (January 2020, 21st ACM Conference on Economics and Computation, EC 2020)

   null (Ed.)

   We identify the first static credible mechanism for multi-item additive auctions that achieves a constant factor of the optimal revenue. This is one instance of a more general framework for designing two-part tariff auctions, adapting the duality framework of Cai et al [CDW16]. Given a (not necessarily incentive compatible) auction format A satisfying certain technical conditions, our framework augments the auction with a personalized entry fee for each bidder, which must be paid before the auction can be accessed. These entry fees depend only on the prior distribution of bidder types, and in particular are independent of realized bids. Our framework can be used with many common auction formats, such as simultaneous first-price, simultaneous second-price, and simultaneous all-pay auctions. If all-pay auctions are used, we prove that the resulting mechanism is credible in the sense that the auctioneer cannot benefit by deviating from the stated mechanism after observing agent bids. If second-price auctions are used, we obtain a truthful O(1)-approximate mechanism with fixed entry fees that are amenable to tuning via online learning techniques. Our results for first price and all-pay are the first revenue guarantees of non-truthful mechanisms in multi-dimensional environments; an open question in the literature [RST17]. 

   more » « less
4. Taming the Communication and Computation Complexity of Combinatorial Auctions: The FUEL Bid Language

   https://doi.org/10.1287/mnsc.2022.4465  

   Bichler, Martin; Milgrom, Paul; Schwarz, Gregor (April 2022, Management Science)

   Combinatorial auctions have found widespread application for allocating multiple items in the presence of complex bidder preferences. The enumerative exclusive OR (XOR) bid language is the de facto standard bid language for spectrum auctions and other applications, despite the difficulties, in larger auctions, of enumerating all the relevant packages or solving the resulting NP-hard winner determination problem. We introduce the flexible use and efficient licensing (FUEL) bid language, which was proposed for radio spectrum auctions to ease both communications and computations compared with XOR-based auctions. We model the resulting allocation problem as an integer program, discuss computational complexity, and conduct an extensive set of computational experiments, showing that the winner determination problem of the FUEL bid language can be solved reliably for large realistic-sized problem instances in less than half an hour on average. In contrast, auctions with an XOR bid language quickly become intractable even for much smaller problem sizes. We compare a sealed-bid FUEL auction to a sealed-bid auction with an XOR bid language and to a simultaneous clock auction. The sealed-bid auction with an XOR bid language incurs significant welfare losses because of the missing bids problem and computational hardness, the simultaneous clock auction leads to a substantially lower efficiency than FUEL because of the exposure problem. This paper was accepted by Axel Ockenfels. 

   more » « less
5. The Strange Role of Information Asymmetry in Auctions—Does More Accurate Value Estimation Benefit a Bidder?

   https://doi.org/10.1609/aaai.v36i5.20459  

   Xu, Haifeng; Cavallo, Ruggiero (June 2022, Proceedings of the AAAI Conference on Artificial Intelligence)

   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. 

   more » « less