A Complete Characterization of Convexity in Flow Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917460152680448 |
|---|---|
| author | Xiao, Han Zhang, Luying Fang, Qizhi |
| author_facet | Xiao, Han Zhang, Luying Fang, Qizhi |
| contents | Flow games coincide precisely with the fundamental class of non-negative totally balanced games. However, the conditions for their convexity have remained elusive. In this paper, we resolve this challenge by providing a complete characterization. Specifically, we show that a flow game is convex if and only if its underlying network satisfies three structural conditions: acyclicity, bottleneck exclusivity, and capacity sufficiency. These structural conditions are also equivalent to dual separability, which resolves the apparent paradox between cycle orientations and game-theoretic convexity by decoupling path contributions via bottleneck exclusivity. Furthermore, our characterization yields an efficient recognition procedure, establishing that flow game convexity is verifiable in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_04729 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Complete Characterization of Convexity in Flow Games Xiao, Han Zhang, Luying Fang, Qizhi Computer Science and Game Theory 05C57, 91A12, 91A43, 91A46 Flow games coincide precisely with the fundamental class of non-negative totally balanced games. However, the conditions for their convexity have remained elusive. In this paper, we resolve this challenge by providing a complete characterization. Specifically, we show that a flow game is convex if and only if its underlying network satisfies three structural conditions: acyclicity, bottleneck exclusivity, and capacity sufficiency. These structural conditions are also equivalent to dual separability, which resolves the apparent paradox between cycle orientations and game-theoretic convexity by decoupling path contributions via bottleneck exclusivity. Furthermore, our characterization yields an efficient recognition procedure, establishing that flow game convexity is verifiable in polynomial time. |
| title | A Complete Characterization of Convexity in Flow Games |
| topic | Computer Science and Game Theory 05C57, 91A12, 91A43, 91A46 |
| url | https://arxiv.org/abs/2604.04729 |