Demostrar que siempre existe un horario de conducción justo

Question

Algunas personas aceptan compartir el coche, pero quieren asegurarse de que cualquier que cualquier acuerdo de coche compartido sea justo y no sobrecargue a una sola persona con demasiada conducción. Se requiere un cierto esquema porque ninguno de ellos va al trabajo todos los días, por lo que el subconjunto de ellos en el coche varía de un día a otro.

Que las personas sean etiquetadas en un conjunto $S = \{p_1,...,p_k\}$ . Decimos que el obligación total de conducir de $p_j$ durante un conjunto de días es el número esperado de veces que $p_j$ habría conducido, si un conductor elegido uniformemente al azar entre las personas que van a trabajar cada día. Es decir, supongamos que el plan de coche compartido dura $d$ días, y en el $i^{th}$ día un subconjunto $S_i \subseteq S$ de la gente va a trabajar. Entonces la obligación total de conducir $\delta_j$ para $p_j$ se puede escribir como $\delta_j = \sum_{i:p_j\in S_i} \frac{1}{|S_i|}$ . Idealmente, nos gustaría requerir que $p_j$ impulsa como máximo $\delta_j$ veces, pero $\delta_j$ puede no ser un número entero.

A horario de conducción es la elección de un conductor para cada día $-$ una secuencia $p_{i_1}, p_{i_2},...,p_{i_d}$ con $p_{i_t}\in S_t-$ y que un feria horario de conducción es uno en el que $p_j$ se elige como conductor en en máximo $\lceil \delta_j \rceil$ días.

1. Demostrar que para cualquier secuencia de conjuntos $S_1,...,S_d$ existe un programa de conducción justo.

Me resulta muy difícil responder a esta pregunta. Mi intuición me dice que siempre debería haber un horario de conducción justo, pero no sé cómo demostrarlo. Estaba pensando que podríamos hacer las cosas de forma inductiva, pero el problema se rompe después del caso base. Por ejemplo, consideremos que el caso base es $S_1$ . Entonces siempre existe un programa de conducción justo porque cada conductor $\in S_1$ sólo puede conducir como máximo una vez. Después del caso base, si sólo tenemos $S_1$ y $S_2$ nos encontramos con problemas porque $S_1$ y $S_2$ pueden ser completamente diferentes, muy similares o mezclados. ¿Cómo podemos demostrar que siempre hay un programa de conducción justo para sólo dos listas? En general, ¿cómo podemos extender esto a $d$ ¿listas?

Answer 1

Siempre debe haber un programa de conducción justo ya que se puede modelar este problema como un red de flujo . La fuente está conectada con todas las personas y la capacidad de un borde de la fuente a una persona $p_j$ es $\lceil\delta_j\rceil$ . El siguiente paso es conectar a cada persona con cada uno de sus días de trabajo. La capacidad de cada uno de estos bordes es $1$ . El último paso es conectar cada día con el fregadero con capacidad $1$ .

La aplicación de la teorema de max-flow min-cut a nuestra red de flujo, podemos ver que el flujo máximo de nuestra red es igual al número de días, ya que el corte mínimo divide nuestra red en el sumidero y todos los demás nodos.

Explicación: Sin pérdida de generalidad, podemos suponer que cada persona trabaja al menos un día y que no hay días sin trabajadores. Por lo tanto, excluimos todos los cortes que pasan por una arista que conecta a una persona con un día. El corte que divide nuestra red en origen y todos los demás nodos no es mínimo ya que $$\sum_j\lceil\delta_j\rceil\ge\sum_j\delta_j= \text{number of days}.$$ Los cortes mixtos se excluyen con la combinación de los argumentos mencionados.

En conclusión, el flujo máximo en nuestra red puede ser retraducido a nuestro problema original de la siguiente manera: Si el flujo desde el nodo correspondiente a la persona $p$ al nodo correspondiente al día $t$ es $1$ que $p$ es el conductor de $t$ .

Tenga en cuenta que existen algoritmos para determinar el flujo máximo como el Algoritmo Ford-Fulkerson .