4 Search Results for "Gkatzelis, Vasilis"

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.63

A Note on Approximating Weighted Nash Social Welfare with Additive Valuations

Authors: Yuda Feng and Shi Li

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract

We give the first O(1)-approximation for the weighted Nash Social Welfare problem with additive valuations. The approximation ratio we obtain is e^{1/e} + ε ≈ 1.445 + ε, which matches the best known approximation ratio for the unweighted case [Barman et al., 2018]. Both our algorithm and analysis are simple. We solve a natural configuration LP for the problem, and obtain the allocation of items to agents using a randomized version of the Shmoys-Tardos rounding algorithm developed for unrelated machine scheduling problems [Shmoys and Tardos, 1993]. In the analysis, we show that the approximation ratio of the algorithm is at most the worst gap between the Nash social welfare of the optimum allocation and that of an EF1 allocation, for an unweighted Nash Social Welfare instance with identical additive valuations. This was shown to be at most e^{1/e} ≈ 1.445 by Barman et al. [Barman et al., 2018], leading to our approximation ratio.

Cite as

Yuda Feng and Shi Li. A Note on Approximating Weighted Nash Social Welfare with Additive Valuations. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 63:1-63:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ICALP.2024.63,
  author =	{Feng, Yuda and Li, Shi},
  title =	{{A Note on Approximating Weighted Nash Social Welfare with Additive Valuations}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{63:1--63:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.63},
  URN =		{urn:nbn:de:0030-drops-202068},
  doi =		{10.4230/LIPIcs.ICALP.2024.63},
  annote =	{Keywords: Nash Social Welfare, Configuration LP, Approximation Algorithms}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.96

Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets

Authors: Yasushi Kawase, Koichi Nishimura, and Hanna Sumita

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract

We study the problem of minimizing a given symmetric strictly convex function over the Minkowski sum of an integral base-polyhedron and an M-convex set. This problem has a hybrid of continuous and discrete structures. This emerges from the problem of allocating mixed goods, consisting of both divisible and indivisible goods, to agents with binary valuations so that the fairness measure, such as the Nash welfare, is maximized. It is known that both an integral base-polyhedron and an M-convex set have similar and nice properties, and the non-hybrid case can be solved in polynomial time. While the hybrid case lacks some of these properties, we show the structure of an optimal solution. Moreover, we exploit a proximity inherent in the problem. Through our findings, we demonstrate that our problem is NP-hard even in the fair allocation setting where all indivisible goods are identical. Moreover, we provide a polynomial-time algorithm for the fair allocation problem when all divisible goods are identical.

Cite as

Yasushi Kawase, Koichi Nishimura, and Hanna Sumita. Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 96:1-96:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.ICALP.2024.96,
  author =	{Kawase, Yasushi and Nishimura, Koichi and Sumita, Hanna},
  title =	{{Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{96:1--96:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.96},
  URN =		{urn:nbn:de:0030-drops-202393},
  doi =		{10.4230/LIPIcs.ICALP.2024.96},
  annote =	{Keywords: Integral base-polyhedron, Fair allocation, Matroid}
}

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}
}

Refine by Author
2 Gkatzelis, Vasilis
1 Balkanski, Eric
1 Christodoulou, Giorgos
1 Feng, Yuda
1 Kawase, Yasushi
Show More...

Refine by Classification
1 Mathematics of computing → Combinatorial optimization
1 Theory of computation → Algorithmic game theory
1 Theory of computation → Algorithmic mechanism design
1 Theory of computation → Approximation algorithms analysis
1 Theory of computation → Computational pricing and auctions

Refine by Keyword
1 Approximation Algorithms
1 Auctions
1 Configuration LP
1 Fair allocation
1 Integral base-polyhedron
Show More...

Refine by Type
4 document

Refine by Publication Year
2 2024
1 2022
1 2023