Flow Games with Public Arcs: the Least Core and the Nucleolus
2026-06-22 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study a type of cooperative game where players control parts of a network but can also use shared parts called public arcs for free. They look at how groups of players can maximize flow through their controlled and public arcs, which is useful for understanding networks like finance or supply chains. The authors focus on two fair ways to divide the total value created by all players working together, called the least core and the nucleolus. They describe properties of the least core and provide an efficient method to find the nucleolus when a stable solution exists.
flow gamespublic arcscooperative gamesleast corenucleolusmaximum flowcoalitionscorepolynomial-time algorithm
Authors
Tianhang Lu, Han Xiao, Qizhi Fang
Abstract
We study flow games with public arcs, an extension of classical cooperative flow games that allows players to use public resources. In these games, a coalition corresponds to a set of arcs, while certain arcs, called public arcs, can be used freely by any coalition. The value of a coalition is the maximum flow value achievable using the arcs controlled by the coalition along with the public arcs. These games have significant applications in financial, communication, and supply-chain networks. We investigate two solution concepts, the least core and the nucleolus. Both solution concepts provide principled ways to allocate the value of the grand coalition among individual players. We provide characterizations of the least core of these games. We also give a polynomial-time algorithm to compute the nucleolus when the core is non-empty.