arXiv preprint ·

Settling the Time and Structural Complexity of Bertrand Networks

MohammadTaghi Hajiaghayi and Suho Shin

Published
Source
arXiv preprint, posted before peer review
Original
Read it at arXiv
Topics
Computer Science & Game TheoryData Structures & AlgorithmsTheoretical Economics

Abstract

In the seminal Bertrand network game introduced by Babaioff et al. (2013), each seller posts a single price to captive buyers and to the markets it shares with neighboring sellers, where sellers cannot price discriminate across the markets. Although the existence of equilibria and polynomial-time algorithms to compute them in trees (Babaioff et al. (2013)) have been known, it has been a major open problem whether there exist efficient algorithms to compute them for general graphs. In this paper, we resolve this open question negatively by proving that computing any constant-error approximate Nash equilibrium in a Bertrand network is $\PPAD$-complete. This hardness holds even on sparse bipartite graphs of maximum degree five with constant integer market weights. Complementing our hardness result, we design an efficient polynomial-time approximation scheme (EPTAS) when both the maximum degree and the number of sellers with captive buyers are bounded. Beyond time complexity, since exact equilibria require randomizing prices over continuous intervals, another fundamental question left open by Babaioff et al. (2013) is whether an exact equilibrium can always be represented with a finite number of price intervals, \ie whether its structural complexity is finite. We resolve this question affirmatively by proving that every achievable equilibrium revenue profile can be realized by an equilibrium with structural complexity $O(2^n)$, which leads to an exact algorithm running in doubly exponential time. We further show that this bound is tight: there exist instances for which the unique equilibrium realizing target revenue profiles has structural complexity $Ω(2^n)$.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Computer Science & Game Theory

Get the few papers worth your time in Computer Science & Game Theory every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics