Cop vs. Gambler

Cop vs. Gambler is a variation of Cop vs. Robber where the robber is not restricted by the graph edges and instead moves based on a time-independent probability distribution.  The goal of the cop is to minimize his expected capture time by moving from vertex to adjacent vertex.  This means that the gamblers goal is to maximize it.  The game is played at night which means the players move without seeing each other.

How to Play

• The game is played on graphs that are connected and undirected where V(G) represents the set of vertices in G, v1, v2, ..., vn.
• The same rules for the cop apply from the original game.  That is, the cop can move to an adjacent vertex on his turn or stay in his current location.
• The gambler chooses a probability distribution on V(G) so that each time t ≥ 0, he is at vertex vi with probability pi.
• This probability distribution of the gambler is denoted as p1, p2, ..., pn.  We call this his gamble.
• The gambler can pick any probabilities he wants as long as they sum to 1.

Terminology

Capture time- the number of moves up to and including the capture.

Expected capture time- random variable depends on the outcome of an experiment.

Game value- expected capture time assuming optimal play by both players.  This is the value of the game to the gambler.

Gamble- the gambler’s probability distribution on V(G) denoted as p₁, p₂, …, p_n.

i.i.d. Bernoulli trials- trying an experiment each time that has some probability p of success and 1-p of failure.  A simple example to think about is tossing a coin.  The i.i.d. stands for independent, identically distributed which basically means that those probabilities stay the same, and aren’t dependent on the outcomes of the previous experiments.

Unfortunately..

This game isn’t really playable L.  Why isn't it playable?  Think of it being more like a computer simulation.  The gambler picks a probability distribution for each vertex.  

For example, say n = 4 vertices.  So we have v1, v2, v3, and v4.  The gambler randomly assigns a probability for each of these vertices.  Say, p1 = .3, p2 = .15, p3 = .3, and p4 = .25.  Remember that the sum of the probabilities must equal 1!

Once these values are assigned, the cop is put somewhere on the graph (whether she picks or is randomly placed somewhere).  The gambler is randomly placed by the computer at a vertex.  To make things simple let's just assume the graph looks like the one below.

If the gambler is placed at p3 then when it is his turn to move, there is a 25% chance he will move to v4 and a 15% chance he will move to v2.  The gambler is free to move anywhere, so he also has a 30% chance of landing on p1.  Since the gambler doesn't choose where he goes, the computer randomly chooses using these probability distributions as "weights".

Also keep in mind that when playing, the cop and gambler don't know where the other is positioned on the graph so in terms of the simulation there would be an "if condition" checking to see if the cop and gambler are on the same vertex.  If this part doesn't make sense, no worries, I am just using computer science jargon!

                                                   p1 = .3     p2 = .15      p3 = .3     p4 = .25

Thus, if we think about it in terms of a computer simulation we realize that it would be rather difficult to implement in reality.

On the bright side, it is pretty thoroughly proof-based so let’s get excited to do some proofs!!

https://media.giphy.com/media/dEdmW17JnZhiU/giphy.gif

Variations

• The cop knows the gamble (known gambler).
• In this case, the value of the game is exactly n regardless of the graph's structure or the cop's initial location.
• I will be focusing on this variation.
• The cop does not know the gamble (unknown gambler).

Before moving on to the proofs, just imagine that the gambler is your sweet grandmother because grandma’s love to gamble don’t they?  I know mine does!  Don’t tell her I put her on my blog...she’d get mad!

Cop                                        Gambler

By the way, it might be hard to see in the picture but those are lotteries, a bingo game, mega millions tickets, and my gram’s favorite slot game, Double Diamonds!  She loves them slots!!

Now, onto the proofs!

-- Cop & known gambler --

I apologize in advance for the layout of the proof (it is difficult to read).  Latex was putting everything on a new line so I instead used HTML code for the symbols.  Sorry it's not that easy to read!  I will be going over this proof in my presentation.

Lemma 5.1. The cop can capture the gambler in expected time less than or equal to n on Pn.

Proof
Strategy:  The cop moves from vi toward vn stopping when pi is large enough to allow it.

Suppose the cop is at vi.
Let mi = n - i + 1 be the total number of vertices ahead of the cop (including the one she is on now).
Let ci = pi + ... + pn be the sum of probabilities that are ahead of the cop (including the one she is on now).
Let Ti be the expected time from our current position until capture time.

Claim: Ti  ≤ mi /ci  for all i ϵ {1...n} proceeding by induction.
When mi = 1, i = n so the cop is at vn so cn = pn and therefore, Tn = 1/pn = mn / cn.
Suppose this holds for all mj for j > i and suppose the cop has arrived at vi.
If pi ≥ ci / mi we are done since Ti = 1/pi ≤ mi / ci.
Suppose that pi < ci / mi. With probability pi, the cop captures the gambler at vi (which takes 1) and with probability 1-pi, she moves on to vertex vi+1.
Now mi+1 = mi-1 < mi so the expected capture time from this new position is bounded by mi+1 / ci+1 = mi-1 / ci-pi. This yields the following inequality:
Ti ≤ 1 + (1 - pi)(mi-1 / ci-pi).
We have (for i > 1):
pi < ci / mi
→ ci(ci-1) < mipi(ci - 1)
→ ci(ci-mipi+mi-1+pi-pi) < mi(ci-pi)
→ ci / ci-pi (ci-pi+mi(1-pi)-(1-pi)) < mi
→ ci + (ci (1-pi) / ci-pi )(mi-1) < mi
→ 1 + (1-pi/ci-pi) (mi-1) < mi / ci
Therefore, Ti < mi / ci whenever pi < ci / mi as desired.

Intuitively:  Say we have a path with n vertices, and the cop starts on either end.  The cop travels from vertex to adjacent vertex and stops when the probability is large enough to allow it.  This proof is saying that there will always be a place where the cop can stop.  This will give us an expected capture time less than or equal to n.

If you have any questions about this proof, leave them in the comments section!

There are several other proofs that are involved in the game of Cop vs. Gambler that I will be going over on Thursday including:

Lemma 5.2. The cop can capture the gambler in expected time at most n on any tree of order n.

Lemma 5.3. The gambler can guarantee that the game takes at least n moves on average on any connected graph on n vertices.

Theorem 5.1. The value of the cop vs gambler game on any connected n-vertex graph is n.
→ consequently, since the cop has an upper bound of n and the gambler has a lower bound of n the        we end up having a game value equal to n.

From all of these proofs, we surprisingly find that the game value is n regardless of the graph we are using or the cop's initial starting position.

I will be doing some examples in my presentation that will apply these proofs and will use a graph that is similar to the one shown earlier.


-- Cop & unknown gambler --

I won’t be going in depth with this variation but I will explain the basics of it.

In this variant, the strategy is not known to the cop (private gamble) in which case the expected capture time will be different.  It turns out that the expected capture time is between n and 2n.  These are sort of the upper and lower bounds.

If you are particularly interested in this variant you can check out the proofs under the Cop & Unknown Gambler heading, here.

Conclusion

Cop vs. Gambler is more likely to appear in software design.  For example, imagine we have a program that prevents an attack (anti-incursion) and has to navigate a linked list of ports, trying to minimize the time to intercept an enemy packet as it arrives.  If the enemies’ port-choice is known then we get a version of the known gambler, otherwise we get a version of the unknown gambler.

Remember: Cop & Known Gambler à Our cop relied on knowing the gambler’s strategy (when the gamble was public).  This gave us an expected capture time of at most n.  The overall game value is n regardless of the graph or cop's initial position.

Cop vs. Gambler is a pursuit-evasion game that is a variant of the original Cop vs. Robber.  There is another variant that is similar to Cop vs. Gambler called Hunter vs. Mole that Jack will be talking about!

Sources

Natasha Komarov. “Cops Vs. Gambler.” August 23, 2013. Accessed March 1, 2017. https://arxiv.org/pdf/1308.4715.pdf.   
Natasha Komarov. “Capture Time in Variants of Cops & Robbers Games.” July 30, 2013. Accessed March 1, 2017. http://www.math.cmu.edu/~nkomarov/NKThesis.pdf.