5 Search Results for "Caragiannis, Ioannis"


Document
Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations

Authors: Siddharth Barman, Umang Bhaskar, Anand Krishna, and Ranjani G. Sundaram

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)


Abstract
We develop polynomial-time algorithms for the fair and efficient allocation of indivisible goods among n agents that have subadditive valuations over the goods. We first consider the Nash social welfare as our objective and design a polynomial-time algorithm that, in the value oracle model, finds an 8n-approximation to the Nash optimal allocation. Subadditive valuations include XOS (fractionally subadditive) and submodular valuations as special cases. Our result, even for the special case of submodular valuations, improves upon the previously best known O(n log n)-approximation ratio of Garg et al. (2020). More generally, we study maximization of p-mean welfare. The p-mean welfare is parameterized by an exponent term p ∈ (-∞, 1] and encompasses a range of welfare functions, such as social welfare (p = 1), Nash social welfare (p → 0), and egalitarian welfare (p → -∞). We give an algorithm that, for subadditive valuations and any given p ∈ (-∞, 1], computes (in the value oracle model and in polynomial time) an allocation with p-mean welfare at least 1/(8n) times the optimal. Further, we show that our approximation guarantees are essentially tight for XOS and, hence, subadditive valuations. We adapt a result of Dobzinski et al. (2010) to show that, under XOS valuations, an O (n^{1-ε}) approximation for the p-mean welfare for any p ∈ (-∞,1] (including the Nash social welfare) requires exponentially many value queries; here, ε > 0 is any fixed constant.

Cite as

Siddharth Barman, Umang Bhaskar, Anand Krishna, and Ranjani G. Sundaram. Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{barman_et_al:LIPIcs.ESA.2020.11,
  author =	{Barman, Siddharth and Bhaskar, Umang and Krishna, Anand and Sundaram, Ranjani G.},
  title =	{{Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.11},
  URN =		{urn:nbn:de:0030-drops-128775},
  doi =		{10.4230/LIPIcs.ESA.2020.11},
  annote =	{Keywords: Discrete Fair Division, Nash Social Welfare, Subadditive Valuations, Submodular Valuations}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies

Authors: Ioannis Caragiannis and Angelo Fanelli

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)


Abstract
We consider the problem of the existence of natural improvement dynamics leading to approximate pure Nash equilibria, with a reasonable small approximation, and the problem of bounding the efficiency of such equilibria in the fundamental framework of weighted congestion game with polynomial latencies of degree at most d >= 1. In this work, by exploiting a simple technique, we firstly show that the game always admits a d-approximate potential function. This implies that every sequence of d-approximate improvement moves by the players always leads the game to a d-approximate pure Nash equilibrium. As a corollary, we also obtain that, under mild assumptions on the structure of the players' strategies, the game always admits a constant approximate potential function. Secondly, by using a simple potential function argument, we are able to show that in the game there always exists a (d+delta)-approximate pure Nash equilibrium, with delta in [0,1], whose cost is 2/(1+delta) times the cost of an optimal state.

Cite as

Ioannis Caragiannis and Angelo Fanelli. On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 133:1-133:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{caragiannis_et_al:LIPIcs.ICALP.2019.133,
  author =	{Caragiannis, Ioannis and Fanelli, Angelo},
  title =	{{On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{133:1--133:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.133},
  URN =		{urn:nbn:de:0030-drops-107095},
  doi =		{10.4230/LIPIcs.ICALP.2019.133},
  annote =	{Keywords: Congestion games, approximate pure Nash equilibrium, potential functions, approximate price of stability}
}
Document
Almost Envy-Free Allocations with Connected Bundles

Authors: Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)


Abstract
We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph G. When the items are arranged in a path, we show that EF1 allocations are guaranteed to exist for arbitrary monotonic utility functions over bundles, provided that either there are at most four agents, or there are any number of agents but they all have identical utility functions. Our existence proofs are based on classical arguments from the divisible cake-cutting setting, and involve discrete analogues of cut-and-choose, of Stromquist's moving-knife protocol, and of the Su-Simmons argument based on Sperner's lemma. Sperner's lemma can also be used to show that on a path, an EF2 allocation exists for any number of agents. Except for the results using Sperner's lemma, all of our procedures can be implemented by efficient algorithms. Our positive results for paths imply the existence of connected EF1 or EF2 allocations whenever G is traceable, i.e., contains a Hamiltonian path. For the case of two agents, we completely characterize the class of graphs G that guarantee the existence of EF1 allocations as the class of graphs whose biconnected components are arranged in a path. This class is strictly larger than the class of traceable graphs; one can check in linear time whether a graph belongs to this class, and if so return an EF1 allocation.

Cite as

Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker. Almost Envy-Free Allocations with Connected Bundles. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 14:1-14:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ITCS.2019.14,
  author =	{Bil\`{o}, Vittorio and Caragiannis, Ioannis and Flammini, Michele and Igarashi, Ayumi and Monaco, Gianpiero and Peters, Dominik and Vinci, Cosimo and Zwicker, William S.},
  title =	{{Almost Envy-Free Allocations with Connected Bundles}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{14:1--14:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.14},
  URN =		{urn:nbn:de:0030-drops-101078},
  doi =		{10.4230/LIPIcs.ITCS.2019.14},
  annote =	{Keywords: Envy-free Division, Cake-cutting, Resource Allocation, Algorithmic Game Theory}
}
Document
Simple Greedy Algorithms for Fundamental Multidimensional Graph Problems

Authors: Vittorio Bilò, Ioannis Caragiannis, Angelo Fanelli, Michele Flammini, and Gianpiero Monaco

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)


Abstract
We revisit fundamental problems in undirected and directed graphs, such as the problems of computing spanning trees, shortest paths, steiner trees, and spanning arborescences of minimum cost. We assume that there are d different cost functions associated with the edges of the input graph and seek for solutions to the resulting multidimensional graph problems so that the p-norm of the different costs of the solution is minimized. We present combinatorial algorithms that achieve very good approximations for this objective. The main advantage of our algorithms is their simplicity: they are as simple as classical combinatorial graph algorithms of Dijkstra and Kruskal, or the greedy algorithm for matroids.

Cite as

Vittorio Bilò, Ioannis Caragiannis, Angelo Fanelli, Michele Flammini, and Gianpiero Monaco. Simple Greedy Algorithms for Fundamental Multidimensional Graph Problems. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 125:1-125:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ICALP.2017.125,
  author =	{Bil\`{o}, Vittorio and Caragiannis, Ioannis and Fanelli, Angelo and Flammini, Michele and Monaco, Gianpiero},
  title =	{{Simple Greedy Algorithms for Fundamental Multidimensional Graph Problems}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{125:1--125:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.125},
  URN =		{urn:nbn:de:0030-drops-74669},
  doi =		{10.4230/LIPIcs.ICALP.2017.125},
  annote =	{Keywords: multidimensional graph problems, matroids, shortest paths, Steiner trees, arborescences}
}
Document
Approximate Pure Nash Equilibria in Weighted Congestion Games

Authors: Christoph Hansknecht, Max Klimm, and Alexander Skopalik

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)


Abstract
We study the existence of approximate pure Nash equilibria in weighted congestion games and develop techniques to obtain approximate potential functions that prove the existence of alpha-approximate pure Nash equilibria and the convergence of alpha-improvement steps. Specifically, we show how to obtain upper bounds for approximation factor alpha for a given class of cost functions. For example for concave cost functions the factor is at most 3/2, for quadratic cost functions it is at most 4/3, and for polynomial cost functions of maximal degree d it is at at most d + 1. For games with two players we obtain tight bounds which are as small as for example 1.054 in the case of quadratic cost functions.

Cite as

Christoph Hansknecht, Max Klimm, and Alexander Skopalik. Approximate Pure Nash Equilibria in Weighted Congestion Games. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 242-257, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{hansknecht_et_al:LIPIcs.APPROX-RANDOM.2014.242,
  author =	{Hansknecht, Christoph and Klimm, Max and Skopalik, Alexander},
  title =	{{Approximate Pure Nash Equilibria in Weighted Congestion Games}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{242--257},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.242},
  URN =		{urn:nbn:de:0030-drops-47005},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.242},
  annote =	{Keywords: Congestion game, Pure Nash equilibrium, Approximate equilibrium, Existence, Potential function}
}
  • Refine by Author
  • 3 Caragiannis, Ioannis
  • 2 Bilò, Vittorio
  • 2 Fanelli, Angelo
  • 2 Flammini, Michele
  • 2 Monaco, Gianpiero
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Algorithmic game theory
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Convergence and learning in games

  • Refine by Keyword
  • 1 Algorithmic Game Theory
  • 1 Approximate equilibrium
  • 1 Cake-cutting
  • 1 Congestion game
  • 1 Congestion games
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2019
  • 1 2014
  • 1 2017
  • 1 2020

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