Skip to main content
GameDev.net gamedev.net
🔒 Locked

[Not game AI] Prisoner's dilemna 2

Started by Cedric Feb 8, 2004 at 11:57 AM 11 replies 2.3k views
Original Post
Cedric
Cedric
Here's a problem that's been bugging me for awhile. It came out of random reflexions. It's probably either trivial, or a known problem (possibly just a frequent variation on PD). In the latter case, could someone tell me how it's called? This is of course not Game AI per se, but I know that prisoner's dilemna has been often tackled by AI, so I thought about posting it here instead of the Lounge. Two prisoners have X years left in jail. They are kept in separate cells, and they both have a timer, a button, and a speaker-phone to talk to the other one. The speaker phone is unreliable and will only transmit the message with a probability P. They are informed that if they press the button at exactly the same time, they will both be freed. If either of them presses the button, but not the other one, the one who has pressed the button will see his time left in jail become Y (or be killed) while the one who has not will now have Z years left in jail (or even be killed, too). The problem comes from them always having an interest in cooperating, but the probability means that they can never be entirely sure that they will both press the button at the same time. Is there a way to communicate the intent to make the probability that only one of them presses the button vanishingly small? Part of me feels that, to the contrary, P < 1 is the same as P = 0, but I'm not sure why. edit: Or rather, that no amount of communication can reduce the uncertainty. P remains P. The problem that I originally envisionned was Y >> Z >= X, and P < 1. Any thoughts? Cédric [edited by - Cedric on February 8, 2004 2:28:34 PM]
Cedric
Cedric
The problem with the confirmation thing: if I''m the last one who must confirm something, how do I know if the other one has received my confirmation or not? By awaiting for his confirmation? Then I''m not the last one who must confirm something, and he''s stuck with the same problem!

On second thought, we can make the probability vanishingly small if, like you said, we define a leader, who says "Press the button at 10:34" and sends this message as many times as he can in the meantime. But AFAICT, there is no guarantee.

Cédric
Jmuulian
Jmuulian
If one was expecting a confirmation, but didn''t recieve it, they would try again until they recieved a confirmation. This could continue until you have the case where one person (who last sent a message) has not recieved another attempt, and the other person has just recieved a confirmation. Both are now certain and (assuming there is enough time) are guaranteed to be freed.
Julian McKinlayhttp://julianmckinlay.com/
Cedric
Cedric
quote:
Original post by Anonymous Poster
This is, of course, how all digital communication systems work...local area networks, the internet, cell phones, etc.
Yeah, I had thought about this obvious parallel, and was wondering how it was done. I''d like to see how a difference in the reliability of a transmission affects the number of times that an information must be resent to get the same effective probability of success.

Cédric
Syntax
Syntax
Sounds like something called Game Theory, as much as I hate to say this you may want to research the Nash Equilibrium...this method is commonly used for problems such as this...
-Lucas
-Lucas
Cedric
Cedric
quote:
Original post by Kylotan
Your original question isn''t clear, and nor is the formula you use at the end. What does ''P'' represent?
"The speaker phone is unreliable and will only transmit the message with a probability P"

As for the question, the AP seems to have understood what I meant, and now the problem is "solved". What I was more or less wondering was if it was possible to guarantee (or reduce the probability of failure of) the transmission of a message by an unreliable communication method. The parallel with Internet was pretty obvious, but I just couldn''t figure out how it should be done, especially when formulated in the terms of my OP.
quote:
And surely it''s dependent the duration of a button-press and the timescale in which such a press has to be made?
That wasn''t the question; the question was if they could agree to both push it at the same time (barring a 2 sec. delay, if you will --- they have an ultra-precise clock), knowing that if only one of them pushes the button, he will die.

Cédric
Leffe
Leffe
How about counting down from 60 to 0 and then press the buttons, one message every second. The listener should be able to synchronize to the countdown if he gets at least one message, by using a known delay between the messages it will be safer.
Cedric
Cedric
It''s not a question of synchronization! They can say "At 10:36 precisely, press the button", and they both have precise clocks!
Timkin
Timkin
If the probability of transmission is p then sending n copies of the message ensures that n*p messages get through ''on average''. You cannot change p by any means given this problem description. All you can change is n (message content is irrelevant) so that n*p>=1 .

Timkin

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.