More Like this

1. Clock Auctions Augmented with Unreliable Advice

   Gkatzelis, Vasilis; Schoepflin, Daniel; Tan, Xizhi (January 2025, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms,(SODA 2025))

   Azar, Yossi; Panigrahi, Debmalya (Ed.)

   We provide the first analysis of (deferred acceptance) clock auctions in the learning-augmented framework. These auctions satisfy a unique list of very appealing properties, including obvious strategyproofness, transparency, and unconditional winner privacy, making them particularly well-suited for real-world applications. However, early work that evaluated their performance from a worst-case analysis perspective concluded that no deterministic clock auction with n bidders can achieve a O (log1-∈ n ) approximation of the optimal social welfare for a constant ∈ > 0, even in very simple settings. This overly pessimistic impossibility result heavily depends on the assumption that the designer has no information regarding the bidders’ values. Leveraging the learning-augmented framework, we instead consider a designer equipped with some (machine-learned) advice regarding the optimal solution; this advice can provide useful guidance if accurate, but it may be unreliable. Our main results are learning-augmented clock auctions that use this advice to achieve much stronger performance guarantees whenever the advice is accurate (known as consistency), while maintaining worst-case guarantees even if this advice is arbitrarily inaccurate (known as robustness ). Our first clock auction achieves the best of both worlds: (1 + ∈ )-consistency for any desired constant ∈ > 0 and O (log n ) robustness; we also extend this auction to achieve error tolerance. We then consider a much stronger notion of consistency, which we refer to as consistency∞ and provide an auction that achieves a near-optimal trade-off between consistency∞ and robustness. Finally, using our impossibility results regarding this trade-off, we prove lower bounds on the “cost of smoothness,” i.e., on the robustness that is achievable if we also require that the performance of the auction degrades smoothly as a function of the prediction error. 

   more » « less
2. Deterministic Budget-Feasible Clock Auctions

   https://doi.org/10.1137/1.9781611977073.114  

   Balkanski, Eric; Garimidi, Pranav; Gkatzelis, Vasilis; Schoepflin, Daniel; Tan, Xizhi (January 2022, 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA22))

   We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategyproof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer, while eliciting each seller’s true cost for providing their service. These solutions predominantly take the form of randomized sealed-bid auctions: they ask the sellers to report their private costs and then use randomization to determine which subset of services will be procured and how much each of the chosen providers will be paid, ensuring that the total payment does not exceed the buyer’s budget. Our main result in this paper is a novel method for designing budget-feasible auctions, leading to solutions that outperform the previously proposed auctions in multiple ways. First, our solutions take the form of descending clock auctions, and thus satisfy a list of very appealing properties, such as obvious strategyproofness, group strategyproofness, transparency, and unconditional winner privacy; this makes these auctions much more likely to be used in practice. Second, in contrast to previous results that heavily depend on randomization, our auctions are deterministic. As a result, we provide an affirmative answer to one of the main open questions in this literature, asking whether a deterministic strategyproof auction can achieve a constant approximation when the buyer’s valuation function is submodular over the set of services. In addition to this, we also provide the first deterministic budget-feasible auction that matches the approximation bound of the best-known randomized auction for the class of subadditive valuations. Finally, using our method, we improve the best-known approximation factor for monotone submodular valuations, which has been the focus of most of the prior work 

   more » « less
3. 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
4. On the hardness of dominant strategy mechanism design

   https://doi.org/10.1145/3519935.3520013  

   Dobzinski, Shahar; Ron, Shiri; Vondrák, Jan (June 2022, STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing)

   Stefano Leonardi (Ed.)

   We study the communication complexity of dominant strategy implementations of combinatorial auctions. We start with two domains that are generally considered “easy”: multi-unit auctions with decreasing marginal values and combinatorial auctions with gross substitutes valuations. For both domains we have fast algorithms that find the welfare-maximizing allocation with communication complexity that is poly-logarithmic in the input size. This immediately implies that welfare maximization can be achieved in ex-post equilibrium with no significant communication cost, by using VCG payments. In contrast, we show that in both domains the communication complexity of any dominant strategy implementation that achieves the optimal welfare is polynomial in the input size. We then move on to studying the approximation ratios achievable by dominant strategy mechanisms. For multi-unit auctions with decreasing marginal values, we provide a dominant-strategy communication FPTAS. For combinatorial auctions with general valuations, we show that there is no dominant strategy mechanism that achieves an approximation ratio better than m1−є that uses poly(m,n) bits of communication, where m is the number of items and n is the number of bidders. In contrast, a randomized dominant strategy mechanism that achieves an O(√m) approximation with poly(m,n) communication is known. This proves the first gap between computationally efficient deterministic dominant strategy mechanisms and randomized ones. En route, we answer an open question on the communication cost of implementing dominant strategy mechanisms for more than two players, and also solve some open problems in the area of simultaneous combinatorial auctions. 

   more » « less
5. Reducing inefficiency in carbon auctions with imperfect competition.

   Goldner, K.; Immorlica, I.; Lucier, B (January 2020, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020)

   Vidick, T. (Ed.)

   We study auctions for carbon licenses, a policy tool used to control the social cost of pollution. Each identical license grants the right to produce a unit of pollution. Each buyer (i.e., firm that pollutes during the manufacturing process) enjoys a decreasing marginal value for licenses, but society suffers an increasing marginal cost for each license distributed. The seller (i.e., the government) can choose a number of licenses to put up for auction, and wishes to maximize the societal welfare: the total economic value of the buyers minus the social cost. Motivated by emission license markets deployed in practice, we focus on uniform price auctions with a price floor and/or price ceiling. The seller has distributional information about the market, and their goal is to tune the auction parameters to maximize expected welfare. The target benchmark is the maximum expected welfare achievable by any such auction under truth-telling behavior. Unfortunately, the uniform price auction is not truthful, and strategic behavior can significantly reduce (even below zero) the welfare of a given auction configuration. We describe a subclass of “safe-price” auctions for which the welfare at any Bayes-Nash equilibrium will approximate the welfare under truth-telling behavior. We then show that the better of a safeprice auction, or a truthful auction that allocates licenses to only a single buyer, will approximate the target benchmark. In particular, we show how to choose a number of licenses and a price floor so that the worst-case welfare, at any equilibrium, is a constant approximation to the best achievable welfare under truth-telling after excluding the welfare contribution of a single buyer. 

   more » « less