Armonía de alquiler

La armonía de alquileres ^{[1] [2]} es una especie de problema de división justa en el que elementos indivisibles y un coste monetario fijo deben dividirse simultáneamente. El problema de los compañeros de casa ^{[3] [4]} y la división-alquiler-asignación de habitación ^{[5] [6]} son ​​nombres alternativos al mismo problema. ^{[7] [8] : 305–328}

En el entorno típico, hay socios que alquilan juntos una casa de una habitación por un costo fijado por el propietario. Cada compañero de casa puede tener preferencias diferentes: uno puede preferir una habitación grande, otro puede preferir una habitación con vista a la calle principal, etc. Los dos problemas siguientes deben resolverse simultáneamente: ${\displaystyle n}$ ${\displaystyle n}$

• (a) Asignar una habitación a cada socio,
• (b) Determine la cantidad que debe pagar cada socio, de modo que la suma de los pagos sea igual al costo fijo.

Hay varias propiedades que nos gustaría que cumpliera la tarea.

• No negatividad (NN) : todos los precios deben ser 0 o más: a ningún socio se le debe pagar para conseguir una habitación.
• Libre de envidia (EF) : dado un esquema de precios (una asignación de alquiler a habitaciones), decimos que un socio prefiere una habitación determinada si cree que la parcela habitación+alquiler es ligeramente mejor que todas las demás parcelas. EF significa que cada socio prefiere el espacio que le ha sido asignado. Es decir, a ningún socio le gustaría alquilar otra habitación por el alquiler asignado a esa habitación.
• Eficiencia de Pareto (PE) : Ninguna otra asignación de socios a habitaciones es débilmente mejor para todos los socios y estrictamente mejor para al menos un socio (dado el vector de precios).

La ausencia de envidia implica eficiencia de Pareto. Prueba: Supongamos por contradicción que existe una asignación alternativa, con el mismo vector de precios, que es estrictamente mejor para al menos un socio. Entonces, en la asignación actual, ese socio siente envidia.

El problema de la armonía del alquiler se ha estudiado bajo dos supuestos diferentes sobre las preferencias de los socios:

• En la versión de utilidad ordinal , cada socio tiene una relación de preferencia sobre los paquetes [habitación, precio]. Dado un vector de precios, el socio sólo debería poder decir qué habitación (o habitaciones) prefiere alquilar a ese precio.
• En la versión de utilidad cardinal , cada socio tiene un vector de valoraciones monetarias. El socio debe decir, por cada habitación, exactamente cuánto dinero está dispuesto a pagar por esa habitación. Se supone que el socio tiene una utilidad cuasilineal , es decir, si valora la habitación y paga , su utilidad neta es . ${\displaystyle v}$ ${\displaystyle p}$ ${\displaystyle v-p}$

El supuesto cardinal implica el supuesto ordinal, ya que dado un vector de valoración siempre es posible construir una relación de preferencia. El supuesto ordinal es más general y supone menos carga mental para los socios.

versión ordinal

Su: una persona por habitación

El protocolo de Francis Su ^[1] hace los siguientes supuestos sobre las preferencias de los socios:

1. Buena casa : En cualquier partición del alquiler, cada persona considera aceptable al menos una habitación + parcela de alquiler.
2. Sin externalidades : La relación de preferencia de cada socio depende de las habitaciones y los alquileres, pero no de las elecciones de los demás.
3. Inquilinos avaros : todo inquilino prefiere débilmente una habitación libre (una habitación con un alquiler de 0) a cualquier otra habitación.
4. Conjuntos de preferencias topológicamente cerrados : un socio que prefiere un espacio para una secuencia convergente de precios, prefiere ese espacio al precio límite.

Normalice el alquiler total a 1. Luego, cada esquema de precios es un punto en un símplex de dimensiones con vértices en . El protocolo de Su opera en una versión dualizada de este simplex de manera similar a los protocolos Simmons-Su para cortar pasteles: para cada vértice de una triangulación del simplex dual, que corresponde a un determinado esquema de precios, pregunta al socio propietario " ¿Qué habitación prefieres en ese esquema de precios?". Esto da como resultado una coloración de Sperner del simplex dual, por lo que existe un pequeño subsímplex que corresponde a una asignación aproximada de habitaciones y alquileres sin envidia. ${\displaystyle (n-1)}$ ${\displaystyle n}$ ${\displaystyle \mathbb {R} ^{n}}$

El protocolo de Su devuelve una secuencia de asignaciones que convergen en una asignación libre de envidia. Los precios siempre son no negativos. Por tanto, el resultado satisface los requisitos de NN y EF.

El protocolo Rental Harmony de Su se ha popularizado en varios artículos de noticias, ^{[9] [10]} y tiene varias implementaciones en línea. ^{[11] [12]}

Azriely y Shmaya: compañeras de cuarto

Azriely y Shmaya ^[2] generalizan la solución de Su a una situación en la que la capacidad de cada habitación puede ser mayor que la de una (es decir, varios socios pueden vivir en la misma habitación).

Acreditan la existencia de asignaciones libres de envidia en las siguientes condiciones:

1. Buena casa : a cada socio le gusta al menos una de las habitaciones según cada vector de precios.
2. Sin externalidades : a todos los socios les gustan las habitaciones libres.
3. Socios avaros : Las preferencias son continuas en los precios.

Las principales herramientas utilizadas en la prueba son:

• El teorema de KKMS: una generalización del teorema de Kkm .
• Teorema del matrimonio de Hall .

Su solución es constructiva en el mismo sentido que la solución de Su: existe un procedimiento que aproxima la solución a cualquier precisión dada.

Propiedades generales de los protocolos ordinales.

R. Tanto en la solución de Su como en la de Azrieli y Shmaya, se permite (pero no se obliga) que la relación de preferencia de cada socio dependa de todo el vector de precios. Es decir, un compañero puede decir "si la habitación A cuesta 1000, entonces prefiero la habitación B a la C, pero si la habitación A cuesta sólo 700, entonces prefiero la habitación C a la habitación B".

Hay varias razones por las que esta generalidad puede resultar útil. ^[2]

1. Planificación futura. Supongamos que el socio piensa que la habitación A es la mejor, luego la B y luego la C. Si A es cara, el socio se decide por B. Pero si A es más barata, el socio podría comprar C (que es la más barata) y luego ahorrar algo de dinero. y cambiar a A.
2. Información incompleta. El vector de precios puede dar al socio alguna indicación sobre la calidad de las habitaciones.
3. Vecinos. El vector de precios puede permitir al socio predecir, hasta cierto punto, qué tipo de personas van a vivir en las habitaciones vecinas.
4. Efectos de irracionalidad, por ejemplo, efectos de encuadre . Si la habitación B y la habitación C son de la misma calidad y tienen el mismo precio, entonces el socio puede comprar A. Pero, si la habitación B se vuelve más cara, entonces el socio puede cambiarse a C, pensando que "es lo mismo que B". pero a precio de ganga...".

B. Tanto la solución de Su como la de Azrieli&Shmaya parten del supuesto de "inquilinos avaros": suponen que un inquilino siempre prefiere una habitación libre a una habitación que no lo es. Esta suposición es fuerte y no siempre realista. Si una de las habitaciones es muy mala, es posible que algunos inquilinos no quieran vivir en esa habitación ni siquiera gratis. Esto es fácil de ver en la versión cardinal: si crees que la habitación A vale 0 y la habitación B vale 100, y que la habitación A es gratuita y la habitación B cuesta 50, entonces ciertamente prefieres la habitación B.

Su ^[1] sugiere debilitar este supuesto de la siguiente manera: cada socio nunca elige la habitación más cara si hay una habitación libre disponible. Esto no requiere que la persona elija la habitación libre. En particular, esto se aplicará si una persona siempre prefiere una habitación gratuita a una habitación que cueste al menos el total del alquiler. Sin embargo, incluso este supuesto debilitado podría resultar poco realista, como en el ejemplo anterior. ^{[8] : 320–321} ${\displaystyle 1/(n-1)}$

Segal-Halevi ^[13] sugieren debilitar aún más el supuesto. Digamos que un precio T es demasiado alto para algún agente i si, siempre que una habitación cuesta T y otra está libre, ninguna habitación prefiere la habitación que cuesta T. La armonía en el alquiler existe siempre que existe un precio demasiado alto para todos los agentes. Este supuesto es más débil que el de los inquilinos avaros y más débil que la cuasilinealidad. Queda abierta la cuestión de si existe un supuesto aún más débil que garantice la existencia de armonía en el alquiler.

Versión cardenal

Como se explicó anteriormente, la entrada a la versión cardinal es una matriz de ofertas: cada socio tiene que presentar una oferta para cada habitación, indicando cuánto (en dólares) vale esa habitación para él.

Una noción clave en las soluciones cardinales es la asignación de suma máxima (también conocida como utilitaria ). Se trata de una asignación de socios a salas que maximiza la suma de las pujas. El problema de encontrar una asignación de suma máxima se conoce como problema de asignación y puede resolverse a tiempo mediante el algoritmo húngaro (donde está el número de socios). Cada asignación de EF es suma máxima y cada asignación de suma máxima es PE. ^[4] ${\displaystyle O(n^{3})}$ ${\displaystyle n}$

Incompatibilidad de EF y NN

Los dos requisitos de estar libre de envidia y de pagos no negativos no siempre son compatibles. Por ejemplo, supongamos que el coste total es 100 y las valoraciones son:

Aquí, la única asignación de suma máxima es darle la habitación 1 al socio 1 y la habitación 2 al socio 2. Para asegurarse de que el socio 2 no tenga envidia, el socio 1 debe pagar 115 y el socio 2 debe pagar -15.

En este ejemplo, la suma de valoraciones es mayor que el coste total. Si la suma de valoraciones es igual al coste total y hay dos o tres socios, entonces siempre existe una asignación EF y NN. ^{[4] : 110–111} Pero si hay cuatro o más socios, entonces nuevamente EF y NN podrían ser incompatibles, como en el siguiente ejemplo (ver ^{[8] : 318–319} como prueba):

Tenga en cuenta que este ejemplo no ocurre en la versión ordinal, ya que los protocolos ordinales asumen la suposición de "Socios avaros": los socios siempre prefieren habitaciones libres. Cuando se cumple esta suposición, siempre existe una asignación EF+NN. Pero, en el ejemplo anterior, el supuesto no se cumple y no existe una asignación EF+NN. Por lo tanto, los protocolos en la versión cardinal deben llegar a un compromiso entre EF y NN. Cada protocolo supone un compromiso diferente.

Brams y Kilgour: NN pero no EF

Brams y Kilgour ^{[8] : 305–328  [14]} sugieren el procedimiento Gap :

1. Calcule una asignación de suma máxima.
2. Si la suma máxima es menor que el costo total, entonces el problema no tiene solución, ya que los socios no quieren pagar el monto total requerido por el propietario.
3. Si la suma máxima es exactamente igual al coste total, entonces se asignan las habitaciones y los socios pagan sus valoraciones.
4. Si la suma máxima es mayor que el costo total, entonces los precios se reducen en función de la brecha entre estos precios y las siguientes valoraciones más bajas (consulte el libro para obtener más detalles).

La idea detrás del último paso es que las siguientes valoraciones más bajas representen la "competencia" en las habitaciones. Si el siguiente mejor postor busca una habitación, entonces debería costar más. Esto es similar en espíritu a la subasta de Vickrey . Sin embargo, mientras que en la subasta de Vickrey el pago es totalmente independiente de la oferta del socio, en el procedimiento Gap el pago es sólo parcialmente independiente. Por lo tanto, el procedimiento Gap no es a prueba de estrategias .

El Procedimiento Gap siempre asigna precios no negativos. Como la asignación es suma máxima, obviamente también es eficiente en términos de Pareto. Sin embargo, algunos socios pueden sentir envidia. Es decir, el procedimiento Gap satisface NN y PE pero no EF.

Además, el Procedimiento de Brecha puede devolver asignaciones que no están libres de envidia, incluso cuando existen asignaciones del EF. Brams se relaciona con este problema diciendo que: "Los precios de brecha tienen en cuenta la competitividad de las ofertas de bienes, lo que hace que el mecanismo de fijación de precios esté orientado al mercado. Aunque la ausencia de envidia es una propiedad deseable, prefiero un mecanismo similar al de mercado cuando hay un conflicto". entre estas dos propiedades; los socios deberían pagar más cuando las ofertas son competitivas, incluso a costa de causar envidia". ^{[8] : 321}

Haake, Raith y Su: EF pero no NN

Haake, Raith y Su ^[7] presentan el Procedimiento de Compensación. El problema que resuelve es más general que el problema de la armonía de alquiler en ciertos aspectos:

• El número de elementos indivisibles a dividir ( m ) puede diferir del número de socios ( n ).
• Puede haber restricciones arbitrarias sobre paquetes de artículos, siempre que sean anónimos (no diferencien entre socios según su identidad). Por ejemplo, no puede haber restricción alguna, o puede haber una restricción como "cada socio debe recibir al menos una cierta cantidad de artículos", o "algunos artículos deben agruparse" (por ejemplo, porque son terrenos que deben permanecer conectado), etc.
• El "coste" total también puede ser positivo, lo que significa que también hay algo de dinero para compartir. Esto es característico de los escenarios de división de herencia. De manera similar, los "elementos" pueden tener una utilidad negativa (por ejemplo, pueden representar tareas indivisibles).

Existe un "requisito de calificación" para un socio: la suma de sus ofertas debe ser al menos el costo total.

El procedimiento funciona en los siguientes pasos.

1. Encuentre una asignación de suma máxima (utilitaria): una asignación con la suma de utilidades más alta que satisfaga las restricciones de los paquetes de artículos. Si no hay restricciones, entonces una asignación que entrega cada artículo al socio con la valoración más alta es suma máxima. Si existen restricciones (como "al menos un artículo por socio"), entonces podría ser más difícil encontrar una asignación de suma máxima.
2. Cobrar a cada socio el valor del paquete que le haya sido asignado. Esto crea la reserva inicial de dinero.
3. Pague el costo del grupo inicial. Si todos los socios cumplen con el requisito de calificación, entonces el dinero en el fondo común es suficiente y puede quedar algo de excedente .
4. Elimina la envidia compensando a los socios envidiosos. Como máximo hay rondas de compensación. El procedimiento es completamente descriptivo y dice explícitamente qué compensaciones deben realizarse y en qué orden. Además, es lo suficientemente sencillo como para realizarlo sin soporte informático. ${\displaystyle n-1}$
5. La suma de las compensaciones realizadas en todas las rondas es la suma más pequeña que se requiere para eliminar la envidia y nunca excede el excedente. Si queda algo de excedente, se puede dividir de cualquier forma que no genere envidia, por ejemplo, dando una cantidad igual a cada socio (el documento analiza otras opciones que pueden considerarse "más justas").

Cuando hay muchos elementos y restricciones complejas, el paso inicial (encontrar una asignación de suma máxima) puede ser difícil de calcular sin una computadora. En este caso, el Procedimiento de Compensación podrá iniciarse con una asignación arbitraria. En este caso, el procedimiento podría concluir con una asignación que contenga ciclos de envidia . Estos ciclos se pueden eliminar moviendo haces a lo largo del ciclo. Esto estrictamente aumenta la suma total de utilidades. Por lo tanto, después de un número limitado de iteraciones, se encontrará una asignación de suma máxima y el procedimiento puede continuar como se indicó anteriormente para crear una asignación libre de envidia.

El Procedimiento de Compensación podría cobrar a algunos socios un pago negativo (es decir, darles a los socios una cantidad positiva de dinero). Esto significa que el Procedimiento de Compensación es EF (por lo tanto también PE) pero no NN. Los autores dicen:

"No excluimos la posibilidad de que un individuo termine siendo pagado por los demás para tomar un paquete de bienes. En el contexto de una división justa, esto no nos parece problemático en absoluto. De hecho, si un grupo no desea excluir a cualquiera de sus miembros, entonces no hay razón por la que el grupo no deba subsidiar a un miembro por recibir un paquete no deseado. Además, el requisito de calificación garantiza que la subvención nunca sea consecuencia de la valoración insuficiente por parte de un jugador del conjunto completo de objetos que va a ser. repartido". ^{[7] : 746}

Sin embargo, otros autores afirman que, en el escenario habitual de los compañeros de casa:

"un compañero de casa al que se le asigna una habitación con un alquiler de habitación negativo recibe un subsidio de algunos de los otros compañeros de casa. En tal situación, algunos compañeros de casa pueden preferir dejar la habitación con un alquiler de habitación negativo sin usar y excluir al compañero de casa a quien se le asigna esa habitación, porque pueden recibir un descuento mayor. Para evitar tal situación, se deben evitar alquileres de habitaciones negativos". ^[4]

Abdulkadiroglu y Sonmez y Unver: EF y NN si es posible

Abdulkadiroğlu et al. ^[5] sugieren un enfoque basado en el mercado. Es una combinación de una subasta ascendente y una subasta descendente . Lo más sencillo es describirlo como una subasta de precio continuo:

1. Inicialice el precio de cada habitación del costo total de la casa. ${\displaystyle 1/n}$
2. Calcular el conjunto de demanda de cada socio: la habitación o conjunto de habitaciones que más le gusta a los precios actuales.
3. Calcule el conjunto de habitaciones sobredemandadas (habitaciones que demandan más socios que el número de habitaciones; consulte el documento para obtener una definición exacta).
4. Aumentar el precio de todas las habitaciones sobredemandadas con la misma tarifa;
5. Al mismo tiempo, disminuya el precio de todas las demás habitaciones con la misma tarifa, de modo que la suma de los precios de todas las habitaciones siempre sea igual al costo total.
6. Actualiza en cada instante la demanda de cada socio y el conjunto de habitaciones sobredemandadas.
7. Cuando el conjunto de habitaciones sobredemandadas esté vacío, deténgase y aplique el teorema del matrimonio de Hall para asignar a cada socio una habitación en su conjunto de demanda.

En la práctica, no es necesario cambiar el precio continuamente, ya que los únicos precios interesantes son los precios en los que cambian los conjuntos de demanda de uno o más socios. Es posible calcular de antemano el conjunto de precios interesantes y convertir la subasta de precio continuo en una subasta de precio discreto. Esta subasta de precio discreto se detiene después de un número finito de pasos. ^{[5] : 525–528}

La asignación devuelta siempre está libre de envidia. Los precios pueden ser negativos, como en el procedimiento de Haake et al. Sin embargo, a diferencia de ese procedimiento, los precios no son negativos si existe una asignación EF con precios no negativos.

Sung y Vlach: EF y NN si es posible

Sung y Vlach ^[4] prueban las siguientes propiedades generales de las asignaciones:

1. La ausencia de envidia implica suma máxima: dada una asignación x , si hay un vector de precios p con el cual x está libre de envidia, entonces x es suma máxima.
2. La suma máxima implica estar libre de envidia: dado un vector de precios p , si hay una asignación x con la cual p está libre de envidia, entonces p está libre de envidia para cualquier asignación de suma máxima.

En base a estas propiedades proponen el siguiente algoritmo:

1. Encuentre una asignación de suma máxima.
2. Encuentre un vector de precios de suma mínima (un vector en el que se minimiza la suma de precios), sujeto a la restricción de ausencia de envidia. Dicho vector de precios es una solución de un problema de programación lineal y puede encontrarse mediante el algoritmo de Bellman-Ford .
3. Si la suma mínima es igual al costo total, implemente la asignación de suma máxima con los precios de suma mínima y finalice.
4. Si la suma mínima es menor que el costo total, entonces aumente todos los precios a una tasa constante hasta que la suma sea igual al costo total (es decir, agregue a cada precio: ). Cambiar todos los precios por el mismo importe garantiza que el encargo siga estando libre de envidia. ${\displaystyle (cost-minsum)/n}$
5. Si la suma mínima es mayor que el costo total, entonces no hay solución que satisfaga tanto NN como EF. Hay varias formas posibles de proceder:
   • Disminuya todos los precios a una tasa constante hasta que la suma sea igual al costo total (es decir, reste de cada precio: ). Algunos precios serán necesariamente negativos, como en la solución de Haake Raith y Su. ${\displaystyle (minsum-cost)/n}$
   • Disminuya solo los precios positivos a una tasa constante, hasta que la suma sea igual al costo total. Aquí los precios no varían en la misma cantidad, por lo que algunos socios necesariamente sentirán envidia, como en la solución de Brams y Kilgour. Sin embargo, en esta solución, los socios envidiosos obtienen su habitación gratis .

La complejidad en tiempo de ejecución tanto para encontrar la asignación de suma máxima como para encontrar precios de suma mínima es . ${\displaystyle O(n^{3})}$

La solución de Sung y Vlach parece tener todas las propiedades deseables de los protocolos anteriores, es decir: PE, EF y NN (si es posible) y tiempo de ejecución polinomial, y además, garantiza que cada socio envidioso obtenga una habitación libre. ^[15] proporciona una implementación de una solución similar, también basada en la resolución de un problema de programación lineal pero citando un artículo diferente.

Mash, Gal, Procaccia y Zick: EF y maximin

Gal, Mash, Procaccia y Zick, ^[16] basándose en su experiencia con la aplicación de división de alquileres en el sitio web Spliddit, señalan que la ausencia de envidia por sí sola no es suficiente para garantizar la satisfacción de los participantes. Por lo tanto, construyen un marco algorítmico, basado en programación lineal, para calcular asignaciones que están libres de envidia y optimizan algún criterio. Basándose en pruebas teóricas y experimentales, concluyen que el criterio maximin (maximizar la utilidad mínima de un agente sujeto a estar libre de envidia) logra resultados óptimos.

Tenga en cuenta que, dado que su solución es siempre EF, podría arrojar precios negativos.

La solución maximin se implementa en el sitio web pref.tools.

Consideraciones presupuestarias

La mayoría de los artículos sobre el modelo cardinal suponen que los agentes tienen funciones de utilidad cuasilineales : su utilidad es el valor de la habitación menos el precio. Pero en realidad, los agentes tienen restricciones presupuestarias: si el precio de la habitación está por encima de su presupuesto, la utilidad cae mucho más rápido que de forma lineal. Procaccia, Vélez y Yu ^[17] estudian este modelo y presentan un algoritmo para encontrar si existe una asignación del FA que satisfaga las restricciones presupuestarias y, de ser así, encontrar una asignación que satisfaga un criterio de equidad adicional.

Consideraciones estratégicas

Todos los protocolos estudiados hasta ahora suponen que los socios revelan sus verdaderas valoraciones. No son a prueba de estrategias : un socio puede ganar reportando valoraciones falsas. De hecho, la seguridad estratégica es incompatible con la ausencia de envidia : no existe un protocolo determinista a prueba de estrategias que siempre devuelva una asignación libre de envidia. Esto es cierto incluso cuando sólo hay dos socios y cuando se permite que los precios sean negativos. Prueba : Supongamos que el costo total es 100 y las valoraciones de los socios son las siguientes (donde están los parámetros y ): ${\displaystyle x,y}$ ${\displaystyle 0<x<y<100}$

La única asignación de suma máxima es dar la habitación 1 al socio 1 y la habitación 2 al socio 2. Sea el precio de la habitación 2 (de modo que el precio de la habitación 1 sea ). Para garantizar que el socio 1 no tenga envidia, debemos tener . Para garantizar que el socio 2 no tenga envidia, debemos tener . ${\displaystyle p_{2}}$ ${\displaystyle 100-p_{2}}$ ${\displaystyle p_{2}\geq x/2}$ ${\displaystyle p_{2}\leq y/2}$

Supongamos que un protocolo determinista fija el precio en algún valor en . Si el precio es superior a , entonces el socio 2 tiene un incentivo para informar un valor inferior de , que aún está por encima , para reducir su pago hacia . De manera similar, si el precio es menor que , entonces el socio 1 tiene un incentivo para informar un valor más alto de , que aún está por debajo de , para impulsar el pago del socio 2 hacia arriba (y así empujar su propio pago hacia abajo). Por tanto, el mecanismo no puede ser a prueba de estrategias. ${\displaystyle p_{2}}$ ${\displaystyle [x/2,y/2]}$ ${\displaystyle x/2}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x/2}$ ${\displaystyle y/2}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y/2}$

Los investigadores han afrontado esta imposibilidad de dos maneras.

Sol y Yang: cambiando el problema

Existe una variante del problema en la que, en lugar de suponer que el coste total de la casa es fijo, suponemos que hay un coste máximo para cada habitación. En esta variante, existe un mecanismo a prueba de estrategias: la regla de asignación determinista que selecciona el costo de suma mínima es a prueba de estrategias. ^[18]

Este resultado puede generalizarse para obtener una mayor flexibilidad en los objetos indivisibles y una prueba de la idoneidad de la estrategia de coalición. ^{[19] [20]}

Dufton y Larson: uso de la aleatorización

Volviendo al problema original de la armonía de alquileres, es posible considerar mecanismos aleatorios . Un mecanismo aleatorio devuelve una distribución de probabilidad sobre las asignaciones de habitaciones y las divisiones de alquiler. Un mecanismo aleatorio tiene expectativas veraces si ningún socio puede aumentar el valor esperado de su utilidad informando erróneamente sus valoraciones a las salas. La equidad de un mecanismo aleatorio se puede medir de varias maneras: ^[6]

1. Libre de envidia ex ante significa que ningún socio envidia la lotería de otro socio. Esta condición es trivial de lograr en un mecanismo veraz: aleatorizar todas las asignaciones posibles con igual probabilidad y cargar a cada socio el costo total. Pero esta condición no es atractiva, ya que existe una gran posibilidad de que, en el resultado final, muchos socios sientan envidia. Quizás no se sientan reconfortados por el hecho de que la lotería haya sido justa. ${\displaystyle 1/n}$

2. Probabilidad garantizada de ausencia de envidia (GPEF) significa que existe una cierta probabilidad de que, independientemente de las valoraciones de los socios, con una probabilidad de al menos , el resultado final esté libre de envidia. Es posible lograr un GPEF de la siguiente manera: encontrar una tarea libre de envidia; elige un número entero al azar; y mover cada socio cíclicamente habitaciones hacia la derecha. Este mecanismo aleatorio es fiel a las expectativas, ya que cada socio tiene la misma probabilidad de aterrizar en cada habitación y el pago esperado es del costo total, independientemente de la oferta del socio. La probabilidad de tener una asignación del EF es la probabilidad de que , que es exactamente . Esto no es alentador, ya que la probabilidad de estar libre de envidia converge a 0 cuando crece el número de socios. Pero es imposible hacerlo mejor: en todo mecanismo de confianza en las expectativas, el GPEF es, como máximo , . ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle 1/n}$ ${\displaystyle i\in \{0,\dots ,n-1\}}$ ${\displaystyle i}$ ${\displaystyle 1/n}$ ${\displaystyle i=0}$ ${\displaystyle 1/n}$ ${\displaystyle 1/n}$

3. Número esperado de socios libres de envidia (ENEF) significa que hay un número entero tal que, si promediamos el número de socios que no envidian en todos los resultados posibles del mecanismo, entonces, independientemente de las valoraciones de los socios, el La expectativa es al menos . El criterio ENEF parece más apropiado que el criterio GPEF, porque mide no sólo la probabilidad de estar completamente libre de envidia, sino también la calidad de los casos en los que la asignación no está completamente libre de envidia. El ENEF máximo de un mecanismo veraz en las expectativas es como máximo . Es posible lograr este límite para . Para , existe un mecanismo de veracidad en la expectativa que casi alcanza este límite: la ENEF es . La idea general es la siguiente. Utilice el mecanismo VCG para calcular una asignación y pagos de suma máxima. Seleccione un compañero al azar. Ignora a ese compañero y usa VCG nuevamente. Combine los resultados de una manera que garantice que el pago total sea igual al costo total (consulte el documento para obtener más detalles). Es posible demostrar que: (a) el mecanismo es veraz en las expectativas; (b) todos los socios, excepto el socio ignorado, no tienen envidia. Por tanto, la ENEF es . Las simulaciones muestran que en aproximadamente el 80% de los casos, el GPEF de este mecanismo también está en su máximo de . ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle n-1+1/n}$ ${\displaystyle n=2}$ ${\displaystyle n>2}$ ${\displaystyle n-1}$ ${\displaystyle n-1}$ ${\displaystyle 1/n}$

Andersson, Ehlers y Svensson: lograr la resistencia a la estrategia parcial

Una posible relajación del requisito de idoneidad estratégica es tratar de minimizar el "grado de manipulabilidad". ^[21] Esto se define contando, para cada perfil, el número de agentes que pueden manipular la regla. Las reglas de asignación justa máximamente preferidas son las reglas de asignación mínimamente manipulables (individualmente y en coalición) justas y con equilibrio presupuestario según este nuevo concepto. Dichas reglas eligen asignaciones con el número máximo de agentes para quienes se maximiza la utilidad entre todas las asignaciones justas y presupuestarias equilibradas.

Ver también

Hay varios problemas en los que sólo hay bienes indivisibles para compartir, sin transferencias monetarias:

• Asignación aleatoria justa : cada agente debe recibir un único objeto; la equidad se logra mediante la aleatorización.
• Problema de asignación de viviendas : cada agente debe recibir un único objeto (casa); No se permite la aleatorización. Los objetivos son eficiencia y/o equidad.
• Coincidencia sin envidia : cada agente debe obtener como máximo un objeto; el objetivo es maximizar el número de asignaciones sujetas a estar libres de envidia.
• Asignación justa de artículos : cada agente puede obtener una cantidad arbitraria de objetos.
• Problema de asignación : cada agente debe recibir un único objeto; el objetivo es maximizar el valor total o minimizar el costo total.

Referencias

1. , FE (1999). "Armonía de alquiler: lema de Sperner en división justa". El Mensual Matemático Estadounidense . 106 (10): 930–942. doi :10.2307/2589747. JSTOR  2589747.
2. Azrieli, Yaron; Shmaya, Eran (2014). "Armonía de alquiler con compañeros de piso". Revista de teoría económica . 153 : 128. arXiv : 1406.6672 . doi :10.1016/j.jet.2014.06.006. S2CID  12129179.
3. Potthoff, Richard F. (2002). "Uso de la programación lineal para encontrar una solución libre de envidia más cercana a la solución de la brecha Brams-Kilgour para el problema de los compañeros de casa". Decisión y negociación grupal . 11 (5): 405. doi :10.1023/A:1020485018300. S2CID  122452727.
4. Sung, Shao Chin; Vlach, Milán (2004). "División competitiva sin envidias". Elección social y bienestar . 23 . doi :10.1007/s00355-003-0240-z. S2CID  11638306.
5. Abdulkadiroğlu, Atila; Sönmez, Tayfun; Utku Ünver, M. (2004). "División cesión-alquiler de habitaciones: una aproximación al mercado". Elección social y bienestar . 22 (3): 515. CiteSeerX 10.1.1.198.186 . doi :10.1007/s00355-003-0231-0. 
6. Lachlan Dufton y Kate Larson (2011). "División de alquiler y asignación de habitaciones aleatorias" (PDF) . Actas del Taller IJCAI-2011 sobre Elección Social e Inteligencia Artificial . IJCAI. págs. 34–39 . Consultado el 5 de marzo de 2016 .
7. Haake, Claus-Jochen; Raith, Matías G.; Su, Francis Edward (2002). "Licitar por estar libre de envidia: un enfoque procesal para los problemas de división justa de n jugadores". Elección social y bienestar . 19 (4): 723. CiteSeerX 10.1.1.26.8883 . doi :10.1007/s003550100149. S2CID  2784141. 
8. J. Brams (2008). Matemáticas y democracia: diseño de mejores procedimientos de votación y división justa . Princeton, Nueva Jersey: Princeton University Press. ISBN 9780691133218.
9. Sun, Albert (28 de abril de 2014). "Para dividir el alquiler, comience con un triángulo". Los New York Times . Consultado el 26 de agosto de 2014 .
10. Procaccia, Ariel (15 de agosto de 2012). "La división justa y el problema de los filósofos quejosos". La mano invisible de Turing . Consultado el 26 de agosto de 2014 .
11. "Página de la división justa de Francis Su". Math.hmc.edu . Consultado el 5 de enero de 2017 .
12. "Divida su alquiler de manera justa". Los New York Times . 28 de abril de 2014 . Consultado el 5 de enero de 2017 .
13. Segal-Halevi, Erel (28 de mayo de 2022). "Armonía de alquiler generalizada". El Mensual Matemático Estadounidense . 129 (5): 403–414. arXiv : 1912.13249 . doi :10.1080/00029890.2022.2037988. ISSN  0002-9890.
14. Brams, Steven J.; Kilgour, D. Marc (2001). "División Feria Competitiva". Revista de Economía Política . 109 (2): 418. doi : 10.1086/319550. S2CID  154200252.
15. "Asignar habitaciones y compartir alquiler - Spliddit". Archivado desde el original el 5 de marzo de 2016 . Consultado el 5 de marzo de 2016 .
16. Gal, Ya'akov (Kobi); Puré, Moshé; Procaccia, Ariel D.; Zick, Yair (21 de julio de 2016). ¿Cuál es la más justa (división de alquiler) de todas? . ACM. págs. 67–84. doi :10.1145/2940716.2940724. ISBN 9781450339360. S2CID  53223944.
17. Ariel D. Procaccia, Rodrigo A. Vélez y Dingli Yu. "División de alquiler justo con un presupuesto". AAAI 2018.
18. Sol, Ning; Yang, Zaifu (2003). "Un mecanismo de asignación justa a prueba de estrategias generales" (PDF) . Cartas de Economía . 81 : 73. doi : 10.1016/s0165-1765(03)00151-4.
19. Andersson, Tommy; Svensson, Lars-Gunnar (2008). "Asignación no manipulable de personas a puestos revisados". Ciencias Sociales Matemáticas . 56 (3): 350. doi :10.1016/j.mathsocsci.2008.05.004.
20. Andersson, Tommy (2009). "Revisión de un mecanismo de asignación justa a prueba de estrategias generales". Boletín de Economía . 29 (3): 1719-1724.
21. Andersson, Tommy; Ehlers, Lars; Svensson, Lars-Gunnar (2014). "Equilibrio presupuestario, equidad y mínima manipulabilidad". Economía Teórica . 9 (3): 753. doi : 10.3982/te1346 . hdl : 10419/150236 .