1 Search Results for "Pliatsika, Venetia"

Document
DOI: 10.4230/LIPIcs.ESA.2017.43
Profit Sharing and Efficiency in Utility Games

Authors: Sreenivas Gollapudi, Kostas Kollias, Debmalya Panigrahi, and Venetia Pliatsika

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We study utility games (Vetta, FOCS 2002) where a set of players join teams to produce social utility, and receive individual utility in the form of payments in return. These games have many natural applications in competitive settings such as labor markets, crowdsourcing, etc. The efficiency of such a game depends on the profit sharing mechanism - the rule that maps utility produced by the players to their individual payments. We study three natural and widely used profit sharing mechanisms - egalitarian or equal sharing, marginal gain or value addition when a player joins, and marginal loss or value depletion when a player leaves. For these settings, we give tight bounds on the price of anarchy, thereby allowing comparison between these popular mechanisms from a (worst case) social welfare perspective.
Cite as

Sreenivas Gollapudi, Kostas Kollias, Debmalya Panigrahi, and Venetia Pliatsika. Profit Sharing and Efficiency in Utility Games. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gollapudi_et_al:LIPIcs.ESA.2017.43,
  author =	{Gollapudi, Sreenivas and Kollias, Kostas and Panigrahi, Debmalya and Pliatsika, Venetia},
  title =	{{Profit Sharing and Efficiency in Utility Games}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{43:1--43:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.43},
  URN =		{urn:nbn:de:0030-drops-78329},
  doi =		{10.4230/LIPIcs.ESA.2017.43},
  annote =	{Keywords: Price of anarchy, submodular maximization, coverage functions}
}
  • Refine by Author
  • 1 Gollapudi, Sreenivas
  • 1 Kollias, Kostas
  • 1 Panigrahi, Debmalya
  • 1 Pliatsika, Venetia

  • Refine by Classification

  • Refine by Keyword
  • 1 Price of anarchy
  • 1 coverage functions
  • 1 submodular maximization

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

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