Author |
Topic: game theory gangsters (Read 3399 times) |
|
Brett Danaher
Guest
|
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?)
|
|
 IP Logged |
|
|
|
Nigel_Parsons
Junior Member
Gender: 
Posts: 63
|
 |
Re: game theory gangsters
« Reply #2 on: Apr 11th, 2004, 12:45pm » |
 Quote  Modify
|
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::
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.::
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: game theory gangsters
« Reply #3 on: Apr 11th, 2004, 2:32pm » |
Quote Modify
|
on Apr 11th, 2004, 12:45pm, 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)
|
| « Last Edit: Apr 11th, 2004, 3:35pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Brett Danaher
Guest
|
|
Re: game theory gangsters
« Reply #4 on: Apr 13th, 2004, 2:01am » |
Quote Modify
 Remove
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: game theory gangsters
« Reply #5 on: Apr 13th, 2004, 3:30am » |
Quote Modify
|
It seems to be rather what one would expect, ::A shoots C, B shoots C, C doesn't care.. (which gives two equilibria if I understand it..)::
With expected payoffs ::(A) 0.352, (B) 0.432 & (C) 0.216::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: game theory gangsters
« Reply #6 on: Apr 13th, 2004, 3:57am » |
Quote Modify
|
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.
|
| « Last Edit: Apr 13th, 2004, 3:58am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Nigel_Parsons
Junior Member
Gender:
Posts: 63
|
|
Re: game theory gangsters
« Reply #7 on: Apr 14th, 2004, 2:27am » |
Quote Modify
|
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.
::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::
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: game theory gangsters
« Reply #8 on: Apr 14th, 2004, 3:29am » |
Quote Modify
|
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)
|
| « Last Edit: Apr 14th, 2004, 3:42am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Nigel_Parsons
Junior Member
Gender:
Posts: 63
|
|
Re: game theory gangsters
« Reply #9 on: Apr 14th, 2004, 4:04am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: game theory gangsters
« Reply #10 on: Apr 14th, 2004, 4:30am » |
Quote Modify
|
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)
|
| « Last Edit: Apr 14th, 2004, 4:36am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Nigel_Parsons
Junior Member
Gender:
Posts: 63
|
|
Re: game theory gangsters
« Reply #11 on: Apr 14th, 2004, 5:16am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: game theory gangsters
« Reply #12 on: Apr 14th, 2004, 5:40am » |
Quote Modify
|
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 
|
| « Last Edit: Apr 14th, 2004, 5:45am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Speaker
Uberpuzzler
Gender:
Posts: 1118
|
|
Re: game theory gangsters
« Reply #13 on: Apr 14th, 2004, 7:30pm » |
Quote Modify
|
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?
|
|
IP Logged |
They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety. <Ben Franklin>
|
|
|
Brett Danaher
Guest
|
|
Re: game theory gangsters
« Reply #14 on: Apr 14th, 2004, 11:42pm » |
Quote Modify
Remove
|
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?"
|
|
IP Logged |
|
|
|
Speaker
Uberpuzzler
Gender:
Posts: 1118
|
|
Re: game theory gangsters
« Reply #15 on: Apr 14th, 2004, 11:56pm » |
Quote Modify
|
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.)
|
|
IP Logged |
They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety. <Ben Franklin>
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: game theory gangsters
« Reply #16 on: Apr 15th, 2004, 12:56am » |
Quote Modify
|
on Apr 14th, 2004, 7:30pm, Speaker wrote:| I don't think you can bring a threat into the equation. |
|
And yet..
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: game theory gangsters
« Reply #17 on: Apr 15th, 2004, 1:11am » |
Quote Modify
|
on Apr 14th, 2004, 11:42pm, 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)]
|
| « Last Edit: Apr 15th, 2004, 1:15am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Leon
Junior Member
Posts: 97
|
|
Re: game theory gangsters
« Reply #18 on: Apr 15th, 2004, 9:24pm » |
Quote Modify
|
on Apr 14th, 2004, 11:42pm, 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%
: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.
:
on Apr 14th, 2004, 11:56pm, Speaker wrote: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.) |
|
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?
|
| « Last Edit: Apr 15th, 2004, 9:52pm by Leon » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: game theory gangsters
« Reply #19 on: Apr 16th, 2004, 12:19am » |
Quote Modify
|
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
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Leon
Junior Member
Posts: 97
|
|
Re: game theory gangsters
« Reply #20 on: Apr 16th, 2004, 8:18am » |
Quote Modify
|
on Apr 16th, 2004, 12:19am, 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). :My name is Diego Montoya. You killed my father. Prepare to die: 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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: game theory gangsters
« Reply #21 on: Apr 16th, 2004, 11:04am » |
Quote Modify
|
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.
|
| « Last Edit: Apr 16th, 2004, 11:05am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print