La armonía del alquiler [1] [2] es una especie de problema de división justa en el que los elementos indivisibles y un costo monetario fijo deben dividirse simultáneamente. El problema de los compañeros de casa [3] [4] y la división-alquiler-asignación-habitación [5] [6] son nombres alternativos al mismo problema. [7] [8] : 305–328
En el entorno típico, hay socios que alquilan juntos un -Casa de habitación por costo fijado por el dueño de la casa. Cada compañero de casa puede tener diferentes preferencias: uno puede preferir una habitación grande, otro puede preferir una habitación con vista a la calle principal, etc. Los siguientes dos problemas deben resolverse simultáneamente:
- (a) Asigne una habitación a cada socio,
- (b) Determine la cantidad que debe pagar cada socio, de manera que la suma de los pagos sea igual al costo fijo.
Hay varias propiedades que nos gustaría que satisfaga la asignación.
- No negatividad (NN) : todos los precios deben ser 0 o más: no se debe pagar a ningún socio para obtener una habitación.
- Sin 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 de habitación + alquiler es débilmente mejor que todas las demás parcelas. EF significa que cada socio prefiere su habitación asignada. Es decir, a ningún socio le gustaría tener otra habitación al precio de alquiler asignado a esa habitación.
- Pareto-eficiencia (PE) : Ninguna otra asignación de socios a las habitaciones es débilmente mejor para todos los socios y estrictamente mejor para al menos uno de los socios (dado el vector de precios).
La ausencia de envidia implica la 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 es envidioso.
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 en 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, 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 como y paga , su utilidad neta es .
El supuesto cardinal implica el supuesto ordinal, ya que dado un vector de valoración siempre es posible construir una relación de preferencia. La suposición ordinal es más general y pone menos carga mental en los socios.
Versión ordinal
Su: una persona por habitación
El protocolo de Francis Su hace los siguientes supuestos sobre las preferencias de los socios:
- Buena casa : En cualquier partición del alquiler, cada persona considera aceptable al menos una habitación + una parcela de alquiler.
- Sin externalidades : La relación de preferencia de cada socio depende de las habitaciones y los alquileres, pero no de las elecciones de otros.
- Socios miserables : cada socio prefiere débilmente una habitación libre (una habitación con un alquiler de 0) a cualquier otra habitación.
- 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. Luego, cada esquema de precios es un punto en un -simplex dimensional 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 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 doble simplex y, por lo tanto, existe un pequeño sub-simplex que corresponde a una asignación aproximada de habitaciones y alquileres sin envidia.
El protocolo de Su devuelve una secuencia de asignaciones que converge en una asignación sin envidia. Los precios son siempre no negativos. Por tanto, el resultado satisface los requisitos NN y EF.
[9] y [10] proporcionan explicaciones popularizadas del protocolo Rental Harmony de Su.
[11] y [12] proporcionan implementaciones en línea.
Azriely y Shmaya: compañeros 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).
Demuestran la existencia de asignaciones sin envidia en las siguientes condiciones:
- Buena casa : a cada socio le gusta al menos una de las habitaciones de cada vector de precios.
- Sin externalidades : a todos los socios les gustan las habitaciones libres.
- Socios tacaños : 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 solución de Azrieli & Shmaya, la relación de preferencia de cada socio puede (pero no está obligada) a depender 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, prefiero la habitación C a la habitación B".
Hay varias razones por las que esta generalización puede resultar útil. [2]
- Planificación futura. Suponga que el socio piensa que la habitación A es mejor, luego B, luego C. Si A es caro, el socio se conforma con B. Pero si A es más barato, el socio podría comprar C (que es el más barato) y luego ahorrar algo de dinero. y cambie a A.
- Información incompleta. El vector de precios puede dar al socio alguna indicación sobre la calidad de las habitaciones.
- Vecinos. El vector de precios puede permitir al socio predecir, hasta cierto punto, qué tipo de personas van a vivir en las habitaciones vecinas.
- 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 precio de ganga .. ".
B. Tanto la solución de Su como la solución de Azrieli & Shmaya hacen una suposición de "inquilinos tacaños": asumen que un inquilino siempre prefiere una habitación libre a una habitación no libre. Esta suposición es fuerte y no siempre realista. Si una de las habitaciones está muy mal, 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 cree que la habitación A vale 0 y la habitación B vale 100, y la habitación A es gratuita y la habitación B cuesta 50, entonces ciertamente prefiere 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 mantendrá si una persona siempre prefiere una habitación libre a una habitación que cuesta al menosdel alquiler total. Sin embargo, incluso esta suposición debilitada podría ser poco realista, como en el ejemplo anterior. [8] : 320–321
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 vale (en dólares) esta habitación para él.
Una noción clave en las soluciones cardinales es una asignación máxima (también conocida como utilitaria ). Se trata de una asignación de socios a salas, que maximiza la suma de ofertas. El problema de encontrar una asignación de suma máxima se conoce como problema de asignación , y el algoritmo húngaro puede resolverlo a tiempo. (dónde es 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]
Incompatibilidad de EF y NN
Los dos requisitos de la ausencia de envidia y los pagos no negativos no siempre son compatibles. Por ejemplo, suponga que el costo total es 100 y las valoraciones son:
Habitación 1 | Habitación 2 | |
---|---|---|
Socio 1 | 150 | 0 |
Socio 2 | 140 | 10 |
Aquí, la única asignación máxima es dar espacio 1 al socio 1 y espacio 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 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, 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 para la prueba):
Habitación 1 | Habitación 2 | Habitacion 3 | Habitación 4 | |
---|---|---|---|---|
Socio 1 | 36 | 34 | 30 | 0 |
Socio 2 | 31 | 36 | 33 | 0 |
Socio 3 | 34 | 30 | 36 | 0 |
Socio 4 | 32 | 33 | 35 | 0 |
Tenga en cuenta que este ejemplo no ocurre en la versión ordinal, ya que los protocolos ordinales hacen la suposición de "socios avaro": los socios siempre prefieren las 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 deben comprometerse entre EF y NN. Cada protocolo tiene un compromiso diferente.
Brams y Kilgour: NN pero no EF
Brams y Kilgour [8] : 305–328 [13] sugieren el Procedimiento Gap :
- Calcule una asignación de suma máxima.
- 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 la cantidad total requerida por el propietario.
- Si la suma máxima es exactamente igual al costo total, entonces se asignan las habitaciones y los socios pagan sus valoraciones.
- 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" en las habitaciones. Si hay una habitación más deseada por el siguiente mejor postor, 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 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. Debido a que la asignación es máxima, obviamente también es Pareto-eficiente. 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 de EF. Brams se relaciona con este problema diciendo que: "Los precios de brecha tienen en cuenta la competitividad de la licitación 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 mercado cuando hay un conflicto entre estas dos propiedades; los socios deben 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 y col. [7] presentar el Procedimiento de Compensación. El problema que resuelve es más general que el problema de la armonía del 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 en los paquetes de elementos, siempre que sean anónimos (no distinga entre socios en función de su identidad). Por ejemplo, no puede haber ninguna restricción en absoluto, o una restricción como "cada socio debe recibir al menos una cierta cantidad de artículos", o "algunos artículos deben estar agrupados" (por ejemplo, porque son parcelas de tierra que deben permanecer conectado), 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 herencia. Del mismo modo, 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.
- Encuentre una asignación de suma máxima (utilitaria): una asignación con una suma de utilidades más alta que satisfaga las restricciones en los paquetes de artículos. Si no hay restricciones, entonces una asignación que otorga cada artículo al socio con la valoración más alta es la suma máxima. Si existen restricciones (como "al menos un artículo por socio"), entonces una asignación de suma máxima podría ser más difícil de encontrar.
- Cobrar a cada socio el valor del paquete que se le asigne. Esto crea la reserva inicial de dinero.
- Pague el costo del grupo inicial. Si todos los socios satisfacen el requisito de calificación, entonces el dinero del fondo común es suficiente y puede que quede algún excedente .
- Elimina la envidia compensando a los socios envidiosos. Hay como máximorondas de compensación. El procedimiento es completamente descriptivo y dice explícitamente qué compensaciones deben hacerse y en qué orden. Además, es lo suficientemente simple como para llevarlo a cabo sin soporte informático.
- 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 puede comenzar con una asignación arbitraria. En este caso, el procedimiento podría concluir con una asignación que contiene ciclos de envidia . Estos ciclos se pueden eliminar 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 puede cobrar a algunos socios un pago negativo (es decir, dar 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 descartamos la posibilidad de que un individuo pueda terminar siendo pagado por los demás para tomar un paquete de bienes. En el contexto de una división justa, no encontramos este problema en absoluto. De hecho, si un grupo no desea excluir a cualquiera de sus miembros, entonces no hay razón por la cual el grupo no deba subsidiar a un miembro por recibir un paquete no deseado. Además, el requisito de calificación garantiza que el subsidio nunca es una consecuencia de la valoración insuficiente de un jugador del conjunto completo de objetos 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 es subsidiado por 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 los alquileres de habitaciones negativos ". [4]
Abdulkadiroglu y Sonmez y Unver: EF y NN si es posible
Abdulkadiroğlu y col. [5] sugieren un enfoque basado en el mercado. Es una combinación de una subasta ascendente y una subasta descendente . Es más sencillo describirlo como una subasta de precio continuo:
- Inicialice el precio de cada habitación para del costo total de la casa.
- Calcule el conjunto de demanda de cada socio: la habitación o conjunto de habitaciones que más le gusta a los precios actuales.
- Calcule el conjunto de habitaciones sobredemandadas (habitaciones que son demandadas por más socios que el número de habitaciones; consulte el documento para obtener una definición exacta).
- Aumentar el precio de todas las habitaciones sobre demandadas en la misma tarifa;
- Simultáneamente, disminuya el precio de todas las demás habitaciones en la misma tarifa, de modo que la suma de los precios de todas las habitaciones siempre sea igual al costo total.
- En cada instante, actualice la demanda de cada socio y el conjunto de habitaciones sobredemandadas.
- 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 el conjunto de precios interesantes por adelantado 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:
- La ausencia de envidia implica suma máxima: dada una asignación x , si hay un vector de precios p con el que x está libre de envidia, entonces x es suma máxima.
- 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.
En base a estas propiedades, proponen el siguiente algoritmo:
- Encuentra una asignación de suma máxima.
- Encuentre un vector de precios mínimo (un vector en el que la suma de los 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 encontrar mediante el algoritmo de Bellman-Ford .
- Si la suma mínima es igual al costo total, implemente la asignación de la suma máxima con los precios mínimos y finalice.
- 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 asegura que la asignación no tenga envidia.
- 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.
- Disminuya solo los precios positivos a una tasa constante, hasta que la suma sea igual al costo total. Aquí, los precios no cambian en la misma cantidad, por lo que algunos socios necesariamente envidiarán, como en la solución de Brams y Kilgour. Sin embargo, en esta solución, los socios envidiosos obtienen su espacio gratis .
La complejidad del tiempo de ejecución de encontrar la asignación de la suma máxima y los precios de la 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 tenga una habitación libre. [14] 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 documento diferente.
Mash, Gal, Procaccia y Zick: EF y maximin
Gal, Mash, Procaccia y Zick, [15] basándose en su experiencia con la aplicación de división de alquileres en el sitio web de 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 son libres de envidia y optimizan algún criterio. Con base en pruebas teóricas y experimentales, concluyen que el criterio maximin - maximizar la utilidad mínima de un agente sujeto a la envidia - alcanza resultados óptimos.
Tenga en cuenta que, dado que su solución es siempre EF, puede devolver precios negativos.
Consideraciones presupuestarias
La mayoría de los artículos del modelo cardinal asumen 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 [16] estudian este modelo y presentan un algoritmo para encontrar si existe una asignación de EF 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 encuestados hasta ahora asumen que los socios revelan sus verdaderas valoraciones. No son a prueba de estrategias : un socio puede beneficiarse informando valoraciones falsas. De hecho, la prueba de estrategia es incompatible con la ausencia de envidia : no existe un protocolo determinista a prueba de estrategia que siempre devuelva una asignación sin envidia. Esto es cierto incluso cuando solo hay dos socios y cuando se permite que los precios sean negativos. Prueba : Suponga que el costo total es 100 y las valoraciones de los socios son las siguientes (donde son parámetros y ):
Habitación 1 | Habitación 2 | |
---|---|---|
Socio 1 | 100 | X |
Socio 2 | 100 | y |
La única asignación de suma máxima es dar espacio 1 al socio 1 y espacio 2 al socio 2. Deje sea el precio de la habitación 2 (de modo que el precio de la habitación 1 sea ). Para asegurarnos de que el socio 1 no tenga envidia, debemos tener. Para asegurarnos de que el socio 2 no tenga envidia, debemos tener.
Supongamos que un protocolo determinista establece el precio a algún valor en . Si el precio es más de, entonces el socio 2 tiene un incentivo para informar un valor más bajo de , que todavía está arriba , para reducir su pago hacia . Del mismo modo, si el precio es inferior a, entonces el socio 1 tiene un incentivo para informar un valor más alto de , que todavía está debajo , para impulsar el pago del socio 2 hacia (y así reducir su propio pago). Por tanto, el mecanismo no puede ser a prueba de estrategias.
Los investigadores se han enfrentado a esta imposibilidad de dos formas.
Sun y Yang: Cambiando el problema
Existe una variante del problema en la que, en lugar de asumir que el costo total de la casa es fijo, asumimos que hay un costo 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. [17]
Este resultado se puede generalizar para una mayor flexibilidad en los objetos indivisibles y una prueba de resistencia a la estrategia de coalición. [18] [19]
Dufton y Larson: uso de la aleatorización
Volviendo al problema original de la armonía del alquiler, 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 es veraz en expectativa si ningún socio puede aumentar el valor esperado de su utilidad al informar erróneamente sus valoraciones a las habitaciones. La equidad de un mecanismo aleatorio se puede medir de varias formas: [6]
1. Ex-ante Envy-Freeness significa que ningún socio envidia la lotería de otro socio. Esta condición es trivial de lograr en un mecanismo veraz: aleatorice todas las asignaciones posibles con la misma probabilidad y cargue a cada sociodel 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 ha sido justa.
2. Probabilidad garantizada de estar libre de envidia (GPEF) significa que existe una cierta probabilidad tal que, independientemente de las valoraciones de los socios, con probabilidad al menos , el resultado final no tendrá envidia. Es posible lograr un GPEF dede la siguiente manera: encuentre una tarea libre de envidia; elige un número enteroal azar; y mover a cada socio cíclicamentehabitaciones a 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 esdel costo total, independientemente de la oferta del socio. La probabilidad de tener una asignación de 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 aumenta el número de socios. Pero es imposible hacerlo mejor: en cada mecanismo de expectativa veraz, el GPEF es como mucho.
3. Número esperado de socios sin envidia (ENEF) significa que hay un determinado número entero tal que, si promediamos el número de socios que no envidian en todos los posibles resultados 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 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. La ENEF máxima de un mecanismo de expectativa veraz es como máximo. Es posible alcanzar este límite para. Para, existe un mecanismo de veracidad en 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 de suma máxima y pagos. Seleccione un socio al azar. Ignore a ese socio y use VCG nuevamente. Combine los resultados de una manera que garantice que el pago total es igual al costo total (consulte el documento para obtener más detalles). Es posible demostrar que: (a) el mecanismo es veraz-en-expectativa; (b) todos los socios, excepto el socio ignorado, no envidian. 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.
Andersson y Ehlers y Svensson: Lograr la resistencia a la estrategia parcial
Una posible relajación del requisito de resistencia a la estrategia es intentar minimizar el "grado de manipulabilidad". [20] Esto se define contando, para cada perfil, el número de agentes que pueden manipular la regla. Las reglas de asignación equitativa máximamente preferidas son las reglas de asignación equitativa y presupuestaria mínimamente manipulables (individual y colectivamente) de acuerdo con 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 con equilibrio presupuestario.
Ver también
Hay varios problemas en los que solo hay partidas indivisibles para compartir, sin transferencias monetarias:
- Asignación aleatoria justa : cada agente debe obtener un solo objeto; la equidad se logra mediante la aleatorización.
- Problema de asignación de casa : cada agente debe obtener un solo objeto (casa); no se permite la aleatorización. Los objetivos son la eficiencia y / o la equidad.
- Emparejamiento sin envidia : cada agente debe obtener como máximo un objeto; el objetivo es maximizar el número de asignaciones sujetas a la ausencia de envidia.
- Asignación justa de artículos : cada agente puede obtener una cantidad arbitraria de objetos.
- Problema de asignación : cada agente debe obtener un solo objeto; el objetivo es maximizar el valor total o minimizar el costo total.
Referencias
- ↑ a b Su, FE (1999). "Armonía de alquiler: Lema de Sperner en Fair Division" . The American Mathematical Monthly . 106 (10): 930–942. doi : 10.2307 / 2589747 . JSTOR 2589747 .
- ^ a b c Azrieli, Yaron; Shmaya, Eran (2014). "Arrendamiento 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 .
- ^ Potthoff, Richard F. (2002). "Uso de programación lineal para encontrar una solución libre de envidia más cercana a la solución Brams-Kilgour Gap para el problema de los compañeros de casa". Decisión y negociación grupal . 11 (5): 405. doi : 10.1023 / A: 1020485018300 .
- ^ a b c d e Sung, Shao Chin; Vlach, Milán (2004). "División competitiva sin envidia". Elección social y bienestar . 23 . doi : 10.1007 / s00355-003-0240-z .
- ^ a b c Abdulkadiroğlu, Atila; Sönmez, Tayfun; Utku Ünver, M. (2004). "División de asignación de habitaciones-alquiler: un enfoque de mercado". Elección social y bienestar . 22 (3): 515. CiteSeerX 10.1.1.198.186 . doi : 10.1007 / s00355-003-0231-0 .
- ^ a b Lachlan Dufton y Kate Larson (2011). "División de asignación de habitación aleatoria-alquiler" (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 .
- ^ a b c Haake, Claus-Jochen; Raith, Matthias G .; Su, Francis Edward (2002). "Hacer una oferta por la ausencia de envidia: un enfoque de procedimiento 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 .
- ^ a b c d e Steven 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.
- ^ Sol, Albert. "Para dividir la renta, comience con un triángulo" . The New York Times . Consultado el 26 de agosto de 2014 .
- ^ Procaccia, Ariel (15 de agosto de 2012). "División justa y el problema de los filósofos llorones" . La mano invisible de Turing . Consultado el 26 de agosto de 2014 .
- ^ "Página de la división justa de Francis Su" . Math.hmc.edu . Consultado el 5 de enero de 2017 .
- ^ "Divida su alquiler equitativamente" . The New York Times . Consultado el 5 de enero de 2017 .
- ^ Brams, Steven J .; Kilgour, D. Marc (2001). "División de Feria Competitiva". Revista de Economía Política . 109 (2): 418. doi : 10.1086 / 319550 .
- ^ "Asignar habitaciones y compartir alquiler - Spliddit" . Archivado desde el original el 5 de marzo de 2016 . Consultado el 5 de marzo de 2016 .
- ^ Gal, Ya'akov (Kobi); Mash, Moshe; Procaccia, Ariel D .; Zick, Yair (21 de julio de 2016). ¿Cuál es la (división de renta) más justa de todas? . ACM. págs. 67–84. doi : 10.1145 / 2940716.2940724 . ISBN 9781450339360.
- ^ Ariel D. Procaccia, Rodrigo A. Velez y Dingli Yu. " División de alquiler justo en un presupuesto ". AAAI 2018.
- ^ Sun, Ning; Yang, Zaifu (2003). "Un mecanismo de asignación justa de prueba de estrategia general" (PDF) . Cartas económicas . 81 : 73. doi : 10.1016 / s0165-1765 (03) 00151-4 .
- ^ Andersson, Tommy; Svensson, Lars-Gunnar (2008). "Asignación no manipulable de personas a puestos revisitados". Ciencias Sociales Matemáticas . 56 (3): 350. doi : 10.1016 / j.mathsocsci.2008.05.004 .
- ^ Andersson, Tommy (2009). "Un mecanismo de asignación equitativa a prueba de estrategia general revisado" . Boletín de Economía . 29 (3): 1719-1724.
- ^ Andersson, Tommy; Ehlers, Lars; Svensson, Lars-Gunnar (2014). "Equilibrio presupuestario, equidad y mínima manipulación" . Economía teórica . 9 (3): 753. doi : 10.3982 / te1346 .