Intercambios de regalos de elefante blanco: mecanismos para una división justa

Un juego popular en las fiestas navideñas en América del Norte es el intercambio de regalos de elefante blanco . En resumen (ignorando las variaciones) funciona de la siguiente manera:

Hay personas y n regalos envueltos. Los jugadores son ordenados arbitrariamente. En el i ª ronda, el jugador que sea$n$$n$$i^{\text{th}}$$i$

• elige un regalo envuelto y lo desenvuelve como su regalo
• "roba" uno de los regalos ya abiertos (de algún jugador ).$k < i$

Si se roba el regalo de un jugador, ahora tiene la oportunidad de hacer lo mismo. Una ronda se completa cuando un jugador elige un regalo envuelto.

Si bien hay muchas variaciones en el sistema, un punto a tener en cuenta es que el último jugador tiene una ventaja injusta porque solo a ellos se les garantiza la posibilidad de elegir cualquier regalo sin envolver .

Esto cae dentro de la clase de métodos de división equitativa relacionados con bienes indivisibles (a diferencia del corte de tortas).

Mi pregunta es:

¿Existen mecanismos para desembolsar los regalos que son justos (en el sentido de que cada jugador tiene la misma oportunidad de elegir un regalo de alto valor bajo su valoración)?

Tenga en cuenta que se necesitará cierta flexibilidad en la definición de feria, ya que los productos son indivisibles y no estamos introduciendo una compensación monetaria para los jugadores.

Esta no es una respuesta completa, pero es incompleta.

Algunos antecedentes y temas relacionados para aquellos que no están familiarizados:

Una buena propiedad sería la ausencia de envidia, en la que a ningún jugador le gustaría comerciar con otro después de que se complete el mecanismo. Desafortunadamente, para bienes indivisibles y sin dinero podemos ver que esto es imposible (puede haber un bien que dos personas piensan que es lo mejor). La otra propiedad común es la proporcionalidad, donde todos obtienen lo que consideran un valor de más de $1/n$ ; Esto también es claramente imposible de obtener siempre (puede haber un elemento que nadie quiere, pero alguien debe terminar con él).

[1] se centra en calcular la asignación de envidia mínima en un escenario de bienes indivisibles. Muestran que un mecanismo de mínima envidia no puede ser veraz. Sin embargo, aún podríamos poder diseñar un juego con un buen precio de estabilidad (aunque los jugadores no sean sinceros).

[2] aplique el criterio de "equidad máxima-mínima". La idea es considerar la función de valoración de cada jugador en subconjuntos de elementos, normalizándola a una en todo el conjunto, y encontrar la asignación que maximice la utilidad mínima de cualquier agente. Una vez más, sin embargo, no consideran nuestro entorno aquí con la demanda unitaria. Otros estudian algoritmos de aproximación para este problema, pero no sé si alguien ha considerado esta restricción.

-

Vale la pena señalar que, por lo general, las nociones de equidad son extremadamente peores: un mecanismo generalmente (¿quizás no siempre?) Se considera libre de envidia si cada jugador tiene una estrategia que garantice que no envidiará la asignación de ningún otro. Si está jugando para maximizar su utilidad esperada, puede o no terminar envidiosa. Lo mismo vale para la proporcionalidad.

Debido a esto, es difícil tratar de relajar estas nociones de una manera natural cuando se toma con este enfoque filosófico de la división justa. Puede ser tentador definir un criterio como "libre de envidia ex ante" en el que esperamos estar libres de envidia en expectativas (lo que sea que eso signifique). Sin embargo, creo que esto realmente se estaría iniciando en una pista completamente nueva de la filosofía actual. Si uno hiciera eso, creo que deberíamos descartar por completo las nociones de libertad de envidia o proporcionalidad y comenzar a pensar en cómo los maximizadores de utilidad esperados jugarían estos juegos de división justa en primer lugar.

$n$$\frac{1}{n}$

Para evitar esto, creo que debemos considerar criterios ordinales en su lugar. Propongo lo siguiente como una relajación "natural":

$(\varepsilon,\delta)$$1-\varepsilon$$\delta n$

$(\varepsilon,\varepsilon)$$\varepsilon$$\varepsilon n$$\varepsilon n$

$(\varepsilon,\varepsilon)$$\varepsilon$

No pretendo que esto capture casi todas las preguntas interesantes sobre esta configuración o el mecanismo del elefante blanco. Por ejemplo, el$(\varepsilon,\varepsilon)$

-

[1] Lipton, Markakis, Mossel, Saberi. "Sobre asignaciones aproximadamente justas de bienes indivisibles". CE 2004.

[2] Bezakova, Dani. "Asignación de bienes indivisibles". SIGECOM 2005.

[3] Bueno, también lo es el dictador en serie aleatorio, pero el dictador en serie aleatorio a menudo tiene buenas propiedades en teoría. También estoy asumiendo que cada artículo solo puede ser robado una vez por ronda.

Gran parte de la experiencia de intercambio de regalos de elefante blanco también está controlada por selección aleatoria. Una variación popular incluye la regla de que las primeras selecciones duran, pero eso no siempre se incluye en la regla. Esto aprovecha la ventaja injusta de ser seleccionado al azar primero de la ecuación. Otra regla requiere que no haya "retrocesos" directos en el juego. Además, la mayoría de los juegos se juegan con una regla de "tres toques", que dice que una vez abierto, luego robado una vez, luego robado dos veces, se congela en futuros robos. Esta regla crea otro nivel de ventaja injusta para aquellos que eligen elegir un regalo que ha sido tocado dos veces.

Nuestro especialista en recreación como AlbinoPhant estudia estos juegos de intercambio de regalos durante todo el año. Si desea agregar una dimensión aleatoria adicional al juego, use una historia de izquierda a derecha dentro del juego. La historia de Lefty the White Elephant se sugiere como muestra.

El beneficio real del intercambio de regalos dentro de esta actividad es el compromiso social que produce este proceso: los regalos generalmente son secundarios a la diversión de las grandes bromas. Sin embargo, todos los jugadores se van con algún nivel de recompensa de regalo.

$n$$G$$G$$n$$n$ .

$\Omega(\log n)$ rondas habrían sido mejores para invocar las propiedades de mezcla del expansor correcto.

Bueno, lo anterior describe lo que habríamos hecho si los jugadores hubieran estado interesados ​​en la teoría de grafos espectrales y / o en la computación de inversos modulares :) En realidad, simplemente jugamos de la manera normal.