La asignación de artículos sin envidia (EF) es un problema de asignación de artículos justa , en el que el criterio de equidad es la ausencia de envidia : cada agente debe recibir un paquete que crea que es al menos tan bueno como el paquete de cualquier otro agente. [1] : 296–297
Dado que los elementos son indivisibles, es posible que no exista una asignación de EF. El caso más simple es cuando hay un solo artículo y al menos dos agentes: si el artículo se asigna a un agente, el otro lo envidiará. Por lo tanto, los procedimientos de división proporcionan varios tipos de relajación.
Asignación de artículos y dinero sin envidia
La libertad de envidia es alcanzable cuando, además de los elementos indivisibles, también hay un bien divisible ("dinero").
Un caso especial de esta configuración es cuando se dividen las habitaciones de un apartamento entre inquilinos. Se caracteriza por dos requisitos: (a) el número de agentes es igual al número de objetos, (b) el monto total de dinero pagado por los agentes debe ser igual al alquiler total (que se fija de antemano). Esto se conoce como el problema Rental Harmony .
Un segundo caso especial es cuando se venden objetos a compradores. En este caso, la suma de los pagos no se fija por adelantado y el objetivo es maximizar los ingresos del vendedor o el bienestar social, sujeto a la ausencia de envidia. Además, el número de objetos puede ser diferente al número de agentes y algunos objetos pueden descartarse. Esto se conoce como el problema de los precios sin envidia .
Un tercer caso es cuando un tercero benevolente está dispuesto a subsidiar la asignación, pero quiere minimizar la cantidad de subsidio sujeto a la ausencia de envidia. Este problema se denomina asignación sin envidia de subsidio mínimo y se estudió en varios contextos.
Agentes de demanda unitaria
Los agentes de demanda unitaria están interesados como máximo en un solo artículo. En la literatura económica, es común suponer que cada agente tiene una función de utilidad en los paquetes (un paquete es un par de un objeto y una cierta cantidad de dinero). La función de utilidad debe ser continua y creciente en dinero. No tiene que ser lineal en dinero, pero tiene que ser "de Arquímedes", es decir, existe algún valor V tal que, por cada dos objetos j y k , la utilidad del objeto j más V debe ser mayor que la utilidad. del objeto k (alternativamente, la utilidad de obtener el objeto j gratis es mayor que la utilidad de obtener el objeto k y pagar V ). La utilidad cuasilineal es un caso especial de la utilidad de Arquímedes, en la que V es la mayor diferencia de valor (para el mismo agente) entre dos objetos.
Svensson [2] primero demostró que, cuando todos los agentes son Arquímedes, existe una asignación sin envidia y es Pareto-óptima.
Demange, Gale y Sotomayor [3] mostraron una subasta ascendente natural que logra una asignación sin envidia mediante pagos monetarios para agentes de demanda unitaria.
Maskin [4] demostró la existencia de una asignación sin envidia óptima de Pareto cuando la dotación monetaria total es mayor que ( n-1 ) V. Las pruebas utilizan el equilibrio competitivo .
Tenga en cuenta que puede ser necesario un subsidio de ( n -1) V : si todos los agentes valoran un solo objeto en V y los otros objetos en 0, entonces la ausencia de envidia requiere un subsidio de V para cada agente que no recibe el objeto.
Tadenuma y Thomson [5] estudian varias propiedades de coherencia de las reglas de asignación sin envidia.
Aragonés [6] caracteriza la cantidad mínima de subvención requerida para la ausencia de envidia. La asignación que logra este subsidio mínimo es casi única: solo hay una forma de combinar objetos con agentes, y todos los agentes son indiferentes entre todas las asignaciones de subsidio mínimo. Coincide con la solución denominada "solución dinero-rawlsiana" de Alkan, Demange y Gale. [7] Se puede encontrar en tiempo polinomial, encontrando una coincidencia de peso máximo y luego encontrando las rutas más cortas en un determinado gráfico inducido.
Klijn [8] presenta otro algoritmo de tiempo polinomial para el mismo escenario. Su algoritmo usa el politopo de pagos laterales que hacen que una asignación dada no tenga envidia: este politopo no está vacío si la asignación original es Pareto-eficiente. La conectividad del gráfico de envidia no dirigida caracteriza los puntos extremos de este politopo. Esto implica un método para encontrar asignaciones extremadamente libres de envidia.
Agentes aditivos
Los agentes aditivos son más generales y pueden recibir varios elementos.
Alkan, Demange y Gale [7] demostraron que siempre existe una asignación sin envidia cuando la cantidad de dinero es suficientemente grande. Esto es cierto incluso cuando los artículos pueden tener valoraciones negativas.
Meertens, Potters y Reijnierse [9] prueban la existencia de asignaciones sin envidia y óptimas de Pareto bajo supuestos muy suaves sobre las valoraciones (no necesariamente cuasilineales).
Cavallo [10] generaliza los criterios binarios tradicionales de ausencia de envidia, proporcionalidad y eficiencia (bienestar) a medidas de grado que oscilan entre 0 y 1. En la configuración canónica de división justa, bajo cualquier mecanismo de asignación eficiente, el peor de los casos es el bienestar la tasa es 0 y la tasa de desproporcionalidad es 1; en otras palabras, los resultados del peor de los casos son los más malos posibles. Busca un mecanismo que logre un alto bienestar, una baja envidia y una baja desproporcionalidad en la expectativa en un espectro de entornos de división justa. El mecanismo VCG no es un candidato satisfactorio, pero el mecanismo de redistribución de Bailey [11] y Cavallo [12] sí lo es.
Halpern y Shah [13] estudian la subvención en el marco general de asignación de artículos. Consideran dos casos:
- La asignación se da por adelantado. En este caso, es "libre de envidia" si y solo si maximiza la suma de utilidades en todas las reasignaciones de sus paquetes a agentes, si y solo si su gráfico de envidia no tiene ciclos. Si el valor de cada bien para cada agente es como máximo V , entonces un subsidio de como máximo ( n -1) mV es siempre suficiente y puede ser necesario. Se puede encontrar una asignación sin envidia con un subsidio mínimo en un tiempo fuertemente polinomial.
- Se puede elegir la asignación. En este caso, una subvención de ( n -1) V es suficiente en los siguientes casos:
- Cuando las valoraciones de los agentes son binarias (0 o 1). Entonces, cualquier asignación de producto máximo o asignación óptima de leximina requiere como máximo ( n -1) subsidio V , y se puede encontrar en tiempo polinomial. Calcular el subsidio mínimo requerido para lograr EF es el equivalente de Turing a verificar la existencia de una asignación sin envidia, que es NP-difícil cuando se restringe a asignaciones que no generan desperdicio.
- Cuando todos los agentes tengan la misma valoración aditiva. Entonces, cada asignación es libre de envidia. Una asignación que requiere como máximo ( n -1) V subsidio se puede encontrar en tiempo polinomial. Una asignación minimiza el subsidio si minimiza la máxima utilidad para cualquier agente. Calcular una asignación de este tipo es NP-difícil y puede resolverse mediante el algoritmo de producto máximo.
- Cuando hay dos agentes, la asignación de elementos por turnos con un pedido de agente específico encuentra una asignación que es libre de envidia con un subsidio como máximo V.
Brustle, Dippel, Narayan, Suzuki y Vetta [14] mejoran los límites superiores del subsidio requerido:
- Con valoraciones aditivas, un subsidio de como máximo V por agente, y como máximo ( n -1) V en general, siempre es suficiente. Además, existe una asignación que alcanza este límite que también es EF1 y equilibrada (las cardinalidades de los paquetes asignados difieren como máximo en un bien). Se puede calcular en tiempo polinomial mediante un algoritmo simple: encuentre iterativamente una coincidencia de peso máximo en el gráfico bipartito agentes-objetos.
- Con valoraciones generales monótonas, un subsidio de como máximo 2 ( n -1) V por agente y como máximo de O ( n 2 V ), siempre es suficiente. En particular, la subvención requerida no depende del número de objetos. Una asignación que logre este límite se puede calcular en tiempo polinomial utilizando consultas de valor.
Caragiannis e Ioannidis [15] estudian el problema computacional de minimizar la subvención:
- Para un número constante de agentes, presentan un algoritmo que aproxima la cantidad mínima de subsidios dentro de la precisión requerida. Para cualquier ε > 0, encuentra una asignación con subsidio como máximo, donde max ( v ) es el valor máximo que un agente asigna a todos los objetos. El algoritmo utiliza programación dinámica y se ejecuta en el tiempo..
- Para un número variable de agentes, un algoritmo de aproximación trivial logra . Sin embargo, lograr un factor de aproximación independiente de n es difícil: es NP-difícil calcular una asignación con subsidio como máximo. La prueba es por reducción de una variante restringida de coincidencia máxima tridimensional , en la que cada vértice aparece exactamente dos veces.
Tenga en cuenta que una asignación sin envidia con subsidio permanece sin envidia si se toma una cantidad fija de cada agente. Por lo tanto, se pueden utilizar métodos similares para encontrar asignaciones que no estén subvencionadas:
- Cobrar a cada agente el pago promedio produce una asignación sin envidia que también está equilibrada en el presupuesto . Minimizar el subsidio equivale a minimizar el monto máximo que debe pagar cualquier agente individual.
- También es posible utilizar un subsidio negativo (impuesto), mientras se minimiza el monto total que todos los agentes tienen que pagar.
Objetivos multidimensionales
A menudo, deben alcanzarse otros objetivos además de la equidad. Por ejemplo, al asignar tareas a agentes, es necesario evitar la envidia y minimizar el tiempo de espera (el tiempo de finalización del último agente). Mu'alem presenta un marco general para los problemas de optimización con garantía de ausencia de envidia que naturalmente extiende las asignaciones justas de artículos utilizando pagos monetarios. [dieciséis]
Aziz [17] tiene como objetivo lograr, mediante transferencias monetarias, una asignación que sea a la vez libre de envidias y equitativa . No solo estudia las utilidades positivas aditivas, sino también las utilidades superaditivas , ya sean positivas o negativas:
- Para los servicios públicos superaditivos, existe un algoritmo de tiempo polinomial que logra la ausencia de envidia, la equidad y el equilibrio presupuestario (es fácil intercambiar el equilibrio presupuestario por el subsidio).
- Si una asignación dada es convertible en EFEQ, entonces el subsidio mínimo requerido para convertirla en EF + EQ se puede encontrar en tiempo lineal.
- Encontrar una asignación que sea convertible al EFEQ con un subsidio mínimo es NP-difícil y no se puede aproximar dentro de ningún factor positivo. Esto se debe simplemente a que verificar la existencia de una asignación de EF (que requiere 0 subsidio) es NP-difícil.
- Un subsidio de como máximo ( n -1) mV siempre es suficiente, y puede ser necesario tanto si se otorga una asignación como si no.
Encontrar una asignación sin envidia siempre que exista
Ordenaciones de preferencia en paquetes: sin envidia
El procedimiento de subcotización encuentra una asignación EF completa para dos agentes, si y solo si existe dicha asignación. Requiere que los agentes clasifiquen paquetes de elementos, pero no requiere información de utilidad cardinal. Funciona siempre que las relaciones de preferencia de los agentes sean estrictamente monótonas, pero no es necesario asumir que son preferencias sensibles . En el peor de los casos, los agentes pueden tener que clasificar todos los paquetes posibles, por lo que el tiempo de ejecución puede ser exponencial en el número de elementos.
Orden de preferencia en los artículos: necesario / posible sin envidia
Por lo general, es más fácil para las personas clasificar elementos individuales que clasificar paquetes. Suponiendo que todos los agentes tengan preferencias de respuesta , es posible elevar la clasificación de artículos a una clasificación de paquete parcial. Por ejemplo, si la clasificación del elemento es w> x> y> z, entonces la capacidad de respuesta implica que {w, x}> {y, z} y {w, y}> {x, z}, pero no implica nada sobre la relación entre {w, z} y {x, y}, entre {x} e {y, z}, etc.
Dado un ranking de elementos:
- Una asignación es necesariamente libre de envidia (NEF) si está libre de envidia de acuerdo con todas las clasificaciones de paquetes sensibles consistentes con la clasificación de artículos;
- Una asignación es posiblemente libre de envidia (PEF) si está libre de envidia de acuerdo con al menos una clasificación de paquete de respuesta consistente con la clasificación de artículos;
- Una asignación es necesariamente óptima de Pareto (NPE) si es óptima de Pareto de acuerdo con todas las clasificaciones de paquetes sensibles consistentes con la clasificación de elementos;
- Una asignación es posiblemente Pareto-óptima (PPE) si es Pareto-óptima de acuerdo con al menos una clasificación de paquete de respuesta consistente con la clasificación de elementos.
Bouveret y Endriss y Lang [18] estudian las cuestiones algorítmicas de encontrar una asignación NEF / PEF con una condición de eficiencia adicional, en particular, integridad o NPE o PPE. En general, PEF es computacionalmente fácil mientras que NEF es computacionalmente difícil.
Decidir si existe una asignación de EF
La asignación vacía es siempre EF. Pero si queremos algo de eficiencia además de EF, entonces el problema de decisión se vuelve computacionalmente difícil: [1] : 300–310
- Decidir si existe un EF y una asignación completa es NP completo . Esto es cierto incluso cuando solo hay dos agentes, e incluso cuando sus utilidades son aditivas e idénticas, ya que en este caso encontrar una asignación de EF equivale a resolver el problema de la partición . [19]
- Decidir si existe una asignación justa requiere una comunicación exponencial (en el número de bienes) cuando hay más de dos agentes. Cuando hay dos agentes, la complejidad de la comunicación depende de combinaciones específicas de parámetros. [20]
- Decidir si existe una asignación EF y Pareto eficiente está por encima de NP: es Σ 2 PAG {\ Displaystyle \ Sigma _ {2} ^ {\ textrm {P}}} -completo incluso con utilidades dicotómicas [21] e incluso con utilidades aditivas . [22] ( Σ 2 PAG {\ Displaystyle \ Sigma _ {2} ^ {\ textrm {P}}} es la clase de problemas que se pueden resolver en tiempo no determinista dado un oráculo que puede resolver cualquier problema en NP).
El problema de decisión puede volverse manejable cuando algunos parámetros del problema se consideran pequeñas constantes fijas: [23]
- Considerando el número de objetos m como parámetro, la existencia de una asignación PE + EF puede decidirse a tiempopara utilidades aditivas o dicotómicas. Cuando las utilidades son binarias y / o idénticas, el tiempo de ejecución cae a. Aquí, la notación oculta expresiones que son polinomiales en los otros parámetros (por ejemplo, número de agentes).
- Considerando el número de agentes n como parámetro, la existencia de una asignación de PE + EF sigue siendo difícil. Con utilidades dicotómicas, es NP-difícil incluso para n = 2. [21] Sin embargo, ahora está en NP, y puede resolverse eficientemente con un oráculo NP (por ejemplo, un solucionador SAT ). Con agentes, se puede hacer con tales oráculos, y al menos se necesitan oráculos a menos que P = NP. Con utilidades aditivas, es NP-duro incluso para n = 2. [21] Además, es W [1] -completo con el número de agentes, incluso si todas las utilidades son idénticas y están codificadas en unario.
- Considerando tanto el número de agentes ny la mayor utilidad V como parámetros, la existencia de una asignación de PE + EF puede decidirse a tiempopara utilidades aditivas usando programación dinámica .
- Considerando tanto el número de agentes n como el número de niveles de utilidad z como parámetros, la existencia de una asignación de PE + EF para utilidades aditivas idénticas se puede decidir utilizando un programa lineal de enteros convariables; El algoritmo de Lenstra permite resolver este tipo de ILP a tiempo.
Encontrar una asignación con un nivel limitado de envidia
Muchos procedimientos encuentran una asignación que está "casi" libre de envidia, es decir, el nivel de envidia está limitado. Hay varias nociones de "casi" ausencia de envidia:
EF1: sin envidia hasta como máximo un artículo
Una asignación se llama EF1 si por cada dos agentes A y B, si eliminamos como máximo un elemento del paquete de B, entonces A no envidia a B. [24] Una asignación EF1 siempre existe y se puede encontrar de manera eficiente mediante varios procedimientos. , particularmente:
- Cuando todos los agentes tienen utilidades aditivas débilmente , el protocolo round-robin encuentra una asignación EF1 completa. Se requiere una aditividad débil ya que cada agente debe poder elegir, en cada situación, un "mejor artículo".
- En el caso más general, cuando todos los agentes tienen utilidades que aumentan monótonamente, el procedimiento de gráfico de envidia encuentra una asignación EF1 completa. El único requisito es que los agentes puedan clasificar paquetes de artículos. Si las valoraciones de los agentes están representadas por una función de utilidad cardinal , entonces la garantía EF1 tiene una interpretación adicional: el nivel de envidia numérico de cada agente es, como máximo, la utilidad marginal-máxima: la utilidad marginal más grande de un solo artículo para ese agente.
- Cuando los agentes tienen utilidades arbitrarias (no necesariamente aditivas o monótonas), el mecanismo A-CEEI devuelve una asignación parcial de EF1. El único requisito es que los agentes puedan clasificar paquetes de artículos. Es posible que quede una pequeña cantidad de elementos sin asignar y que sea necesario agregar una pequeña cantidad de elementos. La asignación es Pareto-eficiente con respecto a los elementos asignados.
- El algoritmo Maximum Nash Welfare selecciona una asignación completa que maximiza el producto de las utilidades. Requiere que cada agente proporcione una valoración numérica de cada artículo y asume que las utilidades de los agentes son aditivas. La asignación resultante es tanto EF1 como Pareto-eficiente . [25]
- Varios otros algoritmos devuelven asignaciones EF1 que también son Pareto-eficientes; consulte Asignación eficiente de artículos aproximadamente equitativa .
- Para dos agentes con valoraciones monótonas arbitrarias, o tres agentes con valoraciones aditivas, se puede calcular una asignación EF1 utilizando un número de consultas logarítmicas en el número de elementos. [26]
- Para dos agentes con funciones de utilidad arbitrarias (no necesariamente monótonas), se puede encontrar una asignación EF1 en tiempo polinomial. [27]
- Para un máximo de 4 agentes con valoraciones monótonas arbitrarias, o n agentes con valoraciones monótonas idénticas, siempre existe una asignación EF1 que también está conectada (cuando los artículos se preordenan en una línea, como casas en una calle). La demostración utiliza un algoritmo similar a los protocolos Simmons-Su . Cuando hay n > 4 agentes, no se sabe si existe una asignación EF1 conectada, pero siempre existe una asignación EF2 conectada . [28]
EFx: sin envidia hasta como máximo cualquier artículo
Una asignación se llama EFx si por cada dos agentes A y B, si eliminamos cualquier elemento del paquete de B, entonces A no envidia a B. [29] EFx es estrictamente más fuerte que EF1: EF1 nos permite eliminar la envidia eliminando el artículo más valioso (para A) del paquete de B; EFx requiere que eliminemos la envidia eliminando el elemento menos valioso (para A). Se sabe que existe una asignación EFx en algunos casos especiales:
- Cuando hay dos agentes, o cuando hay n agentes con valoraciones idénticas . En este caso, la asignación óptima de leximina es EFx y óptima de Pareto. Sin embargo, requiere exponencialmente muchas consultas para calcular. [30] [27]
- Cuando hay n agentes con valoraciones aditivas , pero hay como máximo dos valores diferentes para los bienes. En este caso, cualquier asignación de bienestar de Nash máximo es EFx. Además, existe un algoritmo eficiente para calcular una asignación EFx (aunque no necesariamente el bienestar de Nash máximo). [31]
- I Cuando hay n agentes con valoraciones aditivas , pero hay como máximo dos tipos de valoraciones diferentes. [32]
- Cuando hay tres agentes con valoraciones aditivas . En este caso, existe un algoritmo de tiempo polinomial. [33]
Se conocen algunas aproximaciones:
- Una asignación de EFx aproximada a 1/2 (que también satisface una noción de equidad aproximada diferente llamada Maximin Aware ) se puede encontrar en tiempo polinomial. [34]
- En el tiempo polinomial se puede encontrar una asignación de EFx aproximada de 0,618 (que también es EF1 y se aproxima a otras nociones de equidad llamadas participación de maximin por grupos y participación de maximin por pares ). [35]
- Siempre existe una asignación de EFx parcial , donde el bienestar de Nash es al menos la mitad del máximo bienestar de Nash posible. En otras palabras, después de donar algunos artículos a una organización benéfica, los artículos restantes se pueden asignar de forma EFx. Este límite es el mejor posible. En mercados grandes, donde las valoraciones de un agente para cada artículo son relativamente pequeñas, el algoritmo alcanza EFx con un bienestar de Nash casi óptimo. [36] Es suficiente donar n -1 artículos, y ningún agente envidia el conjunto de artículos donados. [37]
Es una pregunta abierta si existe una asignación EFx en general. El caso abierto más pequeño son 4 agentes con valoraciones aditivas.
A diferencia de EF1, que requiere un número de consultas logarítmicas en el número de elementos, calcular una asignación de EFx puede requerir un número lineal de consultas incluso cuando hay dos agentes con valoraciones aditivas idénticas. [26]
Otra diferencia entre EF1 y EFx es que el número de asignaciones de EFX puede ser tan solo 2 (para cualquier número de elementos), mientras que el número de asignaciones de EF1 es siempre exponencial en el número de elementos. [38]
EFm: casi sin envidia para una mezcla de elementos divisibles e indivisibles
Algunos escenarios de división involucran elementos divisibles e indivisibles, como tierras divisibles y casas indivisibles. Una asignación se llama EFm si por cada dos agentes A y B: [39]
- Si el paquete de B contiene algunos bienes divisibles, entonces A no envidia a B (como en una asignación de EF).
- Si el paquete de B contiene solo bienes indivisibles, entonces A no envidia a B después de eliminar como máximo un artículo del paquete de B (como en una asignación EF1).
Existe una asignación EFm para cualquier número de agentes. Sin embargo, encontrarlo requiere un oráculo para la división exacta de un pastel. Sin este oráculo, una asignación de EFm se puede calcular en tiempo polinomial en dos casos especiales: dos agentes con valoraciones aditivas generales o cualquier número de agentes con valoraciones lineales por partes.
A diferencia de EF1, que es compatible con el óptimo de Pareto, EFm puede ser incompatible con él.
Minimizando la envidia
En lugar de utilizar un límite en el peor de los casos en la cantidad de envidia, se puede intentar minimizar la cantidad de envidia en cada caso particular. Consulte la minimización de la envidia para obtener detalles y referencias.
Encontrar una asignación de EF parcial
El procedimiento AL encuentra una asignación de EF para dos agentes. Puede descartar algunos de los elementos, pero la asignación final es Pareto eficiente en el siguiente sentido: ninguna otra asignación de EF es mejor para uno y débilmente mejor para el otro. El procedimiento AL solo requiere que los agentes clasifiquen elementos individuales. Asume que los agentes tienen preferencias de respuesta y devuelve una asignación que es necesariamente libre de envidia (NEF).
El procedimiento de ganador ajustado devuelve una asignación de EF completa y eficiente para dos agentes, pero es posible que tenga que cortar un solo artículo (alternativamente, un artículo permanece en propiedad compartida). Requiere que los agentes informen un valor numérico para cada artículo y asume que tienen utilidades aditivas .
Cuando cada agente puede obtener como máximo un artículo único, y las valoraciones son binarias (a cada agente le gusta o no le gusta cada artículo), existe un algoritmo de tiempo polinomial que encuentra una coincidencia sin envidia de máxima cardinalidad. [40]
Existencia de asignaciones de EF con valoraciones aleatorias
Si los agentes tienen funciones de utilidad aditiva que se extraen de distribuciones de probabilidad que satisfacen algunos criterios de independencia, y el número de elementos es suficientemente grande en relación con el número de agentes, entonces existe una asignación de EF con alta probabilidad . Particularmente:
- Si el número de elementos es suficientemente grande: , entonces, ¿dónde existe una asignación de EF (la probabilidad va a 1 cuando m va al infinito) y se puede encontrar mediante el protocolo round-robin . [41]
- Si , entonces, ¿dónde existe una asignación de EF y se puede encontrar maximizando el bienestar social? [42] Este límite también es estrecho debido a las conexiones con el problema del cobrador de cupones .
- Si y m es divisible por n, entonces, ¿dónde existe una asignación de EF y se puede encontrar mediante un algoritmo basado en coincidencias? [43]
Por otro lado, si el número de elementos no es lo suficientemente grande, entonces, con alta probabilidad, no existe una asignación de EF.
- Si el número de artículos no es lo suficientemente grande, es decir, , entonces whp no existe una asignación de EF. [42]
- Si y m no es "casi divisible" por n, entonces whp no existe una asignación de EF. [43]
Libertad de envidia frente a otros criterios de equidad
- Cada asignación de EF es mínima-máxima-justa . Esto se deriva directamente de las definiciones ordinales y no depende de la aditividad.
- Si todos los agentes tienen funciones de utilidad aditivas , entonces una asignación de EF también es proporcional y max-min-fair . De lo contrario, una asignación de EF puede no ser proporcional e incluso no máximo-mínimo-justo.
- Toda asignación de un equilibrio competitivo a partir de ingresos iguales también está libre de envidia. Esto es cierto independientemente de la aditividad. [24]
- Cada asignación óptima de Nash (asignación que maximiza el producto de las utilidades) es EF1. [29]
- La ausencia de envidia grupal es un fortalecimiento de la ausencia de envidia, que es aplicable tanto a los objetos divisibles como a los indivisibles.
Consulte Asignación justa de artículos para obtener detalles y referencias.
Tabla de resumen
A continuación, se utilizan las siguientes abreviaturas:
- = el número de agentes que participan en la división;
- = el número de elementos a dividir;
- EF = sin envidia, EF1 = sin envidia excepto-1-ítem (más débil que EF), MEF1 = marginal-sin envidia-excepto-1-ítem (más débil que EF1).
- PE = Pareto-eficiente.
Nombre | #socios | Aporte | Preferencias | #consultas | Justicia | Eficiencia | Comentarios |
---|---|---|---|---|---|---|---|
Vender a menor precio que | 2 | Clasificación de paquetes | Estrictamente monótono | EF | Completo | Si-y-solo-si existe una asignación completa de EF | |
Alabama | 2 | Clasificación de artículos | Débilmente aditivo | Necesariamente-EF | Parcial, pero no dominado por Pareto por otra NEF | ||
Ganador ajustado | 2 | Valoraciones de artículos | Aditivo | EF y equitativo | EDUCACIÓN FÍSICA | Podría dividir un artículo. | |
Round-robin | Clasificación de artículos | Débilmente aditivo | Necesariamente-EF1 | Completo | |||
Gráfico de envidia | Clasificación de paquetes | Monótono | EF1 | Completo | |||
A-CEEI | Clasificación de paquetes | Alguna | ? | EF1 y -maximin-share | Elementos parciales, pero PE wrt asignados | También aproximadamente a prueba de estrategias cuando hay muchos agentes. | |
Bienestar Máximo de Nash [29] | Valoraciones de artículos | Aditivo | NP-hard (pero hay aproximaciones en casos especiales) | EF1, y aproximadamente--maximin-share | EDUCACIÓN FÍSICA | Con los servicios públicos submodulares, la asignación es PE y MEF1. |
Referencias
- ^ a b Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Manual de elección social computacional . Prensa de la Universidad de Cambridge. ISBN 9781107060432.( versión gratuita en línea )
- ^ Svensson, Lars-Gunnar (1983). "Grandes indivisibles: un análisis con respecto al equilibrio y la equidad de precios". Econometrica . 51 (4): 939–954. doi : 10.2307 / 1912044 . ISSN 0012-9682 . JSTOR 1912044 .
- ^ Demange G, Gale D, Sotomayor M (1986). "Subastas de varios artículos". Revista de Economía Política . 94 (4): 863–872. doi : 10.1086 / 261411 . JSTOR 1833206 . S2CID 154114302 .
- ^ Maskin, Eric S. (1987), Feiwel, George R. (ed.), "On the Fair Allocation of Indivisible Goods" , Arrow and the Foundations of the Theory of Economic Policy , Londres: Palgrave Macmillan Reino Unido, págs. 341– 349, doi : 10.1007 / 978-1-349-07357-3_12 , ISBN 978-1-349-07357-3, consultado el 16 de febrero de 2021
- ^ Tadenuma, Koichi; Thomson, William (1991). "No envidia y coherencia en las economías con bienes indivisibles". Econometrica . 59 (6): 1755-1767. doi : 10.2307 / 2938288 . ISSN 0012-9682 . JSTOR 2938288 .
- ^ Aragonés, Enriqueta (1995). "Una derivación de la solución rawlsiana del dinero". Elección social y bienestar . 12 (3): 267–276. doi : 10.1007 / BF00179981 . ISSN 0176-1714 . JSTOR 41106132 . S2CID 154215964 .
- ^ a b Alkan, Ahmet; Demange, Gabrielle; Gale, David (1991). "Asignación equitativa de bienes indivisibles y criterios de justicia". Econometrica . 59 (4): 1023–1039. doi : 10.2307 / 2938172 . ISSN 0012-9682 . JSTOR 2938172 .
- ^ Klijn, Flip (1 de marzo de 2000). "Un algoritmo para asignaciones sin envidia en una economía con objetos y dinero indivisibles" . Elección social y bienestar . 17 (2): 201–215. doi : 10.1007 / s003550050015 . ISSN 1432-217X . S2CID 18544150 .
- ^ Meertens, Marc; Potter, Jos; Reijnierse, Hans (1 de diciembre de 2002). "Asignaciones sin envidia y Pareto eficientes en economías con bienes y dinero indivisibles" . Ciencias Sociales Matemáticas . 44 (3): 223–233. doi : 10.1016 / S0165-4896 (02) 00064-1 . ISSN 0165-4896 .
- ^ Ruggiero Cavallo (2012). Equidad y bienestar a través de la redistribución cuando la utilidad es transferible (PDF) . AAAI-12.
- ^ Bailey, Martin J. (1997). "El proceso de revelación de la demanda: distribuir el excedente". Elección pública . 91 (2): 107–126. doi : 10.1023 / A: 1017949922773 . S2CID 152637454 .
- ^ Cavallo, Ruggiero (2006). "Toma de decisiones óptima con mínimo desperdicio". Actas de la quinta conferencia conjunta internacional sobre agentes autónomos y sistemas multiagente - AAMAS '06 . pag. 882. doi : 10.1145 / 1160633.1160790 . ISBN 1595933034.
- ^ Halpern, Daniel; Shah, Nisarg (2019). Fotakis, Dimitris; Markakis, Evangelos (eds.). "División justa con subsidio" . Teoría algorítmica de juegos . Apuntes de conferencias en Ciencias de la Computación. Cham: Springer International Publishing. 11801 : 374–389. doi : 10.1007 / 978-3-030-30473-7_25 . ISBN 978-3-030-30473-7.
- ^ Brustle, Johannes; Dippel, Jack; Narayan, Vishnu V .; Suzuki, Mashbat; Vetta, Adrian (13 de julio de 2020). "Un dólar cada uno elimina la envidia" . Actas de la 21ª Conferencia ACM sobre Economía y Computación . EC '20. Evento virtual, Hungría: Asociación de Maquinaria Informática: 23–39. arXiv : 1912.02797 . doi : 10.1145 / 3391403.3399447 . ISBN 978-1-4503-7975-5. S2CID 208637311 .
- ^ Caragiannis, Ioannis; Ioannidis, Stavros (6 de febrero de 2020). "Computación de asignaciones sin envidia con subsidios limitados". arXiv : 2002.02789 [ cs.GT ].
- ^ Mu'alem A (2014). "Fair by design: mecanismos multidimensionales sin envidia". Juegos y comportamiento económico . 88 : 29–46. doi : 10.1016 / j.geb.2014.08.001 .
- ^ Aziz, Haris (18 de marzo de 2020). "Lograr la libertad de envidia y la equidad con transferencias monetarias". arXiv : 2003.08125 [ cs.GT ].
- ^ Sylvain Bouveret, Ulle Endriss, Jérôme Lang (2010). División justa bajo preferencias ordinales: cálculo de asignaciones libres de envidia de bienes indivisibles . ECAI 2010. págs. 387–392.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Lipton, RJ; Markakis, E .; Mossel, E .; Saberi, A. (2004). "Sobre asignaciones aproximadamente justas de bienes indivisibles". Actas de la 5ª conferencia ACM sobre comercio electrónico - EC '04 . pag. 125. doi : 10.1145 / 988772.988792 . ISBN 1-58113-771-0.
- ^ Plaut, Benjamín; Roughgarden, Tim (1 de enero de 2020). "Complejidad de la comunicación de la división equitativa discreta" . Revista SIAM de Computación . 49 (1): 206–243. arXiv : 1711.04066 . doi : 10.1137 / 19M1244305 . ISSN 0097-5397 . S2CID 212667868 .
- ^ a b c Bouveret, S .; Lang, J. (2008). "Eficiencia y ausencia de envidia en la división justa de bienes indivisibles: representación lógica y complejidad" . Revista de Investigación en Inteligencia Artificial . 32 : 525–564. doi : 10.1613 / jair.2467 .
- ^ De Keijzer, Bart; Bouveret, Sylvain; Klos, Tomas; Zhang, Yingqian (2009). "Sobre la complejidad de la eficiencia y la ausencia de envidia en la división justa de bienes indivisibles con preferencias aditivas". Teoría de la decisión algorítmica . Apuntes de conferencias en Ciencias de la Computación. 5783 . pag. 98. doi : 10.1007 / 978-3-642-04428-1_9 . ISBN 978-3-642-04427-4.
- ^ Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf (9 de julio de 2016). "Complejidad de la asignación de recursos eficiente y sin envidias: pocos agentes, recursos o niveles de utilidad" . Actas de la XXV Conferencia Conjunta Internacional sobre Inteligencia Artificial . IJCAI'16. Nueva York, Nueva York, EE.UU .: AAAI Press: 102–108. ISBN 978-1-57735-770-4.
- ^ a b Budish, Eric (2011). "El problema de asignación combinatoria: equilibrio competitivo aproximado de ingresos iguales". Revista de Economía Política . 119 (6): 1061-1103. CiteSeerX 10.1.1.357.9766 . doi : 10.1086 / 664613 . S2CID 154703357 .
- ^ Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D .; Shah, Nisarg; Wang, Junxing (2016). La equidad irrazonable del máximo bienestar de Nash (PDF) . Actas de la Conferencia ACM 2016 sobre Economía y Computación - EC '16. pag. 305. doi : 10.1145 / 2940716.2940726 . ISBN 9781450339360.
- ^ a b Oh, Hoon; Procaccia, Ariel D .; Suksompong, Warut (17 de julio de 2019). "Asignación justa de muchos bienes con pocas consultas" . Actas de la Conferencia AAAI sobre Inteligencia Artificial . 33 (1): 2141–2148. doi : 10.1609 / aaai.v33i01.33012141 . ISSN 2374-3468 . S2CID 51867780 .
- ^ a b Bérczi, Kristóf; Bérczi-Kovács, Erika R .; Boros, Endre; Gedefa, Fekadu Tolessa; Kamiyama, Naoyuki; Kavitha, Telikepalli; Kobayashi, Yusuke; Makino, Kazuhisa (8 de junio de 2020). "Relajaciones sin envidia para bienes, quehaceres y elementos mixtos". arXiv : 2006.04428 [ econ.TH ].
- ^ Bilò, Vittorio; Caragiannis, Ioannis; Flammini, Michele; Igarashi, Ayumi; Mónaco, Gianpiero; Peters, Dominik; Vinci, Cosimo; Zwicker, William S. (28 de agosto de 2018). "Asignaciones casi libres de envidia con paquetes conectados". arXiv : 1808.09406 [ cs.GT ].
- ^ a b c Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D .; Shah, Nisarg; Wang, Junxing (2016). La equidad irrazonable del máximo bienestar de Nash (PDF) . Actas de la Conferencia ACM 2016 sobre Economía y Computación - EC '16. pag. 305. doi : 10.1145 / 2940716.2940726 . ISBN 9781450339360.
- ^ Plaut, Benjamín; Roughgarden, Tim (1 de enero de 2020). "Casi libre de envidia con valoraciones generales" . Revista SIAM de Matemática Discreta . 34 (2): 1039–1068. arXiv : 1707.04769 . doi : 10.1137 / 19M124397X . ISSN 0895-4801 .
- ^ Amanatidis, Georgios; Birmpas, Georgios; Filos-Ratsikas, Aris; Hollender, Alexandros; Voudouris, Alexandros A. (1 de junio de 2020). "Máximo bienestar de Nash y otras historias sobre EFX". arXiv : 2001.09838 [ cs.GT ].
- ^ Mahara, Ryoga (20 de agosto de 2020). "Existencia de EFX para dos valoraciones aditivas". arXiv : 2008.08798 [ cs.GT ].
- ^ Chaudhury, Bhaskar Ray; Garg, Jugal; Mehlhorn, Kurt (30 de mayo de 2020). "EFX existe para tres agentes". arXiv : 2002.05119 [ cs.GT ].
- ^ Chan, Hau; Chen, Jing; Li, Bo; Wu, Xiaowei (25 de octubre de 2019). "Asignaciones conscientes de Maximin de bienes indivisibles". arXiv : 1905.09969 [ cs.GT ].
- ^ Amanatidis, Georgios; Ntokos, Apostolos; Markakis, Evangelos (2020). "Varias aves de un tiro: batir 1/2 para EFX y GMMS a través de la eliminación del ciclo de la envidia". Informática Teórica . 841 : 94-109. arXiv : 1909.07650 . doi : 10.1016 / j.tcs.2020.07.006 . S2CID 222070124 .
- ^ Caragiannis, Ioannis; Gravin, Nick; Huang, Xin (17 de junio de 2019). "Libre de envidia hasta cualquier artículo con alto bienestar de Nash: la virtud de donar artículos" . Actas de la Conferencia ACM de 2019 sobre economía y computación . CE '19. Phoenix, AZ, EE.UU .: Asociación de Maquinaria de Computación: 527–545. arXiv : 1902.04319 . doi : 10.1145 / 3328526.3329574 . ISBN 978-1-4503-6792-9. S2CID 60441171 .
- ^ Chaudhury, Bhaskar Ray; Kavitha, Telikepalli; Mehlhorn, Kurt; Sgouritsa, Alkmini (2019-12-23), "A Little Charity Guarantees Almost Envy-Freeness" , Actas del Simposio ACM-SIAM de 2020 sobre algoritmos discretos , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 2658–2672, arXiv : 1907.04596 , doi : 10.1137 / 1.9781611975994.162 , ISBN 978-1-61197-599-4, S2CID 195874127 , consultado el 2 de octubre de 2020
- ^ Suksompong, Warut (30 de septiembre de 2020). "Sobre el número de asignaciones casi sin envidia" . Matemáticas aplicadas discretas . 284 : 606–610. arXiv : 2006.00178 . doi : 10.1016 / j.dam.2020.03.039 . ISSN 0166-218X . S2CID 215715272 .
- ^ Bei, Xiaohui; Li, Zihao; Liu, Jinyan; Liu, Shengxin; Lu, Xinhang (2021). "División equitativa de bienes mixtos divisibles e indivisibles". Inteligencia artificial . 293 : 103436. arXiv : 1911.07048 . doi : 10.1016 / j.artint.2020.103436 . S2CID 231719223 .
- ^ Aigner-Horev, Elad; Segal-Halevi, Erel (22 de diciembre de 2020). "Emparejamientos sin envidia en gráficos bipartitos y sus aplicaciones a la división justa". arXiv : 1901.09527 [ cs.DS ].
- ^ Manurangsi, Pasin; Suksompong, Warut (8 de abril de 2021). "Cerrando brechas en la división asintótica de la feria" . Revista SIAM de Matemática Discreta . 35 (2): 668–706. arXiv : 2004.05563 . doi : 10.1137 / 20M1353381 .
- ^ a b John P. Dickerson; Jonathan Goldman; Jeremy Karp; Ariel D. Procaccia; Tuomas Sandholm (2014). El ascenso y la caída computacional de la equidad . En Actas de la XXVIII Conferencia AAAI sobre Inteligencia Artificial (2014). págs. 1405-1411. CiteSeerX 10.1.1.703.8413 . Enlace ACM
- ^ a b Manurangsi, Pasin; Suksompong, Warut (2 de julio de 2020). "¿Cuándo existen las asignaciones sin envidia?" . Revista SIAM de Matemática Discreta . 34 (3): 1505-1521. arXiv : 1811.01630 . doi : 10.1137 / 19M1279125 .