PaperlayerView exact revision on arXiv

Source-linked AI summary

Competitive exploration in structured environments

James P. Wolfe, Joshua B. Plotkin

arXiv:2610.34643v1physics.soc-phcs.GTq-bio.PE

TL;DR

Competition makes exploration a strategic choice because each forager’s payoff depends on the other’s exploration rate. The paper models this interaction as a game and finds that signaling discovery can improve outcomes in many strict dilemmas.

  • Problem

    When foragers share rewards, each forager’s payoff depends on the other’s exploration rate, raising the question of whether self-interested choices maximize their combined payoff.

    Source: Strategies and payoffs · p. 5

  • Method

    The paper models two foragers’ exploration rates as strategies in a symmetric game, with expected discounted reward depending on both rates and the environment’s parameters.

    Source: Strategies and payoffs · p. 5

  • Results

    Where signaling removes a strict dilemma, the worst Nash-equilibrium collective payoff rises by as much as 20.9%.

    Source: Signaling can remove suboptimal… · p. 13

  • Takeaways & Limitations

    Where signaling removes a dilemma, every remaining Nash equilibrium is socially optimal and locally stable, but signaling cannot remove dilemmas where both agents stay.

    Source: Signaling can remove suboptimal… · p. 13

    The ε-greedy rule does not commit to travel bouts, so at the short distance examined an agent rarely reaches the distant site before returning unless its exploration rate is high.

    Source: Discussion · p. 15

Abstract

from arXiv · show

Organisms must constantly weigh exploiting the resources they know against exploring for better ones. When foragers compete, the best behavior for each forager also depends on what its competitors do. How does competition change the strategic balance between exploration and exploitation? Here we address this question in a minimal model: two $\epsilon$-greedy temporal-difference learners on a one-dimensional lattice, who start at a small reward at one end and are unaware of a larger reward at the other. For a lone forager, the optimal exploration rate increases monotonically with the value of the distant reward, and with its distance up to a critical distance. When two foragers share the lattice and split rewards, the choice of exploration rate becomes a game whose Nash equilibria have both foragers exploring, both staying, or one exploring while the other stays (anti-coordination). Under local best-response dynamics, pairs of foragers often converge on both exploring or both staying, even when anti-coordination would be socially optimal. This social dilemma arises for a wide range of parameters, and it persists even in a simplified model without explicit spatial structure. A minimal, naturalistic signal, in which one forager informs the other that it has found the distant reward, can remove many of the dilemmas in which both foragers explore, and can produce a Nash equilibrium whose collective payoff exceeds that of every outcome available without signaling.

Model

The model places an ε-greedy forager on a one-dimensional lattice with a known small reward and an initially unknown, larger reward at the far end. It extends the setup to competing foragers and computes expected rewards using a Markov-chain representation.

A spatial model of exploration and exploitation

  • A forager moves locally between a known reward at site 0 and an unknown larger reward at site d, with ε setting the chance of random exploration.After discovering the distant reward, its movement bias reverses toward that site; the high-discount regime makes this movement rule equivalent to the temporal-difference learner.Source: A spatial model of exploration and… · p. 3

Markov chain formulation

  • The Markov chain represents movement with states tracking the current site and whether the distant reward has been found, yielding expected reward without simulating runs.Its prediction matches the mean reward of 5,000 TD-learner runs at d = 8 and R = 5.Source: Markov chain formulation · p. 4

Two competing agents

  • Two agents share the lattice and split rewards when they occupy the same site, with parameters chosen so a discoverer remains biased toward the distant reward.The model reuses the single-agent transition matrix and adjusts the reward vector to account for sharing.Source: Two competing agents · pp. 4–5

Results

The results examine how competition shapes exploration and staying, including conflicts between individual and collective interests, and how a discovery signal can encourage division of labor and remove many both-explore dilemmas.

An intermediate exploration rate is optimal for distant, valuable rewards

  • A single agent’s optimal exploration is zero below a reward threshold, then positive; it rises with distance up to a critical distance before dropping discontinuously to zero.Exploration balances reaching the distant reward against stepping away from it after arrival; a larger reward or shorter distance can make an intermediate rate optimal.Source: An intermediate exploration rate is… · p. 5
  • Away from the exploit–explore boundary, the optimal rate for a random distance closely matches the rate for its mean distance.Source: An intermediate exploration rate is… · p. 5

Two competing foragers play a game with multiple equilibria

  • Competition produces Nash equilibria of both-explore, anti-coordination, or both-stay types, and the best response to a competitor’s exploration rate can be non-monotonic.For the example with R = 2.1 and d = 4, both-explore and anti-coordination are equilibria; both-stay is the only equilibrium whenever it is a Nash equilibrium.Source: Strategies and payoffs · pp. 5, 7, Nash equilibria · p. 7
  • Myopic local best-response dynamics can settle on both-stay, both-explore, or anti-coordination outcomes, with the reached outcome depending on initial exploration rates.As distant rewards become smaller or farther away, both-explore locally stable outcomes disappear first, then anti-coordination, potentially leaving both-stay alone.Source: Locally stable equilibria · p. 8

Competition produces a social dilemma

  • Strict dilemmas arise when both-stay or both-explore Nash outcomes underperform a locally stable division of labor; anti-coordination is never the suboptimal Nash type.Division of labor lets one agent collect the near reward while the other explores for an uncontested distant reward. Both exploring becomes socially optimal only when the distant reward is large enough to outweigh the near reward forgone while neither agent stays.Source: Competition produces a social dilemma · pp. 9–11
  • At R = 2.1 and d = 4, the both-explore Nash equilibrium yields 84% of the best locally stable collective payoff yet is reached from 83% of initial conditions.Source: Competition produces a social dilemma · p. 9, Figure 4 · p. 9

Strict dilemmas usually involve a conflict of interest

  • Most strict social dilemmas involve a conflict of interest: reaching a collectively better outcome requires one agent to accept a lower individual payoff.Strict Pareto dilemmas are rare; they can occur with both-stay or both-explore Nash equilibria near the anti-coordination region.Source: Strict dilemmas usually involve a… · p. 11
  • At a symmetric both-explore equilibrium, switching to anti-coordination can sacrifice all distant-reward payoff, so strict dilemmas permitting Pareto improvement lie near the anti-coordination boundary.The agent that stops exploring gains a larger share of the near reward but loses its distant-site returns.Source: Strict dilemmas usually involve a… · p. 11

Signaling can remove suboptimal equilibria

  • Signaling removes many strict dilemmas with both agents exploring; where it succeeds, remaining Nash equilibria are socially optimal, with worst-equilibrium collective-payoff gains up to 20.9%.It cannot remove dilemmas where both agents stay, because neither reaches the distant site to send a signal.Source: Figure 6 · p. 12, Signaling can remove suboptimal… · p. 13
  • After one agent finds the distant reward, the signal makes the other favor the exclusive near reward and lower exploration, enabling division of labor without stopping exploration beforehand.Before discovery both agents face the same problem; afterward, the finder spends most of its time at the distant site, where rewards are shared.Source: Signaling can remove suboptimal… · pp. 12–13
  • At d = 4 and R = 2.1, signaling leaves a sole Nash equilibrium at (0.36, 0), raising worst-equilibrium collective payoff from 9357 to 11362 and exceeding every nonsignaling strategy pair.This removes the strict Pareto dilemma in the example, although the signaling equilibrium is not the signaling game’s global optimum.Source: Table 3 · p. 13, Signaling can remove suboptimal… · p. 13
  • Across horizons, signaling removes 45–100% of Pareto dilemmas but only 8–29% of dilemmas where only the pair benefits collectively; gains are larger in Pareto cases.The dilemmas most likely to be removed are those where each agent, not just the pair, benefits from the better outcome.Source: Signaling can remove suboptimal… · p. 13

Discussion

The model frames exploration as a costly tradeoff shaped by competition: equilibria can be collectively worse than anti-coordination, and a minimal signal can improve some outcomes. Its conclusions are bounded by simplified assumptions about spatial structure, search, environmental change, and the number of foragers.

Discussion

  • Competition creates equilibria where both foragers explore or both stay, even when anti-coordination is collectively better; strict dilemmas usually involve a conflict of interest.Only rarely does the alternative Pareto-dominate the equilibrium, leaving both agents better off, as in a Prisoner’s Dilemma.Source: Discussion · p. 14
  • A signal that one forager found the distant reward removes many both-explore dilemmas, most often when the alternative Pareto-dominates the equilibrium.The signal can produce a Nash equilibrium with a higher collective payoff than outcomes available without signaling.Source: Discussion · p. 14
  • The anti-coordination outcome resembles division of effort in ant colonies, while food-location cues provide natural counterparts to the model’s signal.The model suggests communication may replace a collectively worse equilibrium with a socially better division of effort.Source: Discussion · p. 14
  • Unlike shareable-reward bandit models where agents choose options directly, costly travel makes this model’s equilibria fall into three discrete types.Those types are both agents exploring, one exploring while the other stays, and both staying.Source: Discussion · pp. 14–15
  • The analysis treats exploration rate as a fixed, potentially evolved trait and connects equilibrium reachability to evolutionary game theory and animal personality.It distinguishes whether a strategy pair is a Nash equilibrium from whether incremental adjustment converges on it.Source: Discussion · pp. 14–15
  • The conclusions are limited by a one-dimensional lattice, ε-greedy search without committed travel bouts, a fixed environment, and analysis of only two agents.Higher-dimensional behavior, shifting reward values during foraging, and population-level evolution and signaling selection remain to be analyzed.Source: Discussion · p. 15

Methods

The methods calculate expected payoffs from transition matrices rather than agent simulations. They extend a single-agent Markov chain to two independent movers with shared-site reward splitting, exploit payoff linearity for reward sweeps, and locate equilibria on a discretized strategy grid.

Methods

  • The analysis constructs a single-agent transition matrix, extends it to two agents with a Kronecker product, and uses payoff linearity to reduce reward sweeps to two linear solves.The two-solve approach avoids solving separately for every reward-value pair.Source: Methods · pp. 15–16

The single-agent transition matrix

  • The single-agent chain tracks position and whether the distant site has been visited, with exploitation determined by the relative discounted values of the two rewards.The matrix construction covers every discount factor; in the high-discount regime, all sites lie beyond the equal-value position.Source: The single-agent transition matrix · p. 16

The two-agent transition matrix and reward vectors

  • The joint chain is a Kronecker product because each agent moves according to its own state, while its reward depends on whether the agents share a site.The model assumes both agents prefer the distant reward after visiting it, even when they split it.Source: The two-agent transition matrix and… · p. 16

Linearity of the payoff in the two reward values

  • Because rewards enter linearly, the payoff calculation can reuse two solved components to recover expected payoffs across reward values.The reward vector is expressed as a weighted sum of vectors for the near and distant rewards.Source: Linearity of the payoff in the two… · pp. 16–17

Numerical computation of equilibria

  • Payoffs are exact up to floating-point error, but equilibria and local best-response dynamics are found on a grid of exploration rates.Local stability means neither player gains from a one-step rate change; simultaneous updates choose among the current and neighboring rates.Source: Numerical computation of equilibria · p. 17

Data and code availability

  • Code to reproduce the figures and tables is available on GitHub, and generated data are archived on Zenodo.The passage supplies the repository and archive identifiers.Source: Data and code availability · p. 17

S1 Variable distance to the distant reward

When the distant reward’s distance varies as a Poisson-distributed quantity plus one, the optimal exploration rate is generally close to that for the mean-distance static environment, with differences near the explore-versus-stay boundary.

S1 Variable distance to the distant reward

  • For distance dV sampled as Poisson(λ) + 1, the optimal exploration rate is generally close to the optimum in a static environment at d = λ + 1.The explore-versus-stay boundary is not identical across the two settings.Source: S1 Variable distance to the distant… · p. 20
  • Near the explore-versus-stay boundary, static and variable environments can favor different choices, with the direction of disagreement depending on the discount factor.For longer horizons, some static environments favor exploration when variable ones favor staying; for shorter horizons, the reverse occurs.Source: S1 Variable distance to the distant… · p. 20
  • At smaller distances, a variable environment can slightly increase the optimal exploration rate because exploration must work across likely landscapes.The passage’s overall correspondence is closest away from the boundary where the two environments disagree.Source: S1 Variable distance to the distant… · p. 20

S2 Behavior of the threshold reward ratio

The threshold reward ratio for making exploration worthwhile rises with distance and falls as the foraging horizon grows. A scaling argument attributes the threshold’s growth to the tradeoff between time spent searching and time spent at the distant reward.

S2 Behavior of the threshold reward ratio

  • Exploration becomes worthwhile when the distant-to-near reward ratio exceeds a threshold determined by the costs of reaching and occupying the distant site.The threshold is shown in the main-text figure and can be computed from the transition matrix.Source: S2 Behavior of the threshold reward… · p. 20
  • The threshold reward ratio R* rises with distance, faster than linearly beyond the shortest distances, and decreases as the foraging horizon T grows.The passage reports the faster-than-linear increase beginning at d = 4 for γ = 1 − 1/1000 and at d = 7 for γ = 1 − 1/100000 onward.Source: S2 Behavior of the threshold reward… · p. 20
  • The scaling argument balances time spent at the distant site against search time, whose discounted cost becomes dominant when expected discovery time approaches the horizon.For the stated approximation, δ ≪ 1 ≪ dδ; the agent explores near rate 1 but still finds the distant site rarely.Source: S2 Behavior of the threshold reward… · pp. 20–21

S3 Proof that there is always a dilemma of the first kind when d ≥2

A dilemma of the first kind occurs when a locally stable strategy pair has lower collective payoff than an alternative the agents could reach.

S3 Proof that there is always a dilemma of the first kind when d ≥2

S3.1 Both stay is locally stable

For d ≥2, both agents staying is locally stable: a sufficiently small unilateral increase in exploration lowers the explorer’s payoff. The proof bounds exploration’s opportunity cost below and its expected benefit above.

S3.1 Both stay is locally stable

S3.2 Anti-coordination is better than both stay

For any distance and positive reward values, anti-coordination yields a higher collective payoff than both agents staying. Together with the local stability of both staying, this establishes a dilemma for d ≥2.

S3.2 Anti-coordination is better than both stay

S4 The two-agent payoff in terms of single-agent occupancies

The two-agent payoff can be reduced to single-agent occupancy probabilities and the discounted co-occupancy of reward sites. This representation isolates how reward sharing changes payoffs and clarifies why anti-coordination preserves the near reward while leaving the distant reward uncontested.

S4 The two-agent payoff in terms of single-agent occupancies

  • Because movement rules are independent of the other agent’s location, the two trajectories are independent and the reward-sharing payoff can be expressed through their occupancy indicators.Source: S4 The two-agent payoff in terms of… · p. 23
  • Two-agent payoffs are determined by single-agent occupancy probabilities at the near and distant sites, together with discounted co-occupancies at those sites.Competition subtracts half the reward accrued during discounted time both agents occupy a reward site.Source: S4 The two-agent payoff in terms of… · p. 23
  • At anti-coordination, the stayer collects the near reward whenever the explorer is away, while the explorer’s distant reward remains uncontested.The group payoff is the both-stay payoff plus the explorer’s distant-site reward; any positive exploration rate strictly raises it.Source: S4 The two-agent payoff in terms of… · p. 24
  • In the high-discount regime, the anti-coordination rate maximizing collective payoff is independent of the distant reward’s value.Changing that reward alters the explorer’s and group’s payoffs and which pairs are equilibria, but not the stayer’s payoff or the socially optimal anti-coordination rate.Source: S4 The two-agent payoff in terms of… · p. 24

S5 When both agents staying is a Nash equilibrium

This section identifies when both agents staying is a Nash equilibrium and shows that below a reward-ratio threshold, it is the only Nash equilibrium. The threshold is half the single-agent exploration threshold, reflecting that a staying agent shares the near reward while the distant reward remains uncontested.

S5 When both agents staying is a Nash equilibrium

  • Both agents staying is a Nash equilibrium if and only if R ≤ R∗(d, γ)/2.At d = 1, R∗ = 1, so both staying is never an equilibrium for the considered range R > 2.Source: S5 When both agents staying is a Nash… · pp. 24–25
  • The factor of one half arises because a staying agent shares the near reward, while an exploring agent can reach an uncontested distant reward.Against a staying competitor, this is equivalent to facing the single-agent problem with the reward ratio doubled.Source: S5 When both agents staying is a Nash… · p. 25
  • When R < R∗(d, γ)/2, both agents staying is the only Nash equilibrium.Against any competitor exploration rate, an agent strictly prefers staying to every positive exploration rate.Source: S5 When both agents staying is a Nash… · p. 25
  • A competitor’s exploration never increases the gain from exploring, because it can increase the value of staying and make the distant reward shared.Together, the results locate the both-stay equilibrium region at reward ratios below half the single-agent threshold, up to exploration-grid resolution.Source: S5 When both agents staying is a Nash… · p. 25

S6 Environmental turnover is equivalent to a shorter horizon

The section models patch exhaustion as independent turnover that returns both agents to their initial state without memory of the distant reward. Turnover preserves the game’s strategic outcomes when represented by a shorter effective foraging horizon.

S6 Environmental turnover is equivalent to a shorter horizon

  • Independent patch turnover returns both agents to their initial state without memory of the distant reward.The first turnover time σ satisfies P(σ > t) = (1 − κ)^t.Source: S6 Environmental turnover is… · pp. 25–26
  • Under turnover, the payoff is a strategy-independent common factor times the static-model payoff at discount factor γ(1 − κ).This equivalence holds when the reduced discount factor still satisfies the high-discount condition and preserves the movement rule.Source: S6 Environmental turnover is… · p. 26
  • Best responses, Nash equilibria, locally stable equilibria, and all three kinds of social dilemma remain identical to the static model at the reduced discount factor.The corresponding effective horizon is T_eff = 1/(1 − γ(1 − κ)).Source: S6 Environmental turnover is… · pp. 25–26

S7 A two-site model without explicit spatial structure

This section simplifies the spatial foraging game into a two-site model without explicit spatial structure, retaining distance through exploration success and time costs. At the examined parameter combination, the simplified model reproduces the full model’s equilibrium and basin structure.

S7 A two-site model without explicit spatial structure

  • At the examined parameter combination, the two-site model reproduces the full model’s four locally stable equilibria, their payoff ranking, and the shape of their basins of attraction.The socially optimal equilibria are anti-coordination, while the suboptimal both-explore equilibrium attracts most initial conditions under local best response.Source: S7 A two-site model without explicit… · pp. 26, 28
  • Agents use an ε-greedy rule: they explore with probability ε and otherwise move toward the best reward they have seen.The model uses internal states for unexplored, high-reward, and low-reward conditions, mapped onto two sites.Source: S7 A two-site model without explicit… · pp. 26–27
  • Distance enters the simplified model only through increasing exploration cost c(ε) and increasing success probability s(ε), based on gambler’s-ruin formulas.The simplification retains the probability of reaching the distant site and the expected time required to get there.Source: S7 A two-site model without explicit… · pp. 26–27
  • The payoff approximation subtracts expected movement costs as a per-turn amount rather than discounting the represented travel time step by step.The authors consider this adequate when γ is close to 1 because the aim is to reproduce the original model’s structure, not exact payoffs.Source: S7 A two-site model without explicit… · p. 26

S8 Signaling model: reduce exploration when other agent reaches reward

This section formulates signaling as a reduction in exploration after a competitor reaches the distant reward, then evaluates the signaling game on selected strict dilemmas. The supplementary analyses describe equilibrium structure, dilemma prevalence, and variation in outcomes across parameters.

S8 Signaling model: reduce exploration when other agent reaches reward

S8.1 Technical formulation

  • The transient phase uses agents’ original exploration rates, while terminal phases use phase-specific transition kernels for the joint state.The authors expect retaining original rates when both agents reach the distant site simultaneously to make little difference to results.Source: S8.1 Technical formulation · pp. 28–29

S8.2 Implementation

  • The signaling game is evaluated on strict dilemmas where both exploring is the worst Nash equilibrium, at distances d = 2–30.The d = 1 cases are omitted because the worst Nash equilibrium payoff falls short of the best locally stable payoff by at most 0.022%.Source: S8.2 Implementation · p. 29

Supplementary Figures

  • Strict Pareto dilemmas make up about 2% or fewer of strict dilemmas at every discount factor.Table S1 reports the proportions of dilemmas where collective payoff falls short of an alternative and the subset where each agent also benefits individually.Source: Table S1 · p. 38
  • Signaling resolves more Pareto dilemmas than collective-only dilemmas across the three reported discount factors.For γ = 1 − 1/1000, it removes 5 of 6 Pareto dilemmas versus 35 of 122 collective-only dilemmas; for γ = 1 − 1/5000, it removes 6 of 6 versus 57 of 246; and for γ = 1 − 1/100000, it removes 5 of 11 versus 41 of 534.Source: Table S2 · p. 39
Loading 2610.34643v1…