More Like this

1. Constant Approximation for Private Interdependent Valuations

   https://doi.org/10.1109/FOCS57990.2023.00018  

   Eden, Alon; Feldman, Michal; Goldner, Kira; Mauras, Simon; Mohan, Divyarthi (November 2023, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS))

   The celebrated model of auctions with interdependent valuations, introduced by Milgrom and Weber in 1982, has been studied almost exclusively under private signals $$s_1, \ldots, s_n$$ of the $$n$$ bidders and public valuation functions $$v_i(s_1, \ldots, s_n)$$. Recent work in TCS has shown that this setting admits a constant approximation to the optimal social welfare if the valuations satisfy a natural property called submodularity over signals (SOS). More recently, Eden et al. (2022) have extended the analysis of interdependent valuations to include settings with private signals and \emph{private valuations}, and established $$O(\log^2 n)$$-approximation for SOS valuations. In this paper we show that this setting admits a {\em constant} factor approximation, settling the open question raised by Eden et al. (2022). 

   more » « less
2. 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
3. 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
4. Optimal Deterministic Clock Auctions and Beyond

   Christodoulou, Giorgos; Gkatzelis, Vasilis; Schoepflin, Daniel (February 2022, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022))

   We design and analyze deterministic and randomized clock auctions for single-parameter domains with downward-closed feasibility constraints, aiming to maximize the social welfare. Clock auctions have been shown to satisfy a list of compelling incentive properties making them a very practical solution for real-world applications, partly because they require very little reasoning from the participating bidders. However, the first results regarding the worst-case performance of deterministic clock auctions from a welfare maximization perspective indicated that they face obstacles even for a seemingly very simple family of instances, leading to a logarithmic inapproximability result; this inapproximability result is information-theoretic and holds even if the auction has unbounded computational power. In this paper we propose a deterministic clock auction that achieves a logarithmic approximation for any downward-closed set system, using black box access to a solver for the underlying optimization problem. This proves that our clock auction is optimal and that the aforementioned family of instances exactly captures the information limitations of deterministic clock auctions. We then move beyond deterministic auctions and design randomized clock auctions that achieve improved approximation guarantees for a generalization of this family of instances, suggesting that the earlier indications regarding the performance of clock auctions may have been overly pessimistic. 

   more » « less
5. Disruption and Rerouting in Supply Chain Networks

   https://doi.org/10.1287/opre.2022.2409  

   Birge, John R.; Capponi, Agostino; Chen, Peng-Chu (December 2022, Operations Research)

   We study systemic risk in a supply chain network where firms are connected through purchase orders. Firms can be hit by cost or demand shocks, which can cause defaults. These shocks propagate through the supply chain network via input-output linkages between buyers and suppliers. Firms endogenously take contingency plans to mitigate the impact generated from disruptions. We show that, as long as firms have large initial equity buffers, network fragility is low if both buyer diversification and supplier diversification are low. We find that a single-sourcing strategy is beneficial for a firm only if the default probability of the firm’s supplier is low. Otherwise, a multiple-sourcing strategy is ex post more cost effective for a firm. Funding: J.R. Birge acknowledges financial support from the University of Chicago Booth School of Business. The research of A. Capponi has been supported by the NSF/CMMI CAREER-1752326 award. P.-C. Chen acknowledges financial support from the Research Grant Council of Hong Kong [Early Career Scheme Grant 27210118]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2022.2409 . 

   more » « less