La forma más justa de elegir los regalos

Question

Supongamos que un padre trae a casa de un viaje $2n$ regalos de aproximadamente
valor igual para sus dos hijos. Los niños pueden elegir uno
a la vez que los regalos que desean. ¿Cuál es la forma más justa de hacerlo?
Por ejemplo, si $n=1$ entonces claramente un niño elige primero
(determinado por el lanzamiento de una moneda) y el otro niño elige el segundo. Si
denotan los hijos por 0 y 1, entonces este método es descrito por el
secuencia de elección 01 (suponiendo, como hago a partir de ahora, que 0 elige
primero). Supongamos ahora que $n=2$ . La secuencia de elección 0101 está claramente sesgada
hacia el 0, ya que el 0 tiene la primera opción al principio y después de ambos
han elegido un regalo. La secuencia más justa según cualquier criterio razonable
es 0110. ¿Qué pasa con el general $n$ ? Si $n=2^k$ se puede argumentar que
que la secuencia más justa es la primera $n$ términos de la Thue-Morse
secuencia
( http://mathworld.wolfram.com/Thue-MorseSequence.html ). Otro
Se puede argumentar que la secuencia más justa $a_1,\dots, a_n$ es una
que maximiza el valor de $k$ para el que el polinomio
$(1-2a_1)x^{n-1} + (1-2a_2)x^{n-2}+\cdots+(1-2a_n)$ y su primer $k$
Las derivadas se desvanecen en $x=1$ . (La secuencia de Thue-Morse no tiene
esta propiedad, aunque no recuerdo dónde lo vi alguna vez).

¿Se ha prestado atención a este problema? ¿Cuál es la referencia para el
problema de maximizar $k$ ?

Answer 1

Hola,

Llevo un tiempo merodeando por mathoverflow. No soy un matemático investigador, sólo un aficionado.

Perdóname si me falta alguna etiqueta.

Steven J. Brams y Alan D. Taylor hablaron de la solución Morse-Thue en su libro ''The Win-Win Solution'', ISBN-10: 0393320812, aunque es un libro de divulgación matemática y no estoy seguro de que lo nombren. Creo que lo llaman "elegir lados".

Brian Hayes escribió en su blog sobre este problema en su reproductor de bits:

http://bit-player.org/2007/choosing-up-sides-again

Lo mejor, Mark

Answer 2

He aquí una idea. Para cualquier partición $(A,B)$ de $[2n]$ , donde $|A|=|B|=n$ podemos preguntar a cada niño si prefiere $A$ o $B$ . Si uno prefiere $A$ y el otro prefiere $B$ entonces hemos terminado. En caso contrario, tienen la misma función de preferencia sobre todas esas particiones.

Lema. Existen particiones $(A,B)$ y $(A',B')$ tal que

1. ambos niños prefieren $A$ en $B$ ,

2. ambos niños prefieren $B'$ en $A'$ y

3. $(A',B')$ se obtiene de $(A,B)$ realizando un único intercambio.

Prueba. Realice intercambios hasta que $(A,B)$ se convierte en $(B,A)$ . En algún momento, cada niño debe cambiar de preferencia.

Dado el supuesto de que los regalos son todos aproximadamente del mismo valor, parece justo ofrecer tal $(A,B)$ como una opción y lanzar una moneda para decidir quién se queda con $A$ .

Answer 3

En cuanto a la cuestión de una referencia para maximizar $k$ :

Un polinomio con todos los coeficientes $\pm1$ se llama polinomio de Littlewood, véase, por ejemplo http://en.wikipedia.org/wiki/Littlewood_polynomial . La cuestión de los polinomios de Littlewood que desaparecen en un orden alto en $x=1$ está en la literatura. Véase, por ejemplo, Daniel Berend y Shahar Golan, Littlewood polynomials with high order zeros, Math Comp 75 (2006) 1541-1552, disponible libremente en http://www.ams.org/journals/mcom/2006-75-255/S0025-5718-06-01848-5/S0025-5718-06-01848-5.pdf Resumen ejecutivo; se conocen algunas cifras, se conocen algunos límites, queda mucho por hacer.

Answer 4

Al parecer, el siguiente documento aborda exactamente la cuestión que le interesa:

Un protocolo general sin elicitación para la asignación de bienes indivisibles, por: Sylvain Bouveret y Jérôme Lang, International Joint Conference on Artificial Intelligence (2011) .