Networks of Complements

The 43rd International Colloquium on Automata, Languages and Programming (ICALP) |

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.