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:
Hay varias propiedades que nos gustaría que el encargo cumpliera.
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:
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.
El protocolo de Francis Su [1] hace las siguientes suposiciones sobre las preferencias de los socios:
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.
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 [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:
Las principales herramientas utilizadas en la prueba son:
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.
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]
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
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.
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]
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 [8] : 305–328 [14] sugieren el procedimiento Gap :
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, 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:
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.
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:
Sin embargo, otros autores afirman que, en el escenario habitual de compañeros de casa:
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:
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 [4] demuestran las siguientes propiedades generales de las asignaciones:
Basándose en estas propiedades, proponen el siguiente algoritmo:
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 .
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 [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).
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 [18] estudian un entorno práctico en el que los agentes pueden no estar seguros de sus valoraciones.
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:
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.
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.
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 .
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 ):
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 .
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.
Los investigadores han afrontado esta imposibilidad de dos maneras.
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]
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.
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 .
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 .
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.
Existen varios problemas en los que sólo hay elementos indivisibles para compartir, sin transferencias monetarias:
{{citation}}
: CS1 maint: nombres numéricos: lista de autores ( enlace )