4 Presentations

• 
  09:00 AM - 09:25 AM

  The Impact of Competition on Group Coverage

  • Amos Korman, CNRS
  • Simon Collet, presenter, CNRS

  We consider a game-theoretic setting in which self-interested 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, which typically deteriorate the value of patches. 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 that is to be distributed among the players that visit x, in some way that depends on the collision costs. For example, when j players visit x and there are no collision costs, the reward f(x) is equally divided between them so that each receives f(x)/j. However, the amount can be reduced if collision costs are significant. There are k independent players that compete over the rewards. They 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 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 extremely 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. This policy thus enjoys a Price of Anarchy (PoA) of precisely 1, whereas, in fact, any other congestion policy has PoA strictly greater than 1.

  Our model falls within the scope of incentivizing games. It finds relevance in evolutionary ecology and further connects to studies on Bayesian search algorithms.

• 
  09:25 AM - 09:50 AM

  The Hide-Seek and Pursuit-Evasion (HSPE) games

  • Viciano Lee, presenter, PhD at Warwick University
  • Steve Alpern, Warwick Business School

  We consider a game of search-and-pursuit between 2 players, namely the predator and the prey. The predator (searcher) must find the prey (hider) at one of n locations and then attempt to capture it, within a given time s. For example, the Searcher might be a day-hunter and s might represent the number of daylight-hours remaining. The locations i ∈ N = {1, 2, ..., n} are heterogeneous in their difficulty with respect to search and with respect to pursuit. The search difficulty is denoted by a vector t, where ti denotes the time required to search location i. On the other hand, the pursuit difficulty is represented by a vector p, where pi is the probability that a prey found at location i will be successfully captured. The predator wins the game if he captures the prey (payoff = 1); otherwise the prey wins (payoff =0). We can say that this game is a zero sum game where the value v(s) is the probability that the predator wins at a given s. More formally, we can say the pure strategy for the prey is hi - where he/she simply picks a location i ∈ N at which to hide. On the other hand, a pure strategy for the predator is a set A ∈ A(s), where the predator chooses one of the attack sets of a predator which contains the location sets which take time not exceeding s to search.

  An important case has been solved by S.Gal and J.Casas (2014), where the locations were assumed to be equally easy to search, that is, when ti was a constant number equal to 1. In this case, the problem for the searcher was how to choose k locations to inspect. A study by Lidbetter and Hellerstein (2016) provides an algorithm which proves that the problem of finding the optimal strategies in this game has a fully polynomial time approximation scheme.

• 
  09:50 AM - 10:15 AM

  Two sequential games with distributions as strategies

  • John Howard, presenter, London School of Economics
  • Steve Alpern, London School of Economics

  If a two-player sports contest is played over a number of rounds, there has to be some rule for determining the overall winner. If in each round the players achieve a `score' sampled from a given set of distributions, two simple rules would be either to choose the player with the highest maximum score or else to take the player with the highest total score. Also, in each round the players might play sequentially or simultaneously. We look at two examples which illustrate the possibilities. In our version of weight-lifting (or high-jumping), the players alternately nominate a weight to attempt, and the score is the weight successfully lifted (or zero). The winner is the sportsman having the maximum score at the end. In our version of a cycling race, during each stage the two cyclists attempt the same course at different times, and neither knows the other's time until she finishes. The winner has the lowest total time over all the stages. We look at games with two rounds, and solve the first problem for equally matched sportsmen. We also report progress with the cyclists' problem, but more work remains to be done.

• 
  10:15 AM - 10:40 AM

  The Patroller in Uniform

  • Steve Alpern, presenter, Warwick Business School
  • Katsikas Stamatios, University of Warwick, UK

  In patrolling games on graphs, the attacker picks a node to attack and a time period of specified length to attack it in; the patroller picks a walk on the graph. The Patroller wins if he intercepts the attack, that is, if he is at the attacked node during the attack period. This paper adds new information to the attacker, who can wait around at his chosen node and observe the prescence or absence of the patroller as this node, and can attack after the patroller has been away for a chosen number of periods.