3 Search Results for "Zhao, Junyao"

Document
DOI: 10.4230/LIPIcs.ITCS.2023.93
Beyond Worst-Case Budget-Feasible Mechanism Design

Authors: Aviad Rubinstein and Junyao Zhao

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

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.
Cite as

Aviad Rubinstein and Junyao Zhao. Beyond Worst-Case Budget-Feasible Mechanism Design. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 93:1-93:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.93},
  URN =		{urn:nbn:de:0030-drops-175969},
  doi =		{10.4230/LIPIcs.ITCS.2023.93},
  annote =	{Keywords: Procurement auctions, Mechanism design, Beyond worst-case analysis}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.106
Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation

Authors: Aviad Rubinstein and Junyao Zhao

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
In this work we give two new algorithms that use similar techniques for (non-monotone) submodular function maximization subject to a cardinality constraint. The first is an offline fixed-parameter tractable algorithm that guarantees a 0.539-approximation for all non-negative submodular functions. The second algorithm works in the random-order streaming model. It guarantees a (1/2+c)-approximation for symmetric functions, and we complement it by showing that no space-efficient algorithm can beat 1/2 for asymmetric functions. To the best of our knowledge this is the first provable separation between symmetric and asymmetric submodular function maximization.
Cite as

Aviad Rubinstein and Junyao Zhao. Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 106:1-106:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rubinstein_et_al:LIPIcs.ICALP.2022.106,
  author =	{Rubinstein, Aviad and Zhao, Junyao},
  title =	{{Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{106:1--106:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.106},
  URN =		{urn:nbn:de:0030-drops-164478},
  doi =		{10.4230/LIPIcs.ICALP.2022.106},
  annote =	{Keywords: Submodular optimization, Fixed-parameter tractability, Random-order streaming}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.113
Budget-Smoothed Analysis for Submodular Maximization

Authors: Aviad Rubinstein and Junyao Zhao

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
The greedy algorithm for monotone submodular function maximization subject to cardinality constraint is guaranteed to approximate the optimal solution to within a 1-1/e factor. Although it is well known that this guarantee is essentially tight in the worst case - for greedy and in fact any efficient algorithm, experiments show that greedy performs better in practice. We observe that for many applications in practice, the empirical distribution of the budgets (i.e., cardinality constraints) is supported on a wide range, and moreover, all the existing hardness results in theory break under a large perturbation of the budget. To understand the effect of the budget from both algorithmic and hardness perspectives, we introduce a new notion of budget-smoothed analysis. We prove that greedy is optimal for every budget distribution, and we give a characterization for the worst-case submodular functions. Based on these results, we show that on the algorithmic side, under realistic budget distributions, greedy and related algorithms enjoy provably better approximation guarantees, that hold even for worst-case functions, and on the hardness side, there exist hard functions that are fairly robust to all the budget distributions.
Cite as

Aviad Rubinstein and Junyao Zhao. Budget-Smoothed Analysis for Submodular Maximization. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 113:1-113:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rubinstein_et_al:LIPIcs.ITCS.2022.113,
  author =	{Rubinstein, Aviad and Zhao, Junyao},
  title =	{{Budget-Smoothed Analysis for Submodular Maximization}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{113:1--113:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.113},
  URN =		{urn:nbn:de:0030-drops-157095},
  doi =		{10.4230/LIPIcs.ITCS.2022.113},
  annote =	{Keywords: Submodular optimization, Beyond worst-case analysis, Greedy algorithms, Hardness of approximation}
}
  • Refine by Author
  • 3 Rubinstein, Aviad
  • 3 Zhao, Junyao

  • Refine by Classification
  • 2 Theory of computation → Submodular optimization and polymatroids
  • 1 Theory of computation → Computational pricing and auctions

  • Refine by Keyword
  • 2 Beyond worst-case analysis
  • 2 Submodular optimization
  • 1 Fixed-parameter tractability
  • 1 Greedy algorithms
  • 1 Hardness of approximation
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2022
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact