Pith. sign in

REVIEW 2 major objections 5 minor 1 cited by

Flow Allocation Games

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read In financial networks where firms rank payments by individual coins, there is always a strong equilibrium whose money flows maximize total revenue, and it can be computed in polynomial time.

desk verdict A solid, well-executed game-theoretic analysis of strategic payment priorities in Eisenberg-Noe networks; the coin-ranking vs. edge-ranking dichotomy is genuine and the paper deserves peer review, though the maximal-clearing-state tie-break is a load-bearing modeling choice that should be flagged. read the letter →

arxiv 1908.01714 v3 pith:ZL2DKVGX submitted 2019-08-05 cs.GT q-fin.GNq-fin.RM

Nils Bertschinger , Martin Hoefer , Daniel Schmand This is my paper · ORCID
classification cs.GTq-fin.GNq-fin.RM MSC 91A4391A68
keywords financialnetworksclearingmechanismsstrongequilibriumpureNashpriceofanarchystabilitystrategicflowgamesmaximumcirculation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper analyzes a strategic version of the classical clearing model for financial networks, in which each firm chooses how to allocate the money it receives to its own debts. It claims that when firms are allowed to rank individual units of money, every network has a strong equilibrium—a payment profile that no coalition of firms can profitably overturn—and that this equilibrium simultaneously maximizes the total revenue available to all firms. This matters because it gives a centralized bankruptcy settlement rule that is socially optimal and coalition-proof, computable in strongly polynomial time. The paper contrasts this with the more intuitive case where firms rank whole debt contracts: there, equilibria can fail to exist, and deciding whether one exists is strongly NP-hard.

What carries the argument

The argument is carried by a circulation reformulation. Add an auxiliary source connected to each firm by an edge of capacity equal to that firm's external assets, and connect each firm back to the source by an unbounded edge; every clearing state then corresponds to a circulation in which all source edges are saturated. The revenue-maximizing circulation $f^*$ is computed in strongly polynomial time, and each firm is assigned a threshold-ranking strategy that pays exactly $f^*_e$ to each outgoing edge $e$ before paying the remainder of any debt. The proof that no coalition can profitably deviate chases a cycle: a strictly improving deviation would create a cycle of increased flow, contradicting optimality of $f^*$. A lattice theorem for clearing states justifies reading utilities from the coordinate-wise maximal clearing state for every strategy profile, and that state is computable in strongly polynomial time.

What would settle it

Exhaustively search all small coin-ranking games, say up to six firms with unit debts and external assets, and for each compute the maximum circulation $f^*$, assign threshold strategies with thresholds equal to $f^*_e$, and check by coalition-deviation search whether any coalition strictly improves; because the paper claims none can, a single violation would refute Theorem 6.

Watch

Extended reading notes

Core claim

The central discovery is that the strategic payment game has two sharply different regimes depending on how priorities are expressed. In a coin-ranking game, where each firm's strategy distributes single units of money monotonically to its debts, the revenue-maximizing circulation in the auxiliary network is itself the clearing outcome of a strong equilibrium: no coalition can strictly improve all of its members, even if deviating firms may use arbitrary continuous strategies and any clearing state may be chosen for the deviation (Theorem 6 with Remark 7). Moreover, this strong equilibrium maximizes total revenue and can be computed in strongly polynomial time. In an edge-ranking game, where priorities are over whole debt contracts rather than coins, pure Nash and strong equilibria need not exist, and deciding existence, computing equilibria, and computing socially optimal profiles are all strongly NP-hard (Theorems 13 and 14).

Load-bearing premise

The load-bearing premise is that utilities are read from the revenue-maximizing, coordinate-wise largest clearing state for each strategy profile; if a clearing system resolved ties toward a smaller fixed point, existence of an optimal strong equilibrium could change.

Editorial extensions

If this is right

  • A regulator who can assign unit-level payment priorities can implement a clearing profile that maximizes total assets and is stable against coalitional deviations, using a strongly polynomial algorithm.
  • In coin-ranking games the strong price of anarchy is bounded by the minimum, over all optimal circulations and cycle decompositions, of the largest cycle length; optimal networks built from short payment cycles have nearly optimal strong equilibria.
  • The pure Nash price of anarchy in coin-ranking games is unbounded even without external assets, so stability against unilateral deviations alone gives no revenue guarantee.
  • Edge-ranking games can have no pure Nash or strong equilibrium; deciding existence and computing equilibria or optimal revenue are strongly NP-hard.
  • The best strong equilibrium in an edge-ranking game can be a factor $\Omega(n)$ worse than the social optimum, and the price of stability can be unbounded.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If a clearing mechanism resolved multiple fixed points by the coordinate-wise minimal state instead of the maximal one, the Theorem 6 construction would not obviously survive; the existence of an optimal strong equilibrium is sensitive to this tie-breaking choice.
  • A regulatory reading the paper does not test is that settlement protocols should be written as unit-level priority rules, equivalently threshold payments, since the dichotomy suggests this small implementation detail decides whether optimal coalition-proof clearing is possible.
  • The unbounded Nash price of anarchy combined with the bounded strong price of anarchy indicates that decentralized clearing performance depends on coordinated payment cycles rather than individual optimization; whether real interbank networks exhibit such cycles is an empirical question.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper analyzes a game-theoretic variant of the Eisenberg-Noe clearing model. Each firm is a node in a directed liability network and chooses a payment strategy—either an edge-ranking or a coin-ranking strategy—that specifies how its available assets are allocated to outgoing obligations. For a fixed strategy profile, clearing states are asset vectors satisfying a fixed-point equation; the paper defines utility through the coordinate-wise maximal such state, which maximizes total assets. The authors prove structural results (clearing states form a lattice for monotone strategies, and the maximal state is computable in strongly polynomial time) and then give an extensive equilibrium analysis. In coin-ranking games, there always exists a strong equilibrium whose flows maximize total revenue and it is computable in polynomial time (Theorem 6), although best responses are strongly NP-hard to compute (Theorem 9). The strong price of anarchy is bounded by the min-max cycle length of an optimal circulation (Theorem 11) with a matching lower bound (Proposition 12), while the Nash price of anarchy is unbounded (Proposition 10). Edge-ranking games behave much worse: pure Nash and strong equilibria can be absent, and deciding existence, computing equilibria, and computing a social optimum are strongly NP-hard (Theorem 14); moreover, the strong price of stability can be linear in n and the Nash price of stability unbounded (Propositions 16 and 17).

Significance. If the results hold, the paper provides a crisp algorithmic dichotomy with a striking positive conclusion: when firms may rank individual units of money, a centralized clearing authority can compute, in strongly polynomial time, a strong equilibrium that also maximizes total revenue. This stands against the edge-ranking case, where equilibria may not exist and all natural decision problems are intractable. The paper's strengths include explicit constructions in hardness reductions, a lattice-based fixed-point analysis, and tight bounds on the strong price of anarchy. There are no fitted parameters or calibrated quantities; all statements are derived from the model definitions. The two main caveats are the choice of the maximal clearing state as the payoff-relevant outcome, which is load-bearing for Theorem 6, and a gap in the proof of the strong price of anarchy bound in Theorem 11.

major comments (2)
  1. [Section 1.3 (Clearing States and Utilities) and Theorem 6] The central positive result is stated for utilities defined by the coordinate-wise maximal clearing state, and this tie-breaking rule is load-bearing. Theorem 6 constructs a threshold strategy profile from an optimal circulation f* and proves that no coalition can improve relative to the maximal clearing state of that profile. If a clearing mechanism resolved the fixed-point multiplicity differently, for example by selecting the coordinate-wise minimal state, the same profile need not realize the revenue-maximizing flows, and the paper supplies no argument that any other profile is an optimal-revenue strong equilibrium under such a rule. Since Theorem 3 shows that multiple clearing states are not a degenerate exception, the normative conclusion in the abstract and introduction—that centralized bankruptcy settlement can achieve a socially optimal strong equilibrium—is contingent on an optimistic, non-obvious selection rule. The paper should either justify the maximal-state rule as the right model of a clearing mechanism or explicitly qualify the policy conclusion as depending on that rule.
  2. [Section 3.3, proof of Theorem 11] The proof of the strong price of anarchy bound needs clarification. The cycles Ci in the decomposition of f* are cycles of the auxiliary circulation network G′, as indicated by the revenue identity Rev(f*) = Sum_i |Ci| − Sum_v ax_v. For a cycle that contains the auxiliary source s, the firms on that cycle cannot rank the auxiliary edges (s,v) and (v,s), so the proposed joint deviation cannot be implemented in the way described. Moreover, the first firm on such a cycle already receives its external assets through a saturated edge (s,v); rerouting those assets along the cycle is a reallocation rather than an addition of new flow, and that firm may lose returns from its previous allocation, so it is not clear that every firm in the coalition strictly gains. If the intended decomposition contains only cycles of the original network, then the revenue identity is incorrect when external assets are present. The proof should state the intended restriction on the cycles and provide a separate argument for cycles that pass through the auxiliary source.
minor comments (5)
  1. [Title and metadata] The manuscript's own title is 'Strategic Payments in Financial Networks,' whereas the arXiv metadata lists 'Flow Allocation Games'; please align the metadata with the manuscript title.
  2. [Section 1.3, Proposition 1] Proposition 1 is stated without proof and justified only by a citation to Brouwer's fixed-point theorem; since the paper later develops its own lattice-based fixed-point analysis, a short proof or a more explicit reference would make the section self-contained.
  3. [Section 4.2, Proposition 16] The proof of Proposition 16 is hard to follow and appears to refer to a construction different from the one in Proposition 12; in particular, the statement that 'the only node with more than a single outgoing edge is still v1' is not consistent with the Proposition 12 construction, in which nodes v2,...,vd have multiple outgoing edges. Please rewrite the construction so that the claimed lower bound can be verified.
  4. [Appendix A.1, proof of Theorem 9] In the sentence 'Observe that firms c1,...,cm and x1,...,xn each have a single outgoing edge,' the symbols x1,...,xn appear to be a typo for z1,...,zn; please correct this and make the naming of variable-gadget firms consistent throughout the proof.
  5. [Section 3.2, proof of Theorem 6] The phrase 'saturates all outgoing auxiliary edges from s' should more precisely read 'saturates all auxiliary edges (s,v)' so as not to conflict with the auxiliary edges (v,s) that carry surplus flow back to the source.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorem 6 is a genuine equilibrium-existence proof from explicit model definitions, and no claim reduces to a fitted input, self-citation chain, or definitional equivalence.

full rationale

The paper's central claims are proven rather than assumed. In particular, Theorem 6 constructs a strong equilibrium from an optimal circulation f* in the auxiliary circulation network G' and verifies the no-profitable-deviation property directly; the proof does not define the equilibrium to be the optimum, but instead shows that any coalitional improvement would create an augmenting cycle contradicting optimality of f*. The utility notion is fixed in Section 1.3 by choosing the coordinate-wise maximal clearing state, but this is a stated modeling assumption about clearing, not an input that is renamed as the conclusion. The lattice structure of clearing states (Theorem 3) is derived from the Knaster-Tarski fixed-point theorem applied to monotone strategy functions, which is independent evidence rather than a self-citation. The hardness results for edge-ranking games are proven by reductions from 3-Dimensional Matching and Satisfiability, with game constructions given in the appendix, so they do not rest on circular reasoning. The paper does cite prior work, including Eisenberg and Noe, Tardos, and Shapley and Scarf, but these citations supply standard algorithmic or fixed-point tools and are not used as substitutes for the paper's own arguments. No parameter fitting, calibrated quantity called a prediction, or author-imported uniqueness theorem appears anywhere in the derivation chain. The only potentially value-laden choice is the maximal-clearing-state tie-break, but changing that rule would change the model rather than expose a circular derivation; the paper's theorems are conditional on its explicitly stated clearing convention. Overall, the derivation is self-contained and internally sound under the stated assumptions, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The claims rest on standard fixed-point and algorithmic theorems, plus explicit modeling assumptions about integrality and tie-breaking. No free parameters are fitted, and no new physical entities are postulated.

assumptions (5)
  • standard math Brouwer's fixed point theorem
    Used to show existence of a clearing state for continuous strategies in Proposition 1 (Section 1.3).
  • standard math Knaster-Tarski fixed point theorem
    Used to prove the lattice structure of clearing states (Theorem 3, Section 2.2).
  • standard math Tardos' strongly polynomial minimum-cost circulation algorithm
    Used to compute the optimal circulation in Theorem 6 (Section 3.2).
  • domain assumption All input values (external assets ax_v and liabilities c(e)) are integers
    Required for the coin-ranking model that treats money as discrete coins (Section 1.3).
  • domain assumption Utilities are determined by the revenue-maximizing (coordinate-wise maximal) clearing state
    The game fixes the clearing state to the maximum-revenue fixed point; all equilibrium results are relative to this tie-breaking rule (Section 1.3, 'Clearing States and Utilities').

how reviews work

0 comments
Cite this review

Pith. "Pith review of Flow Allocation Games." pith.science (2026). https://pith.science/paper/ZL2DKVGX

@misc{pith2026190801714,
  author       = {Pith},
  title        = {Pith review of: Flow Allocation Games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZL2DKVGX}},
  note         = {Machine review of arXiv:1908.01714}
}
read the original abstract

We study a game-theoretic variant of the maximum circulation problem. In a flow allocation game, we are given a directed flow network. Each node is a rational agent and can strategically allocate any incoming flow to the outgoing edges. Given the strategy choices of all agents, a maximal circulation that adheres to the chosen allocation strategies evolves in the network. Each agent wants to maximize the amount of flow through her node. Flow allocation games can be used to express strategic incentives of clearing in financial networks. We provide a cumulative set of results on the existence and computational complexity of pure Nash and strong equilibria, as well as tight bounds on the (strong) prices of anarchy and stability. Our results show an interesting dichotomy: Ranking strategies over individual flow units allow to obtain optimal strong equilibria for many objective functions. In contrast, more intuitive ranking strategies over edges can give rise to unfavorable incentive properties.

Figures

Figures reproduced from arXiv: 1908.01714 by the authors.

Figure 1
Figure 1. A coin-ranking game with d = 5 and a strong price of anarchy of d − 1 = 4. Proposition 12. For every d ≥ 2, there is coin-ranking game with strong price of anarchy of d − 1. Proof. The game is given by a graph G with d+ (d−1)(d−2) firms. G is constructed as follows. The firms v1, . . . , vd are called central firms and they form a cycle of length d. For each i = 1, . . . , d − 1, there are firms (vi,j )j=1,...,d−2 t… view at source ↗
Figure 2
Figure 2. An edge-ranking game without a pure Nash equilibri [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Edge-Ranking Game with unbounded Price of Stabili [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Structures used in the proof of Theorem 9. [PITH_FULL_IMAGE:figures/full_fig_p017_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Cycles Protocol: A Peer-to-Peer Electronic Clearing System

    cs.CE 2025-07 conditional novelty 5.0 of 10

    Cycles is a permissionless clearing protocol that uses graph optimization over obligation networks to discharge multilateral debt atomically with minimal liquidity, combining MTCS with a TEE-and-zero-knowledge privacy...

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages · cited by 1 Pith paper

  1. [1]

    Systemic risk in endogenous financial networks

    Daron Acemoglu, Asuman Ozdaglar, and Alireza Tahbaz-Sa lehi. Systemic risk in endogenous financial networks. Available at SSRN: https://ssrn.com/a bstract=2553900, January 22 2015. Columbia Business School Research Paper No. 15-17

    work page 2015

  2. [2]

    Strategic default in fina ncial network

    Nizar Allouch and Maya Jalloul. Strategic default in fina ncial network. Technical report, School of Economics, University of Kent, 2017. Studies in Economic s 1721

    work page 2017

  3. [3]

    Computational complexity and information asymmetry in financial products

    Sanjeev Arora, Boaz Barak, Markus Brunnermeier, and Ron g Ge. Computational complexity and information asymmetry in financial products. Comm. ACM , 54(5):101–107, 2011

    work page 2011

  4. [4]

    Power in threshol d network flow games

    Yoram Bachrach and Jeffrey Rosenschein. Power in threshol d network flow games. Auton. Agents and Multi-Agent Syst. , 18(1):106–132, 2009

    work page 2009

  5. [5]

    Network valuation in finan cial systems, 2016

    Paolo Barucca, Marco Bardoscia, Fabio Caccioli, Marco D ’Errico, Gabriele Visentin, Stefano Battiston, and Guido Caldarelli. Network valuation in finan cial systems, 2016

    work page 2016

  6. [6]

    The computational h ardness of pricing compound op- tions

    Mark Braverman and Kanika Pasricha. The computational h ardness of pricing compound op- tions. In Proc. 5th Symp. Innov. Theoret. Comput. Sci. (ITCS) , pages 103–104, 2014

    work page 2014

  7. [7]

    Liquidity risk and contagion

    Rodrigo Cifuentes, Gianluigi Ferrucci, and Hyun Song Sh in. Liquidity risk and contagion. Bank of England, Working Paper No. 264, 2005

    work page 2005

  8. [8]

    Indirect contagion and sy stemic stress testing

    Rama Cont and Eric Schaanning. Indirect contagion and sy stemic stress testing. Available at SSRN: https://ssrn.com/abstract=2541114, June 13 2017. 14

    work page 2017

Show all 31 references
  1. [9]

    Stab le flows over time

    Agnes Cseh, Jannik Matuschke, and Martin Skutella. Stab le flows over time. Algorithms, 6(3):532–545, 2013

    2013

  2. [10]

    Algorithmic aspects of the core of combinatorial optimization games

    Xiaotie Deng, Toshihide Ibaraki, and Hiroshi Nagamoch i. Algorithmic aspects of the core of combinatorial optimization games. Math. Oper. Res. , 24(3):751–766, 1999

    1999

  3. [11]

    Totally balanced game s arising from controlled programming problems

    Pradeep Dubey and Lloyd Shapley. Totally balanced game s arising from controlled programming problems. Math. Prog., 29(3):245–267, 1984

    1984

  4. [12]

    Systemic risk in financi al systems

    Larry Eisenberg and Thomas Noe. Systemic risk in financi al systems. Manag. Sci. , 47(2):236– 249, 2001

    2001

  5. [13]

    Intermediation and voluntary exposu re to counterparty risk

    Maryam Farboodi. Intermediation and voluntary exposu re to counterparty risk. Available at SSRN: https://ssrn.com/abstract=2535900, August 1 2014

    2014

  6. [14]

    No-arbitrage pricing under systemic risk : Accounting for cross-ownership

    Tom Fischer. No-arbitrage pricing under systemic risk : Accounting for cross-ownership. Math. Finance, 24(1):97–124, 2014

    2014

  7. [15]

    On stable matchings and flows

    Tam´ as Fleiner. On stable matchings and flows. Algorithms, 7(1):1–14, 2014

    2014

  8. [16]

    Contagion in financial n etworks

    Prasanna Gai and Sujit Kapadia. Contagion in financial n etworks. Proc. Royal Soc. London A: Math. Phys. Eng. Sci. , 466(2120):2401–2423, 2010

    2010

  9. [17]

    On some network flow gam es

    Daniel Granot and Frieda Granot. On some network flow gam es. Math. Oper. Res. , 17(4):792– 841, 1992

    1992

  10. [18]

    Multi-p layer flow games

    Shibashis Guha, Orna Kupferman, and Gal Vardi. Multi-p layer flow games. In Proc. 17th Conf. Auton. Agents and Multi-Agent Syst. (AAMAS) , pages 104–112, 2018

    2018

  11. [19]

    Sensitivity and com putational complexity in financial networks

    Brett Hemenway and Sanjeev Khanna. Sensitivity and com putational complexity in financial networks. Algorithmic Finance, 5(3-4):95–110, 2016

    2016

  12. [20]

    Generalized network proble ms yielding totally balanced games

    Ehud Kalai and Eitan Zemel. Generalized network proble ms yielding totally balanced games. Oper. Res., 30(5):998–1008, 1982

    1982

  13. [21]

    Totally balanced games and g ames of flow

    Ehud Kalai and Eitan Zemel. Totally balanced games and g ames of flow. Math. Oper. Res. , 7(3):476–478, 1982

    1982

  14. [22]

    Reducibility among combinatorial probl ems

    Richard Karp. Reducibility among combinatorial probl ems. In R.E. Miller and J.W. Thatcher, editors, Complexity of Computer Computations . Plenum Press, New York, 1972

    1972

  15. [23]

    Flow games

    Orna Kupferman, Gal Vardi, and Moshe Vardi. Flow games. In Proc. 37th Conf. Found. Software Tech. Theor. Comput. Sci. (FSTTCS) , pages 38:38–38:16, 2017

    2017

  16. [24]

    On the core of the mu lticommodity flow game

    Evangelos Markakis and Amin Saberi. On the core of the mu lticommodity flow game. Decis. Support Syst. , 39(1):3–10, 2005

    2005

  17. [25]

    Algorithms, games and the int ernet

    Christos Papadimitriou. Algorithms, games and the int ernet. In Proc. 33rd Symp. Theory Comput. (STOC) , pages 749–753, 2001

    2001

  18. [26]

    L. C. G. Rogers and L. A. M. Veraart. Failure and rescue in an interbank network. Manag. Sci. , 59(4):882–898, 2013

    2013

  19. [27]

    Finding clearing payments in financial networks with credit default swaps is PPAD-comple te

    Steffen Schuldenzucker, Sven Seuken, and Stefano Battis ton. Finding clearing payments in financial networks with credit default swaps is PPAD-comple te. In Proc. 8th Symp. Innov. Theoret. Comput. Sci. (ITCS) , pages 32:1–32:20, 2017. 15

    2017

  20. [28]

    On cores and indivisib ility

    Lloyd Shapley and Herbert Scarf. On cores and indivisib ility. J. Math. Econ. , 1(1):23–37, 1974

    1974

  21. [29]

    Valuing corporate debt: The effect of c ross-holdings of stock and debt

    Teruyoshi Suzuki. Valuing corporate debt: The effect of c ross-holdings of stock and debt. J. Oper. Res. Soc. Japan , 2, 2002

    2002

  22. [30]

    A strongly polynomial minimum cost circulation algorithm

    ´Eva Tardos. A strongly polynomial minimum cost circulation algorithm. Combinatorica, 5(3):247–256, 1985. 16 A Missing Proofs A.1 Proof of Theorem 9 v xi,1,0 zi,0 zi,1xi,1,1 xi,2,0 xi,2,1 xi,3,0 xi,3,1 xi,4,0 xi,4,1 zi (a) Variable Gadget v c1 c2 c3 c4 x1,1,1 x2,1,1 x3,1,0 x1,...

    1985

  23. [31]

    for i = 1, . . . ,|T |. If there is a solution to I, all vertices ti ∈ T receive a flow of 1. This flow is forwarded to vertices vi 9 and can be seen as their external asset. Hence, there is a stro ng equilibrium in all copies and also in the game as a whole. On th e other hand,...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.