Formalizing Cooperation and Competition: An AI-Assisted Mathematical Addendum to a 2018 Planning Thesis

Haitham Masaud Amar

cs.GTOct 21, 2026

Formalizing Cooperation and Competition: An AI-Assisted Mathematical Addendum to a 2018 Planning Thesis

Authors: Haitham Masaud Amar

Abstract

We present an AI-assisted mathematical addendum to Strategic Trip Planning: Striking a Balance Between Competition and Cooperation (Amar, 2018). We reconstruct selected relationships between strategic choice, cooperative stability, participant approval and enforcement. The thesis's Nash-to-core proposition is under-specified until outsider opportunities are stated. We verify two-person implications under fixed outsiders and explicit efficiency conditions. Under isolation, the original example has an empty TU core; its funded counterpart uses an explicit external subsidy. For a monotone resource model we characterize the exact financing gap. A finite negotiation procedure implemented in Lean is proved to terminate with participant approval, joint-cost non-worsening and local optimality against permitted approved moves. Supporting formalizations address bargaining geometry and regret-based efficiency. A resource-game counterinstance shows why monotonicity alone provides no uniform price-of-anarchy bound. Reproducible computations compare a documented heuristic reconstruction with the verified procedure on 44 source-based instances and 96 starting cases from four additional synthetic network families. Acceptance-matched heuristic and randomized pairwise-search controls contextualize the optimization results. The mathematical ingredients are established results; the contribution is a traceable reconstruction linking source statements, explicit assumptions, checked proofs, executable code and retained counterinstances. The study illustrates how AI-assisted investigation can turn engineering intuitions from legacy research into precise mathematical claims whose conditions and computational consequences can be inspected and reproduced.

Figures & tables

Symbol	Meaning
$s$ , $b$ , $s^{*}$	Current profile, feasible baseline, joint comparator
$c_{i}(s)$ , $C(s)$	Base player cost and its declared sum
$v_{s}(S)$ , $v_{\mathrm{iso}}(S)$	Fixed-outsider and isolated coalition opportunities
$h_{i}$ , $F_{h}$	Participant acceptance ceiling and approved profiles
$\widehat{c}_{i}$ , $L_{i}^{t}$	Enforced cost and time-dependent observed cost
$R_{i}(T)$ , $B_{i}(T)$	All-action regret bound and cumulative cost-distortion bound

Table 1

Traveller 1 / Traveller 2	$p_{1}$	$p_{2}$
$p_{1}$	$(8,8)$	$(4,5)$
$p_{2}$	$(5,4)$	$(7,7)$

Table 2

Figure 1: Feasible expected gains, the efficient frontier, pure Nash outcomes and an attainable Nash-product maximizer. Gains use the interacting status quo $(8,8)$ , not isolated exit costs. The shaded triangle represents joint lotteries over the displayed deterministic outcomes.

Resource model	Procedure	Approved	Physical Nash	Approved pairwise terminal	Computed global minimum
Vertex	H1	21/21	21/21	16/21	16/21
Vertex	H3	21/21	21/21	18/21	18/21
Vertex	V	21/21	21/21	21/21	21/21
Edge	H1	21/21	19/21	11/21	11/21
Edge	H3	21/21	21/21	17/21	17/21
Edge	V	21/21	21/21	21/21	21/21

Table 4

Figure 2: Joint-cost paths on the source-derived vertex instance. The paths are newly reconstructed executions, not the published negotiation trace. All shown paths reach the computed minimum 254; accepted-update counts are not communication rounds or runtime.

Figure 3: Joint-cost gaps above the computed optimum for the 21 coalesced cases per resource model. Markers are horizontally offset for readability. Seed indices are discrete case identifiers; no statistical confidence intervals or general approximation guarantee are implied.

Family (24 starts each)	H1 raw approved	V approved	V approved minimum	V unrestricted minimum	V underlying-cost Nash
Grid	19	24	23	18	22
Ring with shortcuts	12	24	23	13	17
Layered	11	24	22	12	14
Parallel corridors	14	24	24	14	14

Table 7

Figure 4: Gap decomposition on independent network families. Each group contains 24 baseline-specific cases. Approval cost is the participation gap; H1 and V search gaps compare published outcomes with the exact approved minimum. H1 includes baseline fallback when raw approval fails; matched controls are reported separately below. Vertical scales differ between families; horizontal offsets only reveal repeated values.

Procedure	Raw approved	Raw Nash	Approved optimum	Mean gap
H1	56/96	80/96	46/96	4.5833
H1-A	96/96	53/96	54/96	3.3958
H1-A-strict	96/96	52/96	54/96	3.4583
V	96/96	67/96	92/96	0.1771

Table 9

Paper result	Declarations, source and added scope
Theorem 1, TU	fixed_outsider_core_iff ; fixed_outsider_minima_exist . Proposition 4.2.1, p.52/PDF72; explicit reference-dependent outsider rule
Theorem 1, NTU	strong_iff_fixed_ntu_core . NTU description and core, (3.2)–(3.3), p.41/PDF61; vector opportunities retained
Theorem 2	two_player_nash_optimum_core ; two_player_nash_pareto_strong . Pairwise bargaining and Pareto example, pp.55–59/PDF75–79; efficiency condition explicit
Actual source instance	ExampleOne.fixed_outsider_core_exists ; ExampleOne.fixed_outsider_ntu_core . Figure 4.2, equations (4.2)–(4.5), Table 4.1, pp.58–59/PDF78–79
Theorem 3	ResourceModel.minima_singleton_dominated ; solo_le_member ; singleton_total ; coalition_minima_exist . Resource costs, §3.2.1 pp.39–42/PDF59–62; §4.5 pp.64–65/PDF84–85; §6.3.2 pp.124–125/PDF144–145; explicit monotone additive subclass
Theorem 4	dominated_core_iff . Cost core (4.23), p.65/PDF85; isolation completion

Table 10

Price of Anarchy

See all 9 papers

Intermittent Strategic Cooperation of Two Selfish Agents on Graphs
Jun 15, 2026Itay Shedlezki, Noa AgmonNash Equilibrium Game Theory
Bar-Ilan University · Ramat Gan, Israel
Reasonably reasoning AI agents can avoid game-theoretic failures in zero-shot, provably
Mar 19, 2026Enoch Hyunwook KangLLM Agents Nash Equilibrium
Foster School of Business, University of Washington
Competition and Cooperation of LLM Agents in Games
Apr 1, 2026Jiayi Yao, Cong Chen, Baosen ZhangLLM Agents Multi-Agent LLM Systems
Department of Electrical and Computer Engineering, University of Washington, Seattle. · Thayer School of Engineering at Dartmouth College.

Jun 15, 2026J/K move · Enter open · S save

Intermittent Strategic Cooperation of Two Selfish Agents on Graphs

Itay Shedlezki, Noa Agmon

Bar-Ilan University · Ramat Gan, Israel

Nash Equilibrium Game Theory Robust MAPF Multi-Agent Path Finding Nash Equilibrium Computation

Open paper AskPDF arXiv

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.

Abstract

Price of Anarchy

Explore similar work

Intermittent Strategic Cooperation of Two Selfish Agents on Graphs

Reasonably reasoning AI agents can avoid game-theoretic failures in zero-shot, provably

Competition and Cooperation of LLM Agents in Games