License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.140
URN: urn:nbn:de:0030-drops-62849
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6284/
Go to the corresponding LIPIcs Volume Portal

Babaioff, Moshe ; Blumrosen, Liad ; Nisan, Noam

Networks of Complements

pdf-format:
LIPIcs-ICALP-2016-140.pdf (0.6 MB)

Abstract

We consider a network of sellers, each selling a single product, where the graph structure represents pair-wise complementarities between products. We study how the network structure affects revenue and social welfare of equilibria of the pricing game between the sellers. We prove positive and negative results, both of "Price of Anarchy" and of "Price of Stability" type, for special families of graphs (paths, cycles) as well as more general ones (trees, graphs). We describe best-reply dynamics that converge to non-trivial equilibrium in several families of graphs, and we use these dynamics to prove the existence of approximately-efficient equilibria.

BibTeX - Entry

@InProceedings{babaioff_et_al:LIPIcs:2016:6284,
  author =	{Moshe Babaioff and Liad Blumrosen and Noam Nisan},
  title =	{{Networks of Complements}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{140:1--140:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6284},
  URN =		{urn:nbn:de:0030-drops-62849},
  doi =		{10.4230/LIPIcs.ICALP.2016.140},
  annote =	{Keywords: Complements, Pricing, Networks, Game Theory, Price of Stability}
}

Keywords: Complements, Pricing, Networks, Game Theory, Price of Stability
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI