pith. sign in

arxiv: 2606.23288 · v1 · pith:IBSBRO7Tnew · submitted 2026-06-22 · 💰 econ.TH · cs.GT

Flow Games with Public Arcs: the Least Core and the Nucleolus

Tianhang Lu , Han Xiao , Qizhi Fang This is my paper

Pith reviewed 2026-06-26 06:09 UTC · model grok-4.3

classification 💰 econ.TH cs.GT
keywords flow gamespublic arcsleast corenucleoluscooperative game theorymaximum flownetwork allocation
0
0 comments X

The pith

Flow games with public arcs have their least core characterized and nucleolus computed in polynomial time when the core is non-empty.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies an extension of cooperative flow games in which coalitions control private arcs but may also use public arcs freely when computing maximum flows. It focuses on the least core, which finds allocations that minimize the worst-case excess, and the nucleolus, which refines this by lexicographically minimizing the vector of excesses. Characterizations are derived for the least core of these games, and a polynomial-time algorithm is supplied for the nucleolus precisely when the core is non-empty. The setting models allocation problems in networks with shared resources such as financial, communication, or supply-chain systems.

Core claim

The authors characterize the least core of flow games with public arcs and give a polynomial-time algorithm to compute the nucleolus when the core is non-empty.

What carries the argument

The flow game with public arcs, in which a coalition's value equals the maximum flow value obtainable from its private arcs together with all public arcs.

If this is right

  • The least core allocations satisfy explicit linear inequalities derived from the max-flow values of coalitions.
  • When the core is non-empty the nucleolus can be found by solving a sequence of linear programs in polynomial time.
  • These solution concepts directly yield fair divisions of the grand-coalition flow value among players who control arcs.
  • The characterizations allow verification of candidate allocations without enumerating all coalitions.
  • The results apply to any network whose value function is defined by maximum flows augmented by public arcs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same characterizations might be tested on variants where public arcs have limited capacities.
  • The polynomial algorithm could be adapted to compute the nucleolus even when the core is empty by relaxing the initial feasibility step.
  • Similar techniques may carry over to other cooperative games whose values are defined by optimization problems rather than simple additive payoffs.
  • Applications in supply chains could be checked by constructing explicit public-arc instances from real logistics data and comparing the computed nucleolus to observed cost-sharing rules.

Load-bearing premise

Public arcs can be used freely by any coalition without capacity conflicts or additional costs.

What would settle it

A concrete flow network with public arcs in which an allocation claimed to lie in the least core violates one of the derived characterizing conditions, or in which the nucleolus algorithm runs slower than polynomial time on a family of instances with non-empty cores.

Figures

Figures reproduced from arXiv: 2606.23288 by Han Xiao, Qizhi Fang, Tianhang Lu.

Figure 1
Figure 1. Figure 1: An example showing that universal flows and maximum flows need not coincide. [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An example of players in (A ∩ N) \ N∗ . A key property of veto players is given in the following lemma. Moreover, this lemma gives a method to quickly determine whether a player is a veto player by using x ∗ . Lemma 14. Let e ∈ N. The following statements are equivalent: (i) e is a veto player; (ii) x ∗ (e) > 0; (iii) There exists a minimum cut C without public arcs such that e ∈ C. Proof. (i) ⇒ (ii). If e… view at source ↗
Figure 3
Figure 3. Figure 3: An example of jumps (red, black, and green represent [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript extends classical cooperative flow games by adding public arcs that any coalition may use freely when computing its max-flow value. The authors characterize the least core of the resulting TU game and present a polynomial-time algorithm for the nucleolus whenever the core is nonempty. Applications to financial, communication, and supply-chain networks are noted.

Significance. The extension models shared public resources in networks in a natural way and yields standard cooperative-game solution concepts. The polynomial-time nucleolus algorithm (when the core is nonempty) is a concrete algorithmic contribution, as nucleolus computation is NP-hard in general TU games. The paper therefore supplies both structural characterizations and an efficient computational procedure.

minor comments (3)
  1. [Abstract] The abstract states that characterizations of the least core are provided; the introduction or §3 should explicitly reference the theorem numbers that contain these characterizations so readers can locate them immediately.
  2. [§2] Notation for the set of public arcs (denoted P in the model) is introduced without a small illustrative network; adding a one-paragraph example early in §2 would improve readability without lengthening the paper.
  3. [§4] The complexity claim for the nucleolus algorithm is stated as polynomial; the running-time bound (e.g., O(|V|·|E|^2) or similar) should be stated explicitly in the theorem that presents the algorithm.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive evaluation of the manuscript. The report recommends minor revision but lists no specific major comments. We will address any minor editorial or presentational issues in the revised version.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper defines flow games with public arcs by extending the standard max-flow value of a coalition to include freely usable public arcs, then directly applies the standard definitions of the least core and nucleolus from cooperative game theory to the resulting TU game. The claimed characterizations and polynomial-time algorithm (when the core is nonempty) are presented as consequences of this construction without any self-referential fitting, self-citation chains, or renaming of inputs as outputs. No load-bearing step reduces to its own inputs by construction, and the abstract and described approach remain self-contained against external benchmarks in cooperative game theory.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based on the abstract, the paper relies on standard definitions from cooperative game theory and network flows without introducing new free parameters or invented entities.

axioms (1)
  • domain assumption The value of a coalition is the maximum flow achievable using the arcs controlled by the coalition along with the public arcs.
    This is the fundamental definition of the game value in the abstract.

pith-pipeline@v0.9.1-grok · 5658 in / 1097 out tokens · 41714 ms · 2026-06-26T06:09:49.608990+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references

  1. [1]

    Ahuja, R.K., Magnanti, T.L., Orlin, J.B., et al.: Network flows: theory, algorithms, and applications, vol. 1. Prentice Hall Englewood Cliffs, USA (1993)

    1993

  2. [2]

    In: Mathematical Foun- dations of Computer Science 2011

    Bachrach, Y.: The least-core of threshold network flow games. In: Mathematical Foun- dations of Computer Science 2011. pp. 36–47. Springer Berlin Heidelberg, Berlin, Hei- delberg (2011)

    2011

  3. [3]

    Synthesis Lectures on Artificial Intelligence and Machine Learning5(6), 1–168 (2011)

    Chalkiadakis, G., Elkind, E., Wooldridge, M.: Computational aspects of cooperative game theory. Synthesis Lectures on Artificial Intelligence and Machine Learning5(6), 1–168 (2011)

    2011

  4. [4]

    In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm

    Deng, X., Fang, Q., Sun, X.: Finding nucleolus of flow game. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm. p. 124–131. SODA ’06, Society for Industrial and Applied Mathematics, USA (2006)

    2006

  5. [5]

    In: Computing and Combinatorics

    Fang, Q., Li, B., Shan, X., Sun, X.: The least-core and nucleolus of path cooperative games. In: Computing and Combinatorics. pp. 70–82. Springer International Publish- ing, Cham (2015)

    2015

  6. [6]

    International Journal of Game Theory 31, 39–45 (2002)

    Fang, Q., Zhu, S., Cai, M., Deng, X.: On computational complexity of membership test in flow games and linear production games. International Journal of Game Theory 31, 39–45 (2002)

    2002

  7. [7]

    INFOR: Information Systems and Operational Research 9(3), 293–304 (1971)

    Florian, M., Rossin-Arthiat, M., De Werra, D.: A property of minimum concave cost flows in capacitated networks. INFOR: Information Systems and Operational Research 9(3), 293–304 (1971)

    1971

  8. [8]

    Canadian Journal of Mathematics8, 399–404 (1956)

    Ford Jr, L.R., Fulkerson, D.R.: Maximal flow through a network. Canadian Journal of Mathematics8, 399–404 (1956)

    1956

  9. [9]

    Acta Informatica13(1), 53–58 (1980)

    Galil, Z.: Applications of efficient mergeable heaps for optimization problems on trees. Acta Informatica13(1), 53–58 (1980)

    1980

  10. [10]

    arXiv preprint arXiv:2403.06037 (2024)

    Gangam, R.R., Garg, N., Shahkar, P., Vazirani, V.V.: Leximin and leximax fair core imputations for the max-flow, mst, and bipartiteb-matching games. arXiv preprint arXiv:2403.06037 (2024)

    arXiv 2024

  11. [11]

    Contributions to the Theory of Games4(40), 47–85 (1959)

    Gillies, D.B.: Solutions to general non-zero-sum games. Contributions to the Theory of Games4(40), 47–85 (1959)

    1959

  12. [12]

    ACM Transactions on Computation Theory (TOCT)7(1), 1–52 (2015)

    Greco, G., Malizia, E., Palopoli, L., Scarcello, F.: The complexity of the nucleolus in compact games. ACM Transactions on Computation Theory (TOCT)7(1), 1–52 (2015)

    2015

  13. [13]

    Gr¨ otschel, M., Lov´ asz, L., Schrijver, A.: Geometric algorithms and combinatorial op- timization, vol. 2. Springer Science & Business Media (2012) 15

    2012

  14. [14]

    Mathematics of Operations Research7(3), 476–478 (1982)

    Kalai, E., Zemel, E.: Totally balanced games and games of flow. Mathematics of Operations Research7(3), 476–478 (1982)

    1982

  15. [15]

    Mathe- matics of Operations Research28(2), 294–308 (2003)

    Kern, W., Paulusma, D.: Matching games: the least core and the nucleolus. Mathe- matics of Operations Research28(2), 294–308 (2003)

    2003

  16. [16]

    Mathematical Programming183, 555–581 (2020)

    K¨ onemann, J., Pashkovich, K., Toth, J.: Computing the nucleolus of weighted cooper- ative matching games in polynomial time. Mathematical Programming183, 555–581 (2020)

    2020

  17. [17]

    Mathematics of Operations Research4(4), 303–338 (1979)

    Maschler, M., Peleg, B., Shapley, L.S.: Geometric properties of the kernel, nucleo- lus, and related solution concepts. Mathematics of Operations Research4(4), 303–338 (1979)

    1979

  18. [18]

    Mathematics of Operations Research3(3), 189–196 (1978)

    Megiddo, N.: Computational complexity of the game theory approach to cost allocation for a tree. Mathematics of Operations Research3(3), 189–196 (1978)

    1978

  19. [19]

    Mathematical Programming22(1), 121–121 (1982)

    Picard, J.C., Queyranne, M.: On the structure of all minimum cuts in a network and applications. Mathematical Programming22(1), 121–121 (1982)

    1982

  20. [20]

    Games and Economic Behavior54(1), 205–225 (2006)

    Potters, J., Reijnierse, H., Biswas, A.: The nucleolus of balanced simple flow networks. Games and Economic Behavior54(1), 205–225 (2006)

    2006

  21. [21]

    Games and Economic Behavior16(2), 238–260 (1996)

    Reijnierse, H., Maschler, M., Potters, J., Tijs, S.: Simple flow games. Games and Economic Behavior16(2), 238–260 (1996)

    1996

  22. [22]

    SIAM Journal on Applied Mathematics17(6), 1163–1170 (1969)

    Schmeidler, D.: The nucleolus of a characteristic function game. SIAM Journal on Applied Mathematics17(6), 1163–1170 (1969)

    1969

  23. [23]

    Wiley-Interscience Series in Discrete Mathematics (1986)

    Schrijver, A.: Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics (1986)

    1986

  24. [24]

    Econometrica: Journal of the Econometric Society pp

    Shapley, L.S., Shubik, M.: Quasi-cores in a monetary economy with nonconvex prefer- ences. Econometrica: Journal of the Econometric Society pp. 805–827 (1966)

    1966

  25. [25]

    Mathematical Programming163(1), 243–271 (2017)

    Sziklai, B., Fleiner, T., Solymosi, T.: On the core and nucleolus of directed acyclic graph games. Mathematical Programming163(1), 243–271 (2017)

    2017

  26. [26]

    Operations Re- search Letters8(1), 31–34 (1989)

    Tamir, A.: On the core of a traveling salesman cost allocation game. Operations Re- search Letters8(1), 31–34 (1989)

    1989

  27. [27]

    Mathematical Pro- gramming198(1), 1–25 (2023) 16 A Proofs A.1 Proof of Lemma 2 Proof.(i)P 1(ϵ1)⊆R |N| +

    Xiao, H., Fang, Q.: Arboricity games: the core and the nucleolus. Mathematical Pro- gramming198(1), 1–25 (2023) 16 A Proofs A.1 Proof of Lemma 2 Proof.(i)P 1(ϵ1)⊆R |N| + . Suppose thatx∈P 1(ϵ1) and that there existse 0 ∈Nsuch thatx(e 0)<0. In this case, ϵ1 ≤x(e 0)−v({e 0})<0. LetS⊆N\ {e 0}. IfS̸=N\ {e 0}, then e(x, S)> x(S∪ {e 0})−v(S)≥e(x, S∪ {e 0})≥ϵ 1....

    2023

  28. [28]

    We prove that ϵ1 =ϵ ′ 1, andP 1(ϵ1) =P ′ 1(ϵ′ 1)

    as the linear program obtained by replacing the inequalities in the linear program (P 1), and letϵ ′ 1 be the optimal objective function value of (P ′ 1). We prove that ϵ1 =ϵ ′ 1, andP 1(ϵ1) =P ′ 1(ϵ′ 1). Letx∈P 1(ϵ1). By Lemma 2,x(e)≥0,∀e∈N. Letf∈ F. LetS f ={e∈N|f(e) = 1}. IfS f ⊊N, thenx(f)−c(f)≥x(S f)−v(S f)≥ϵ 1. If Sf =N, thenx(f) =x(N) =v(N), and si...

  29. [29]

    This shows thatP ′ 1(ϵ′ 1)⊆P 1(ϵ′

    is a feasible solution of (P 1). This shows thatP ′ 1(ϵ′ 1)⊆P 1(ϵ′

  30. [30]

    Therefore, we have shown thatϵ 1 =ϵ ′

    andϵ ′ 1 ≤ϵ 1. Therefore, we have shown thatϵ 1 =ϵ ′

  31. [31]

    17 A.3 Proof of Lemma 5 Proof.Let (π, y) be an optimal solution of the dual program (3)

    SinceP 1(ϵ1)⊆P ′ 1(ϵ1) andP ′ 1(ϵ′ 1)⊆P 1(ϵ′ 1), we obtainP 1(ϵ1) =P ′ 1(ϵ′ 1). 17 A.3 Proof of Lemma 5 Proof.Let (π, y) be an optimal solution of the dual program (3). For eache∈E, define σ(e) =    x(e)− π(∂ −e)−π(∂ +e) +y(e) , e∈N, − π(∂ −e)−π(∂ +e) +y(e) , e∈N 0. By dual feasibility,σ(e)≥0 andy(e)≤0,∀e∈E. Since (π, y) is dual optimal,gis optimal for...

  32. [32]

    , kthen 21:returnx

    = 0 fori= 1, . . . , kthen 21:returnx. 22:end if 23:end if 24:end loop Claim 1.If the algorithm returnsx, thenxis a relative interior point ofP 1(ϵ1). Proof.Letxbe the vector output by the algorithm, and letf∈ F x. We prove thatfis a universal flow. Lety∈P 1(ϵ1). According to step 20, we havea i(f) = 0 fori= 1, . . . , k; therefore,f∈span(F). LetF={f 1, ....

  33. [33]

    Ify∈P ′ 1(ϵ′ 1), then for anyS⊆N, we have (y,0)(S) =y(S\ {e i})≥v ′(S\ {e i}) +ϵ ′ 1 =v(S) +ϵ ′ 1

    be the least core of (N ′, v′). Ify∈P ′ 1(ϵ′ 1), then for anyS⊆N, we have (y,0)(S) =y(S\ {e i})≥v ′(S\ {e i}) +ϵ ′ 1 =v(S) +ϵ ′ 1. Thus,ϵ 1 ≥ϵ ′

  34. [34]

    Therefore,ϵ ′ 1 ≥ϵ 1

    Conversely, ifz∈P 1(ϵ1) andz(e i) = 0, then for anyS⊆N ′, we have z(S) =z(S∪ {e i})≥v(S∪ {e i}) +ϵ 1 =v ′(S) +ϵ 1. Therefore,ϵ ′ 1 ≥ϵ 1. In summary, we haveϵ 1 =ϵ ′ 1 andP ′ 1(ϵ′

  35. [35]

    Letx= (x ′,0)

    ={y|(y,0)∈P 1(ϵ1)}. Letx= (x ′,0). Sincex(e i) = 0 andxis an extreme point ofP 1(ϵ1), it follows thatx ′ is an extreme point ofP ′ 1(ϵ′ 1). By induction,ϵ ′ 1 = 1 k′ −1 andk ′x′ is the convex hull of characteristic vectors of minimum cuts constrained toN ′. Ifk=k ′, thenϵ 1 =ϵ ′ 1 = 1 k −1. Since minimum cuts constrained toN ′ are also minimum cuts constr...