跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.22216 · v1

Settling the Time and Structural Complexity of Bertrand Networks

首次提交 2026-11-17 12:52
版本更新 2026-11-17 12:52
雷达观测 2026-11-18 19:43
arXiv ↗PDF ↗

摘要

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(2n)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 Ω(2n)Ω(2^n).

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-17 12:52 · 最新观测版本

Settling the Time and Structural Complexity of Bertrand Networks

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(2n)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 Ω(2n)Ω(2^n).

查看此版本解读 →查看此版本原文 ↗