Armonía en el alquiler

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

En un contexto típico, hay parejas que alquilan juntas una casa de dos habitaciones por un precio que fija el propietario. Cada uno de los inquilinos puede tener preferencias diferentes: uno puede preferir una habitación grande, otro puede preferir una habitación con vistas 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 el encargo cumpliera.

• No negatividad (NN) : todos los precios deben ser 0 o más: ningún socio debe recibir pago para obtener una habitación.
• Sin envidia (FE) : 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 porción de habitación + alquiler es ligeramente mejor que todas las demás. FE significa que cada socio prefiere la habitación que le corresponde. Es decir, ningún socio querría tomar otra habitación por el alquiler asignado a esa habitación.
• Eficiencia de Pareto (EP) : Ninguna otra asignación de socios a las 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 en el sentido de Pareto. Demostración: 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 es envidioso.

El problema de la armonía en el 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 solo 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, para 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 como 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 una menor carga mental para los socios.

Versión ordinal

Su: una persona por habitación

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

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

Normalice el alquiler total a 1. Entonces, cada esquema de precios es un punto en un símplex de dimensión 1 con vértices en . El protocolo de Su opera sobre una versión dualizada de este símplex de manera similar a los protocolos Simmons-Su para el corte de torta: para cada vértice de una triangulación del símplex dual, que corresponde a un cierto esquema de precios, le pregunta al socio propietario "¿qué habitación prefiere en ese esquema de precios?". Esto da como resultado una coloración de Sperner del símplex dual y, por lo tanto, 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 converge a una asignación sin envidia. Los precios siempre son no negativos. Por lo 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 una (es decir, varios socios pueden vivir en la misma habitación).

Prueban 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 dado cada vector de precios.
2. Sin externalidades : a todos los socios les gustan las habitaciones gratuitas.
3. Socios avaros : Las preferencias son continuas en precios.

Las principales herramientas utilizadas en la prueba son:

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

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

Propiedades generales de los protocolos ordinales

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

Hay varias razones por las que dicha generalidad puede ser ú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 la A es cara, el socio se decide por la B. Pero si la A es más barata, el socio podría comprar la C (que es la más barata) y luego ahorrar algo de dinero y cambiarse a la 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, en cierta medida, 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 cambiar a C, pensando que "es lo mismo que B pero a un precio de ganga...".

B. Tanto la solución de Su como la de Azrieli y Shmaya parten de la hipótesis de que los inquilinos son avaros: suponen que un inquilino siempre prefiere una habitación gratis a una que no lo es. Esta hipótesis es sólida y no siempre realista. Si una de las habitaciones es muy mala, es posible que algunos inquilinos no quieran vivir en ella 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 la habitación A es gratis y la habitación B cuesta 50, entonces seguramente 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 cumplirá si una persona siempre prefiere una habitación libre a una habitación que cueste al menos el 20% del alquiler total. Sin embargo, incluso este supuesto debilitado podría ser poco realista, como en el ejemplo anterior. ^{[8] : 320–321} ${\displaystyle 1/(n-1)}$

Segal-Halevi ^[13] muestra que el supuesto puede debilitarse aún más. 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 exista un precio que sea demasiado alto para todos los agentes. Este supuesto es más débil que el supuesto de los inquilinos avaros y más débil que la cuasililinealidad. Es una cuestión abierta si existe un supuesto aún más débil que garantice la existencia de la armonía en el alquiler.

Versión cardinal

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. Generalmente se supone que los agentes tienen utilidades cuasilineales , de modo que su utilidad para una habitación es su valor por la habitación menos el precio de la misma.

Una noción clave en las soluciones cardinales es una asignación de suma máxima (también conocida como utilitaria ). Se trata de una asignación de socios a las habitaciones, que maximiza la suma de las ofertas. El problema de encontrar una asignación de suma máxima se conoce como el problema de asignación , y se puede resolver mediante el algoritmo húngaro en el tiempo (donde es el número de socios). Cada asignación de EF es de 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 no envidiar y de no realizar pagos negativos no siempre son compatibles. Por ejemplo, supongamos que el costo total es 100 y las valoraciones son:

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

En este ejemplo, la suma de las valoraciones es mayor que el costo total. Si la suma de las valoraciones es igual al costo total y hay dos o tres socios, entonces siempre existe una asignación de 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} para la prueba):

Tenga en cuenta que este ejemplo no se da en la versión ordinal, ya que los protocolos ordinales hacen 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, la suposición no se cumple y no existe una asignación EF+NN. Por lo tanto, los protocolos en la versión cardinal tienen que llegar a un compromiso entre EF y NN. Cada protocolo hace un compromiso diferente.

Brams y Kilgour: NN pero no EF

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

1. Calcular una asignación de suma máxima.
2. Si el importe máximo es menor que el coste total, entonces el problema es irresoluble, ya que los socios no quieren pagar el importe total exigido 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 representan la "competencia" por las habitaciones. Si hay una habitación que es más solicitada por el siguiente postor más alto, entonces debería costar más. Esto es similar en espíritu a la subasta Vickrey . Sin embargo, mientras que en la subasta Vickrey el pago es completamente independiente de la oferta del socio, en el procedimiento Gap el pago es solo 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 de suma máxima, obviamente también es eficiente en términos de Pareto. Sin embargo, algunos socios pueden envidiarlo. 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 existan asignaciones de EF. Brams se relaciona con este problema diciendo que: "Los precios de brecha tienen en cuenta la competitividad de las ofertas por 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 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 y 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 alquileres en ciertos aspectos:

• El número de elementos indivisibles a dividir ( m ) puede ser diferente al número de socios ( n ).
• Pueden existir restricciones arbitrarias sobre los paquetes de elementos, siempre que sean anónimos (no diferencien entre socios en función de su identidad). Por ejemplo, puede no haber ninguna restricción, o una restricción como "cada socio debe recibir al menos una cierta cantidad de elementos", o "algunos elementos deben estar agrupados" (por ejemplo, porque son lotes de tierra que deben permanecer conectados), etc.
• El "costo" 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 herencias. De manera similar, los "artículos" pueden tener una utilidad negativa (por ejemplo, pueden representar tareas indivisibles).

Existe un "requisito de calificación" para ser 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 sobre los paquetes de artículos. Si no hay restricciones, entonces una asignación que le dé cada artículo al socio con la valoración más alta es de suma máxima. Si hay restricciones (como "al menos un artículo por socio"), entonces una asignación de suma máxima puede ser más difícil de encontrar.
2. Cobrar a cada socio el valor del paquete que le corresponde. Esto crea el fondo común inicial de dinero.
3. Pagar el costo del fondo inicial. Si todos los socios cumplen con el requisito de calificación, entonces el dinero del fondo es suficiente y puede quedar algún excedente .
4. Eliminar la envidia compensando a la pareja envidiosa. Hay varias 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 simple como para llevarlo a cabo sin la ayuda de un ordenador. ${\displaystyle n-1}$
5. La suma de las compensaciones realizadas en todas las rondas es la suma mínima que se requiere para eliminar la envidia, y nunca excede el excedente. Si queda algún excedente, se puede dividir de cualquier manera que no genere envidia, por ejemplo, dando una cantidad igual a cada socio (el artículo analiza otras opciones que pueden considerarse "más justas").

Cuando hay muchos ítems 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 puede comenzar con una asignación arbitraria. En este caso, el procedimiento puede concluir con una asignación que contenga ciclos de envidia . Estos ciclos pueden eliminarse moviendo paquetes a lo largo del ciclo. Esto aumenta estrictamente 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 sin envidia.

El procedimiento de compensación podría cobrar a algunos socios un pago negativo (es decir, darles 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 descartamos la posibilidad de que un individuo pueda terminar recibiendo un pago de los demás por tomar un conjunto de bienes. En el contexto de una división justa, no nos parece problemático en absoluto. De hecho, si un grupo no desea excluir a ninguno de sus miembros, entonces no hay razón por la cual el grupo no deba subsidiar a un miembro por recibir un conjunto no deseado. Además, el requisito de calificación garantiza que la subvención nunca sea consecuencia de una valoración insuficiente por parte de un jugador del conjunto completo de objetos a distribuir". ^{[7] : 746}

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

"Un compañero de casa al que se le asigna una habitación con un alquiler negativo recibe una subvención 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 alquiler negativo sin usar y excluir al compañero de casa al que se le asigna esa habitación, porque puede recibir un descuento mayor. Para evitar tal situación, deben evitarse los alquileres negativos de las habitaciones". ^[4]

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

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

1. Inicializa el precio de cada habitación al 50 % del coste 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 gustan a los precios actuales.
3. Calcule el conjunto de habitaciones con sobredemanda (habitaciones que son demandadas por más socios que el número de habitaciones; consulte el documento para obtener la definición exacta).
4. Aumentar el precio de todas las habitaciones sobredemandadas en la misma tarifa;
5. Simultáneamente, disminuya el precio de todas las demás habitaciones de la misma tarifa, de modo que la suma de los precios de todas las habitaciones siempre sea igual al costo total.
6. En cada instante, actualiza la demanda de cada socio y el conjunto de habitaciones sobredemandadas.
7. Cuando el conjunto de habitaciones con exceso de demanda 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 aquellos en los que cambian los conjuntos de demanda de uno o más socios. Es posible calcular el conjunto de precios interesantes de antemano 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 de FE con precios no negativos.

Sung y Vlach: EF y NN si es posible

Sung y Vlach ^[4] demuestran 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 ausencia de envidia: dado un vector de precios p , si hay una asignación x con la que p está libre de envidia, entonces p está libre de envidia para cualquier asignación de suma máxima.

Basándose en estas propiedades, proponen el siguiente algoritmo:

1. Encuentra una asignación de suma máxima.
2. Hallar un vector de precios de suma mínima (un vector en el que la suma de precios se minimiza), 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 se puede hallar mediante el algoritmo 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 la misma cantidad garantiza que la asignación permanezca libre de envidia. ${\displaystyle (cost-minsum)/n}$
5. Si la suma mínima es mayor que el costo total, entonces no existe una solución que satisfaga tanto NN como EF. Hay varias formas posibles de proceder:
   • Disminuir todos los precios a una tasa constante hasta que la suma sea igual al costo total (es decir, restar de cada precio: ). Algunos precios serán necesariamente negativos, como en la solución de Haake Raith y Su. ${\displaystyle (minsum-cost)/n}$
   • Disminuir sólo los precios positivos a una tasa constante, hasta que la suma sea igual al costo total. En este caso, los precios no cambian 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 los 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 y EF y NN (si es posible) y tiempo de ejecución polinomial, y además, garantiza que cada socio envidioso obtenga una habitación gratis. ^[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.

Aragonés: EF y dinero-Rawlsiano

Aragonés ^[16] presentó un algoritmo politemporal para encontrar una solución EF que, entre todas las soluciones EF, maximice el pago más pequeño por parte de un agente (se denomina solución Money Rawlsian).

Mash, Gal, Procaccia y Zick: EF e igualitario

Gal, Mash, Procaccia y Zick, ^[17] basándose en su experiencia con la aplicación de división de rentas 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 sean a la vez libres de envidia y optimicen algún criterio. Con base en pruebas teóricas y experimentales, concluyen que la regla igualitaria -maximizar la utilidad mínima de un agente sujeto a la ausencia de envidia- logra resultados óptimos.

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

La solución maximin está implementada en el sitio web spliddit.org y en el sitio web pref.tools.

Peters, Procaccia y Zhu: EF robusta

Peters, Procaccia y Zhu ^[18] estudian un entorno práctico en el que los agentes pueden no estar seguros de sus valoraciones.

Agentes con un presupuesto limitado

Restricciones presupuestarias estrictas

La mayoría de los artículos sobre el modelo cardinal suponen que los agentes tienen funciones de utilidad cuasililineales (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 es superior a su presupuesto, la utilidad cae mucho más rápido que de manera lineal. De hecho, un agente siempre prefiere cualquier habitación con un precio que se ajuste a su presupuesto, a una habitación con un precio mayor que su presupuesto.

En este caso, puede que no exista un vector de precios que sea a la vez EF y asequible. Por ejemplo, ^[19] supongamos que el alquiler total es de 1000, hay dos habitaciones y dos agentes con valoraciones idénticas: 800 y 200, y presupuesto idéntico: 600. Hay un único vector de precios en el que ambos agentes tienen la misma utilidad cuasilineal: (800,200); pero el agente de la habitación 1 no tiene suficiente presupuesto para pagar. Por el contrario, hay vectores de precios asequibles, por ejemplo (600,400), pero no están libres de envidia.

Nótese que la condición de "precio demasiado alto" ^[13] todavía se cumple en este caso, pero las preferencias no son continuas (los agentes prefieren solo la habitación 2 cuando p1>600 y solo la habitación 1 cuando p1<=600).

Procaccia, Velez y Yu ^[19] presentan un algoritmo eficiente para determinar si existe una asignación que sea a la vez EF y asequible. Si es así, encuentran una asignación que, entre todas las asignaciones EF asequibles, maximice la utilidad más pequeña (como en la asignación de artículos igualitaria ).

Airiau, Gilbert, Grandi, Lang y Wilczynski ^[20] sugieren dos soluciones para superar el problema de inexistencia con restricciones presupuestarias:

• Relajando el EF a un EF económico , lo que significa que el agente i puede envidiar al agente j si j paga más que el presupuesto de i . Es más probable que exista una asignación BF-EF que una asignación EF, pero aún así no se garantiza que exista. Muestran un MILP para calcular una asignación BF-EF si existe. También muestran un algoritmo politemporal para un vector de precio fijo y un algoritmo pseudopolitemporal para una asignación de habitación fija.
• Permitiendo la asignación fraccionaria , es decir, asignar (1,2) con precio a los agentes (1,2) durante medio año e invertir la asignación durante la otra mitad, y cobrar a cada agente 500. Muestran un programa lineal para encontrar una asignación EF fraccionaria si existe. Muestran que encontrar una asignación EF con la menor cantidad de cambios totales es NP-difícil (por reducción del problema de partición o del problema del vendedor de Hamming ), pero se puede resolver en tiempo O*(2 ^k ) por programación dinámica , donde k es el tamaño de la descomposición de Birkhoff ^{[ desambiguación necesaria ]} ( k ≤ n ² ). Conjeturan que minimizar la mayor cantidad de cambios por agente también es NP-difícil.

Ambas relajaciones amplían significativamente el conjunto de asignaciones de FE. Sin embargo, incluso con cada una de ellas, es posible que no exista una asignación de FE.

Restricciones presupuestarias blandas

Velez ^[21] estudia la división de rentas de EF bajo restricciones presupuestarias blandas . Cada agente informa sus valores para las habitaciones, su presupuesto y su desutilidad marginal por tener que pagar más que el presupuesto (por ejemplo, la tasa de interés ). Presenta un algoritmo que encuentra una división de rentas de EF que sea, además, igualitaria (utilidad mínima máxima), o monetaria-rawlsiana (renta mínima-máxima), o que satisfaga una de otras condiciones similares. El tiempo de ejecución está en O( n ^{k + c} ), donde n es el número de agentes, k es el número de diferentes valores de desutilidad (por ejemplo, diferentes tasas de interés) y c > 2 es alguna constante.

Velez ^[22] estudia las propiedades estratégicas de estos algoritmos. Muestra que los resultados no cooperativos con información completa de cada uno de los algoritmos son exactamente las asignaciones de FE con respecto a las preferencias verdaderas, siempre y cuando el número de desutilidades permitidas esté limitado.

Utilidades lineales por partes

Arunachaleswaran, Barman y Rathi ^[23] estudian un escenario sustancialmente más general que el cuasilineal, en el que la utilidad de cada agente de cada habitación puede ser cualquier función lineal por partes del alquiler. Este escenario generaliza la restricción presupuestaria blanda. Como hay un precio demasiado alto, siempre existe una asignación EF. Muestran un FPTAS , un algoritmo que encuentra una asignación que es EF hasta (1+ ε ), en polinomio temporal en 1/ ε y n ^{k + c} , donde n es el número de agentes, k es el número de diferentes valores de desutilidad (por ejemplo, diferentes tasas de interés) y c >2 es alguna constante. También muestran que las líneas del problema en la intersección de las clases de complejidad PPAD y PLS .

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 si informa valoraciones falsas. De hecho, la a prueba de estrategias 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 solo hay dos socios y cuando se permite que los precios sean negativos. Demostración : supongamos que el costo total es 100 y las valoraciones de los socios son las siguientes (donde son parámetros y ): ${\displaystyle x,y}$ ${\displaystyle 0<x<y<100}$

La única asignación 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 envidie, debemos tener . Para garantizar que el socio 2 no envidie, 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 un valor determinado en . Si el precio es superior a , entonces el socio 2 tiene un incentivo para informar un valor inferior de , que sigue estando por encima de , con el fin de reducir su pago hacia . De manera similar, si el precio es inferior a , entonces el socio 1 tiene un incentivo para informar un valor superior de , que sigue estando por debajo de , con el fin de aumentar el pago del socio 2 hacia (y, por lo tanto, reducir su propio pago). Por lo 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 coste mínimo es a prueba de estrategias. ^[24]

Este resultado se puede generalizar para lograr una mayor flexibilidad en los objetos indivisibles y como prueba de la imposibilidad de aplicar estrategias de coalición. ^{[25] [26]}

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 asignaciones de habitaciones y divisiones de alquiler. Un mecanismo aleatorio es veraz en expectativa si ningún socio puede aumentar el valor esperado de su utilidad informando incorrectamente sus valoraciones de las habitaciones. La imparcialidad de un mecanismo aleatorio se puede medir de varias maneras: ^[6]

1. La ausencia de envidia ex ante significa que ningún socio envidia la lotería de ningún otro socio. Esta condición es fácil de lograr en un mecanismo veraz: aleatorizar todas las asignaciones posibles con la misma probabilidad y cobrar 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. Puede que no se sientan reconfortados por el hecho de que la lotería haya sido justa. ${\displaystyle 1/n}$

2. La probabilidad garantizada de ausencia de envidia (GPEF, por sus siglas en inglés) 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 una GPEF de de la siguiente manera: encontrar una asignación libre de envidia; elegir un número entero al azar; y mover a cada socio cíclicamente habitaciones hacia la derecha. Este mecanismo aleatorio es veraz en expectativa, 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 EF es la probabilidad de que , que es exactamente . Esto no es alentador, ya que la probabilidad de ausencia de envidia converge a 0 cuando el número de socios crece. Pero es imposible hacerlo mejor: en cada mecanismo veraz en expectativa, la 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. El número esperado de socios libres de envidia (ENEF) significa que hay un cierto 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, la expectativa es al menos . El criterio ENEF parece más apropiado que el criterio GPEF, porque mide no solo la probabilidad de una ausencia total 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 de expectativa veraz es como máximo . Es posible alcanzar este límite para . Para , hay un mecanismo de expectativa veraz que casi alcanza este límite: el 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 socio al azar. Ignore a ese socio y utilice 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 sus expectativas; (b) todos los socios, excepto el socio ignorado, no envidian. Por lo tanto, la ENEF es . Las simulaciones muestran que en aproximadamente el 80% de los casos, la 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 y Ehlers y Svensson: Lograr la a prueba de estrategias parciales

Una posible relajación del requisito de protección frente a estrategias es intentar minimizar el "grado de manipulabilidad". ^[27] Esto se define contando, para cada perfil, el número de agentes que pueden manipular la regla. Las reglas de asignación justa de máxima preferencia son las reglas de asignación justa y equilibrada presupuestariamente mínimamente manipulables (individual y colectivamente) según este nuevo concepto. Dichas reglas eligen asignaciones con el número máximo de agentes para los que se maximiza la utilidad entre todas las asignaciones justas y equilibradas presupuestariamente.

Véase también

Existen varios problemas en los que sólo hay elementos 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 la eficiencia y/o la equidad.
• Coincidencia sin envidia : cada agente debe recibir como máximo un objeto; el objetivo es maximizar la cantidad de asignaciones sujetas a ausencia de envidia.
• Asignación justa de objetos : 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. Su, FE (1999). "Armonía de alquiler: el lema de Sperner en la división justa". The American Mathematical Monthly . 106 (10): 930–942. doi :10.2307/2589747. JSTOR  2589747.
2. Azrieli, Yaron; Shmaya, Eran (2014). "Armonía en el alquiler con compañeros de habitación". Journal of Economic Theory . 153 : 128. arXiv : 1406.6672 . doi :10.1016/j.jet.2014.06.006. S2CID  12129179.
3. Potthoff, Richard F. (2002). "Uso de programación lineal para encontrar una solución libre de envidia más cercana a la solución de la brecha de 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, Milan (2004). "División competitiva sin envidia". 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). "Randomised Room Assignment-Rent Division" (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, Matthias G.; Su, Francis Edward (2002). "Pujar por la ausencia de envidia: un enfoque procedimental para los problemas de reparto justo entre n jugadores". Elección social y bienestar . 19 (4): 723. CiteSeerX 10.1.1.26.8883 . doi :10.1007/s003550100149. S2CID  2784141. 
8. Steven J. Brams (2008). Matemáticas y democracia: diseño de mejores procedimientos de votación y de división justa . Princeton, NJ: Princeton University Press. ISBN 9780691133218.
9. Sun, Albert (28 de abril de 2014). "Para dividir la renta, hay que empezar con un triángulo". The New York Times . Consultado el 26 de agosto de 2014 .
10. Procaccia, Ariel (15 de agosto de 2012). «División justa y el problema de los filósofos quejumbrosos». La mano invisible de Turing . Consultado el 26 de agosto de 2014 .
11. "Página de división justa de Francis Su". Math.hmc.edu . Consultado el 5 de enero de 2017 .
12. "Divide tu renta de manera justa". The 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". The American Mathematical Monthly . 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. Aragones, Enriqueta (1995-06-01). "Una derivación de la solución monetaria rawlsiana". Elección social y bienestar . 12 (3): 267–276. doi :10.1007/BF00179981. ISSN  1432-217X.
17. Gal, Ya'akov (Kobi); Mash, Moshe; Procaccia, Ariel D.; Zick, Yair (21 de julio de 2016). ¿Cuál es la división de rentas más justa de todas? . ACM. págs. 67–84. doi :10.1145/2940716.2940724. ISBN 9781450339360. Número de identificación del sujeto  53223944.
18. Peters, Dominik; Procaccia, Ariel D.; Zhu, David (6 de diciembre de 2022). "División robusta de la renta". Avances en sistemas de procesamiento de información neuronal . 35 : 13864–13876.
19. Ariel D. Procaccia, Rodrigo A. Vélez y Dingli Yu. "División de alquiler justo con un presupuesto". AAAI 2018.
20. Airiau, Stéphane; Gilbert, Hugo; Grandi, Humberto; Lang, Jé rô me; Wilczynski, Anaë lle (2023), "División de alquiler justo con un presupuesto revisado", ECAI 2023 , Fronteras en aplicaciones e inteligencia artificial, IOS Press, págs. 52–59, doi :10.3233/FAIA230253, ISBN 978-1-64368-436-9, consultado el 28 de julio de 2024{{citation}}: CS1 maint: nombres numéricos: lista de autores ( enlace )
21. Velez, Rodrigo A. (1 de julio de 2022). "Un algoritmo polinomial para la división de renta sin envidia maxmin y minmax en un presupuesto blando". Elección social y bienestar . 59 (1): 93–118. doi :10.1007/s00355-021-01386-z. ISSN  1432-217X.
22. Velez, Rodrigo A. (2023). "División equitativa de la renta con un presupuesto blando". Juegos y comportamiento económico . 139 (C): 1–14. doi :10.1016/j.geb.2023.01.008.
23. Arunachaleswaran, Eshwar Ram; Barman, Siddharth; Rathi, Nidhi (agosto de 2022). "Esquemas de aproximación de tiempo completamente polinomial para la división justa de la renta". Matemáticas de la investigación de operaciones . 47 (3): 1970–1998. arXiv : 1807.04163 . doi :10.1287/moor.2021.1196. ISSN  0364-765X.
24. Sun, Ning; Yang, Zaifu (2003). "Un mecanismo de asignación justa de la estrategia general" (PDF) . Economics Letters . 81 : 73. doi :10.1016/s0165-1765(03)00151-4.
25. Andersson, Tommy; Svensson, Lars-Gunnar (2008). "Revisión de la asignación no manipulable de individuos a posiciones". Ciencias Sociales Matemáticas . 56 (3): 350. doi :10.1016/j.mathsocsci.2008.05.004.
26. Andersson, Tommy (2009). "Revisión de un mecanismo de asignación equitativa a prueba de estrategias generales". Boletín Económico . 29 (3): 1719–1724.
27. 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 .