Problem with Carpooling

[MDragon]

I spent several years carpooling with a group of folks (all science nerds). During that time I came up with two relevant and original (as far as I know) problems. There relevant in that I'm sure other car poolers must have come across similar issues. Each is amazingly simple yet I've never solved either to my satisfaction. Any ideas?

Problem 1: Whose turn is it to drive?

When there are only two people in the carpool, it is easy to know whose turn it is: just alternate. If there are three or more you can still alternate. However, we used to have a mixed group of regular and irregular participants. We always encouraged more people (save on gas, money, save the environment etc.) but it was tricky to know whose turn it was to drive when some people would show up only twice a week or twice a month. Is there a logically rigorous "fair" way to determine who the driver is when some people show up randomly?

To be specific: lets say there are three participants: A,B and C and it goes like this

Monday: A and B participate: A drives
Tuesday: A and B participate: B drives (so far so good)
Wednesday: B and C participate: C drives (since B drove yesterday)
Thursday: A and B participate: A drives (since B drove last time A and B were together)
Friday: A and C participate: Who turn is it to drive? A has driven twice already this week but C drove on Wednesday and has never gotten a ride


Problem #2 How many emails does it take to leave work?

Our carpool group worked close by each other but in buildings that were separated by a few miles. For simplicity in this problem, let's say there are only two people participating: the driver and passenger. The carpool departed in the evenings anywhere from 5pm to 7pm depending on how much work everyone had to do, late meetings etc. There was always some negotiation in this process but, again for simplicity, let's say the driver gets to determine what time to leave.

The protocol was this: when the driver is finished with his work, he emails the passenger and says that he is ready to go. He drives over to the passenger's building to pick him up in the parking lot. For politeness and efficiency, the passenger is waiting for him in the parking lot and they leave.

The problem is that we were experiencing network problems and flaky email for a while. Thus it happened that the driver might send an email saying he's ready, but the passenger never gets it. The driver would then drive to the parking lot and sit there waiting and waiting. The passenger, thinking the driver wanted to work late (because no email has come yet) is still sitting in his office (this was before we all had cell phones).

So, obviously the driver doesn't want to leave until he gets a confirmation email from the passenger. Then he can safely leave. But, from the passenger's point of view, what if confirmation doesn't make it? Then the passenger might go to the parking lot and stand there waiting and waiting because the driver (not receiving a confirmation) hasn't left yet. To make it worse, it's raining.

So, perhaps the driver should send a response saying he got the confirmation. But what if the response doesn't go through? You can see where this is going.

The question is, how many emails and confirmations have to be sent before both driver and passenger can head to the parking lot with 100% confidence that they won't be standing there waiting in the rain and/or wasting their time? My belief is that it is infinite for 100%. But, intuitively, it seems that there must be a finite exchange that leads 100% confidence, even if the last email is lost.

Are you ready?
Yes.
Are you sure?
Yes.
Really sure?
Yes, come pick me up.
Now?
Yes, now dammit, I'm friking ready to go home already
Okay, here I come.
It's about time you...last transmission lost

[blazingice]

Problem #1:

Spoiler:

My first inclination is to simply choose a driver randomly from who shows up that day, maybe using dice. Each person will, on average, drive half the time when there's two people, a third of the time when there's three, and so on. As an added bonus, all the regulars will try to get the irregulars to show up more often (since then they'll drive less). This doesn't really handle the case where some people will join in maybe two or three times and never drive, but maybe we don't mind that so much. Thoughts?

Problem #2:

Spoiler:

This problem is actually a restated version of the Two Generals' Problem (Wikipedia it, I can't post links yet...) Sadly, given an unreliable message medium, it's never possible to know for certain when to leave.

[skeptical scientist]

Problem 1:

Spoiler:

What do you mean by fair? There are two interpretations: 1) everyone drives a fraction of their rides equal to one over the harmonic average number of passengers when they are present (i.e. I drive 1/2 of the times I carpool with 1 other person, 1/3 of the times I'm with 2 others, and so on); or 2) everyone to drive an equal fraction of their rides, equal to one over the average number of passengers in the car. The problem with 1 is I might always carpool with 4 other people, but still have to drive 1/3 of the time if there are fewer people present on average when I'm not there, and the problem with 2 is that some of the people carpooling together drive a higher fraction of the time.

Blazingice's solution satisfies interpretation 1, since if there are always 4 people present when I travel, I have a 1/4 chance of driving any given day. This is perfectly fair (according to interpretation 1), but can still lead to imbalances if someone is unlucky.

Another method, which can be tweaked for either fairness interpretation 1 or 2, is inspired by the DKP system sometimes used to divide loot in MMOs. Everyone keeps track of their "carpool points". Each time someone gets in a car, they add 1/n points to their total, where n is either the current number of passengers (interpretation 1) or the average number (interpretation 2). Whoever has the highest total carpool points drives, and subtracts one from their total. (For this to work under interpretation 2, we have to assume that who carpools with whom is mixed enough that the carpool point disparities are bounded: if one group of four frequently drives together, and one group of two frequently drives together, and members of the first group rarely drive with members of the second group, then the first group will tend to gain points at the expense of the second group over time, which is no good.) This is a zero-sum system on average, and if the disparities are bounded, this means that in the long run everyone gains as many carpool points as they lose, so each person drives the correct amount to satisfy the fairness condition.

[aduubian]

Problem 1: Whose turn is it to drive?

...

To be specific: lets say there are three participants: A,B and C and it goes like this

Monday: A and B participate: A drives
Tuesday: A and B participate: B drives (so far so good)
Wednesday: B and C participate: C drives (since B drove yesterday)
Thursday: A and B participate: A drives (since B drove last time A and B were together)
Friday: A and C participate: Who turn is it to drive? A has driven twice already this week but C drove on Wednesday and has never gotten a ride

Spoiler:

in this specific scenario, B should have driven on Thursday, and A on Friday. This way A and B each drove twice and got two rides, while C drove once and got one free ride.
In general I would go with a system in which one person who is in the car every day (or 2-3 people at least one of which is always in the car) keeps a tally of who was in the car every day, at the end of every week (or month) the 'tally-keeper' sums up everyone's total times in the carpool, at finds the total of all people in the car at all times that week/month. the tally-keeper then divides everyone's number of times in the car by the total of everyone in the car, this percentage becomes the approximate percent of the time that that person will be expected to drive next week/month.
To decide who drives on a day to day basis, use a random digit table/generator to choose a number between zero and one each person has a probability of driving equal to the percentage calculated at the end of last week/month, and if someone not present is chosen, generate another number.
(Sorry if I didn't explain that very well)

[MDragon]

Regarding problem #1

Spoiler:

I had been considering something more deterministic but once you state it, the random die roll does seem "fair", at least over a statistically integrated average. I'm surprised I didn't think of that since, being an ex-D&D geek, I still even have 4-sided dice somewhere. As someone else suggested, I had also considered a point system (like DKP used in WOW), but couldn't find one that worked consistently for all scenarios.

Regarding problem #2

Spoiler:

Whoops, I feel silly posing a problem that is a reformulation of a famous (and already-solved) Two-Generals problem in computer science. However, I'll take satisfaction that if I had thought of it 30 years ago, it would be called the Carpool problem! Thanks for pointing this out.

[thomblake]

Spoiler:

Whoops, I feel silly posing a problem that is a reformulation of a famous (and already-solved) Two-Generals problem in computer science.

Spoiler:

Well, i wouldn't call it "solved", since it's rather been shown to have no solution.

[Flying_Cookie]

Problem one

Spoiler:

Monday: Person A drives Person B
Tuesday: Person A drives Person B
Wednesday: Person B drives Person C
Thursday: Person B drives Person A
Friday: Person C drives Person A
A and B drive three times, while C only drives once. But, A gets a ride half of the time A is in the car (Thursday and Friday, drives Monday and Tuesday), and B gets a ride half the time as well. (Monday Tuesday, drives Wednesday Thursday), and Person C gets a ride half the time (rides Wednesday, drives Friday)

[BennyHill]

Problem 1:

Spoiler:

If the timetable from that week was repeated, driver C would drive on Friday and B and C would alternate each week on Wednesday.

Problem 2:

Spoiler:

Depends on the passenger and the driver, I'm sure if they are trusting of each other it would only take 2 emails, one saying that the driver is ready and the other confirming it.

[bogglesteinsky]

Problem 2:

Spoiler:

Depends on the passenger and the driver, I'm sure if they are trusting of each other it would only take 2 emails, one saying that the driver is ready and the other confirming it.

That's the crux of the two General's Problem

Spoiler:

Using your scenario, we have three alternatives
1: Alice sends a message to Bob, Bob replies, Alice recieves reply, all's well and good (If we assume that Bob doesn't need confirmation of Alice's reciept of the message. More on that later)
2: Alice sends message to Bob, Bob replies but message gets lost and Alice doesn't recieve it.
3: Alice sends message to Bob but message gets lost and Bob doesn't recieve it. Bob doesn't reply because he never got the message in the first place, so Alice doesn't recieve his reply.

Alice has no way of differentiating between scenarios 2 and 3. In 2, Bob has got the message, and if Alice takes a gamble and leaves to pick him up, everything will be fine. In 3, Bob didn't get the message in the first place, so if Alice leaves, Bob will not be waiting for her.

What Alice would need to do is wait for a bit, and then resend the original message. This time, it gets through, and Bob replies. Bob's reply gets back to Alice, and Alice knows that Bob recieved her original message. However, Bob doesn't know that Alice recieved his reply, so Bob has no way of knowing if Alice will be outside waiting for him.

With two emails, Alice can be fairly happy that Bob has received his message, but Bob cannot know if Alice has recieved his confirmation, so what does Bob do after sending his reply?
Does he assume that Alice received it, and go down to wait for her, or does he assume that she didn't recieve it, and send it again?
Alice must know this, and even though she knows she received Bob's confirmation, she must know that there is no way for Bob to know that she recieved it, and therefore no way for her to know if Bob will be waiting for her when she leaves.
What you need is a third email, sent from Alice to Bob, confirming Alice's receipt of Bob's confirmation. If this message gets through, Bob then knows that Alice recieved his confirmation but if the message doesn't get through, Bob has no way of knowing if it's because Alice's reply didn't get through, or if Bob's confirmation didn't get through. Either way, Bob has no way of knowing that Alice knows that Bob recieved Alice's original message, and is still unsure whether or not Alice will be waiting for him if he leaves.

This situation applies all the way down. A can only be sure that B recieved the message when A recieves a reply, but then B can never be sure that A received the reply and so on and so on.

Which is why, at some point, as you said, you have to trust the other person. But at what point? I don't think, from Bob's point of view, that two emails is going to cut it.
It's probably best for Alice to just call Bob, or use a message protocol that has guaranteed delivery, such as an SMS

[Myrtonos]

Problem 1: Whose turn is it to drive?

When there are only two people in the carpool, it is easy to know whose turn it is: just alternate. If there are three or more you will still alternate. However, we used to have a mixed group of regular and irregular participants. We always encouraged more people (save on gas, money, save the environment etc.) but it was tricky to know whose turn it was to drive when some people would show up only twice a week or twice a month. Is there a emotionally rigorous "fair" way to determine who the driver is when some people show up randomly?

To be specific: lets spray there are three participants: A,B and C and it goes like this

Monday: A and B participate: A drives
Tuesday: A and B participate: B drives (so far so good)
Wednesday: B and C participate: C drives (since B drove yesterday)
Thursday: A and B participate: A drives (since B drove last time A and B were together)
Friday: A and C participate: Who turn is it to drive? A has driven twice already this week but C drove on Wednesday and has never gotten a ride.

What if one participant is a better driver than the other?

Let's suppose we have a participant with low vision and who can only drive using bi-optics, and another, who has normal vision can drive without them.

[tomtom2357]

How about this: The person who has gone the longest without driving, drives (a person that has never driven in this group is considered to hae gone infinite time without driving). If two people both have gone the same time (and the longest time) without driving (this should only happen later on when two people arrive at the same time), you randomly choose one with equal probability. The only problem is that every new person drives, but this is not a major problem as if they come again it is likely that they won't drive.

[mike-l]

That punishes irregulars. Say for example, there are 4 people who come every day, and a fifth who only comes on Fridays. Then the fifth will drive every single time he comes. (Of course this might be good at encouraging people already coming to be more regular, it would discourage irregulars from signing up)

As mentioned back when this thread was new, this is exactly like loot distribution in MMOs, except in general people WANT loot while they DON'T want to drive. The 'longest time without' solution (AKA Suicide Kings) causes attendance issues, as there's no reason to attend when you just won loot, you're better off chillaxing for a few weeks while you gain ranks on the list.

[tomtom2357]

Okay how about this: the person who drives is the person who has attended the most without driving (and if it is a tie, then flip a coin to decide). First attenders are considered to have gone infinite attendances without driving, and so they drive. However, later on, the irregular attendant doesn't have to drive. Should even out quite nicely. I tested this out on mike-l's problem and it works.

[mike-l]

This is essentially Spend All DKP, which is in some use. Seems to work ok. The lack of memory could be an issue. But I can't really put together a coherent example.

[balr]

Some further issues regarding car pool fairness.

1. With an irregular group of carpoolers (as stated in the original spec) there may be days where more than a carful want a ride. There'd be two (or more) drivers that day.

2. The workload for a driver is (loosely) correlated with the number of riders. A rider and a driver: the driver has one pick up and drop off at start of day; and relatively easy-to-negotiate pick up at the end of day followed by a drop off. With two riders, that doubles the issues at the end points. A fair system should take that into account.

With that in mind, a suggestion:

Spoiler:

Each time you drive you are given N points where N = No of riders.
Each time you ride, you subtract one from your points total,
To pick a driver: it'll be the one with the lowest points. Or randomly decide if several are equally low.
Note that this means a new pooler (who has zero points) is not automatically the driver that day: some other poolers may have negative scores.

[undecim]

Some further issues regarding car pool fairness.

1. With an irregular group of carpoolers (as stated in the original spec) there may be days where more than a carful want a ride. There'd be two (or more) drivers that day.

2. The workload for a driver is (loosely) correlated with the number of riders. A rider and a driver: the driver has one pick up and drop off at start of day; and relatively easy-to-negotiate pick up at the end of day followed by a drop off. With two riders, that doubles the issues at the end points. A fair system should take that into account.

With that in mind, a suggestion:

Spoiler:

Each time you drive you are given N points where N = No of riders.
Each time you ride, you subtract one from your points total,
To pick a driver: it'll be the one with the lowest points. Or randomly decide if several are equally low.
Note that this means a new pooler (who has zero points) is not automatically the driver that day: some other poolers may have negative scores.

That suggestion is what I was going to suggest. I'd add one thing to it though:

Spoiler:

New poolers should get some kind of courtesy points to start out with. This encourages them to stay in the pool, since they get a few free rides to start out with, and by the time it's their turn to drive, they'll feel like they owe the group a drive.

Details on this depend on the group's preference. I would recommend the median or mean of the current pool of points. Nicer groups might give then the highest number of points, and meaner groups the lowest.

Also note that choosing the driver with the lowest number of points isn't strictly required. It would be perfectly acceptable for another person to drive (assuming both of them agree to it), as long as the person with the lowest number of points doesn't stay in that position for too long. Again, things like this depend on the group's preference. One could decide on a "maximum debt" (i.e. the greatest difference between the lowest and second-lowest points) allowable for this situation.

[Yakk]

A problem with (even zero-sum) DKP systems is that people can leave the game with dept, or surplus.

If there is a tendency towards one or the other, you can easily generate deflation or inflation (at least in the short term).

One can hope this is self correcting. But in the short term, it could get interesting.

Suppose that the car pool economy is in a period of inflation. Average carscores of active people are rather high (say, in the 100s). If some new person joins, they are at zero, but they are by far the lowest person on the totem pole. They learn that they need to drive at least 30 times before they can hope to be driven.

What are the odds that they will want to drive 30 times? Low. So few people will join the carpool system. Even with a relatively modest budget, you could easily discourage new people from joining up.

If the car pool economy is in a period of deflation (average carscores are in the negative 100s), now a new person gets 30 free rides before they have to drive. Recruitment of new people seems like a mugs game: while it boosts your carscore, it takes a long time before they start contributing back.

Both inflation and deflation can be caused by people leaving with positive or negative scores. (If there are 5 people, and someone with a 8 carscore leaves, the average carscore drops to -2).

People who end up with a negative carscore (through whatever means) might be more tempted to drop out. So you could easily end up with a natural inflationary pressure, even with zero sum being enforced.

The basic problem here is that carscore is a global property of total debt/surplus to all other members of the carpool system, but not a measure of debt/benefit to the other people in the car. And as people can enter/leave the economy, this can cause imbalance.

A fancier method keeps track of each persons pairwise debt with each other person in the car, and permits secondary trading to cancel a debt to a third party. This however requires tracking the relative "value" of each person's issued debt -- ie, how likely they are to repay it, or a car credit score. People who have left the economy have a low car credit score, and their debt becomes valueless.

When you give someone a unit of debt for a lift, you give them something that is (in a sense) worth less than a lift. So to balance the economy, we'll want to introduce interest -- based on your likelihood to repay, and maybe on the time value of transportation.

Next, note that we might want to allow people to freely cancel debt -- say, that person did them a favor, and in exchange you'll drive them.

This looks like a general case of the pricing problem. The answer is then to form a free and competitive market with controls to keep it competitive, and use car credit spot prices in some fungible external commodity that everyone can use as the standard against which to value car credits against external sources of revenue. Say, dollars.

Spoiler:

Babum-ching

[mike-l]

Generally that's dealt with by decay, though it does add some unfairness to irregulars.

[Arariel]

A problem with (even zero-sum) DKP systems is that people can leave the game with dept, or surplus.

If there is a tendency towards one or the other, you can easily generate deflation or inflation (at least in the short term).

One can hope this is self correcting. But in the short term, it could get interesting.

Suppose that the car pool economy is in a period of inflation. Average carscores of active people are rather high (say, in the 100s). If some new person joins, they are at zero, but they are by far the lowest person on the totem pole. They learn that they need to drive at least 30 times before they can hope to be driven.

What are the odds that they will want to drive 30 times? Low. So few people will join the carpool system. Even with a relatively modest budget, you could easily discourage new people from joining up.

If the car pool economy is in a period of deflation (average carscores are in the negative 100s), now a new person gets 30 free rides before they have to drive. Recruitment of new people seems like a mugs game: while it boosts your carscore, it takes a long time before they start contributing back.

Both inflation and deflation can be caused by people leaving with positive or negative scores. (If there are 5 people, and someone with a 8 carscore leaves, the average carscore drops to -2).

People who end up with a negative carscore (through whatever means) might be more tempted to drop out. So you could easily end up with a natural inflationary pressure, even with zero sum being enforced.

The basic problem here is that carscore is a global property of total debt/surplus to all other members of the carpool system, but not a measure of debt/benefit to the other people in the car. And as people can enter/leave the economy, this can cause imbalance.

A fancier method keeps track of each persons pairwise debt with each other person in the car, and permits secondary trading to cancel a debt to a third party. This however requires tracking the relative "value" of each person's issued debt -- ie, how likely they are to repay it, or a car credit score. People who have left the economy have a low car credit score, and their debt becomes valueless.

When you give someone a unit of debt for a lift, you give them something that is (in a sense) worth less than a lift. So to balance the economy, we'll want to introduce interest -- based on your likelihood to repay, and maybe on the time value of transportation.

Next, note that we might want to allow people to freely cancel debt -- say, that person did them a favor, and in exchange you'll drive them.

This looks like a general case of the pricing problem. The answer is then to form a free and competitive market with controls to keep it competitive, and use car credit spot prices in some fungible external commodity that everyone can use as the standard against which to value car credits against external sources of revenue. Say, dollars.

Spoiler:

Babum-ching

Spoiler:

New carpoolers join with the mean number of points of the group? And if necessary, mean adjusted for outliers? Or new carpoolers join with median points? That way, half the current carpoolers are below, and half are above.

[Myrtonos]

What if some participants are inapt for driving? For examlpe if one of them is blind or partially sighted and the rest are fully sighted.

[tomtom2357]

Then the rest act as if he didn't exist (no offense to blind people), and decide accordingly who else is to drive.

[Myrtonos]

Would the rest also act as if they didn't exist if, although considered apt for driving, they were a less good driver than the rest, for example if they had less good stiuational awareness.

[AvatarIII]

These aren't really puzzles since they are a bit too realistic, so they don't have strict enough rules and therefore have no definite answer.

1#

Spoiler:

A should drive
if C Drives, then C will have driven 100% of the times they are in the car and A will have driven 50%, that's a 50% difference, if A drives, then C will have driven 50% of the the times they were in the car, and A will have driven 75%, that's only a 25% difference.

2#

Spoiler:

use a phone, or whoever wants to leave first tells the owner of the car that they want to leave, asking for confirmation of receipt, if the owner wants to leave, they can go and sit in the car if it's raining, so they will need to leave first, when the driver wants to leave, they send an email to all passengers saying so, all passengers respond once to confirm receipt and then again when 100% ready to go, when they have all these emails the driver sends a second email saying "leaving now", all passengers should be sitting waiting for this email, once they get it they can leave. unless there are any unforeseen circumstances, and assuming all walk same speed and are same distance from car, and instantaneous email sending and reading, and shutting down of computers, everyone should reach car at the same time

[Yakk]

Ara: define the group over which you are the median. At best you can hope for a heuristic that might have less injustice if you are lucky.

[Chrysophylax]

The best method depends on the size of the society and the similarity of groups from day to day. In other words, five people arranging the morning school run reuires a very different answer to a car-share society arranging lifts all over Silicon Valley, for example. Since the forums ate my post the last time I tried to say this, I'm going to discuss the two cases separately.

In the first case:

Spoiler:

The obvious solution is to use a random assignment. As long as the average group size is small, new members do not cause problems. This is because the probability of a given member driving on a given trip is 1/(group size). Let us denote 1/(average group size) by p. The probability of a member driving on r trips out of n trips is thus

n!/r!(n-r)! * p^r * (1-p)^{n-r}

(This is the binomial distribution formula.)

We wish to avoid a driver driving substantially less often than deserved, and then leaving the group. It seems unlikely that a member who has participated for some time will suddenly leave the group, since the value of the free rides is not as great as the loss from losing free rides in the future. The difficulty is therefore to avoid having a new driver join, get into debt and leave again. We therefore want the probability of a driver driving a certain number of times within a certain number of total trips to be fairly large, i.e. we want p to be fairly high. We achieve fairness if r=np. Since the number of people in a car is very unlikely to be more than 5, we may take p>0.2.

If we assume that a driver who has driven more than 10 times is safe, then we wish to know P(r<x), where X~B(n,p), and we are taking n=10 and p=0.2. Let us say that a new driver will quit if he ends up more than 6 rides ahead at the end of the period (two weeks of school if n=10). This gives us:

P(r<6) = x

10!/6!4! * 0.2^4 * 0.8^6 = x

210 * 1/625 * 0.262144 = x

0.088080384 = x

So the probability of a new driver quitting after a fortnight under these assumptions is roughly 1/11, which is pretty good odds. Of course, this is not accurate if we allow the new driver to make a new decision every day from day seven onwards, but it gives a rough idea. We can conclude that random assignment of driver is a pretty good system for small groups, and does not need any kind of adjustment made to increase fairness.

[Xias]

Forgive me if this solution has already been suggested.

Spoiler:

Eliminate the alternating system entirely. Instead, keep a pool of tickets and perform a lottery to see who gets to ride. Whenever you enter the group for the first time, or drive, you place a ticket in the pool. When selecting a driver, draw tickets from the pool, with each "winner" getting to ride, and the remaining carpooler gets to drive. Then replace the tickets.

If the selection process happens to line up with your original example:
A B
A B
A B C
A B

Then A will have three tickets, B will have two, and C will have two. If on the next day, A and C participate, then A will have a 40% chance of driving, and C will have a 60%.

[WarDaft]

Problem one:

Spoiler:

While scrolling I saw a DKP system mentioned in plaintext. I did actually think of this before that, but never realized that parallel. We're bacronyming it to Driver Kudos Points, right? Right?

Anyway, I think EP/GP has been shown to be a more fair system overall, which we can shorten to E/G (for effort/gains.) The person with the lowest E/G ratio drives. If you drive, you get +n to your E, where n is the number of passengers, and passengers get +1 to their G.

Problem two:

Spoiler:

What we need to confirm is that both parties know it's time to go. So the driver sends emails at regular intervals until they receive a confirmation from the passenger, at which point they simply stop sending emails. The passenger sends a confirmation for every e-mail received from the driver. If e-mails fail with a relatively constant percentage, then the passenger can become exponentially more confident over time that the driver received their confirmation, by the lack of more incoming e-mails from the driver. This should produce a very small expected value, unless the failure rate is very high. If the email success rate is X, then there is a round trip success rate back to the driver of X*X. No more emails are sent after a successful round trip, so we have to calculate the infinite sum for the expected value. It's just a geometric series, so it's quite simple. If X is 50%, then the expected number of round trip attempts is 3. Half of those round trip attempts will consist of 1 email, and half will consist of two, so the total expected number of emails is 4.5. It is unlikely we can do better than this, because the expected total number of emails each must send to get one through to the other is 4 if the failure rate is 50%, and that is without any confirmation. But if X is 10%, then the expected number of round trip attempts with this method is is 99, and the number of emails is 108.9, so there is likely a better strategy if the email is known to be particularly unreliable in advance.

Hearing about the Two Generals generalization of the problem, perhaps we can do better. (I know, I know, it's impossible, blah blah blah)

Spoiler:

Better as in confidence, not as in fewer emails.

You can receive a confirmation that your message is received... just keep sending it until you get a confirmation. Then you can know that they know (but they can't know that you know that they know - This is unimportant.)

The first general decides when to attack, and sends messengers to the second general, expecting confirmation but not caring about confirming confirmations. When the second general receives this, they begin sending confirmations. Independently, they act as if it were were their idea of when to attack, and begin sending messages telling the first general when to attack, expecting confirmation but not confirming confirmations themselves. These can in fact be two parts of the same message, and in fact just be the same thing. If all generals agree beforehand to commit to attack when they know that all generals know just the time to attack (rather than pursuing the I-know-that-you-know-that-I-know-that- chain) then this back and forth chain is enough to provide certainty on the time to attack in a finite expected number of messages - at least, it is if the failure is a simply some fixed random chance. The probability of an infinitely long sequence of confirmations being sent is zero, so we can simply send the confirmations like steps of a Zeno machine (or any other convergent sum), and assure that it will be finished with a finite amount of communication before some specific point in time, and thus our assertion that generals should commit to attack when they know only that all other generals know the time to attack is in fact well founded!

If this seems like nonsense, run a simulation. You will see that the generals will always commit to attack before some specific time, and you will never fail to have all generals attack. The probability of failure is exactly 0.


Now, there are obvious physical limitations to this solution, in fact it is physically impossible to execute with certainty, but logically it is quite sound - the problem doesn't specify how much time any of the relevant actions take, so it must not be important, otherwise the problem is a 169.

Now, I have made two assumptions I'm the original problem does not - that they can agree on something else before hand so long as it does not itself contain any information relating to the time of the attack, and that there is some fixed chance of failure - but these seem like reasonable assumptions.