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:
Hay varias propiedades que nos gustaría que cumpliera la tarea.
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:
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.
El protocolo de Francis Su [1] hace los siguientes supuestos sobre las preferencias de los socios:
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.
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 [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).
Acreditan 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: existe un procedimiento que aproxima la solución a cualquier precisión dada.
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]
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 sólida 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
Segal-Halevi [13] muestra que la suposición 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 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.
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 habitación.
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]
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 [8] : 305–328 [14] sugieren el procedimiento Gap :
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 [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:
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.
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:
Sin embargo, otros autores afirman que, en el escenario habitual de los compañeros de casa:
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:
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 [4] prueban las siguientes propiedades generales de las asignaciones:
En base a 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 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, EF y NN (si es posible) y tiempo de ejecución polinómico, 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.
Aragonés [16] presentó un algoritmo politime 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 llama solución Money Rawls).
Gal, Mash, Procaccia y Zick, [17] 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 la regla igualitaria (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 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 estar inseguros acerca de sus valoraciones.
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. De hecho, un agente siempre prefiere cualquier habitación con un precio máximo de su presupuesto, a una habitación con un precio superior a 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 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, existen vectores de precios asequibles, por ejemplo (600.400), pero no están exentos de envidia.
Tenga en cuenta 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, Vélez 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í, encuentra una asignación que, entre todas las asignaciones asequibles del FE, maximiza la utilidad más pequeña (como en la asignación igualitaria de ítems ).
Airiau, Gilbert, Grandi, Lang y Wilczynski [20] sugieren dos soluciones para superar el problema de la inexistencia con restricciones presupuestarias:
Ambas flexibilizaciones amplían significativamente el conjunto de asignaciones del FA. Sin embargo, incluso con cada una de estas flexibilizaciones, es posible que no exista una asignación del FA.
Vélez [21] estudia la división de alquileres de EF bajo restricciones presupuestarias suaves . Cada agente informa el valor de 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 renta EF que es, además, igualitaria (utilidad máxima mínima), o dinero-Rawlsiana (renta mínima-máxima), o que satisface alguna 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.
Vélez [22] estudia las propiedades estratégicas de estos algoritmos. Muestra que los resultados no cooperativos de información completa de cada uno de los algoritmos son exactamente las asignaciones de EF frente a las preferencias verdaderas, si el número de desutilidades permitidas es limitado.
Arunachaleswaran, Barman y Rathi [23] estudian un escenario sustancialmente más general que cuasilineal, en el que la utilidad de cada agente de cada habitación puede ser cualquier función lineal por partes del alquiler. Esta configuración generaliza la restricción presupuestaria blanda. Como el precio es demasiado alto, siempre existe una asignación EF. Muestran un FPTAS , un algoritmo que encuentra una asignación que es EF hasta (1+ ε ), en un polinomio de tiempo en 1/ ε y n k + c , donde n es el número de agentes, k es el número de desutilidades diferentes. valores (por ejemplo, diferentes tipos de interés), y c >2 es alguna constante. También muestran que el problema se ubica 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 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 ):
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 .
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.
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 costo de suma mínima es a prueba de estrategias. [24]
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. [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 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.
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 , .
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 .
Una posible relajación del requisito de idoneidad estratégica es tratar de 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 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.
Hay varios problemas en los que sólo hay bienes indivisibles para compartir, sin transferencias monetarias:
{{citation}}
: Mantenimiento CS1: nombres numéricos: lista de autores ( enlace )