pith. sign in

arxiv: 2605.19440 · v1 · pith:D5QW5ASLnew · submitted 2026-05-19 · 💻 cs.GT

Competitive Search with a Faulty Satnav (GPS): When Probability Matching is Rational

Steve Alpern , Mark Broom This is my paper

Pith reviewed 2026-05-20 02:14 UTC · model grok-4.3

classification 💻 cs.GT
keywords competitive searchNash equilibriumprobability matchingfaulty GPSstar graphsymmetric equilibriumgame theory
0
0 comments X

The pith

Searchers rationally choose to follow a faulty GPS with probability q that approaches the GPS accuracy p as the number of competitors grows large.

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

The paper examines a competitive search game in which n searchers race to reach a hidden treasure first on a star network with k possible destinations, splitting the prize equally among first arrivals. Each searcher can consult a shared GPS that correctly indicates the treasure location with known probability p but gives the wrong direction otherwise. Every searcher picks a probability q of following the GPS recommendation at the central node. The authors prove that for every combination of n, k and p there is exactly one value of q that forms a symmetric Nash equilibrium. This equilibrium q rises with p and with k but falls with n, and it converges to p itself when n tends to infinity with k and p held fixed, providing a new setting in which the behavioural pattern called probability matching is the rational choice.

Core claim

In the competitive search game on a star graph with n searchers, k leaves and GPS accuracy p, there exists a unique symmetric equilibrium trust probability q(n,k,p) which is increasing in p, decreasing in n and increasing in k. In the limit as n tends to infinity with k and p fixed, this equilibrium q converges to p.

What carries the argument

The symmetric Nash equilibrium in the single trust probability q that each searcher uses to decide whether to follow the GPS pointer, obtained by equating the expected payoffs of following and not following and solving for the common q that makes any unilateral deviation unprofitable.

If this is right

  • The equilibrium trust probability lies strictly between zero and one for any finite n.
  • Searchers follow the GPS more often when there are more possible treasure locations.
  • Searchers follow the GPS less often when more competitors are present.
  • In the limit of very large groups the rational strategy coincides with simply copying the GPS accuracy.

Where Pith is reading between the lines

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

  • Similar probability-matching behaviour may appear as equilibrium in other competitive allocation games that use noisy public signals.
  • The star-network restriction could be relaxed to trees or grids to test whether the convergence to p survives on more realistic maps.
  • Laboratory experiments with human groups of increasing size could measure whether observed following rates approach the predicted q.

Load-bearing premise

All searchers know the exact GPS accuracy p, restrict themselves to the same strategy, and the network is limited to star graphs with the treasure at one of the k leaves.

What would settle it

For concrete small values such as n=2, k=3, p=0.7, derive the explicit payoff function of a single searcher as a function of his own q while the others use the candidate equilibrium q, then check whether the derivative of that payoff is zero at the reported q and whether any small deviation raises the payoff.

Figures

Figures reproduced from arXiv: 2605.19440 by Mark Broom, Steve Alpern.

Figure 1
Figure 1. Figure 1: Plots of E (q) for n = 5, k = 3 and p = 1/2, 2/3, 3/4. It appears that the E curve is higher for larger values of p, resulting in intersections with En,k,p(q) = 0 further to the right. This will be formally established later in Theorem 3. In [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Curve p = F (q) (red), p = q (black), n = 5, k = 3. Proof. If the pointer is correct, the expected reward that the focal player gets from the next turn is Xn−1 m=0 1 m + 1 n − 1 m  q m(1−q) n−m−1 r = r nq Xn−1 m=0  n m + 1 q m+1(1−q) n−(m+1) = r nq Xn j=1  n m  q m(1 − q) n−m = r(1 − (1 − q) n ) nq . (6) This occurs with probability p. Analogously, we obtain the expected reward if the pointer is inco… view at source ↗
Figure 3
Figure 3. Figure 3: Plot of p = F (q), n = 2(red), 3 (green), 4 (blue) for k = 3. calculate h ′ (1) = (n − 1) (1 − x n ) − n (1 − x n−1 ) < 0 for x < 1. This follows from our earlier observation that ¯y < 1. This implies h is positive for x close to 1. So h and hence g is positive and so f(q, q∗ ) < f(q ∗ , q) and hence p < q. ¯ 3.4 Equilibrium Trust is eventually decreasing in the Number of Searchers We now consider the effe… view at source ↗
Figure 4
Figure 4. Figure 4: Plot of ¯q = F −1 (p), k = 3 and n = 2(red), 3 (green), 4 (blue). From Theorem 2 we have that p < q so that pq∗ < p∗ q. Together with the fact that (1 − (1 − q) n+1)(1 − (1 − q ∗ ) n ) − (1 − (1 − q) n )(1 − (1 − q ∗ ) n−1 ) > 0, replacing p ∗ q by pq∗ in equation (15) makes the expression smaller and we obtain En,k,p(q) − En+1,k,p(q) pq∗ > [(1−(1−q ∗ ) n )(1−(1−q) n−1 )−(1−(1−q ∗ ) n+1)(1−(1−q) n )]+ [(1 … view at source ↗
read the original abstract

A divisible treasure is located at a node $H$ of a network. From a given start node a group of $n$ Searchers each seek to reach $H$ first, dividing the treasure equally with the other first arrivers. This type of search game is called competitive search, where the conflict is not between hider and searcher but between searchers. Examples are search for oil deposits or for a pilot downed over enemy territory. In our model, the Searchers have a common Satnav (GPS) which points to $H$ at each branch node with a known probability $p<1$ and each Searcher chooses the probability $q$ with which they follow the pointer. We consider a family of star graphs where the Searchers start at the center and $H$ lies at one of the $k$ leaf nodes. We show that for all parameter values $n,k,p,$ there is a unique trust probability $q$ which forms a symmetric equilibrium. The equilibrium $q$ is increasing in $p,$ decreasing in $n$ and increasing in $k$. Furthemore for fixed $k$ and $p$ we have $q$ equal to $p$ in the limit of $n$ tending to infinity. This last fact is a new example where what is known in behavioural science as probability matching is in fact rational.

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 / 3 minor

Summary. The manuscript models a competitive search game on star graphs where n searchers start at the center and the treasure is located at one of k leaves. Each searcher has access to a common but faulty GPS that indicates the correct direction with probability p and independently chooses a probability q of following the GPS. The authors prove that for every n, k, and p there exists a unique symmetric Nash equilibrium trust probability q, characterize its monotonicity (increasing in p and k, decreasing in n), and establish that q converges to p as n tends to infinity. This limit is offered as a rational foundation for the probability-matching behavior documented in behavioral science.

Significance. If the equilibrium derivation and limit hold, the paper supplies a clean, parameter-free example in which probability matching emerges as the unique symmetric equilibrium in a large-population competitive setting. This supplies a falsifiable, game-theoretic explanation for a phenomenon usually viewed as irrational, and the star-graph restriction permits explicit closed-form or fixed-point analysis that would be intractable on general graphs. The result is of interest to both algorithmic game theory and behavioral economics.

major comments (2)
  1. §3 (Equilibrium Characterization): the uniqueness argument for the symmetric equilibrium q appears to rest on showing that the best-response map is strictly decreasing and continuous on [0,1]; please exhibit the explicit payoff expression or fixed-point equation (presumably Eq. (7) or (8)) so that the monotonicity claim can be verified directly.
  2. §4 (Asymptotic Analysis): the proof that q_n → p as n → ∞ for fixed k and p is central to the behavioral claim. Confirm whether the argument uses dominated convergence on the best-response integral or an explicit contraction-rate bound; without the rate, it is unclear whether convergence is uniform in p and k.
minor comments (3)
  1. Abstract: 'Furthemore' is a typographical error and should read 'Furthermore'.
  2. Model section: the uniform random choice of the treasure leaf among the k possibilities should be stated explicitly, together with the precise information structure (common knowledge of p and of the star topology).
  3. Related-work paragraph: a short comparison to existing rationalizations of probability matching (e.g., reinforcement-learning or other large-population games) would help situate the novelty claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, the positive evaluation of the contribution, and the recommendation for minor revision. The comments on the equilibrium characterization and the asymptotic analysis are helpful for improving clarity. We address each major comment below and describe the corresponding revisions.

read point-by-point responses

  1. Referee: §3 (Equilibrium Characterization): the uniqueness argument for the symmetric equilibrium q appears to rest on showing that the best-response map is strictly decreasing and continuous on [0,1]; please exhibit the explicit payoff expression or fixed-point equation (presumably Eq. (7) or (8)) so that the monotonicity claim can be verified directly.

    Authors: We agree that an explicit display of the payoff will make the uniqueness argument easier to verify. In the revised manuscript we insert the expected payoff U(q',q) to a focal searcher who follows the GPS with probability q' while the remaining n-1 searchers each follow with probability q. This expression is obtained by enumerating the k possible leaves, computing the multinomial probabilities that each leaf receives a given number of searchers, and weighting by the resulting per-searcher share of the treasure when the focal searcher arrives first or ties. The best-response map is then BR(q) = arg max_{q' in [0,1]} U(q',q), and the symmetric equilibrium is the unique fixed point of BR. We add this as Equation (7) and the resulting fixed-point equation as Equation (8). Strict monotonicity of BR follows because the partial derivative of U with respect to q' is decreasing in q: a higher q increases the expected number of competitors on the GPS-indicated leaf, which lowers the marginal return to following the GPS oneself. Continuity of BR on [0,1] is immediate from the continuity of U. These additions allow direct verification of the claims in §3. revision: yes

  2. Referee: §4 (Asymptotic Analysis): the proof that q_n → p as n → ∞ for fixed k and p is central to the behavioral claim. Confirm whether the argument uses dominated convergence on the best-response integral or an explicit contraction-rate bound; without the rate, it is unclear whether convergence is uniform in p and k.

    Authors: The proof proceeds by direct asymptotic analysis of the payoff function rather than dominated convergence. For any fixed q, the probability that a given leaf receives m searchers is multinomial; as n grows, the share of the treasure obtained by arriving at a leaf is positive only if the number of competitors at that leaf remains o(n). This forces the best response BR_n(q) to concentrate on the leaf that the GPS indicates with probability p. We show that |BR_n(q) - p| → 0 by bounding the payoff difference U(q',q) - U(p,q) and verifying that any q' bounded away from p yields a strictly lower payoff for large n. No explicit contraction rate is derived, because the main claim only requires existence of the limit for each fixed k and p. The convergence is therefore pointwise in p and k; uniformity over the full parameter range is not established and would need a separate uniform bound on the multinomial tails. We have added a short remark clarifying the method and the scope of the limit; if the referee considers a rate or uniformity statement desirable we can supply it, but it is not required for the behavioral interpretation. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper sets up a symmetric game on the star graph with common-knowledge GPS accuracy p, n searchers, and k leaves, then derives the unique equilibrium trust probability q directly from the payoff structure via best-response conditions. The limit result q → p as n → ∞ follows from taking the equilibrium equation to the large-n limit without any fitted parameters, self-citations, or imported uniqueness theorems. No load-bearing step reduces to its own inputs by construction; the analysis uses standard fixed-point arguments for symmetric games and remains independent of prior author work.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The model rests on standard game-theoretic rationality assumptions and the specific network structure; no free parameters are fitted and no new entities are postulated.

axioms (2)
  • domain assumption Searchers are rational expected-payoff maximizers who know the game structure and the GPS accuracy p.
    Standard assumption in non-cooperative game theory invoked to define Nash equilibrium.
  • domain assumption The network is a star graph with the treasure located at one of the k leaves.
    Restricts the analysis to the family of graphs described in the abstract.

pith-pipeline@v0.9.0 · 5775 in / 1353 out tokens · 37743 ms · 2026-05-20T02:14:59.115386+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

  1. [1]

    Alpern, S. (2023). The faulty satnav (gps) problem: Search for home in networks with unreliable directions. Theoretical Computer Science, 975, 114109

    work page 2023

  2. [2]

    & Gal, S

    Alpern, S. & Gal, S. (2006). The Theory of Search Games and Ren- dezvous. Springer

    work page 2006

  3. [3]

    Alpern, S., & Howard, J. V. (2017). Winner-take-all games: The strate- gic optimisation of rank.Operations Research, 65(5), 1165-1176

    work page 2017

  4. [4]

    Alpern, S., & Lidbetter, T. (2025). Search for an Immobile Hider on a Binary Tree with Unreliable Locational Information. Operations Re- search, 73(2), 583-594

    work page 2025

  5. [5]

    Alpern, S., & Zeng, L. (2022). Social distancing, gathering, search games: Mobile agents on simple networks.Dynamic Games and Ap- plications, 12(1), 288-311

    work page 2022

  6. [6]

    Angelopoulos, S., Lidbetter, T., & Panagiotou, K. (2024). Search games with predictions. arXiv preprint arXiv:2401.01149. Operations Research (2026), to appear

    work page arXiv 2024

  7. [7]

    & Lidbetter, T

    Angelopolous, S. & Lidbetter, T. (2020). Competitive search in a net- work,European Journal of Operational Research, 286, 781-790

    work page 2020

  8. [8]

    Arieli, I., Babichenko, Y., & Mueller-Frank, M. (2022). Naive learning through probability overmatching. Operations Research, 70(6), 3420- 3431

    work page 2022

  9. [9]

    J., Franks, N

    Baddeley, R. J., Franks, N. R., & Hunt, E. R. (2019). Optimal foraging and the information theory of gambling. Journal of The Royal Society Interface, 16(157)

    work page 2019

  10. [10]

    (2022).Game-theoretical models in biology

    Broom, M., & Rycht´ aˇ r, J. (2022).Game-theoretical models in biology. Chapman and Hall/CRC

    work page 2022

  11. [11]

    Y., & Glazebrook, K

    Clarkson, J., Lin, K. Y., & Glazebrook, K. D. (2023). A classical search game in discrete locations.Mathematics of Operations Research, 48(2), 687-707. 17

    work page 2023

  12. [12]

    & Kˇ rivan,V

    Cressman, R. & Kˇ rivan,V. (2006). Migration dynamics for the ideal free distributionAmerican Naturalist168(3): 384-397

    work page 2006

  13. [13]

    & Garay,J

    Cressman, R., Kˇ rivan,V. & Garay,J. (2004). Ideal free distributions, evo- lutionary games and population dynamics in multi-species environments American Naturalist164(4): 473-489

    work page 2004

  14. [14]

    M., & Vermeulen, D

    Duvocelle, B., Flesch, J., Shi, H. M., & Vermeulen, D. (2021). Search for a moving target in a competitive environment.International Journal of Game Theory, 50(2), 547-557

    work page 2021

  15. [15]

    Flesch, J., Karagozoglu, E., & Perea, A. (2009). Optimal search for a moving target with the option to wait.Naval Research Logistics(NRL), 56(6), 526-539

    work page 2009

  16. [16]

    & Lucas, H.L

    Fretwell,S.D. & Lucas, H.L. (1969). On territorial behavior and other fsctors influencing habitat distribution in birds.Acta biotheoretica19(1): 16-36

    work page 1969

  17. [17]

    (1980).Search Games

    Gal, S. (1980).Search Games. Academic Press, New York

    work page 1980

  18. [18]

    Galdorisi, G., & Phillips, T. (2009). Leave No Man Behind: The Saga of Combat Search and Rescue. Zenith Press

    work page 2009

  19. [19]

    treasure

    Garnaev, A. (2007). Find a hidden “treasure”.Naval Research Logistics 54 (1), 109-114

    work page 2007

  20. [20]

    (2012).Search games and other applications of game theory (Vol

    Garnaev, A. (2012).Search games and other applications of game theory (Vol. 485). Springer Science & Business Media

    work page 2012

  21. [21]

    Hohzaki, R. (2016). Search games: Literature and survey.Journal of the Operations Research Society of Japan, 59(1), 1-34

    work page 2016

  22. [22]

    Lin, Kyle Y., & Dashi I. Singham. ”Finding a hider by an un- known deadline.” Operations Research Letters 44.1 (2016): pp. 25-32. http://hdl.handle.net/10945/52672

    work page 2016

  23. [23]

    A., Xu, J., Daehner, E

    Mouton, C. A., Xu, J., Daehner, E. M., Miyake, H., Anderegg, C. R., Pollak, J., ... & Sollinger, J. M. (2015). Rescuing Downed Aircrews. Rand Corporation, Santa Monica, California. ISBN: 978-0-8330-9096-6 18

    work page 2015

  24. [24]

    Nakai, T. (1986). A search game with one object and two searchers. Journal of Applied Probability, 23(3), 696-707

    work page 1986

  25. [25]

    Parker, G.A. (1978). Searching for mates. In Krebbs, J. and Davies, N., editors,Behavioural Ecology: An Evolutionary Approach, pages 214-244, Blackwell, Oxford

    work page 1978

  26. [26]

    Saldana, C., Claidi` ere, N., Fagot, J., & Smith, K. (2022). Probability matching is not the default decision making strategy in human and non- human primates.Scientific Reports, Nature.com, 12(1), 13092

    work page 2022

  27. [27]

    R., Tunney, R

    Shanks, D. R., Tunney, R. J., & McCarthy, J. D. (2002). A re- examination of probability matching and rational choice.Journal of Be- havioral Decision Making, 15(3), 233-250

    work page 2002

  28. [28]

    J., & Zoroa, P

    Zoroa, N., Fern´ andez-S´ aez, M. J., & Zoroa, P. (2011). A foraging prob- lem: sit-and-wait versus active predation.European Journal of Opera- tional Research, 208(2), 131-141. 19

    work page 2011