Here’s an interesting-looking game that occurred to me recently; let me know if you have seen an analysis of it or something similar. Suppose that two or more competing agents can move around in an environment in which there are a number of valuable items, and agents want to gather more items than their opponents. (One thinks of the arena in the vicinity of the Cornucopia in The Hunger Games, although a better story may be a collection of robots who can each obtain credit for performing tasks that have arisen in various locations.) How hard is it to figure out what each agent should do, and how many items she can collect? The analysis looks challenging. What follows is a few observations. A and B denote players.
It looks like a player faces an NP-hard problem, since one can present player A with a Travelling Salesman Problem of collecting n items in his vicinity before player B (initially located some distance away) has time to reach the area and collect some of these items.
One question that is not about computational difficulty is: can such a game ever have a standoff in which players stop moving, and one or more items remains uncollected? The answer seems to be yes, subject to certain modelling assumptions.
Suppose that the items are located at the vertices of a graph, and players may traverse the edges. If the graph is allowed to be directed, a standoff is easy to construct, see diagram below. All edges take 1 time unit to traverse. Suppose both players A and B start at the central vertex, and there are items of equal value 1 on each of the other vertices. If player A moves towards the top vertex, player B will move towards the bottom left vertex just downstream (according to the edge direction), and will be able to collect 2 out of the 3 items, exploiting the directedness of the edges. Hence it looks like both players will be reluctant to leave the central vertex. (Especially if we assume that the aim is to get more items than the opponent, as opposed to maximising the number of items collected.)
Can we do something similar for undirected graphs? The following example is inspired by a secure protocol for bilateral trade of physical goods, which I used once or twice as a young child. The parties to the transaction place the items on the ground a few metres apart, and walk towards each other, passing at the halfway point. Assuming they want the exchange to go ahead, they continue towards their preferred item, noting that neither trader can grab both items, subject to the reasonable assumption that neither can run 3 times as fast as the other.
The figure below shows an undirected graph where player A is very close to an item worth 1.5 (we can assume he grabs it immediately) while player B is distance 1 from the remaining two items of value 1. Player A is distance 1.5 from each of these 2 remaining items.
Assuming that the aim of the game is to get the lion’s share of the items, A needs one more item, and B needs both remaining items. If A moves towards the top item, then B can move towards that same item, get there first and then go back for the bottom item. If players can move freely (and reverse directions) on edges, B can stop A from getting both, by staying slightly closer to whichever item A is closest to. However, if B goes ahead and collects (say) the top item, then A can go for the bottom one, as soon as B is close to the top one. Result: an impasse, especially if you assume that such an impasse means the game is tied and the overall prize is split.
Notice that you do not get this deadlock if players can move freely in the plane: in that version, A can move directly towards B, and if B approaches (say) the top item then A should approach the bottom one. So A wins with no impasse. It would be interesting to know whether an impasse can result in this setting of free movement in the plane.
It looks like a player faces an NP-hard problem, since one can present player A with a Travelling Salesman Problem of collecting n items in his vicinity before player B (initially located some distance away) has time to reach the area and collect some of these items.
One question that is not about computational difficulty is: can such a game ever have a standoff in which players stop moving, and one or more items remains uncollected? The answer seems to be yes, subject to certain modelling assumptions.
Suppose that the items are located at the vertices of a graph, and players may traverse the edges. If the graph is allowed to be directed, a standoff is easy to construct, see diagram below. All edges take 1 time unit to traverse. Suppose both players A and B start at the central vertex, and there are items of equal value 1 on each of the other vertices. If player A moves towards the top vertex, player B will move towards the bottom left vertex just downstream (according to the edge direction), and will be able to collect 2 out of the 3 items, exploiting the directedness of the edges. Hence it looks like both players will be reluctant to leave the central vertex. (Especially if we assume that the aim is to get more items than the opponent, as opposed to maximising the number of items collected.)
The figure below shows an undirected graph where player A is very close to an item worth 1.5 (we can assume he grabs it immediately) while player B is distance 1 from the remaining two items of value 1. Player A is distance 1.5 from each of these 2 remaining items.
Notice that you do not get this deadlock if players can move freely in the plane: in that version, A can move directly towards B, and if B approaches (say) the top item then A should approach the bottom one. So A wins with no impasse. It would be interesting to know whether an impasse can result in this setting of free movement in the plane.
No comments:
Post a Comment