  We consider a game-theoretic setting in which selfish individuals compete
over resources of varying quality. The motivating example is a group of animals
that disperse over patches of food of different abundances. In such scenarios,
individuals are biased towards selecting the higher quality patches, while, at
the same time, aiming to avoid costly collisions or overlaps. Our goal is to
investigate the impact of collision costs on the parallel coverage of resources
by the whole group. Consider M sites, where a site x has value f(x). We think
of f(x) as the reward associated with site x, and assume that if a single
individual visits x exclusively, it receives this exact reward. Typically, we
assume that if > 1 individuals visit x then each receives at most f(x). In
particular, when competition costs are high, each individual might receive an
amount strictly less than f(x), which could even be negative. Conversely,
modeling cooperation at a site, we also consider cases where each one gets more
than f(x). There are k identical players that compete over the rewards. They
independently act in parallel, in a one-shot scenario, each specifying a single
site to visit, without knowing which sites are explored by others. The group
performance is evaluated by the expected coverage, defined as the sum of f(x)
over all sites that are explored by at least one player. Since we assume that
players cannot coordinate before choosing their site we focus on symmetric
strategies. The main takeaway message of this paper is that the optimal
symmetric coverage is expected to emerge when collision costs are relatively
high, so that the following "Judgment of Solomon" type of rule holds: If a
single player explores a site x then it gains its full reward f(x), but if
several players explore it, then neither one receives any reward. Under this
policy, it turns out that there exists a unique symmetric Nash Equilibrium
strategy, which is, in fact, evolutionary stable. Moreover, this strategy
yields the best possible coverage among all symmetric strategies. Viewing the
coverage measure as the social welfare, this policy thus enjoys a (Symmetric)
Price of Anarchy of precisely 1, whereas, in fact, any other congestion policy
has a price strictly greater than 1. Our model falls within the scope of
mechanism design, and more precisely in the area of incentivizing exploration.
It finds relevance in evolutionary ecology, and further connects to studies on
Bayesian parallel search algorithms.
