A Fair Carpool Scheduling Algorithm
June 2, 2017 9:54 PM   Subscribe

We present a simple carpool scheduling algorithm in which no penalty is assessed to a carpool member who does not ride on any given day. The algorithm is shown to be fair, in a certain reasonable sense. The amount of bookkeeping grows only linearly with the number of carpool members. Full Paper PDF

The paper, authored by Ronald Fagin and John H. Williams, was originally published in 1983 in the IBM Journal of Research and Development. It gives a mathematical definition of "fairness", examines several alternatives for carpool scheduling, and proves that their proposal, a relatively simple credit/debit system, is fair.

Bonus: C# implementation on GitHub
posted by jcreigh (12 comments total)

This post was deleted for the following reason: Poster's Request -- frimble



 
I carpooled when I was a kid. Depending on the other passengers it was a certain level of hell. But then I also carpooled with my best friend my senior year of high school, and that was amazing. We could get Starbucks.
posted by tooloudinhere at 10:10 PM on June 2, 2017


OK that's a great paper. Now we just need to determine how many Bitcoin per Duodecadon and destroy Uber.
posted by rouftop at 10:45 PM on June 2, 2017 [4 favorites]


I am fascinated and slightly jaw-dropped, and HOW did your coworker come across this in the first place? Inquiring minds want to know.
posted by Eyebrows McGee at 10:57 PM on June 2, 2017


I like this because if you're a bunch of geeks carpooling every day for a few years, its easy to imagine how this topic could come to be so well thought out.
posted by aubilenon at 11:10 PM on June 2, 2017 [1 favorite]


From the top of page 134, right hand column:
For example, if there are four people named Don, John, Phylis, and Ron...
John and Ron are the authors, I wonder who Don and Phylis are.
posted by Dr Dracator at 11:24 PM on June 2, 2017 [2 favorites]


John and Ron are the authors, I wonder who Don and Phylis are.
Further, the authors thank Phyllis Reisner, Don Stanat, and Jim Sutton, who at various times participated with the authors in the carpool in which Scheduling Algorithm 4 was developed.
posted by J.K. Seazer at 11:49 PM on June 2, 2017 [5 favorites]


I wrote an Android app called Fairpool based on this paper back when I was carpooling from Oakland to Livermore in 2010. It worked pretty well - it actually feels intuitively fair.
posted by JoeBlubaugh at 1:07 AM on June 3, 2017 [8 favorites]


Ronald Fagin

Peg, you will get to drive soon
When the ride token passes
You see it all in 2^N
It's your favorite scheduling algorithm
posted by RobotVoodooPower at 6:43 AM on June 3, 2017 [5 favorites]


This is great fun.

But, does a car with N people actually provide any advantage to the riders that is larger than a car with N+1 people? Algorithm 4 implicitly seems to assumes so when charging riders. (Perhaps that's true if you pick people up at their homes, and thus it takes longer with more people?) This seems just as bad as algorithm 2: we're not punishing drivers on bad days by quite as much, but now we're also punishing riders on bad days. Fixing the cost per rider and payment per driver seems intuitively more fair to me: why should either the rider or driver be punished for happening to land on bad days? That doesn't align with my understanding of fairness.

If you ask me, a random selection weighted by each person's participation in the carpool over some time interval seems both intuitively more fair and much easier to implement. It doesn't actually reward people for non-participation, since they presumably have to drive their own cars 100% of the time on non-participation days anyway. If not-driving is winning, then they still win by participating. If you use a moving window of a few weeks or months as the interval, it rewards increased participation on timescales that humans can appreciate.
posted by eotvos at 7:44 AM on June 3, 2017


But, does a car with N people actually provide any advantage to the riders that is larger than a car with N+1 people? Algorithm 4 implicitly seems to assumes so when charging riders.

Think of it as providing the rider with a discount/reward for efficient carpooling. (This becomes more evident in the generalized "many drivers" case.) If you have 6 riders, incentivizing them to travel in 2 cars instead of 3 is good for everyone involved.

Another way to look at it is, if you have 3 people in 1 car, they're splitting the abstracted cost of the drive 3 ways. If you've got 4 people, you get a 4-way split instead; the driver who's "picking up the tab" this time is still paying 1 drive-cost, but the other 3 each need to chip in less to cover the total.
posted by NMcCoy at 1:00 PM on June 3, 2017 [1 favorite]


I guess you could approximate the same result stochastically with no bookkeeping by just randomly selecting a driver from whoever is participating each day. I guess if there's someone who needs to drive on a regular schedule, that starts to get worse.

Realistically, I think the flaw with this algorithm is it assumes that the cost for driving is equal for everyone. Even if everyone's car gets the same fuel economy, some people just like driving more than others.
posted by aubilenon at 10:51 PM on June 3, 2017 [1 favorite]


you could approximate the same result stochastically with no bookkeeping by just randomly selecting a driver
That's assuming that everyone is available to drive/ride on an equal number of days, the algorithm is designed specifically to address an unequal numbers of rides.

I think the flaw with this algorithm is it assumes that the cost for driving is equal for everyone.
You could tweak the algorithm to penalise the driver of an inefficient/polluting car, but then they would just have to drive more often which wouldn't really solve the problem.

Anyway here is an excel s/sheet with the algorithm.
posted by Lanark at 10:29 AM on June 19, 2017


« Older Think of it as redistribution   |   Three and a Half Pounds of Bees Newer »


This thread has been archived and is closed to new comments