More Like this

1. Robust Auctions for Revenue via Enhanced Competition

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

   Roughgarden, Tim; Talgam-Cohen, Inbal; Yan, Qiqi (July 2020, Operations Research)

   Most results in revenue-maximizing mechanism design hinge on “getting the price right”—selling goods to bidders at prices low enough to encourage a sale but high enough to garner nontrivial revenue. This approach is difficult to implement when the seller has little or no a priori information about bidder valuations or when the setting is sufficiently complex, such as matching markets with heterogeneous goods. In this paper, we apply a robust approach to designing auctions for revenue. Instead of relying on prior knowledge regarding bidder valuations, we “let the market do the work” and let prices emerge from competition for scarce goods. We analyze the revenue guarantees of one of the simplest imaginable implementations of this idea: first, we enhance competition in the market by increasing demand (or alternatively, by limiting supply), and second, we run a standard second price (Vickrey) auction. In their renowned work from 1996 , Bulow and Klemperer [Bulow J, Klemperer P (1996) Auctions vs. negotiations. Amer. Econom. Rev. 86(1):180–194.] apply this method to markets with single goods. As our main result, we give the first application beyond single-parameter settings, proving that, simultaneously for many valuation distributions, this method achieves expected revenue at least as good as the optimal revenue in the original market. Our robust and simple approach provides a handle on the elusive optimal revenue in multiitem matching markets and shows when the use of welfare-maximizing Vickrey auctions is justified, even if revenue is a priority. By establishing quantitative tradeoffs, our work provides guidelines for a seller in choosing among two different revenue-extracting strategies: sophisticated pricing based on market research or advertising to draw additional bidders. 

   more » « less
2. 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
3. An Efficient epsilon-BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization

   Cai, Yang; Oikonomou, Argyris; Velegkas, Grigoris; Zhao, Mingfei (January 2021, ACM-SIAM Symposium on Discrete Algorithms (SODA21))

   We consider the black-box reduction from multi-dimensional revenue maximization to virtual welfare maximization. Cai et al. [12, 13, 14, 15] show a polynomial-time approximation-preserving re-duction, however, the mechanism produced by their reduction is only approximately Bayesian incentive compatible (ε-BIC). We provide two new polynomial time transformations that convert anyε-BICmechanism to an exactly BIC mechanism with only a negligible revenue loss. (i) Our first transformation applies to any mechanism design setting with downward-closed outcome space and only requires sample accessto the agents’ type distributions. (ii) Our second transformation applies to the fully general outcome space, removing the downward-closed assumption, but requires full access to the agents’ type distributions. Both transformations only require query access to the originalε-BIC mechanism. Otherε-BIC to BICtransformations for revenue exist in the literature but all require exponential time to run in either of the settings we consider. As an application of our transformations, we improve the reduction by Cai et al. to generate an exactly BIC mechanism. 

   more » « less
4. EFx Budget-Feasible Allocations with High Nash Welfare

   Garbea, Marius; Gkatzelis, Vasilis; Tan, Xizhi (October 2023, 26th European Conference on Artificial Intelligence)

   We study the problem of allocating indivisible items to budget-constrained agents, aiming to provide fairness and efficiency guarantees. Specifically, our goal is to ensure that the resulting allocation is envy-free up to any item (EFx) while minimizing the amount of inefficiency that this needs to introduce. We first show that there exist two-agent problem instances for which no EFx allocation is Pareto-efficient. We, therefore, turn to approximation and use the (Pareto-efficient) maximum Nash welfare allocation as a benchmark. For two-agent instances, we provide a procedure that always returns an EFx allocation while achieving the best possible approximation of the optimal Nash social welfare that EFx allocations can achieve. For the more complicated case of three-agent instances, we provide a procedure that guarantees EFx, while achieving a constant approximation of the optimal Nash social welfare for any number of items. 

   more » « less
5. Non-linear Welfare-Aware Strategic Learning

   Xie, Tian; Zhang, Xueru (August 2024, 7th AAAI Conference on AI, Ethics, and Society)

   This paper studies algorithmic decision-making in the presence of strategic individual behaviors, where an ML model is used to make decisions about human agents and the latter can adapt their behavior strategically to improve their future data. Existing results on strategic learning have largely focused on the linear setting where agents with linear labeling functions best respond to a (noisy) linear decision policy. Instead, this work focuses on general non-linear settings where agents respond to the decision policy with only "local information" of the policy. Moreover, we simultaneously consider the objectives of maximizing decision-maker welfare (model prediction accuracy), social welfare (agent improvement caused by strategic behaviors), and agent welfare (the extent that ML underestimates the agents). We first generalize the agent best response model in previous works to the non-linear setting, then reveal the compatibility of welfare objectives. We show the three welfare can attain the optimum simultaneously only under restrictive conditions which are challenging to achieve in non-linear settings. The theoretical results imply that existing works solely maximizing the welfare of a subset of parties inevitably diminish the welfare of the others. We thus claim the necessity of balancing the welfare of each party in non-linear settings and propose an irreducible optimization algorithm suitable for general strategic learning. Experiments on synthetic and real data validate the proposed algorithm. 

   more » « less