License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.93
URN: urn:nbn:de:0030-drops-175969
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17596/
Go to the corresponding LIPIcs Volume Portal

Rubinstein, Aviad ; Zhao, Junyao

Beyond Worst-Case Budget-Feasible Mechanism Design

pdf-format:
LIPIcs-ITCS-2023-93.pdf (0.9 MB)

Abstract

Motivated by large-market applications such as crowdsourcing, we revisit the problem of budget-feasible mechanism design under a "small-bidder assumption". Anari, Goel, and Nikzad (2018) gave a mechanism that has optimal competitive ratio 1-1/e on worst-case instances. However, we observe that on many realistic instances, their mechanism is significantly outperformed by a simpler open clock auction by Ensthaler and Giebe (2014), although the open clock auction only achieves competitive ratio 1/2 in the worst case. Is there a mechanism that gets the best of both worlds, i.e., a mechanism that is worst-case optimal and performs favorably on realistic instances? To answer this question, we initiate the study of beyond worst-case budget-feasible mechanism design.
Our first main result is the design and the analysis of a natural mechanism that gives an affirmative answer to our question above:
- We prove that on every instance, our mechanism performs at least as good as all uniform mechanisms, including Anari, Goel, and Nikzad’s and Ensthaler and Giebe’s mechanisms.
- Moreover, we empirically evaluate our mechanism on various realistic instances and observe that it beats the worst-case 1-1/e competitive ratio by a large margin and compares favorably to both mechanisms mentioned above.
Our second main result is more interesting in theory: We show that in the semi-adversarial model of budget-smoothed analysis, where the adversary designs a single worst-case market for a distribution of budgets, our mechanism is optimal among all (including non-uniform) mechanisms; furthermore our mechanism guarantees a strictly better-than-(1-1/e) expected competitive ratio for any non-trivial budget distribution regardless of the market. (In contrast, given any bounded range of budgets, we can construct a single market where Anari, Goel, and Nikzad’s mechanism achieves only 1-1/e competitive ratio for every budget in this range.) We complement the positive result with a characterization of the worst-case markets for any given budget distribution and prove a fairly robust hardness result that holds against any budget distribution and any mechanism.

BibTeX - Entry

@InProceedings{rubinstein_et_al:LIPIcs.ITCS.2023.93,
  author =	{Rubinstein, Aviad and Zhao, Junyao},
  title =	{{Beyond Worst-Case Budget-Feasible Mechanism Design}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{93:1--93:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17596},
  URN =		{urn:nbn:de:0030-drops-175969},
  doi =		{10.4230/LIPIcs.ITCS.2023.93},
  annote =	{Keywords: Procurement auctions, Mechanism design, Beyond worst-case analysis}
}

Keywords: Procurement auctions, Mechanism design, Beyond worst-case analysis
Collection: 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Issue Date: 2023
Date of publication: 01.02.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI