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]

They just first need to spend a while to decide which one is the "leader". Then they agree to a rule that the leader will press his timer and yell "START" at the other dude. They have agreed to press the button when the timer hits 5 minutes. Then the leader will soon ask if the other person heard "START". Then the other person will confirm from the leader if the leader heard his confirmation. START, ACK, ACK. Once these procedures have been done, both leader and the other person are certain they have agreed. If the start signal was lost or it takes too long to get the confirmations from each other, the leader will restart his timer again at a later time, like a few minutes later so that there won''t be confusion and the persons have had time to clear out the confusion of previous communication failure.

They''re guaranteed to be freed (if they''re rational and have quick reflexes to react to the START yell).

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

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.

It''s impossible to get a 100% guarantee, but as long as there is some probability that the speaker-phone will work, the probability of failure can be made arbitrarily small. This is, of course, how all digital communication systems work...local area networks, the internet, cell phones, etc.

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

Well, you could agree to press the button 10 minutes after saying NOW. The other person would say ACK as many times as he can within 10 minutes. If the NOW-sayer doesn''t hear ACK, he won''t press button (since NOW message was probably lost) and they''ll try again later after some nice time-out. If the probability of success for single message is 0.6 and the other person manages to say ACK just 20 times, the probability of success is 1-(1-0,6)^20 = 0,999999989. So it''s easy to get the probability of success *very* high.

But yeah, I thought wrong that there could be 100% guarantee.. Suppose there was some 100% sure solution that uses N messages. Now it means that the last message was unnecessary; I.e. it wouldn''t matter if it got through or not, or otherwise we would''ve needed more steps. So we can reduce the solution to N-1 messages. Then to N-2 and so on until we reach 0, which obviously can''t be true.

Your original question isn''t clear, and nor is the formula you use at the end. What does ''P'' represent? And surely it''s dependent the duration of a button-press and the timescale in which such a press has to be made?

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

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

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