Armonía de alquiler

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

1. Buena vivienda : En cualquier división del alquiler, cada persona encuentra aceptable al menos una habitación más una parcela de alquiler.
2. Sin externalidades : La relación de preferencia de cada socio depende de las habitaciones y los alquileres, pero no de las decisiones tomadas por los demás.
3. Inquilinos tacaños : cada inquilino prefiere ligeramente una habitación gratuita (una habitación con un alquiler de 0) a cualquier otra habitación.
4. Conjuntos de preferencias topológicamente cerrados : Un socio que prefiere un espacio para una secuencia convergente de precios, prefiere ese espacio al precio límite.

Normalice el alquiler total a 1. Entonces, cada esquema de precios es un punto en un${\displaystyle (n-1)}$-símplex dimensional con${\displaystyle n}$vértices en${\displaystyle \mathbb {R} ^{n}}$El protocolo de Su opera sobre una versión dualizada de este símplex de forma similar a los protocolos de Simmons-Su para el reparto de pasteles: para cada vértice de una triangulación del símplex dual, que corresponde a un determinado esquema de precios, 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 subsímplex pequeño 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 libre de envidia. Los precios son siempre 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).

Demuestran 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 dada cada vector de precios.
2. Sin externalidades : A todos los socios les gustan las habitaciones gratuitas.
3. Socios tacaños : Las preferencias son continuas en los precios.

Las principales herramientas utilizadas en la demostración son:

• El teorema KKMS : una generalización del teorema Kkm .
• El 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.

A. Tanto en la solución de Su como en la de Azrieli y 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, 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 tal generalidad puede ser útil. ^{[ 2 ]}

1. Planificación futura. Supongamos que uno de los socios piensa que la habitación A es la mejor, luego la B y después la C. Si la A es cara, el socio se decide por la B. Pero si la A es más barata, podría comprar la C (que es la más barata) y luego ahorrar 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, hasta cierto punto, qué tipo de personas van a vivir en las habitaciones vecinas.
4. Efectos de irracionalidad, por ejemplo, efectos de encuadre . Si la habitación B y la habitación C son de la misma calidad y tienen el mismo precio, la pareja podría comprar la A. Pero si la habitación B se encarece, la pareja podría optar por la C, pensando que "es igual que la B, pero a un precio de ganga".

B. Tanto la solución de Su como la de Azrieli y Shmaya parten de la premisa de que los inquilinos son tacaños: asumen que un inquilino siempre prefiere una habitación gratuita a una que no lo sea. Esta premisa es fuerte 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 se ve fácilmente 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 gratuita y la habitación B cuesta 50, entonces sin duda preferirás la habitación B.

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

Segal-Halevi ^{[ 13 ]} demuestra 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, ningún agente prefiere la habitación que cuesta T. Existe armonía en los alquileres siempre que exista un precio demasiado alto para todos los agentes. Esta suposición es más débil que la de inquilinos tacaños y más débil que la cuasilinealidad. Queda por determinar si existe una suposición aún más débil que garantice la existencia de armonía en los alquileres.

Los dos requisitos de ausencia de envidia y pagos no 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 consiste en darle la habitación 1 al socio 1 y la habitación 2 al socio 2. Para asegurar 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 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 demostración):

Cabe destacar que este ejemplo no se presenta en la versión ordinal, ya que los protocolos ordinales parten de la premisa de "Socios Avaros": los socios siempre prefieren habitaciones libres. Cuando esta premisa se cumple, siempre existe una asignación EF+NN. Sin embargo, en el ejemplo anterior, la premisa 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 realiza un compromiso diferente.

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

1. Calcular una asignación de suma máxima.
2. Si la suma máxima es menor que el costo total, entonces el problema es irresoluble, ya que los socios no quieren pagar la cantidad total requerida 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 respectivas valoraciones.
4. Si la suma máxima es mayor que el coste total, los precios se reducen en función de la diferencia 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 una habitación es más deseada por el siguiente postor con la oferta más alta, entonces debería costar más. Esto es similar en esencia 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 solo parcialmente independiente. Por lo tanto, el procedimiento Gap no es inmune a la manipulación estratégica .

El procedimiento Gap siempre asigna precios no negativos. Dado que la asignación es de suma máxima, obviamente también es Pareto-eficiente. Sin embargo, algunos socios podrían 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 EF. Brams se relaciona con este problema diciendo que: «Los precios de brecha sí tienen en cuenta la competitividad de las ofertas por los bienes, lo que hace que el mecanismo de fijación de precios esté orientado al mercado. Si bien la ausencia de envidia es una propiedad deseable, prefiero un mecanismo de mercado cuando existe 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 armonía en el alquiler en ciertos aspectos:

• El número de elementos indivisibles a dividir ( m ) puede diferir del número de socios ( n ).
• Se pueden establecer restricciones arbitrarias para los conjuntos de artículos, siempre que sean anónimos (sin diferenciar entre socios en función de su identidad). Por ejemplo, puede no haber ninguna restricción, o bien una como «cada socio debe recibir al menos una cantidad determinada de artículos», o «algunos artículos deben agruparse» (por ejemplo, porque son parcelas de terreno que deben permanecer conectadas), etc.
• El "costo" total también puede ser positivo, lo que significa que hay dinero para repartir. Esto es característico de los repartos de herencias. Del mismo modo, los "bienes" pueden tener utilidad negativa (por ejemplo, pueden representar tareas indivisibles).

Existe un "requisito de cualificación" para ser socio: la suma de sus ofertas debe ser, como mínimo, igual al coste total.

El procedimiento se realiza en los siguientes pasos.

1. Encontrar una asignación de máxima utilidad (utilitaria): una asignación con la mayor suma de utilidades que satisfaga las restricciones sobre los conjuntos de artículos. Si no hay restricciones, una asignación que dé cada artículo al socio con la mayor valoración es de máxima utilidad. Si existen restricciones (como "al menos un artículo por socio"), encontrar una asignación de máxima utilidad puede ser más difícil.
2. Cobrar a cada socio el valor del paquete que le corresponde. Esto crea el fondo inicial de dinero.
3. Paga el coste con el fondo inicial. Si todos los socios cumplen los requisitos de cualificación, el dinero del fondo será suficiente y puede que quede algún excedente .
4. Elimina la envidia compensando a las parejas envidiosas. Hay como máximo${\displaystyle n-1}$rondas de compensación. El procedimiento es totalmente descriptivo e indica explícitamente qué compensaciones deben realizarse y en qué orden. Además, es lo suficientemente sencillo como para llevarlo a cabo sin asistencia informática.
5. La suma de las compensaciones realizadas en todas las rondas es la cantidad mínima necesaria para eliminar la envidia, y nunca supera el excedente. Si queda algún excedente, puede dividirse de cualquier forma que no genere envidia, por ejemplo, asignando una cantidad igual a cada participante (el documento analiza otras opciones que podrían considerarse más justas).

Cuando existen numerosos elementos y restricciones complejas, el paso inicial —encontrar una asignación de suma máxima— puede resultar difícil de calcular sin un ordenador. En este caso, el procedimiento de compensación puede comenzar con una asignación arbitraria. En tal caso, el procedimiento podría concluir con una asignación que contenga ciclos de envidia . Estos ciclos pueden eliminarse moviendo los paquetes a lo largo del ciclo. Esto incrementa estrictamente la suma total de utilidades. Por lo tanto, tras un número limitado de iteraciones, se encontrará una asignación de suma máxima y el procedimiento puede continuar como se describió 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 una cantidad positiva de dinero). Esto significa que el procedimiento de compensación es EF (y por lo tanto también PE) pero no NN. Los autores dicen:

«No descartamos la posibilidad de que un individuo termine recibiendo un pago de los demás para tomar un conjunto de bienes. En el contexto de una distribución justa, no consideramos que esto sea problemático en absoluto. De hecho, si un grupo no desea excluir a ninguno de sus miembros, no hay razón para que no subsidie ​​a un miembro por recibir un conjunto no deseado. Además, el requisito de calificación garantiza que el subsidio 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 piso:

"Un compañero de piso al que se le asigna una habitación con renta negativa recibe una subvención de otros compañeros. En tal situación, algunos compañeros pueden preferir dejar la habitación con renta negativa sin usar y excluir al compañero al que se le asignó, ya que podrían obtener un mayor descuento. Para evitar esta situación, deben evitarse las rentas negativas". ^{[ 4 ]}

Abdulkadiroğlu et al. ^{[ 5 ]} sugieren un enfoque basado en el mercado. Es una combinación de una subasta ascendente y una subasta descendente . Se describe de forma más sencilla como una subasta de precio continuo:

1. Inicialice el precio de cada habitación a${\displaystyle 1/n}$del costo total de la casa.
2. Calcula el conjunto de demanda de cada socio: la habitación o el conjunto de habitaciones que más le gustan a los precios actuales.
3. Calcula el conjunto de habitaciones con exceso de demanda (habitaciones que son solicitadas por más parejas que el número de habitaciones disponibles; consulta el documento para obtener la definición exacta).
4. Aumentar el precio de todas las habitaciones con exceso de demanda al mismo precio;
5. Simultáneamente, disminuya el precio de todas las demás habitaciones en la misma proporción, de manera que la suma de los precios de todas las habitaciones sea siempre igual al costo total.
6. En cada instante, actualice la demanda de cada socio y el conjunto de habitaciones con exceso de demanda.
7. Cuando el conjunto de habitaciones con exceso de demanda esté vacío, deténgase y aplique el teorema matrimonial de Hall para asignar a cada miembro de la pareja una habitación de su conjunto de demanda.

En la práctica, no es necesario modificar el precio continuamente, ya que los únicos precios interesantes son aquellos en los que cambian las demandas 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 finaliza tras un número finito de pasos. ^{[ 5 ] : 525–528}

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

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 existe un vector de precios p con el que x no genera envidia, entonces x es suma máxima.
2. La suma máxima implica ausencia de envidia: dado un vector de precios p , si existe 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. Encontrar un vector de precios de suma mínima (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 la solución de un problema de programación lineal y puede hallarse mediante el algoritmo de Bellman-Ford .
3. Si la suma mínima es igual al costo total, implemente la asignación de suma máxima con los precios de suma mínima y finalice.
4. Si la suma mínima es menor que el costo total, entonces aumente todos los precios a una tasa constante hasta que la suma sea igual al costo total (es decir, agregue a cada precio:${\displaystyle (cost-minsum)/n}$). Cambiar todos los precios en la misma cantidad garantiza que la asignación permanezca libre de envidia.
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 maneras 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:${\displaystyle (minsum-cost)/n}$). Algunos precios serán necesariamente negativos, como en la solución de Haake Raith y Su.
   • Disminuya únicamente los precios positivos a un ritmo constante hasta que la suma sea igual al costo total. En este caso, los precios no varían en la misma cantidad, por lo que algunos socios 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 temporal de encontrar la asignación de suma máxima y 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, EF y NN (si es posible) y tiempo de ejecución polinomial, y además, garantiza que cada socio envidioso obtenga una habitación libre. ^{[ 15 ]} proporciona una implementación de una solución similar, también basada en la resolución de un problema de programación lineal, pero citando un artículo diferente.

Aragones ^{[ 16 ]} presentó un algoritmo de tiempo polinomial 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, desarrollan un marco algorítmico, basado en programación lineal, para calcular asignaciones que sean libres de envidia y que optimicen algún criterio. A partir de pruebas teóricas y experimentales, concluyen que la regla igualitaria —que maximiza la utilidad mínima de un agente sujeto a la ausencia de envidia— alcanza resultados óptimos.

Tenga en cuenta que, dado que su solución siempre es EF, podría devolver 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 estudios sobre el 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 supera su presupuesto, la utilidad disminuye mucho más rápidamente que de forma lineal. De hecho, un agente siempre prefiere una habitación cuyo precio sea como máximo igual a su presupuesto, a una habitación cuyo precio sea 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 presupuesto suficiente 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 ]} sigue vigente 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. De ser así, encuentra una asignación que, entre todas las asignaciones asequibles EF, maximiza la utilidad más pequeña (como en la asignación igualitaria de artículos ).

Airiau, Gilbert, Grandi, Lang y Wilczynski ^{[ 20 ]} sugieren dos soluciones para superar el problema de la no existencia con restricciones presupuestarias:

• Relajando EF a EF económico , lo que significa que el agente i puede envidiar al agente j si j paga más que i.presupuesto. Es más probable que exista una asignación BF-EF que una asignación EF, pero aún así no está garantizada. Muestran un MILP para calcular una asignación BF-EF si existe. También muestran un algoritmo de tiempo polinomial para un vector de precios fijo y un algoritmo de tiempo pseudopolinomial para una asignación de habitaciones fija.
• Permitir la asignación fraccionaria , es decir, asignar (1,2) con precio a los agentes (1,2) durante medio año y revertir la asignación para 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 viajante de Hamming ), pero puede resolverse en tiempo O*(2 ^k ) por programación dinámica , donde k es el tamaño del algoritmo de Birkhoff ( k ≤ n ² ). Conjeturan que minimizar la mayor cantidad de cambios por agente también es NP-difícil.

Ambas flexibilizaciones amplían significativamente el conjunto de asignaciones de EF. Sin embargo, incluso con cada una de estas flexibilizaciones, es posible que no exista ninguna asignación de EF.

Velez ^{[ 21 ]} estudia la división de renta EF bajo restricciones presupuestarias flexibles . 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 renta EF que es, además, igualitaria (máxima utilidad mínima), o dinero-Rawlsiana (renta mínima-máxima), o satisface una de otras condiciones similares. El tiempo de ejecución es 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 de información completa de cada uno de los algoritmos son exactamente las asignaciones EF con respecto a las preferencias verdaderas, si y solo si el número de desutilidades permitidas está acotado.

Existe una variante del problema en la que, en lugar de suponer que el coste total de la vivienda es fijo, suponemos que existe un coste máximo para cada habitación. En esta variante, existe un mecanismo a prueba de manipulación: la regla de asignación determinista que selecciona el coste mínimo es a prueba de manipulación. ^{[ 24 ]}

Este resultado puede generalizarse para una mayor flexibilidad en los objetos indivisibles y una prueba de la invulnerabilidad a las estrategias coalicionales. ^{[ 25 ] [ 26 ]}

Volviendo al problema original de armonía en el alquiler, es posible considerar mecanismos aleatorios . Un mecanismo aleatorio devuelve una distribución de probabilidad sobre las asignaciones de habitaciones y las divisiones del alquiler. Un mecanismo aleatorio es veraz en términos de expectativas si ningún socio puede aumentar el valor esperado de su utilidad informando erróneamente sus valoraciones a las habitaciones. La equidad 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 trivial de lograr en un mecanismo veraz: aleatorizar sobre todas las asignaciones posibles con igual probabilidad y cobrar a cada socio.${\displaystyle 1/n}$del costo total. Pero esta condición no es atractiva, ya que existe una alta probabilidad de que, como resultado, muchos socios sientan envidia. Puede que no les consuele el hecho de que la lotería haya sido justa.

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

3. El número esperado de parejas libres de envidia (ENEF) significa que hay un cierto número entero.${\displaystyle N}$de tal manera 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${\displaystyle N}$El criterio ENEF parece más apropiado que el criterio GPEF, porque mide no solo la probabilidad de 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 veraz en expectativas es como máximo${\displaystyle n-1+1/n}$Es posible alcanzar este límite para${\displaystyle n=2}$. Para${\displaystyle n>2}$, existe un mecanismo de veracidad en expectativas que casi alcanza este límite: el ENEF es${\displaystyle n-1}$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 utilice VCG nuevamente. Combine los resultados de manera que se garantice que el pago total sea igual al costo total (consulte el artículo 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 tienen envidia. Por lo tanto, el ENEF es${\displaystyle n-1}$Las simulaciones muestran que en aproximadamente el 80% de los casos, el GPEF de este mecanismo también está en su máximo de${\displaystyle 1/n}$.

Una posible flexibilización del requisito de resistencia a la manipulación estratégica consiste en 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 preferidas al máximo son las reglas de asignación justa y equilibrada presupuestariamente mínimamente manipulables (individual y coalicionalmente) según este nuevo concepto. Dichas reglas eligen asignaciones con el número máximo de agentes para quienes la utilidad se maximiza entre todas las asignaciones justas y equilibradas presupuestariamente.