DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2023.11

Strategyproof Scheduling with Predictions

Authors: Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan

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

Abstract

In their seminal paper that initiated the field of algorithmic mechanism design, Nisan and Ronen [Noam Nisan and Amir Ronen, 1999] studied the problem of designing strategyproof mechanisms for scheduling jobs on unrelated machines aiming to minimize the makespan. They provided a strategyproof mechanism that achieves an n-approximation and they made the bold conjecture that this is the best approximation achievable by any deterministic strategyproof scheduling mechanism. After more than two decades and several efforts, n remains the best known approximation and very recent work by Christodoulou et al. [George Christodoulou et al., 2021] has been able to prove an Ω(√n) approximation lower bound for all deterministic strategyproof mechanisms. This strong negative result, however, heavily depends on the fact that the performance of these mechanisms is evaluated using worst-case analysis. To overcome such overly pessimistic, and often uninformative, worst-case bounds, a surge of recent work has focused on the "learning-augmented framework", whose goal is to leverage machine-learned predictions to obtain improved approximations when these predictions are accurate (consistency), while also achieving near-optimal worst-case approximations even when the predictions are arbitrarily wrong (robustness). In this work, we study the classic strategic scheduling problem of Nisan and Ronen [Noam Nisan and Amir Ronen, 1999] using the learning-augmented framework and give a deterministic polynomial-time strategyproof mechanism that is 6-consistent and 2n-robust. We thus achieve the "best of both worlds": an O(1) consistency and an O(n) robustness that asymptotically matches the best-known approximation. We then extend this result to provide more general worst-case approximation guarantees as a function of the prediction error. Finally, we complement our positive results by showing that any 1-consistent deterministic strategyproof mechanism has unbounded robustness.

Cite as

Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. Strategyproof Scheduling with Predictions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{balkanski_et_al:LIPIcs.ITCS.2023.11,
  author =	{Balkanski, Eric and Gkatzelis, Vasilis and Tan, Xizhi},
  title =	{{Strategyproof Scheduling with Predictions}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{11:1--11: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/entities/document/10.4230/LIPIcs.ITCS.2023.11},
  URN =		{urn:nbn:de:0030-drops-175143},
  doi =		{10.4230/LIPIcs.ITCS.2023.11},
  annote =	{Keywords: Mechanism Design with Predictions, Strategyproof Scheduling}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2022.49

Optimal Deterministic Clock Auctions and Beyond

Authors: Giorgos Christodoulou, Vasilis Gkatzelis, and Daniel Schoepflin

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

Abstract

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.

Cite as

Giorgos Christodoulou, Vasilis Gkatzelis, and Daniel Schoepflin. Optimal Deterministic Clock Auctions and Beyond. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 49:1-49:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.ITCS.2022.49,
  author =	{Christodoulou, Giorgos and Gkatzelis, Vasilis and Schoepflin, Daniel},
  title =	{{Optimal Deterministic Clock Auctions and Beyond}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{49:1--49: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.49},
  URN =		{urn:nbn:de:0030-drops-156453},
  doi =		{10.4230/LIPIcs.ITCS.2022.49},
  annote =	{Keywords: Auctions, Obvious Strategyproofness, Mechanism Design}
}

Search Results

Documents authored by Gkatzelis, Vasilis

Strategyproof Scheduling with Predictions

Abstract

Cite as

Optimal Deterministic Clock Auctions and Beyond

Abstract

Cite as

Thanks for your feedback!

Could not send message