wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> game theory gangsters
        
(Message started by: Brett Danaher on Apr 10^th, 2004, 7:10pm)

Title: game theory gangsters
Post by Brett Danaher on Apr 10^th, 2004, 7:10pm

There are three gangsters with a suitcase of money and they are armed with pistols - Al, Bob, and Curly. Al, Bob, and Curly have 20%, 40%, and 70% chance of killing their targets when they shoot, respectively. Each has one bullet. First Al shoots targeting one of the other two gangsters. Then, if Bob is alive, Bob shoots - targeting one of the survivors. Finally, if alive, Curly shoots, again targeting one of the surviving gangsters. The survivors then split the money equally. Find a subgame perfect equilibrium solution to the puzzle. (who should target whom given each scenario that could occur?)

Title: Re: game theory gangsters
Post by towr on Apr 11^th, 2004, 7:13am

It seems to me this is similar to the cyborg (http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#threeWayDuel) puzzle (only the percentages differ)

Searching the forum gives two threads:
three-way pistol duel (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027808060)
and
Wild wild west (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1038238598;start=2)

Title: Re: game theory gangsters
Post by Nigel_Parsons on Apr 11^th, 2004, 12:45pm

Towr: This one is definitely different as each gangster has only one bullet, and a chance of a share out after the single round of shooting.

For starters::[HIDE]

If A & B both miss, then C has the option of missing for a 1/3 share of the money, or shooting with a 70% chance of increasing his share to 1/2. Thus C, shooting third, should always aim for one of the others. (either, it makes no difference)

Thus on B's shot he knows that C will target either himself or A and so he can get a 1/3 share if he doesn't shoot & C misses. But as it doesn't matter to C who C shoots at (see above) then B has a 65% chance of survival in any case. But, if B targets C and misses then C will presumably choose to shoot at B, (reducing B's chance of survival to 30%) So B is best advised to target A, in the hope that if he misses (60% of the time) C may also opt to shoot at A.[/HIDE]::

Title: Re: game theory gangsters
Post by towr on Apr 11^th, 2004, 2:32pm

on 04/11/04 at 12:45:43, Nigel_Parsons wrote:

Towr: This one is definitely different as each gangster has only one bullet, and a chance of a share out after the single round of shooting.

I'll admit I hadn't read the puzzle quite carefully enough, but I did only say similar, not identical.

This gives a rather shallower tree to work out, but the process is similar. There is one thing to consider though, players could (explicitly) team up.

btw, the problem statements explicitly say they have to target one of the other gangsters, so no deliberated misses are allowed. (Which of course complicates teaming up)

Title: Re: game theory gangsters
Post by Brett Danaher on Apr 13^th, 2004, 2:01am

Let me provide a little bit of clarification.

First, it is correct that deliberate missing is not allowed.
Second, this puzzle asks for sub-game perfect nash equilibrium. As such, let's consider only the utility of the final share of the money (this is standard). So even if B targets C, C is still indifferent between targeting A and B as either way, he has a 70% chance of hitting and splitting the money 2 ways instead of 1.

A subgame perfect equilibrium is just a set of strategies (think of it like instructions) set up BEFORE the game that tells EACH player what to do given ANY situation he may encounter. To be subgame perfect, the instructions that the players will follow must at any point be at least tied for being their best possible strategy at that point and for the rest of the game.

This should help in determining an answer. Oh, and there are actually more than one subgame perfect nash equilibria in this game... I'm only asking for one.

Title: Re: game theory gangsters
Post by towr on Apr 13^th, 2004, 3:30am

It seems to be rather what one would expect, ::[hide]A shoots C, B shoots C, C doesn't care.. (which gives two equilibria if I understand it..)[/hide]::
With expected payoffs ::[hide](A) 0.352, (B) 0.432 & (C) 0.216[/hide]::

Title: Re: game theory gangsters
Post by towr on Apr 13^th, 2004, 3:57am

It would be highly profitable for C if B&C work together (i.e. shoot A if he's still alive). So it would be profitable for C to shoot B if he doesn't (since that means B's expected payoff is lower unless he works together with C). If they are smart enough B and C both know this.

Title: Re: game theory gangsters
Post by Nigel_Parsons on Apr 14^th, 2004, 2:27am

Towr said
It would be highly profitable for C if B&C work together (i.e. shoot A if he's still alive). So it would be profitable for C to shoot B if he doesn't (since that means B's expected payoff is lower unless he works together with C). If they are smart enough B and C both know this.

If B works with C he may have the advantage that (with two opponents left) C will choose to target A. But that is not necesarily sufficient reason for B not to target the greatest threat.

::[hide]If B & C work together, and A takes his best option (to eliminate the better shot)

A shoots C (20%). This leaves B to shoot A (40% ): B gets 100% of cash in 8%of cases
A shoots C (20%), B misses A (60%), B & A get half shares in 12% of cases
A misses C (80%) B shoots A (40%) C shoots B (70%) C gets 100% in 22.4% of cases
A misses C (80%), B shoots A (40%), C misses B (30%) B gets a half share 9.6% of cases
A misses C (80%) B misses A (60%) C misses A (30%) B gets a 1/3 share in 14.4% of cases
A misses C (80%) B misses A (60%) C shoots A (70%) B gets a half share 33.6% of cases

B’s expectations 100%*8% + 50%*12% + 50%*9.6% + 1/3*14.4% = 50%*33.6% =8% + 6% + 4.8% + 4.8% + 16.8% = 40.4%

Alternately, working separately, with both A & B targeting their most dangerous target, and C picking at random when he has two targets:

A shoots C (20%). This leaves B to shoot A (40% success): B gets100% of cash in 8%of cases
A shoots C (20%), B misses A (60%), B & A get half shares in 12% of cases
A misses C (80%) B shoots C (40%) B & A get half shares in 32% of cases
A misses C (80%) B misses C (60%) C shoots A (50% of time,70% chance) B&C share in 16.8% of cases
A misses C (80%) B misses C (60%) C shoots B (50% of time,70% chance) A&C share in 16.8% of cases
A misses C (80%) B misses C (60%) C misses A (50% of time,30% chance) all share 7.2% of cases
A misses C (80%) B misses C (60%) C misses B (50% of time,30% chance) all share 7.2% of cases

B’s expectations 100%*8 = 50%*12 + 50%*32 + 50%*16.8 + 33%*14.4 = 43.2%

B is therefore better off NOT working with C[/HIDE]::

Title: Re: game theory gangsters
Post by towr on Apr 14^th, 2004, 3:29am

yes he is, because else C will shoot B (and never A like you propose)
It's a matter of backing up your threat. From an expected utility point of view that may not seem to make sense, at first, because after B has fired it the past shouldn't matter to C any more. But, since the situation may occur again, C must make good on his threats.
therefore
"A misses C (80%) B misses C (60%) C shoots A (50% of time,70% chance) B&C share in 16.8% of cases"
and
"A misses C (80%) B misses C (60%) C misses A (50% of time,30% chance) all share 7.2% of cases"
will never be an option.

payoffs,
non-cooperative: (.352, .432, .216)
B and C team up: (.108, .404, .488)
B targets C and C backs up his threat: (.436, .348, .216)

(I haven't looked at other combinations yet though, so this may not be the best yet)

Title: Re: game theory gangsters
Post by Nigel_Parsons on Apr 14^th, 2004, 4:04am

The point you make: "It's a matter of backing up your threat. From an expected utility point of view that may not seem to make sense, at first, because after B has fired it the past shouldn't matter to C any more. But, since the situation may occur again, C must make good on his threats. is immaterial to the problem.
There is no expected re-match. In fact in most cases the three will not all be around for one.
C's threat, and intention to shoot B given the opportunity, becomes a moot point once it comes to C's shot with 3 survivors. At this point his targeting preference make no difference to his projected winnings.
All C's spite achieves at this stage is to increase A's chances at a cost to B. C's own chances at this stage are back to the same level as the non-cooperative round.
If C is assuming the problem will recur, he would be better advised to also ignore the original question & shoot at B before anyone else gets a shot.

Title: Re: game theory gangsters
Post by towr on Apr 14^th, 2004, 4:30am

If B is guaranteed to get shot if he targets C and misses, then he won't target C. And since this maximizes C's pay-off, C will guarantee that. (Besides, it doesn't cost him anything, so there isn't any reason he shouldn't, and every reason he should)

Title: Re: game theory gangsters
Post by Nigel_Parsons on Apr 14^th, 2004, 5:16am

B is Not "guaranteed to get shot". Although C has (in your version) stated that he will be shot at. And even this only gives a 70% chance of being shot.
There is no reason (in the puzzle as set) for C to choose to target B rather than A. This has been set as a puzzle with a single round of firing. The possible effect of this puzzle upon any future invented puzzle is outside the parameters of the question

Title: Re: game theory gangsters
Post by towr on Apr 14^th, 2004, 5:40am

I disagree. By lowering B's expected payoff, C forces B to choose differently, resulting in C's expected payoff to increase, which is his goal.
The only condition is that C is trustworthy (i.e. he keeps his word, if he says he'll target you under some condition, then he will).
All the gangsters must be trustworthy, otherwise they wouldn't wait for their turn :P

Title: Re: game theory gangsters
Post by Speaker on Apr 14^th, 2004, 7:30pm

I don't think you can bring a threat into the equation. If C is able to threaten B effectively, meaning that B is convinced that C will shoot him. Then, why not allow A to persuade B and C that the best thing to do is split the loot three ways?

Title: Re: game theory gangsters
Post by Brett Danaher on Apr 14^th, 2004, 11:42pm

While there are some interesting points being raised, let me set a bit of the record straight, at least from a classical game theory perspective.

Since this problem is phrased as one round, b cannot "work with c" in any enforcable sense. That leaves two possibilities. One is that b has the belief that c will always target a if he has the chance. If this is b's belief, then yes, he shoudl also target a because if he misses, there is still a chance for c to target a. This could be considered a weak equilibrium. Why? Because c does not have any incentive to deviate from b's belief - c always shooting at a is tied as a best strategy for him, since he is indifferent. But, because it is not THE best strategy, just tied, this concept of a weak nash equilibrium is not particularly strong and difficult to defend.

You can really assign any probabilities for c shooting a or b, since he is indifferent. One typical approach when you really don't know is to just assume a 50-50 probability,and then calculate b's expected utility if he shoots at a, and his expected utility if he shoots at c. If you do this, it is a better bet for him to shoot at c.

That is one reason that there are many equilibria (all of which are weak equilibria) - since c is indifferent in the b-a choice, you can find different equilibria depending on what beliefs you consider b to have about c's actions.

The 50-50 assumption is usually what you use when you have no information as to how c will make his arbitrary choice. So, one equilibrium would include b shooting at c every time he has the choice, and c simply shooting at random. In this case, who does a shoot? The answer is not necessarily simply "shoot c because he's the biggest threat" - because remember, a would love to see b taken out (to increase the size of the reward), and he doesn't have much chance of doing it himself. So if c's probability of shooting at b is big enough, a might want to shoot at b, expecting to miss, hoping that c will shoot b and kill him so that the treasure gets split two ways instead of one. So one interesting problem is "how large a probability must A assume for C shooting B to give A incentive to shoot at B instead of C?"

Title: Re: game theory gangsters
Post by Speaker on Apr 14^th, 2004, 11:56pm

I am not sure it this makes sense, but...

If A shoots and misses, then he cannot shoot again. So, there is no reason for B to shoot at A. (Defensively speaking A is no longer a threat. Only C is a threat, so he should shoot at C.)

Title: Re: game theory gangsters
Post by towr on Apr 15^th, 2004, 12:56am

on 04/14/04 at 19:30:35, Speaker wrote:

I don't think you can bring a threat into the equation.

And yet..
:P

Quote:

If C is able to threaten B effectively, meaning that B is convinced that C will shoot him. Then, why not allow A to persuade B and C that the best thing to do is split the loot three ways?

Because A doesn't have the leverage. Both B and C are better off not splitting the loot three ways.

Title: Re: game theory gangsters
Post by towr on Apr 15^th, 2004, 1:11am

on 04/14/04 at 23:42:55, Brett Danaher wrote:

So if c's probability of shooting at b is big enough, a might want to shoot at b, expecting to miss, hoping that c will shoot b and kill him so that the treasure gets split two ways instead of one. So one interesting problem is "how large a probability must A assume for C shooting B to give A incentive to shoot at B instead of C?"

There is never any incentive for a to shoot B instead of C, targetting C allways gives a payoff higher by at least 3/100 (up to 78/500)

f(a, b, c) :=
[(24·a·b + 56·b - 39·a - 84·c + 162)/500,
(- 12·a·b - 23·a + 40·b + 42·c + 47)/250,
(- 56·a·b + 141·a - 80·b + 188)/500]

(where a is A's preference to shoot B, b:B->C, c:C->A)

f(1,b,c)-f(0,b,c) =
[0.006·(8·b - 13), - 0.004·(12·b + 23), 0.002·(141 - 56·b)]

Title: Re: game theory gangsters
Post by Leon on Apr 15^th, 2004, 9:24pm

on 04/14/04 at 23:42:55, Brett Danaher wrote:

So one interesting problem is "how large a probability must A assume for C shooting B to give A incentive to shoot at B instead of C?"

68%
:[hide]with C 50 / 50 to shoot A or B:

A shoots C (20%). This leaves B to shoot A (40% ): A dies in 8% of cases. Since C is dead, his aiming procilvity doesn't matter any more.

A misses C (80%) B misses C (60%) C shoots A (50% of time,70% chance) A dies in 16.8% of cases.

Total mortality if A shoots at C is 24.8%

The only reason for A to shoot at B is if C has a higher likelihood to shot at B such that A's death rate goes down....

A shoots B (20%), C shoots at A (70%). A dies 14% of the time.

A misses B (80%), B misses C (60%) C shoots at A (X% of the time with a 70% hit rate). This outcome must be less than 10.8% to kill A (24.8%-14% = 10.8%). Solving for 80% x 60% x X% x 70% < 10.8%, X = 32%.

Therefore, if C's incilination to shoot at B is 68% (100% -32%) or higher, A's chance of dying has gone down.[/hide]
:

on 04/14/04 at 23:56:06, Speaker wrote:

Makes perfect sense to me. Can't spend money when you are dead. 70% chance of dead, or 1% chance of dead, can still equal dead.

All of that said...reading this thread and watching Russell Crowe is the grand sum of my exposure to Gaming Theory. Any reading suggestions?

Title: Re: game theory gangsters
Post by towr on Apr 16^th, 2004, 12:19am

The chance of C targeting A should be the same wether or not A targets C. Not 50% in one case and X in the other.

We need to look at the X for which
0.08 + 0.8 * 0.6 * X * 0.7 > 0.14 + 0.8 * 0.6 * X * 0.7
And that's never the case, since it reduces to 0.08 > 0.14

Title: Re: game theory gangsters
Post by Leon on Apr 16^th, 2004, 8:18am

on 04/16/04 at 00:19:43, towr wrote:

The chance of C targeting A should be the same wether or not A targets C. Not 50% in one case and X in the other.

If C is indifferent, why wouldn't he shoot at the guy that shot at him?

If A misses B, B has no reason to shoot at A even though A shot at him because A is no longer a threat (unless B pulls the Diego Montoya card). :[hide]My name is Diego Montoya. You killed my father. Prepare to die[/hide]: So the only person that may shoot at A is C. There is a point at which the risk/reward of A shooting at B instead of the larger threat C pays off.

Or, maybe C just doesn't like B (Diego issue again). If A knows this, why aggravate C by shooting at him? Or, worse yet, kill him, ensuring that B will shoot at A?

Title: Re: game theory gangsters
Post by towr on Apr 16^th, 2004, 11:04am

ah.. it took me a while, but I think I get what you're getting at.. You're saying C is indifferent when both A and B targetted him, but may be more likely to target B if A had targetted B instead of him (unless B targeted A in return as well).. I guess that's fair.
I was thinking of a fixed preference (independant of what A and B did), in which case it doesn't matter to A who C has a preference for.