1. On the Approximate Core and Nucleon of Flow Games
- Author
-
Liu, Pengfei, Xiao, Han, and Fang, Qizhi
- Subjects
Computer Science - Computer Science and Game Theory ,05C57, 91A12, 91A43, 91A46 - Abstract
The flow game with public arcs is a cooperative revenue game derived from a flow network. In this game, each player possesses an arc, while certain arcs, known as public arcs, are not owned by any specific player and are accessible to any coalition. The aim of this game is to maximize the flow that can be routed in the network through strategic coalition formation. By exploring its connection to the maximum partially disjoint path problem, we investigate the approximate core and nucleon of the flow game with public arcs. The approximate core is an extension of the core that allows for some deviation in group rationality, while the nucleon is a multiplicative analogue of the nucleolus. In this paper, we provide two complete characterizations for the optimal approximate core and show that the nucleon can be computed in polynomial time.
- Published
- 2024