2026-07-23T02:57:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6284 2024-03-06T10:37:56Z ddc:004 open_access

Networks of Complements Babaioff, Moshe Blumrosen, Liad Nisan, Noam Complements Pricing Networks Game Theory Price of Stability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moshe Babaioff and Liad Blumrosen and Noam Nisan 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.140 urn:nbn:de:0030-drops-62849 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.140 eng https://creativecommons.org/licenses/by/3.0/legalcode