Firstly, this is - in a way - somewhat golf-ish question (as in: code golf stack exchange), so if it doesn't fit this forum then feel free to close it. But nevertheless please read the rest of the question before doing so.
I have been thinking for a long time about the "fair division of transportation costs" problem.
Let's say that we have a couple of co-workers, who ecologically drive together to work in one vehicle (car, van, bus - pick one).
The first worker is the driver and we can call him $w_0$. His destination is the workplace $W$. For simplicity we may introduce function $C(x, y, n)$, which always precisely returns the cost of driving $n$ people from the place $x$ to $y$.
Since the driver picks up his friends, the cost of the travel increases both because there are now more people to carry and (possibly) because the distance increases. So all the friends of the driver proposes that they will share the cost of driving together to work.
And that's where's the actual problem: How to divide the cost of the travel in a way, which will be just for all the passengers and the driver?
Part of my question is how to precisely define the problem, because it is not really an easy one. The better (but still not perfect) version of the question would be: How to divide the cost of the travel, so that the division will represent the actual increase of the cost for the driver caused by subsequent passengers?
To give you an idea of how complicated the problem is, let's consider a driver's route from home to work. For fun, I placed him in my hometown in the neighborhood where I grew up and defined his workplace as the (otherwise worth visiting) Technology Museum.
This is the simplest case when the driver covers 100% costs of the travel.
The second case is when he picks up his friend en route to the work:
I suppose that both workers wouldn't feel unjustly if:
- Driver ($w_0$) paid $C(w_0, w_1, 1) + {{C(w_2, W, 1)} \over {2}}$
- First friend ($w_1$) paid ${C(w_2, W, 1)} \over {2}$
Driver needs to pay the price of the whole route, but shares the cost of the last part with his friend, because now the car needs to carry two people instead of one.
The third case complicates things even more:
Now the driver picks up the second friend. We could extend the previous formula to three people, but now it would not be just anymore. And the reason is that the friend $w_1$ (blue) would have to cover part of the cost of the green route. However, if there was no $w_2$, the driver could pick a shorter route, thus lowering the overall cost.
But even if there was no $w_2$, the previous formula also wouldn't be just. The reason is that the driver must now drive longer route to pick $w_1$ than if he drove directly to the work. So $w_1$ probably also needs to cover some cost of $w_0$ reaching his home before driving together to work.
Similarly, in case 4, friends $w_1$, $w_2$ and $w_3$ would have to cover the cost of reaching $w_4$ and then going the long route around whereas if there was no $w_4$, then actually $w_0$ could simply drive his regular, shortest possible route.
This is a really scenic route though, so maybe the first three passengers wouldn't complain that much.
Let me summarize the requirements:
- Some semi-obvious ones: we always drive on roads, there is always a route between two points, perfect weather conditions, no detours, no accidents etc. In a nutshell, no overcomplicating already complicated task.
- The only cost is fuel and the only factors influencing the amount of burnt fuel are: driven distance and number of people onboard (to simplify the problem, we completely ignore wear of the car and other possible costs)
- The driver has a quantum-powered$^1$ car navigation system, which always picks the shortest possible path, which visits all points and ends up in $W$ (so that we may eliminate the injustice of not picking the optimal route)
- The solution must work for any finite number of people.
- The solution must contain explanation, why it is just for the driver and passengers.
Also, I don't know the optimal solution (so this is not a riddle)
If you figure out any other nasty case (possible injustice), feel free to post it as well. The location of shown map is (50.782684, 16.282753). It may help validate the solutions.
$^1$ Traveling salesman problem is known to be NP-hard