Some people agree to carpool, but they want to make sure that any
carpool arrangement is fair and doesn't overload any single person
with too much driving. Some scheme is required because none of them
goes to work every day, and so the subset of them in the car varies
from day to day.Let the people be labeled in a set $S = \{p_1,…,p_k\}$. We say that
the total driving obligation of $p_j$ over a set of days is the
expected number of times that $p_j$ would have driven, had a driver
been chosen uniformly at random from among the people going to work
each day. That is, suppose the carpool plan lasts for $d$ days, and on
the $i^{th}$ day a subset $S_i \subseteq S$ of the people go to work.
Then the total driving obligation $\delta_j$ for $p_j$ can be written
as $\delta_j = \sum_{i:p_j\in S_i} \frac{1}{|S_i|}$. Ideally, we'd
like to require that $p_j$ drives at most $\delta_j$ times, but
$\delta_j$ may not be an integer.A driving schedule is a choice of a driver for each day$-$a sequence
$p_{i_1}, p_{i_2},…,p_{i_d}$ with $p_{i_t}\in S_t-$and that a fair
driving schedule is one in which $p_j$ is chosen as a driver on at
most $\lceil \delta_j \rceil$ days.
- Prove that for any sequence of sets $S_1,…,S_d$, there exists a fair driving schedule.
I'm finding this question very difficult to answer. My intuition tells me that there should always be a fair driving schedule, but I don't know how to prove that. I was thinking that we could do things inductively, but the problem breaks down after the base case. For example, consider the base case being $S_1$. Then there always exists a fair driving schedule because every driver $\in S_1$ can only drive at most once. After the base case, if we have just $S_1$ and $S_2$, we run into trouble because $S_1$ and $S_2$ can be completely different, very similar, or mixed. How can we show that there is always a fair driving schedule for just two lists? Generally, how can we extend this to $d$ lists?
Best Answer
There should be always a fair driving schedule since you can model this problem as a flow network. The source is connected with all persons and the capacity of an edge from the source to a person $p_j$ is $\lceil\delta_j\rceil$. The next step is to connect every person with each of his working days. The capacity of each of this edges is $1$. The last step is to connect each day with the sink with capacity $1$.
Applying the max-flow min-cut theorem to our flow network, we can see that the maximal flow of our network is equal to the number of days, since the minimal cut splits our network into the sink and all other nodes.
Explanation: Without loss of generality, we can assume that each person works at least one day and there are no days without workers. Therefore we exclude all cuts running through an edge which connects a person with a day. The cut which splits our network in source and all other nodes is not minimal since $$\sum_j\lceil\delta_j\rceil\ge\sum_j\delta_j= \text{number of days}.$$ The mixed cuts are excluded with the combination of the abovementioned arguments.
In conclusion, the maximal flow in our network can be retranslated to our original problem in the following way: If the flow from the node corresponding to person $p$ to the node corresponding to day $t$ is $1$, than $p$ is the driver on $t$.
Note that there are algorithms to determine the maximal flow like the Ford-Fulkerson-Algorithm.