pith. sign in

arxiv: 2606.17216 · v1 · pith:3TVDW2V6new · submitted 2026-06-15 · 💻 cs.MA · cs.GT· cs.RO

Intermittent Strategic Cooperation of Two Selfish Agents on Graphs

Itay Shedlezki , Noa Agmon This is my paper

Pith reviewed 2026-06-27 01:46 UTC · model grok-4.3

classification 💻 cs.MA cs.GTcs.RO
keywords intermittent cooperationpath planningNash equilibriummulti-agent systemsgame theory on graphsstrategic cooperationpure Nash equilibriatwo-agent navigation
0
0 comments X

The pith

Two self-interested agents on graphs always have at least one stable joint strategy for intermittent cooperation.

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

The paper examines how two selfish agents can cooperate at certain points on their paths to shorten travel times while each pursues its own target. It models this as a two-player game and shows that pure Nash equilibria, where neither agent wants to deviate, always exist. These equilibria have a very specific structure that limits when and how cooperation can occur stably. The authors provide a fast algorithm to find all such equilibria and discuss ways to choose among them using bargaining ideas. A sympathetic reader would care because this suggests that strategic cooperation can be reliable even without a central authority.

Core claim

In the Intermittent Strategic Cooperation-Based Two-Agent Path Planning problem, stable cooperation between two agents must follow a highly constrained form. At least one pure Nash equilibrium exists in every instance, and all relevant equilibria can be enumerated in polynomial time.

What carries the argument

The characterization of Pure Nash Equilibrium joint strategies in the IC2PP game, which enforces that stable cooperation occurs only at specific constrained points along the agents' paths.

If this is right

  • Stable intermittent cooperation is possible but must adhere to a highly constrained form.
  • At least one pure Nash equilibrium exists for any graph instance.
  • A polynomial-time algorithm can enumerate all relevant equilibria.
  • Coordination mechanisms based on bargaining can select among multiple equilibria to improve outcomes.

Where Pith is reading between the lines

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

  • If the model holds, real-world multi-agent navigation systems could use these equilibria to predict stable cooperation without enforcement.
  • Extending the approach to more than two agents might reveal whether existence and efficient computation generalize.
  • The constrained form of cooperation suggests that only certain graph structures allow beneficial teaming up.

Load-bearing premise

The interactions can be accurately captured as a finite two-player game where agents choose paths and cooperation points with payoffs as negative travel times.

What would settle it

A specific graph where two agents have targets such that no pure Nash equilibrium joint strategy exists despite the problem setup.

Figures

Figures reproduced from arXiv: 2606.17216 by Itay Shedlezki, Noa Agmon.

Figure 1
Figure 1. Figure 1: Agent a1 reaches node c1 in time for cooperation. While it could depart earlier without cooperating (t = 7 vs. t = 8), cooperation reduces the total path time (18 vs. 19). Formally, when agent ai arrives at node v at time t i v , its waiting time for the other agent a−i , denoted w i v , and its incurred travel delay δ i v , both at node v, depend on the arrival time t −i v of a−i . Specifically w i v (t i… view at source ↗
Figure 2
Figure 2. Figure 2: Structure of a cooperative joint strategy [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Although c1 is the earliest cooperation node reachable by both agents, cooperation there allows agent a1 to deviate and leave agent a2 with an inferior outcome, leading a2 to avoid c1. To ensure that neither agent has an incentive to deviate from its intended path during the joining segment, we explicitly consider two types of potential deviations: 1. Cooperation deviation: If agent a1’s (w.l.o.g.) path in… view at source ↗
Figure 4
Figure 4. Figure 4: Possible deviations in the joining segment. [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The shortest independent path from s2 to c passes through a. However, since this path allows a1 to enforce cooperation and then deviate early, it is not considered non-cooperative. The two non-cooperative paths to c, namely (s1, c) and (s2, b, c), are nevertheless not mutually robust: agent a2, which arrives later at c, would prefer to deviate to its shortest independent path (s2, a, c). 4.2 Cooperation se… view at source ↗
Figure 6
Figure 6. Figure 6: The optimal departure node for a2 along the path x1, x2, x3, x4 is x4, while for a1, it is x3. Along the path x1, x2, x3, the optimal departure node for a2 is x2, and for the path x1, x2, the optimal departure node for a1 is x1. Thus, the only PNE in this scenario is the path containing only x1. example in [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: A PNE exists from c1 to c3, but not when both agents follow SCPc1,c3 , since a1 prefers to deviate at c2. Equilibrium is obtained when both instead follow c1, a, c3. Definition 4 (Stable Cooperation Partial Path). A cooperation partial path πcs,cd between cooperation nodes cs, cd ∈ VC is a stable cooperation partial path if the departure node cd is the optimal departure node for both agents along the path.… view at source ↗
Figure 8
Figure 8. Figure 8: Two non-dominated ECJSs: cooperation at c1 benefits a1, while cooperation at c2 benefits a2; both outperform no cooperation. This coordination problem can be modeled as a correlation game [4], where agreement on a joint strategy is essential to avoid suboptimal outcomes. Coordination can be achieved either through conventions [49, 57] 18 [PITH_FULL_IMAGE:figures/full_fig_p018_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Effects of cooperation factors on average amount of PNEs. [PITH_FULL_IMAGE:figures/full_fig_p021_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Effects of cooperation factors on individual path times. [PITH_FULL_IMAGE:figures/full_fig_p021_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Effects of cooperation factors on social welfare. [PITH_FULL_IMAGE:figures/full_fig_p022_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Social welfare optimization occurs when both agents follow the shortest path from their initial nodes to a [PITH_FULL_IMAGE:figures/full_fig_p033_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Although a1 and a2 can begin cooperation at c2 earlier than at c1, the optimal social welfare is achieved when the cooperation starts at c1. a pruning approach that leverages Lemma 1 to reduce the number of evaluated cooperation nodes while ensuring all possible cooperation paths are considered. Using a shortest path algorithm from s1 and s2, we can determine the shortest path time to each cooperation nod… view at source ↗
Figure 14
Figure 14. Figure 14: Although a1 and a2 can individually reach c2 by t = 6, starting cooperation earlier at c1 allows them to reach c2 by t = 5, improving path efficiency. As a result, c2 can be excluded from the set of potential cooperation starting nodes, as initiating cooperation earlier at c1 yields a more efficient outcome. Algorithm 6 is designed to identify the optimal joint strategy (π ∗ 1 , π∗ 2 ) that minimizes soci… view at source ↗
Figure 15
Figure 15. Figure 15: Effects of cooperation factors on individual path times across all tested scenarios, including those with a single [PITH_FULL_IMAGE:figures/full_fig_p037_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Effects of cooperation factors on social welfare across all tested scenarios, including those with a single PNE. [PITH_FULL_IMAGE:figures/full_fig_p038_16.png] view at source ↗
read the original abstract

We study strategic space- and time-constrained cooperation between two self-interested agents through the Intermittent Strategic Cooperation-Based Two-Agent Path Planning (IC2PP) problem, a shortest-path game on graphs in which agents navigate toward individual targets while optionally cooperating at specific nodes to reduce their own travel times. Although such cooperation can strictly benefit both agents, it is strategically fragile: agents may deviate at any point along their paths. Modeled as a 2-player game, we characterize the structure of Pure Nash Equilibrium (PNE) joint strategies in IC2PP, and show that stable cooperation must follow a highly constrained form. We further prove that at least one PNE exists in every instance of IC2PP, and present a polynomial-time algorithm for enumerating all relevant PNEs. When multiple equilibria arise, we study coordination mechanisms based on bargaining-theoretic selection concepts and empirically compare equilibrium outcomes in terms of individual travel times and social welfare.

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

1 major / 1 minor

Summary. The paper introduces the Intermittent Strategic Cooperation-Based Two-Agent Path Planning (IC2PP) problem as a shortest-path game on graphs in which two self-interested agents navigate to individual targets while optionally cooperating at specific nodes to reduce their travel times. Modeled as a 2-player game, the manuscript characterizes the structure of Pure Nash Equilibrium (PNE) joint strategies, asserts that stable cooperation must follow a highly constrained form, proves that at least one PNE exists in every instance, and presents a polynomial-time algorithm for enumerating all relevant PNEs. It further examines coordination mechanisms based on bargaining-theoretic selection concepts and provides empirical comparisons of equilibrium outcomes with respect to individual travel times and social welfare.

Significance. If the asserted PNE existence proof and polynomial-time enumeration algorithm are correct and the game is finite with well-defined payoffs, the work would supply a theoretical basis for computing stable cooperation in selfish multi-agent path planning on graphs. The constrained form of equilibria and the enumeration procedure could support mechanism design in robotics and transportation domains; the bargaining and empirical components add practical value by addressing equilibrium selection.

major comments (1)
  1. [Abstract] Abstract: the central claims that 'at least one PNE exists in every instance' and that a 'polynomial-time algorithm for enumerating all relevant PNEs' exists are stated without any derivation steps, strategy-space definition, payoff formalization, or algorithm description. No section, equation, or pseudocode is supplied against which to verify finiteness of the game, correctness of the existence argument, or polynomial runtime.
minor comments (1)
  1. [Abstract] Abstract: the term 'relevant PNEs' is used without definition or clarification of the selection criterion.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review. We address the single major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claims that 'at least one PNE exists in every instance' and that a 'polynomial-time algorithm for enumerating all relevant PNEs' exists are stated without any derivation steps, strategy-space definition, payoff formalization, or algorithm description. No section, equation, or pseudocode is supplied against which to verify finiteness of the game, correctness of the existence argument, or polynomial runtime.

    Authors: Abstracts are concise summaries by design and do not include derivations, definitions, or pseudocode; those appear in the main text. The strategy space and payoffs are formalized in the problem formulation section. Finiteness follows from the finite action sets of both agents. The PNE existence result is stated and proved as a theorem in the equilibrium analysis section. The enumeration procedure, including its pseudocode and polynomial runtime bound, is given in the algorithms section. These elements in the body of the manuscript permit verification of the abstract claims. revision: no

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained game-theoretic modeling

full rationale

The abstract models IC2PP as a finite 2-player game with payoffs as negative travel times and claims a proof of PNE existence plus a polynomial enumeration algorithm. No equations, fitted parameters, or self-citations are supplied that reduce any claimed result to its own inputs by construction. The structure of PNEs and existence proof are presented as independent analysis of the defined game, consistent with standard non-cooperative game theory on graphs. No load-bearing step matches any enumerated circularity pattern.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Based on abstract only; full details on modeling assumptions, graph properties, or payoff definitions are unavailable.

axioms (1)
  • domain assumption The interaction is modeled as a finite 2-player game with perfect information where agents choose paths and cooperation points.
    Invoked by the statement 'Modeled as a 2-player game'.
invented entities (1)
  • IC2PP problem no independent evidence
    purpose: Formalize intermittent strategic cooperation as a shortest-path game
    Newly defined in the paper.

pith-pipeline@v0.9.1-grok · 5693 in / 1156 out tokens · 44785 ms · 2026-06-27T01:46:55.492944+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

76 extracted references · 5 canonical work pages

  1. [1]

    The price of stability for network design with fair cost allocation.SIAM Journal on Computing, 38(4), 2008

    Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Éva Tardos, Tom Wexler, and Tim Roughgarden. The price of stability for network design with fair cost allocation.SIAM Journal on Computing, 38(4), 2008

    2008

  2. [2]

    Multiple mobile robot task and motion planning: A survey .ACM Computing Surveys, 55(10):1–35, 2023

    Luke Antonyshyn, Jefferson Silveira, Sidney Givigi, and Joshua Marshall. Multiple mobile robot task and motion planning: A survey .ACM Computing Surveys, 55(10):1–35, 2023

    2023

  3. [3]

    Dynamic coalition formation and the core.Journal of Economic Behavior & Organization, 49(3), 2002

    Tone Arnold and Ulrich Schwalbe. Dynamic coalition formation and the core.Journal of Economic Behavior & Organization, 49(3), 2002

    2002

  4. [4]

    Subjectivity and correlation in randomized strategies.Journal of mathematical Economics, 1(1), 1974

    Robert J Aumann. Subjectivity and correlation in randomized strategies.Journal of mathematical Economics, 1(1), 1974

    1974

  5. [5]

    Timed network games.Information and Computation, 290:104996, 2023

    Guy Avni, Shibashis Guha, and Orna Kupferman. Timed network games.Information and Computation, 290:104996, 2023. ISSN 0890-5401. doi: https://doi.org/10.1016/j.ic.2022.104996. URL https: //www.sciencedirect.com/science/article/pii/S0890540122001511

    work page doi:10.1016/j.ic.2022.104996 2023

  6. [6]

    Hedonic games

    Haris Aziz and Rahul Savani. Hedonic games. InHandbook of Computational Social Choice. Cambridge University Press, 2016

    2016

  7. [7]

    Computing desirable partitions in additively separable hedonic games.Artificial Intelligence, 195, 2013

    Haris Aziz, Felix Brandt, and Hans Georg Seedig. Computing desirable partitions in additively separable hedonic games.Artificial Intelligence, 195, 2013

    2013

  8. [8]

    Neighborhood stability in assign- ments on graphs.arXiv preprint arXiv:2407.05240, 2024

    Haris Aziz, Grzegorz Lisowski, Mashbat Suzuki, and Jeremy Vollen. Neighborhood stability in assign- ments on graphs.arXiv preprint arXiv:2407.05240, 2024

    arXiv 2024

  9. [9]

    Masoud Bashiri and Cody H. Fleming. A platoon-based intersection management system for autonomous vehicles. In2017 IEEE Intelligent Vehicles Symposium (IV), pages 667–672, 2017. doi: 10.1109/IVS. 2017.7995794

    work page doi:10.1109/ivs 2017

  10. [10]

    Stable dinner party seating arrange- ments

    Damien Berriaud, Andrei Constantinescu, and Roger Wattenhofer. Stable dinner party seating arrange- ments. InProc. of WINE, 2023

    2023

  11. [11]

    PhD thesis, Politecnico di Torino, 2022

    Andrea Bertolini.Decentralized algorithms for multi-agent pathfinding. PhD thesis, Politecnico di Torino, 2022

    2022

  12. [12]

    Sharing rides with friends: A coalition formation algorithm for ridesharing

    Filippo Bistaffa, Alessandro Farinelli, and Sarvapali Ramchurn. Sharing rides with friends: A coalition formation algorithm for ridesharing. InProc. of AAAI, 2015

    2015

  13. [13]

    Hedonic seat arrangement problems.arXiv preprint arXiv:2002.10898, 2020

    Hans L Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, and Tom C van der Zanden. Hedonic seat arrangement problems.arXiv preprint arXiv:2002.10898, 2020. 23

    arXiv 2002

  14. [14]

    Multi-agent path finding with task assignment and supporting constraints

    Caroline Bonhomme, Christophe Grand, Charles Lesire, Jean-Louis Dufour, and Christophe Guettier. Multi-agent path finding with task assignment and supporting constraints. InProc. of ECAI, 2024

    2024

  15. [15]

    Coordinating resources in stackelberg security games.European Journal of Operational Research, 291(3), 2021

    Víctor Bucarey , Carlos Casorrán, Martine Labbé, Fernando Ordoñez, and Oscar Figueroa. Coordinating resources in stackelberg security games.European Journal of Operational Research, 291(3), 2021

    2021

  16. [16]

    Topological distance games.Theoretical Computer Science, 981, 2024

    Martin Bullinger and Warut Suksompong. Topological distance games.Theoretical Computer Science, 981, 2024

    2024

  17. [17]

    Interaction- aware game-theoretic motion planning for automated vehicles using bi-level optimization

    Christoph Burger, Johannes Fischer, Frank Bieder, Ömer ¸ Sahin Ta¸ s, and Christoph Stiller. Interaction- aware game-theoretic motion planning for automated vehicles using bi-level optimization. InProc. of the International Conference on Intelligent Transportation Systems (ITSC), pages 3978–3985, 2022

    2022

  18. [18]

    A distributed approach to autonomous intersec- tion management via multi-agent reinforcement learning, 2024

    Matteo Cederle, Marco Fabris, and Gian Antonio Susto. A distributed approach to autonomous intersec- tion management via multi-agent reinforcement learning, 2024. URL https://arxiv.org/abs/2405. 08655

    2024

  19. [19]

    Optimal seat arrangement: what are the hard and easy cases?arXiv preprint arXiv:2305.10381, 2023

    Esra Ceylan, Jiehua Chen, and Sanjukta Roy. Optimal seat arrangement: what are the hard and easy cases?arXiv preprint arXiv:2305.10381, 2023

    arXiv 2023

  20. [20]

    Dispatching through pricing: Modeling ride-sharing and designing dynamic prices

    Mengjing Chen, Weiran Shen, Pingzhong Tang, and Song Zuo. Dispatching through pricing: Modeling ride-sharing and designing dynamic prices. InProc. of IJCAI, 2019

    2019

  21. [21]

    Stackelberg security games: Computing the shortest-path equilibrium.Expert Systems with Applications, 42(8), 2015

    Julio B Clempner and Alexander S Poznyak. Stackelberg security games: Computing the shortest-path equilibrium.Expert Systems with Applications, 42(8), 2015

    2015

  22. [22]

    Collaborative urban trans- portation: Recent advances in theory and practice.European Journal of Operational Research, 273(3), 2019

    Catherine Cleophas, Caitlin Cottrill, Jan Fabian Ehmke, and Kevin Tierney. Collaborative urban trans- portation: Recent advances in theory and practice.European Journal of Operational Research, 273(3), 2019

    2019

  23. [23]

    Individual rationality in topologi- cal distance games is surprisingly hard.arXiv preprint arXiv:2404.14128, 2024

    Argyrios Deligkas, Eduard Eiben, Dušan Knop, and Šimon Schierreich. Individual rationality in topologi- cal distance games is surprisingly hard.arXiv preprint arXiv:2404.14128, 2024

    arXiv 2024

  24. [24]

    A multiagent approach to autonomous intersection management.Journal of artificial intelligence research, 31, 2008

    Kurt Dresner and Peter Stone. A multiagent approach to autonomous intersection management.Journal of artificial intelligence research, 31, 2008

    2008

  25. [25]

    Multi-hop ride sharing.Proceedings of the International Symposium on Combinatorial Search, 4(1):71–79, 8 2021

    Florian Drews and Dennis Luxen. Multi-hop ride sharing.Proceedings of the International Symposium on Combinatorial Search, 4(1):71–79, 8 2021. doi: 10.1609/socs.v4i1.18279. URL https://ojs.aaai. org/index.php/SOCS/article/view/18279

    work page doi:10.1609/socs.v4i1.18279 2021

  26. [26]

    Hedonic coalitions: Optimality and stability.Econometrica: Journal of the Econometric Society, 1980

    Jacques H Dreze and Joseph Greenberg. Hedonic coalitions: Optimality and stability.Econometrica: Journal of the Econometric Society, 1980

    1980

  27. [27]

    Existence and efficiency of equilibria for cost- sharing in generalized weighted congestion games.ACM Transactions on Economics and Computation (TEAC), 8(2), 2020

    Martin Gairing, Kostas Kollias, and Grammateia Kotsialou. Existence and efficiency of equilibria for cost- sharing in generalized weighted congestion games.ACM Transactions on Economics and Computation (TEAC), 8(2), 2020

    2020

  28. [28]

    Congestion games with capacitated resources.Theory of Computing Systems, 57(3), 2015

    Laurent Gourves, Jérôme Monnot, Stefano Moretti, and Nguyen Kim Thang. Congestion games with capacitated resources.Theory of Computing Systems, 57(3), 2015

    2015

  29. [29]

    Collaborative transportation with overlapping coalitions.European Journal of Operational Research, 271(1), 2018

    Mario Guajardo, Mikael Rönnqvist, Patrik Flisberg, and Mikael Frisk. Collaborative transportation with overlapping coalitions.European Journal of Operational Research, 271(1), 2018

    2018

  30. [30]

    Cost-sharing mechanisms for network design

    Anupam Gupta, Aravind Srinivasan, and Éva Tardos. Cost-sharing mechanisms for network design. Algorithmica, 50(1):98–119, 2008

    2008

  31. [31]

    Autonomous intersection management: Multi- intersection optimization

    Matthew Hausknecht, Tsz-Chiu Au, and Peter Stone. Autonomous intersection management: Multi- intersection optimization. InProc. of IROS, 2011

    2011

  32. [32]

    The effect of collusion in congestion games

    Ara Hayrapetyan, Éva Tardos, and Tom Wexler. The effect of collusion in congestion games. InProc. of ACM STOC, 2006. 24

    2006

  33. [33]

    Probabilistic physical search on general graphs: approximations and heuristics.Autonomous Agents and Multi-Agent Systems, 34(1), 2020

    Noam Hazon and Mira Gonen. Probabilistic physical search on general graphs: approximations and heuristics.Autonomous Agents and Multi-Agent Systems, 34(1), 2020

    2020

  34. [34]

    Collaborative multi agent physical search with probabilistic knowledge

    Noam Hazon, Yonatan Aumann, and Sarit Kraus. Collaborative multi agent physical search with probabilistic knowledge. InProc. of IJCAI, 2009

    2009

  35. [35]

    Physical search problems with probabilis- tic knowledge.Artificial Intelligence, 196, 2013

    Noam Hazon, Yonatan Aumann, Sarit Kraus, and David Sarne. Physical search problems with probabilis- tic knowledge.Artificial Intelligence, 196, 2013

    2013

  36. [36]

    Decentralized multi-agent path finding for uav traffic management

    Florence Ho, Rúben Geraldes, Artur Gonçalves, Bastien Rigault, Benjamin Sportich, Daisuke Kubo, Marc Cavazza, and Helmut Prendinger. Decentralized multi-agent path finding for uav traffic management. IEEE Transactions on Intelligent Transportation Systems, 23(2), 2020

    2020

  37. [37]

    Mirrokni, Heiko Röglin, and Shang-Hua Teng

    Martin Hoefer, Vahab S. Mirrokni, Heiko Röglin, and Shang-Hua Teng. Competitive routing over time.Theoretical Computer Science, 412(39):5420–5432, 2011. ISSN 0304-3975. doi: https:// doi.org/10.1016/j.tcs.2011.05.055. URL https://www.sciencedirect.com/science/article/pii/ S0304397511004956

    work page doi:10.1016/j.tcs.2011.05.055 2011

  38. [38]

    Dynamics in matching and coalition formation games with structural constraints.Artificial Intelligence, 262, 2018

    Martin Hoefer, Daniel Vaz, and Lisa Wagner. Dynamics in matching and coalition formation games with structural constraints.Artificial Intelligence, 262, 2018

    2018

  39. [39]

    Tictac: From transfer-incapable carpooling to transfer-allowed carpooling

    Yunfei Hou, Xu Li, and Chunming Qiao. Tictac: From transfer-incapable carpooling to transfer-allowed carpooling. InProc. of GLOBECOM, 2012

    2012

  40. [40]

    A survey of task allocation and load balancing in distributed systems.IEEE Transactions on Parallel and Distributed Systems, 27(2), 2015

    Yichuan Jiang. A survey of task allocation and load balancing in distributed systems.IEEE Transactions on Parallel and Distributed Systems, 27(2), 2015

    2015

  41. [41]

    Toward 6g-v2x: Edge-assisted platoon coordination for cooperative intersection control

    Jozef Juraško, Lukáš Lovás, Rastislav Bencel, and Peter Trúchly . Toward 6g-v2x: Edge-assisted platoon coordination for cooperative intersection control. In2025 International Symposium ELMAR, pages 21–24,

  42. [42]

    doi: 10.1109/ELMAR66948.2025.11194002

    work page doi:10.1109/elmar66948.2025.11194002 2025

  43. [43]

    Other solutions to nash’s bargaining problem.Econometrica, pages 513–518, 1975

    Ehud Kalai and Meir Smorodinsky . Other solutions to nash’s bargaining problem.Econometrica, pages 513–518, 1975

    1975

  44. [44]

    Simultaneous optimization of traffic signal control and vehicle platooning scheme based on connected and automated vehicle (cav) technology.IEEE Access, 2025

    Jiwon Kang, Yongjun Choi, and Keemin Sohn. Simultaneous optimization of traffic signal control and vehicle platooning scheme based on connected and automated vehicle (cav) technology.IEEE Access, 2025

    2025

  45. [45]

    Consideration of multiple objectives in horizontal cooperation with an application to transportation planning.IISE Transactions, 49(12), 2017

    Alf Kimms and Igor Kozeletskyi. Consideration of multiple objectives in horizontal cooperation with an application to transportation planning.IISE Transactions, 49(12), 2017

    2017

  46. [46]

    Klusch and A

    M. Klusch and A. Gerber. Dynamic coalition formation among rational agents.IEEE Intelligent Systems, 17(3), 2002

    2002

  47. [47]

    Worst-case equilibria

    Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. InProc. of STACS, 1999

    1999

  48. [48]

    Multi-hypothesis interactions in game-theoretic motion planning

    Forrest Laine, David Fridovich-Keil, Chih-Yuan Chiu, and Claire Tomlin. Multi-hypothesis interactions in game-theoretic motion planning. InProc. of IEEE International Conference on Robotics and Automation (ICRA), 2021

    2021

  49. [49]

    Lucidgames: Online unscented inverse dynamic games for adaptive trajectory prediction and planning.IEEE Robotics and Automation Letters, 6 (3):5485–5492, 2021

    Simon Le Cleac’h, Mac Schwager, and Zachary Manchester. Lucidgames: Online unscented inverse dynamic games for adaptive trajectory prediction and planning.IEEE Robotics and Automation Letters, 6 (3):5485–5492, 2021

    2021

  50. [50]

    John Wiley & Sons, 2008

    David Lewis.Convention: A philosophical study. John Wiley & Sons, 2008

    2008

  51. [51]

    A review of path-planning approaches for multiple mobile robots.Machines, 10(9):773, 2022

    Shiwei Lin, Ang Liu, Jianguo Wang, and Xiaoying Kong. A review of path-planning approaches for multiple mobile robots.Machines, 10(9):773, 2022

    2022

  52. [52]

    John F et al. Nash. The bargaining problem.Econometrica, 18(2), 1950. 25

    1950

  53. [53]

    Ramchurn, Maria Polukarov, Alessandro Farinelli, Cuong Truong, and Nicholas R

    Sarvapali D. Ramchurn, Maria Polukarov, Alessandro Farinelli, Cuong Truong, and Nicholas R. Jennings. Coalition formation with spatial and temporal constraints. InProc. of AAMAS, 2010

    2010

  54. [54]

    Ridesharing with driver location preferences.arXiv preprint arXiv:1905.13191, 2019

    Duncan Rheingans-Yoo, Scott Duke Kominers, Hongyao Ma, and David C Parkes. Ridesharing with driver location preferences.arXiv preprint arXiv:1905.13191, 2019

    arXiv 1905

  55. [55]

    Efficiency and fairness in team search with self-interested agents.Autonomous Agents and Multi-Agent Systems, 30, 2016

    Igor Rochlin, Yonatan Aumann, David Sarne, and Luba Golosman. Efficiency and fairness in team search with self-interested agents.Autonomous Agents and Multi-Agent Systems, 30, 2016

    2016

  56. [56]

    Multi-agent pathfinding: Definitions, variants, and benchmarks

    Roni Stern, Nathan Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, TK Kumar, et al. Multi-agent pathfinding: Definitions, variants, and benchmarks. InProc. of SoCS, 2019

    2019

  57. [57]

    Ad hoc autonomous agent teams: Collaboration without pre-coordination

    Peter Stone, Gal Kaminka, Sarit Kraus, and Jeffrey Rosenschein. Ad hoc autonomous agent teams: Collaboration without pre-coordination. InProc. of AAAI, 2010

    2010

  58. [58]

    Convention as correlated equilibrium.Erkenntnis, 42(1), 1995

    Peter Vanderschraaf. Convention as correlated equilibrium.Erkenntnis, 42(1), 1995

    1995

  59. [59]

    Congestion games: Optimization in competition

    Berthold Vöcking and R Aachen. Congestion games: Optimization in competition. InACiD, 2006

    2006

  60. [60]

    Game-theoretic planning for self-driving cars in multivehicle competitive scenarios.IEEE Transactions on Robotics, 37(4): 1313–1325, 2021

    Mingyu Wang, Zijian Wang, John Talbot, J Christian Gerdes, and Mac Schwager. Game-theoretic planning for self-driving cars in multivehicle competitive scenarios.IEEE Transactions on Robotics, 37(4): 1313–1325, 2021

    2021

  61. [61]

    Self-adaptation-based dynamic coalition formation in a distributed agent network: A mechanism and a brief survey .IEEE Transactions on Parallel and Distributed Systems, 24(5), 2013

    Dayong Ye, Minjie Zhang, and Danny Sutanto. Self-adaptation-based dynamic coalition formation in a distributed agent network: A mechanism and a brief survey .IEEE Transactions on Parallel and Distributed Systems, 24(5), 2013

    2013

  62. [62]

    An open loop stackelberg solution to optimal strategy for uav pursuit-evasion game.Aerospace Science and Technology, 129, 2022

    Yiqun Zhang, Pengfei Zhang, Xiaodong Wang, Feng Song, Chaoyong Li, and Junhong Hao. An open loop stackelberg solution to optimal strategy for uav pursuit-evasion game.Aerospace Science and Technology, 129, 2022

    2022

  63. [63]

    Dynamic car dispatching and pricing: Revenue and fairness for ridesharing platforms.arXiv preprint arXiv:2207.06318, 2022

    Zishuo Zhao, Xi Chen, Xuefeng Zhang, and Yuan Zhou. Dynamic car dispatching and pricing: Revenue and fairness for ridesharing platforms.arXiv preprint arXiv:2207.06318, 2022

    arXiv 2022

  64. [64]

    Multi-agent cooperative transportation: Optimal and efficient task allocation and path finding

    Ning Zhou, Nikolai WF Bode, and Edmund R Hunt. Multi-agent cooperative transportation: Optimal and efficient task allocation and path finding. 2026. A Best Response Algorithm Algorithm 5 identifies the best response strategy for agent a1, given a2’s pathπ. The algorithm begins by computing SIP s1 (the shortest independent paths from a1’s starting node to ...

    2026

  65. [65]

    The shortest independent path froms i tog i. 27

  66. [66]

    Since a−i’s path to cs is non-cooperative (Condition 2, it follows that cs is the first cooperation node along π−i that ai can reach at a cooperation-relevant time

    The path SIP si,c∗ 1 ◦π −i c∗ 1 ,d ◦SIP d,gi, where c∗ 1 is the first cooperation node along π−i that ai can reach at a cooperation-relevant time, anddis the optimal departure node fora i alongπ −i c∗ 1 ,gi Since(π 1, π2)is an ECJS, following Condition 5, it holds that: T(π i |π −i)≤T(SIP si,gi) We therefore examine the cooperation-assisted path SIP si,c∗...

  67. [67]

    IfT(π i(N C) si,cs )≤T(π −i(N C) s−i,cs ), thenT(SIP si,cs)≤T(π i(N C) si,cs )≤T(π −i(N C) s−i,cs )Thus: max(T(π i(N C) si,cs ), T(π −i(N C) s−i,cs )) = max(T(SIP si,cs), T(π −i(N C) s−i,cs )) =T(π −i(N C) s−i,cs ) Hence: T(π i|π−i) =T(π i∗ |π−i)

  68. [68]

    If T(π i(N C) si,cs )> T(π −i(N C) s−i,cs ), then, since π1(N C) s1,cs and π2(N C) s2,cs are Mutually-Robust Non-Cooperative Partial Paths, it follows thatπ i(N C) si,cs =SIP si,cs. Thus: max(T(π i(N C) si,cs ), T(π −i(N C) s−i,cs )) = max(T(SIP si,cs), T(π −i(N C) s−i,cs )) Hence: T(π i|π−i) =T(π i∗ |π−i) In both cases, ai’s pathπi serves as the best res...

  69. [69]

    (a) We assume, by contradiction, that the joint strategy (π1, π2) contains more than one cooperation segment

    Condition 1: We consider both parts of Condition 1: (a) the agents cooperate along exactly one continuous cooperation segment, and (b) this cooperation segment is stable. (a) We assume, by contradiction, that the joint strategy (π1, π2) contains more than one cooperation segment. In that case, it can be expressed as: π1 =π 1 s1,cs1 ◦π C cs1 ,cd1 ◦π 1 cd1 ...

  70. [70]

    We consider two options: (a) The path of one of the agents, without loss of generality a2, to cs, π2 s2,cs, is not non-cooperative

    Condition 2: We assume, by contradiction, that the paths of the two agents from their starting nodes to cs are notMutually-Robust Non-Cooperative Partial Paths. We consider two options: (a) The path of one of the agents, without loss of generality a2, to cs, π2 s2,cs, is not non-cooperative. In this case, there exists a cooperation node along this path, c...

  71. [71]

    This implies that: T(π 1 s1,cs ◦π 2 cs,cd′ ◦SIP cd′ ,g1 |π2)< T(SIP s1,cs ◦π 2 cs,cd ◦SIP cd,g1 |π2) =T(π 1, π2) which contradicts the assumption that(π 1, π2)is a PNE

    Condition 3: We assume, by contradiction, that the optimal departure node for one of the agents, without loss of generalitya 1, along the other agent’s pathπ2 cs,g2 isc d′ ̸=c d. This implies that: T(π 1 s1,cs ◦π 2 cs,cd′ ◦SIP cd′ ,g1 |π2)< T(SIP s1,cs ◦π 2 cs,cd ◦SIP cd,g1 |π2) =T(π 1, π2) which contradicts the assumption that(π 1, π2)is a PNE. 29

  72. [72]

    Since (π1, π2) involves a single continuous cooperation segment (Condition 1), and cd is the cooperation departure node, the joint path(π 1 cd,g1 , π2 cd,g2)contains no cooperation

    Condition 4: We assume, by contradiction, that for one of the agents, without loss of generality a1, the partial path π1 cd,g1 from the departure node cd to its target node g1 differs from the shortest independent path SIP cd,g1. Since (π1, π2) involves a single continuous cooperation segment (Condition 1), and cd is the cooperation departure node, the jo...

  73. [73]

    In this case, the independent shortest path fora 1 would be a better response to theπ 2 thanπ 1: T(SIP s1,g1 , π2)< T(π 1, π2)

    Condition 5: We assume, by contradiction, that one of the agents, without loss of generality a1, prefers to take its independent path directly from its starting node to its target node, SIP s1,g1. In this case, the independent shortest path fora 1 would be a better response to theπ 2 thanπ 1: T(SIP s1,g1 , π2)< T(π 1, π2). This contradicts the assumption ...

  74. [74]

    that minimizes social welfare for two agents navigating a graph with m cooperation nodes. The algorithm starts by finding SIP s1 and SIP s2 (all shortest independent paths from the initial nodes to other graph nodes), and SIP g1 and SIP g2 (all shortest independent paths to the target nodes from other graph nodes) [lines 1-4]. These paths are then used to...

  75. [75]

    Cooperation Continuity:The joint strategy that optimizes social welfare through cooperation is one in which a1 and a2 independently follow the shortest paths to a cooperation starting node cs (SIP s1,cs , SIP s2,cs), cooperate along the joint shortest path to a cooperation departure node cd (SCP cs,cd), and then each independently follows the shortest pat...

  76. [76]

    Early Cooperation:If agents a1 and a2 can reach a cooperation nodec∈V C earlier through cooperation rather than individually, then c is not the first cooperation node in the joint strategy that optimizes social welfare. 34 Algorithm 6SOCIALWELFAREOPTIMALPATH(G, V C, s1, s2, g1, g2) 1:SIP s1 ←ALL SHORTEST PATHS FROM(G, τ 1, s1)▷Find shortest paths from sta...

    arXiv 1991