pith. sign in

arxiv: 2303.08507 · v3 · submitted 2023-03-15 · 💻 cs.DM · cs.GT

Nonatomic Non-Cooperative Neighbourhood Balancing Games

David Auger , Johanne Cohen , Antoine Lobstein This is my paper

Pith reviewed 2026-05-24 09:50 UTC · model grok-4.3

classification 💻 cs.DM cs.GT
keywords neighbourhood gamesbalancing gamesnonatomic gamescongestion gamesWardrop gamesNash equilibriumprice of anarchygraph games
0
0 comments X

The pith

A weighted graph models influences among resources in a new class of games that generalizes Wardrop and congestion games.

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

The authors define nonatomic non-cooperative neighbourhood balancing games where each player selects a resource and pays a cost that increases with the load on nearby resources. These influences are represented by a weighted graph, allowing directed or undirected connections. This setup extends standard models of selfish resource allocation. The work identifies conditions under which Nash equilibria exist and evaluates how efficient those equilibria are compared to the social optimum. Special attention is given to cases where the graph is unweighted and simple.

Core claim

By representing resource interactions through a weighted graph, neighbourhood balancing games capture a broad family of cost structures that include classic congestion and Wardrop games as special cases. Equilibria exist when the graph meets suitable structural requirements, and their inefficiency can be quantified using standard measures from algorithmic game theory.

What carries the argument

The weighted directed or undirected graph that encodes how the load on one resource affects the cost of another.

If this is right

  • Equilibria existence depends on properties of the influence graph.
  • Efficiency bounds can be derived analogous to those in congestion games.
  • Simple graphs yield more concrete existence and efficiency results.
  • These games apply to distributed resource allocation problems with local dependencies.

Where Pith is reading between the lines

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

  • Such models might help design better distributed systems by accounting for spillover effects between choices.
  • Extending the analysis to dynamic or time-varying graphs could reveal stability properties over time.
  • Connections to potential games may allow computation of equilibria in polynomial time for certain graph classes.

Load-bearing premise

The effects between different resources are fully captured by fixed weights on a graph without higher-order interactions.

What would settle it

A concrete counterexample where no weighted graph reproduces the observed cost dependencies between resources, or an instance where the predicted equilibria fail to form.

Figures

Figures reproduced from arXiv: 2303.08507 by Antoine Lobstein, David Auger, Johanne Cohen.

Figure 1
Figure 1. Figure 1: Costs functions for the example in Subsection 2.1. [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: We consider a game with 2 vertices. The curves represent the costs of the two vertices as a function of the mass on vertex 1. There are three equilibria in this case: x1 = 0, x1 = γ (second intersection of the costs curves) and x1 = r. Equilibria x1 = 0 and x1 = r are strong; however x1 = γ is not strong since a small quantity ǫ of mass can always move from 2 to 1 and improve its cost. 0 r x1 cost C1 C2 [… view at source ↗
Figure 3
Figure 3. Figure 3: We consider a game with 2 vertices. The curves represent the costs of the two vertices as a function of the mass on vertex 1. There is only one equilibrium in x1 = 0, which is not strong [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: With n = 2 and r = 1 (so that x2 = 1 − x1), consider α1,2 = α2,1 = 1, f1(x1) = 1 and f2(x2) = 1 + x2. This gives C1(x) = 2 − x1, C2(x) = 2, and Φ(x) = x1 + (x2 + 1 2 x 2 2 ) + x1x2 = (3 − x 2 1 )/2 (this potential function is given by Equation (3) in the upcoming Proposition 3.6; we can check that this is indeed a potential. Otherwise, other potentials are equal to this one up to an additive constant; also… view at source ↗
Figure 5
Figure 5. Figure 5: The costs and equilibria for three different value [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: A family of graphical games reaching the maximum pr [PITH_FULL_IMAGE:figures/full_fig_p020_6.png] view at source ↗
read the original abstract

We introduce a game where players selfishly choose a resource and endure a cost depending on the number of players choosing nearby resources. We model the influences among resources by a weighted graph, directed or not. These games are generalizations of well-known games like Wardrop and congestion games. We study the conditions of equilibria existence and their efficiency if they exist. We conclude with studies of games whose influences among resources can be modelled by simple graphs.

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

2 major / 2 minor

Summary. The paper introduces nonatomic non-cooperative neighbourhood balancing games in which selfish players select a resource and incur a cost that depends on the number of players choosing nearby resources. Influences among resources are modeled by a weighted graph (directed or undirected). The model is positioned as a generalization of Wardrop and congestion games. The authors claim to study conditions for the existence of equilibria and to analyze their efficiency (when equilibria exist), with a concluding section on the special case of simple graphs.

Significance. If the existence and efficiency claims can be established with explicit conditions and proofs, the framework would provide a clean graph-based extension of classic non-atomic routing games that incorporates local neighborhood effects. This could be useful for modeling systems with spatial or network-structured interactions. The modeling choice of weighted directed graphs is standard and non-controversial.

major comments (2)
  1. [Abstract] Abstract: the central claims are that the authors 'study the conditions of equilibria existence and their efficiency if they exist,' yet the provided text contains neither the conditions, any theorem statements, proof sketches, nor numerical evidence. These results are load-bearing for the paper's contribution and cannot be assessed from the manuscript as given.
  2. The manuscript asserts that the games generalize Wardrop and congestion games, but does not identify which structural properties (e.g., potential functions, convexity assumptions, or monotonicity conditions on the cost functions) are preserved or lost under the neighborhood-graph extension. Without this, it is unclear whether standard existence arguments carry over.
minor comments (2)
  1. The abstract and title use inconsistent spelling ('neighbourhood' vs. 'neighborhood').
  2. The concluding studies on simple graphs are mentioned but not described; a brief statement of what is shown in that special case would help readers.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the review and the opportunity to clarify the manuscript's contributions. We respond to each major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claims are that the authors 'study the conditions of equilibria existence and their efficiency if they exist,' yet the provided text contains neither the conditions, any theorem statements, proof sketches, nor numerical evidence. These results are load-bearing for the paper's contribution and cannot be assessed from the manuscript as given.

    Authors: We agree that the current manuscript does not contain explicit conditions for equilibrium existence, theorem statements, proof sketches, or numerical evidence, despite the abstract's claim. This is a substantive gap. We will revise the manuscript to add a section with formal conditions (e.g., on cost function monotonicity and graph weights), theorem statements, and proof outlines for existence and efficiency analysis. revision: yes

  2. Referee: [—] The manuscript asserts that the games generalize Wardrop and congestion games, but does not identify which structural properties (e.g., potential functions, convexity assumptions, or monotonicity conditions on the cost functions) are preserved or lost under the neighborhood-graph extension. Without this, it is unclear whether standard existence arguments carry over.

    Authors: The manuscript claims a generalization via the weighted neighborhood graph but does not analyze preserved or lost properties such as potential functions or convexity. We concur that this clarification is required to evaluate carry-over of standard arguments. In revision we will insert a discussion specifying, for example, that monotonicity of costs is preserved under non-negative weights while potential functions generally are not in directed graphs. revision: yes

Circularity Check

0 steps flagged

No significant circularity; new model and equilibrium results derived independently

full rationale

The paper defines a new class of nonatomic games via weighted (directed or undirected) graphs modeling resource influences, explicitly positioned as a generalization of Wardrop and congestion games. Equilibrium existence and efficiency bounds are stated as theorems proved from the model axioms and standard game-theoretic arguments; no parameter is fitted to data and then relabeled as a prediction, no self-citation supplies a load-bearing uniqueness theorem, and no ansatz is smuggled in. The final section on simple graphs is presented merely as a special case, not as a foundational reduction. The derivation chain therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only abstract available; no free parameters, axioms, or invented entities identifiable.

pith-pipeline@v0.9.0 · 5585 in / 807 out tokens · 33792 ms · 2026-05-24T09:50:34.223269+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

38 extracted references · 38 canonical work pages

  1. [1]

    Game theory and learning for wirel ess networks: fundamentals and applications

    Lasaulce S, Tembine H. Game theory and learning for wirel ess networks: fundamentals and applications. Academic Press, 2011. doi:10.1016/C2009-0-62852-X

    work page doi:10.1016/c2009-0-62852-x 2011

  2. [2]

    RA T sele ction games in HetNets

    Aryafar E, Keshavarz-Haddad A, Wang M, Chiang M. RA T sele ction games in HetNets. In: INFOCOM, 2013 Proceedings IEEE. IEEE, 2013 pp. 998–1006. doi:10.110 9/INFCOM.2013.6566889

    work page arXiv 2013

  3. [3]

    Road paper

    Wardrop JG. Road paper. some theoretical aspects of road traffic research. Proceedings of the institution of civil engineers , 1952. 1(3):325–362. doi:10.1680/ipeds.1952.11259

    work page doi:10.1680/ipeds.1952.11259 1952

  4. [4]

    A class of games possessing pure-strategy Nash equilibria

    Rosenthal RW . A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 1973. 2:65–67. doi:10.1007/BF01737559

    work page doi:10.1007/bf01737559 1973

  5. [5]

    Wardrop equilibria

    Correa JR, Stier-Moses NE. Wardrop equilibria. Encyclopedia of Operations Research and Management Science. Wiley, 2011. doi:10.1002/9780470400531.eorms0962

    work page doi:10.1002/9780470400531.eorms0962 2011

  6. [6]

    Studies in the Econom ics of Transportation

    Beckmann M, McGuire CB, Winsten CB. Studies in the Econom ics of Transportation. The Economic Journal, 1957. 67(265)

    work page 1957

  7. [7]

    Worst-case equilibria

    Koutsoupias E, Papadimitriou C. Worst-case equilibria . In: Annual Symposium on Theoretical Aspects of Computer Science. Springer, 1999 pp. 404–413. doi:10.10 07/3-540-49116-3 38

    work page 1999

  8. [8]

    How bad is selfish routing? Journal of the ACM (JACM), 2002

    Roughgarden T, Tardos ´E. How bad is selfish routing? Journal of the ACM (JACM), 2002. 49(2):236–259. doi:10.1145/506147.506153

    work page doi:10.1145/506147.506153 2002

  9. [9]

    The price of anarchy is independent of the network topology

    Roughgarden T. The price of anarchy is independent of the network topology. In: Proceedings of the thiry- fourth annual ACM symposium on Theory of computing. 2002 pp. 428–437. doi:10.1145/509907.509971. D. Auger et al. / Neighbourhood Balancing Games 267

    work page doi:10.1145/509907.509971 2002

  10. [10]

    On the pri ce of anarchy of highly congested nonatomic network games

    Colini-Baldeschi R, Cominetti R, Scarsini M. On the pri ce of anarchy of highly congested nonatomic network games. In: Algorithmic Game Theory: 9th Internatio nal Symposium, SAGT 2016, Liverpool, UK, September 19–21, 2016, Proceedings 9. Springer, 2016 pp . 117–128. doi:10.1007/978-3-662-53354- 3 10

    work page doi:10.1007/978-3-662-53354- 2016

  11. [11]

    When is selfish routing bad? The price of anarchy in light and heavy traffic

    Colini-Baldeschi R, Cominetti R, Mertikopoulos P , Sca rsini M. When is selfish routing bad? The price of anarchy in light and heavy traffic. Operations Research , 2020. 68(2):411–434. doi:10.1287/ opre.2019.1894

    work page arXiv 2020

  12. [12]

    Selfishness need not be bad

    Wu Z, M¨ ohring RH, Chen Y , Xu D. Selfishness need not be bad . Operations Research, 2021. 69(2):410–

    work page 2021

  13. [13]

    doi:10.1287/opre.2020.2036

    work page doi:10.1287/opre.2020.2036 2020

  14. [14]

    Algorith mic game theory, volume 1

    Nisan N, Roughgarden T, Tardos E, V azirani VV . Algorith mic game theory, volume 1. Cambridge Uni- versity Press Cambridge, 2007. ISBN-10:0521872820, 13:97 8-0521872829

    work page 2007

  15. [15]

    Tight bounds for worst-case equil ibria

    Czumaj A, V¨ ocking B. Tight bounds for worst-case equil ibria. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 2002 pp. 413–42 0. ISBN:0-89871-513-X,

    work page 2002

  16. [16]

    Coordinat ion Mechanisms

    Christodoulou G, Koutsoupias E, Nanavati A. Coordinat ion Mechanisms. In: Proceedings of the 31st International Colloquium on Automata, Languages and P rogramming (ICALP). 2004 pp. 345–357. doi:10.1007/978-3-540-27836-8 31

    work page doi:10.1007/978-3-540-27836-8 2004

  17. [17]

    An introduction to population protocols

    D¨ urr C, Thang NK. Non-clairvoyant scheduling games. I n: International Symposium on Algorithmic Game Theory. Springer, 2009 pp. 135–146. doi:10.1007/978- 3-642-04645-2 13

    work page doi:10.1007/978- 2009

  18. [18]

    Coordination M echanisms for Selfish Scheduling

    Immorlica N, Li L, Mirrokni VS, Schulz A. Coordination M echanisms for Selfish Scheduling. In: Pro- ceedings of the 1st International Workshop on Internet and N etwork Economics (WINE). 2005 pp. 55–69. doi:10.1007/11600930 7

    work page doi:10.1007/11600930 2005

  19. [19]

    N P-hardness of pure Nash equilibrium in Scheduling and Connection Games

    Thang NK. N P-hardness of pure Nash equilibrium in Scheduling and Connection Games. In: Proceedings of the 35th International Conference on Current Trends in Th eory and Practice of Computer Science (SOFSEM). 2009 pp. 413–424. doi:10.1007/978-3-540-95891 -8 38

    work page doi:10.1007/978-3-540-95891 2009

  20. [20]

    Optimal coordination mecha nisms for multi-job scheduling games

    Abed F, Correa JR, Huang CC. Optimal coordination mecha nisms for multi-job scheduling games. In: European Symposium on Algorithms. Springer, 2014 pp. 13–24 . doi:10.1007/978-3-662-44777-2 2

    work page doi:10.1007/978-3-662-44777-2 2014

  21. [21]

    Tradeoffs in worst-case equilibria

    A werbuch B, Azar Y , Richter Y , Tsur D. Tradeoffs in worst-case equilibria. Theoretical Computer Science,

    work page

  22. [22]

    doi:10.1016/j.tcs.2006.05.010

    361(2-3):200–209. doi:10.1016/j.tcs.2006.05.010

    work page doi:10.1016/j.tcs.2006.05.010 2006

  23. [23]

    Papadimitriou, and Kunal Talwar

    Gairing M, L¨ ucking T, Mavronicolas M, Monien B. Comput ing Nash equilibria for scheduling on re- stricted parallel links. In: Proceedings of the 36th ACM Sym posium on Theory of Computing (STOC). 2004 pp. 613–622. doi:10.1145/1007352.1007446

    work page doi:10.1145/1007352.1007446 2004

  24. [24]

    Intrinsic robustness of the price of ana rchy

    Roughgarden T. Intrinsic robustness of the price of ana rchy. Journal of the ACM (JACM), 2015. 62(5):32. doi:10.1145/2806883

    work page doi:10.1145/2806883 2015

  25. [25]

    Performance guarantees of local search for multiprocessor scheduling

    Schuurman P , Vredeveld T. Performance guarantees of local search for multiprocessor scheduling. Informs Journal on Computing , 2007. 361(1):52–63. doi:10.1287/ijoc.1050.0152

    work page doi:10.1287/ijoc.1050.0152 2007

  26. [26]

    On the performance of user equilib ria in traffic networks

    Schulz AS, Moses NES. On the performance of user equilib ria in traffic networks. In: SODA, volume 3. 2003 pp. 86–87. doi:10.1145/644108.644121

    work page doi:10.1145/644108.644121 2003

  27. [27]

    Tight bounds for self- ish and greedy load balancing

    Caragiannis I, Flammini M, Kaklamanis C, Kanellopoulo s P , Moscardelli L. Tight bounds for self- ish and greedy load balancing. In: Automata, Languages and P rogramming: 33rd International Collo- quium, ICALP 2006, V enice, Italy, July 10-14, 2006, Proceedings, Part I 33. Springer, 2006 pp. 311–322. doi:10.1007/11786986 28. 268 D. Auger et al. / Neighbou...

    work page doi:10.1007/11786986 2006

  28. [28]

    On the price of anarchy and stability of correlated equilibria of linear congestion games

    Christodoulou G, Koutsoupias E. On the price of anarchy and stability of correlated equilibria of linear congestion games. In: Algorithms–ESA 2005: 13th Annual Eur opean Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings 13. Springer, 2005 pp . 59–70. doi:10.1007/11561071 8

    work page doi:10.1007/11561071 2005

  29. [29]

    Price of stability in polyn omial congestion games

    Christodoulou G, Gairing M. Price of stability in polyn omial congestion games. ACM Transactions on Economics and Computation (TEAC) , 2015. 4(2):1–17. doi:10.1145/2841229

    work page doi:10.1145/2841229 2015

  30. [30]

    Nash equilibria in competitive societies, wit h applications to facility location, traffic routing and auctions

    V etta A. Nash equilibria in competitive societies, wit h applications to facility location, traffic routing and auctions. In: Foundations of Computer Science, 2002. Proce edings. The 43rd Annual IEEE Symposium on. IEEE, 2002 pp. 416–425. doi:10.1109/SFCS.2002.118196 6

    work page doi:10.1109/sfcs.2002.118196 2002

  31. [31]

    Nash equilibria in V oronoi games on graphs

    D¨ urr C, Thang NK. Nash equilibria in V oronoi games on graphs. In: European Symposium on Algorithms. Springer, 2007 pp. 17–28. doi:10.1007/978-3-540-75520-3 4

    work page doi:10.1007/978-3-540-75520-3 2007

  32. [32]

    V oronoi game on graphs and its complexity

    Teramoto S, Demaine ED, Uehara R. V oronoi game on graphs and its complexity. In: 2006 IEEE Sympo- sium on Computational Intelligence and Games. IEEE, 2006 pp . 265–271. doi:10.1109/CIG.2006.311711

    work page doi:10.1109/cig.2006.311711 2006

  33. [33]

    V oronoi game o n graphs

    Bandyapadhyay S, Banik A, Das S, Sarkar H. V oronoi game o n graphs. Theoretical Computer Science ,

    work page

  34. [34]

    doi:10.1016/j.tcs.2014.10.003

    562:270–282. doi:10.1016/j.tcs.2014.10.003

    work page doi:10.1016/j.tcs.2014.10.003 2014

  35. [35]

    Equilibrium points in n-person games

    Nash Jr JF. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 1950. 36(1):48–49. doi:10.1073/pnas.36.1.48

    work page doi:10.1073/pnas.36.1.48 1950

  36. [36]

    On the computational complexity of finding akernel, report CRM300

    Chv´ atal V . On the computational complexity of finding akernel, report CRM300. Universit´e de Montr´eal, Centre de Recherches Math ´ematiques, 1973

    work page 1973

  37. [37]

    Computers and intractability, vo lume 174

    Garey MR, Johnson DS. Computers and intractability, vo lume 174. Freeman San Francisco, 1979. ISBN- 10:0716710455, 13:978-0716710455

    work page 1979

  38. [38]

    ¨Uber ein Paradoxon aus der V erkehrsplanung

    Braess D. ¨Uber ein Paradoxon aus der V erkehrsplanung. Unternehmensforschung, 1968. 12:258–268. doi:10.1007/BF01918335

    work page doi:10.1007/bf01918335 1968