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

Jun 15, 2026

Intermittent Strategic Cooperation of Two Selfish Agents on Graphs

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.

Itay Shedlezki, Noa Agmon

Bar-Ilan University · Ramat Gan, Israel

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

Ask PDF

Mar 19, 2026

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

As autonomous AI agents increasingly mediate online platform markets, a fundamental question emerges: do these markets generate stable strategic outcomes? In repeated strategic environments, the Nash equilibrium provides a natural benchmark for this stability. However, empirical evidence on off-the-shelf LLM agents is mixed, leaving it unclear whether independently deployed agents can converge to equilibrium behavior without explicit strategic post-training. In this paper, we provide an affirmative answer. Extending the Bayesian learning literature in theoretical economics, we prove that AI agents, acting as Bayesian posterior samplers rather than expected utility maximizers, are guaranteed to eventually become weakly close to a Nash equilibrium in infinitely repeated games. We further extend this analysis to settings in which stage payoffs are unknown ex ante, and agents observe only their privately realized stochastic payoffs, and obtain the same convergence guarantees. Finally, we empirically evaluate these theoretical implications across five repeated-game environments, ranging from the Prisoner's Dilemma to marketing promotion games. Taken together, our findings suggest that strategic stability in AI-mediated markets can emerge from the intrinsic reasoning and learning properties of modern AI agents, without the need for unrealistic universal fine-tuning.

Enoch Hyunwook Kang

Foster School of Business, University of Washington

LLM Agents Nash Equilibrium Repeated Games

Ask PDF

Apr 1, 2026

Competition and Cooperation of LLM Agents in Games

Large language model (LLM) agents are increasingly deployed in competitive multi-agent settings, raising fundamental questions about whether they converge to equilibria and how their strategic behavior can be characterized. In this paper, we study LLM agent interactions in two standard games: a network resource allocation game and a Cournot competition game. Rather than converging to Nash equilibria, we find that LLM agents tend to cooperate when given multi-round prompts and non-zero-sum context. Chain-of-thought analysis reveals that fairness reasoning is central to this behavior. We propose an analytical framework that captures the dynamics of LLM agent reasoning across rounds and explains these experimental findings.

Jiayi Yao, Cong Chen, Baosen Zhang

Department of Electrical and Computer Engineering, University of Washington, Seattle. · Thayer School of Engineering at Dartmouth College.

LLM Agents Multi-Agent LLM Systems Game-Playing Agents Multi-Agent Coordination Cooperative Game Theory

Ask PDF

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