Maximización del bienestar

El problema de maximización del bienestar es un problema de optimización estudiado en economía y ciencias de la computación . Su objetivo es dividir un conjunto de elementos entre agentes con diferentes funciones de utilidad , de modo que el bienestar, definido como la suma de las utilidades de los agentes, sea lo más alto posible. En otras palabras, el objetivo es encontrar una asignación de elementos que satisfaga la regla utilitarista . ^[1]

Un problema equivalente en el contexto de subastas combinatorias se denomina problema de determinación del ganador . En este contexto, cada agente presenta una lista de ofertas sobre conjuntos de artículos y el objetivo es determinar qué oferta u ofertas deberían ganar, de modo que la suma de las ofertas ganadoras sea máxima.

Definiciones

Hay un conjunto M de m elementos y un conjunto N de n agentes. Cada agente i en N tiene una función de utilidad . La función asigna un valor real a cada subconjunto posible de elementos. Por lo general, se supone que las funciones de utilidad son funciones de conjunto monótonas , es decir, implica . También se supone que . Junto con la monotonía, esto implica que todas las utilidades son no negativas. ${\displaystyle u_{i}:2^{M}\to \mathbb {R} }$ ${\displaystyle Z_{1}\supseteq Z_{2}}$ ${\displaystyle u_{i}(Z_{1})\geq u_{i}(Z_{2})}$ ${\displaystyle u_{i}(\emptyset )=0}$

Una asignación es una partición ordenada de los elementos en n subconjuntos disjuntos, un subconjunto por agente, denotado , tal que .El bienestar de una asignación es la suma de las utilidades de los agentes: . ${\displaystyle \mathbf {X} =(X_{1},\ldots ,X_{n})}$ ${\displaystyle M=X_{1}\sqcup \cdots \sqcup X_{n}}$ ${\displaystyle W(\mathbf {X} ):=\sum _{i\in N}u_{i}(X_{i})}$

El problema de maximización del bienestar es: encontrar una asignación X que maximice W ( X ).

El problema de maximización del bienestar tiene muchas variantes, dependiendo del tipo de funciones de utilidad permitidas, la forma en que el algoritmo puede acceder a las funciones de utilidad y si existen restricciones adicionales a las asignaciones permitidas.

Agentes aditivos

Un agente aditivo tiene una función de utilidad que es una función de conjunto aditivo : para cada agente aditivo i y elemento j , existe un valor , tal que para cada conjunto Z de elementos. Cuando todos los agentes son aditivos, la maximización del bienestar se puede realizar mediante un algoritmo de tiempo polinomial simple : dar cada elemento j a un agente para el que es máximo (deshaciendo los empates arbitrariamente). El problema se vuelve más desafiante cuando hay restricciones adicionales en la asignación. ${\displaystyle v_{i,j}}$ ${\displaystyle u_{i}(Z)=\sum _{j\in X_{i}}v_{i,j}}$ ${\displaystyle v_{i,j}}$

Restricciones de equidad

Se puede querer maximizar el bienestar entre todas las asignaciones que son justas , por ejemplo, libres de envidia hasta un elemento (EF1), proporcionales hasta un elemento (PROP1) o equitativas hasta un elemento (EQ1). Este problema es fuertemente NP-hard cuando n es variable. Para cualquier n fijo ≥ 2, el problema es débilmente NP-hard, ^{[2] [3]} y tiene un algoritmo de tiempo pseudo-polinomial basado en programación dinámica. ^[2] Para n = 2 , el problema tiene un esquema de aproximación de tiempo completamente polinomial . ^[4]

Existen algoritmos para resolver este problema en tiempo polinomial cuando hay pocos tipos de agentes, pocos tipos de elementos o niveles de valor pequeños. ^[5] El problema también se puede resolver en tiempo polinomial cuando las utilidades aditivas de los agentes son binarias (el valor de cada elemento es 0 o 1), así como para una clase más general de utilidades denominadas binarias generalizadas . ^[6]

Restricciones de matroides

Otra restricción de la asignación es que los paquetes deben ser conjuntos independientes de un matroide . Por ejemplo, cada paquete debe contener como máximo k elementos, donde k es un entero fijo (esto corresponde a un matroide uniforme ). O bien, los elementos pueden dividirse en categorías y cada paquete debe contener como máximo k _c elementos de cada categoría c (esto corresponde a un matroide de partición ). En general, puede haber un matroide diferente para cada agente, y la asignación debe dar a cada agente i un subconjunto Xi _que sea un conjunto independiente de su propio matroide.

La maximización del bienestar con utilidades aditivas bajo restricciones de matroides heterogéneas se puede realizar en tiempo polinomial, mediante reducción al problema de intersección de matroides ponderados . ^[7]

Agentes sustitutos brutos

Las utilidades de sustitución bruta son más generales que las utilidades aditivas. La maximización del bienestar con agentes de sustitución bruta se puede realizar en tiempo polinomial. Esto se debe a que, con agentes de sustitución bruta, siempre existe un equilibrio walrasiano , que maximiza la suma de utilidades. ^[8] Un equilibrio walrasiano se puede encontrar en tiempo polinomial.

Agentes submodulares

Un agente submodular tiene una función de utilidad que es una función de conjunto submodular . Esto significa que la utilidad del agente tiene marginales decrecientes . Las utilidades submodulares son más generales que las utilidades brutas sustitutivas.

Dureza

La maximización del bienestar con agentes submodulares es NP-hard. ^[9] Además, no se puede aproximar a un factor mejor que (1-1/e)≈0,632 a menos que P=NP. ^[10] Además, una aproximación mejor que (1-1/e) requeriría un número exponencial de consultas a un oráculo de valores , independientemente de si P=NP. ^[11]

Algoritmo codicioso

El bienestar máximo se puede aproximar mediante el siguiente algoritmo codicioso de tiempo polinomial :

• Inicializar X ₁ = X ₂ = ... = X _n = vacío.
• Para cada elemento g (en un orden arbitrario):
  • Calcular, para cada agente i , su utilidad marginal para g , definida como: u _i ( X _i + g ) - u _i ( X _i ).
  • Entregue el artículo g a un agente con la mayor utilidad marginal.

Lehman, Lehman y Nisan ^[9] demuestran que el algoritmo voraz encuentra una aproximación de 1/2 factor (observan que este resultado se desprende de un resultado de Fisher, Nemhauser y Wolsey ^[12] con respecto a la maximización de una única valoración submodular sobre un matroide). La idea de la prueba es la siguiente. Supongamos que el algoritmo asigna un elemento g a algún agente i . Esto contribuye al bienestar en cierta cantidad v , que es la utilidad marginal de g para i en ese punto. Supongamos que, en la solución óptima, g debería entregarse a otro agente, digamos k. Consideremos cómo cambia el bienestar si movemos g de i a k :

• La utilidad de k aumenta por su utilidad marginal de g , que como máximo es v por la selección codiciosa.
• La utilidad marginal del conjunto restante de i aumenta como máximo en v . Esto se desprende de la submodularidad: la utilidad marginal de g , cuando se agrega al conjunto restante, no puede ser mayor que su utilidad marginal cuando el algoritmo la procesó.

Por lo tanto, por cada contribución de v al bienestar del algoritmo, la contribución potencial al bienestar óptimo podría ser como máximo 2 v . Por lo tanto, el bienestar óptimo es como máximo 2 veces el bienestar del algoritmo. El factor de 2 es ajustado para el algoritmo voraz. Por ejemplo, supongamos que hay dos elementos x,y y las valoraciones son:

La asignación óptima es Alice: {y}, George: {x}, con un bienestar de 2. Pero si el algoritmo codicioso asigna x primero, podría asignarlo a Alice. Entonces, independientemente de cómo se asigne y, el bienestar es solo 1.

Algoritmos que utilizan un oráculo de valores

Un oráculo de valores es un oráculo que, dado un conjunto de elementos, devuelve el valor del agente a este conjunto. En este modelo:

• Dobzinski y Schapira ^[13] presentan un algoritmo de aproximación politemporal y un algoritmo de aproximación (1-1/e)≈0,632 para el caso especial en el que las utilidades de los agentes son funciones de cobertura de conjuntos. ${\displaystyle n/(2n-1)}$
• Vondrak ^{[14] : Sec.5} y Calinescu, Chekuri, Pal y Vondrak ^[15] presentan un algoritmo politemporal aleatorio que encuentra una aproximación (1-1/e) con alta probabilidad . Su algoritmo utiliza un algoritmo continuo-codicioso - un algoritmo que extiende un paquete fraccional (un paquete que contiene una fracción p _j de cada elemento j ) en una dirección codiciosa (de manera similar al descenso de gradiente ). Su algoritmo necesita calcular el valor de los paquetes fraccionales, definido como el valor esperado del paquete obtenido cuando cada elemento j se selecciona independientemente con probabilidad p _j . En general, calcular el valor de un paquete fraccional puede requerir 2 ^m llamadas a un oráculo de valores; sin embargo, se puede calcular aproximadamente con alta probabilidad mediante muestreo aleatorio . Esto conduce a un algoritmo aleatorio que alcanza una aproximación (1-1/e) con alta probabilidad. En los casos en que los paquetes fraccionarios se pueden evaluar de manera eficiente (por ejemplo, cuando las funciones de utilidad son funciones de cobertura de conjuntos), el algoritmo se puede hacer determinista. ^{[15] : Sec.5} Mencionan como un problema abierto si existe un algoritmo de aproximación politemporal determinista (1-1/e) para funciones submodulares generales.

El problema de maximización del bienestar (con n funciones submodulares diferentes) se puede reducir al problema de maximizar una única función de conjunto submodular sujeta a una restricción matroide : ^{[9] [14] [15]} dada una instancia con m elementos y n agentes, construir una instancia con m * n pares (agente, elemento), donde cada par representa la asignación de un elemento a un agente. Construir una única función que asigne, a cada conjunto de pares, el bienestar total de la asignación correspondiente. Se puede demostrar que, si todas las utilidades son submodulares, entonces esta función de bienestar también es submodular. Esta función debe maximizarse sujeta a una restricción matroide de partición , asegurando que cada elemento se asigne a un agente como máximo.

Algoritmos que utilizan un oráculo de demanda

Otra forma de acceder a las utilidades de los agentes es mediante un oráculo de demanda (un oráculo que, dado un vector de precios, devuelve el paquete más deseado por el agente). En este modelo:

• Dobzinski y Schapira ^[13] presentan un algoritmo de aproximación politemporal (1-1/e).
• Feige y Vondrak ^[16] mejoran esto a (1-1/e+ε) para algunos ε positivos pequeños (esto no contradice el resultado de dureza anterior, ya que el resultado de dureza utiliza solo un oráculo de valor; en los ejemplos de dureza, el oráculo de demanda en sí mismo requeriría exponencialmente muchas consultas) .

Agentes subaditivos

Cuando las utilidades de los agentes son funciones de conjunto subaditivas (más generales que submodulares), una aproximación requeriría un número exponencial de consultas de valores. ^[11] ${\displaystyle {\frac {1}{m^{1/2-\epsilon }}}}$

Feige ^[17] presenta una forma de redondear cualquier solución fraccionaria de una relajación LP para este problema a una solución factible con un bienestar de al menos la mitad del valor de la solución fraccionaria. Esto da una aproximación 1/2 para agentes subaditivos generales y una aproximación (1-1/e) para el caso especial de valoraciones fraccionariamente subaditivas .

Agentes superaditivos

Cuando las utilidades de los agentes son funciones de conjunto superaditivas (más generales que supermodulares), una aproximación requeriría un número superpolinómico de consultas de valores. ^[11] ${\displaystyle {\frac {(\log m)^{1+\epsilon }}{m}}}$

Agentes con un solo objetivo

Un agente con una sola mente quiere solo un conjunto específico de artículos. Para cada agente con una sola mente i , existe un conjunto demandado D _i , y un valor V _i > 0, tal que . Es decir, el agente recibe una utilidad positiva fija si y solo si su paquete contiene su conjunto demandado. ${\displaystyle u_{i}(Z)={\begin{cases}V_{i}&Z\supseteq D_{i}\\0&{\text{otherwise}}\end{cases}}}$

La maximización del bienestar con agentes unidireccionales es NP-difícil incluso cuando para todo i . En este caso, el problema es equivalente al empaquetamiento de conjuntos , que se sabe que es NP-difícil. Además, no se puede aproximar dentro de ningún factor constante (en contraste con el caso de los agentes submodulares). ^[18] El algoritmo más conocido lo aproxima dentro de un factor de . ^[19] ${\displaystyle V_{i}=1}$ ${\displaystyle O({\sqrt {m}})}$

Agentes generales

Cuando los agentes pueden tener funciones de utilidad monótonas arbitrarias (incluidos los elementos complementarios ), la maximización del bienestar es difícil de aproximar dentro de un factor de para cualquier . ^[20] Sin embargo, existen algoritmos basados ​​en la búsqueda en el espacio de estados que funcionan muy bien en la práctica. ^[21] ${\displaystyle O(n^{1/2-\epsilon })}$ ${\displaystyle \epsilon >0}$

Véase también

• Problema de maximización de utilidad
• Maximización de beneficios

Referencias

1. Vondrak, Jan (17 de mayo de 2008). "Aproximación óptima para el problema de bienestar submodular en el modelo de oráculo de valores". Actas del cuadragésimo simposio anual de la ACM sobre teoría de la computación . STOC '08. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 67–74. doi :10.1145/1374376.1374389. ISBN 978-1-60558-047-0.S2CID 170510  .
2. Aziz, Haris; Huang, Xin; Mattei, Nicholas; Segal-Halevi, Erel (13 de octubre de 2022). "Computing welfare-Maximizing fair assignments of indivisible goods" (Cálculo del bienestar: maximización de asignaciones justas de bienes indivisibles). Revista Europea de Investigación Operativa . 307 (2): 773–784. arXiv : 2012.03979 . doi :10.1016/j.ejor.2022.10.013. ISSN  0377-2217. S2CID  235266307.
3. Sun, Ankang; Chen, Bo; Doan, Xuan Vinh (2 de diciembre de 2022). "Equitabilidad y maximización del bienestar para la asignación de elementos indivisibles". Agentes autónomos y sistemas multiagente . 37 (1): 8. doi : 10.1007/s10458-022-09587-1 . ISSN  1573-7454. S2CID  254152607.
4. Bu, Xiaolin; Li, Zihao; Liu, Shengxin; Canción, Jiaxin; Tao, Biaoshuai (27 de mayo de 2022). "Sobre la complejidad de maximizar el bienestar social dentro de asignaciones justas de bienes indivisibles". arXiv : 2205.14296 [cs.GT].
5. Nguyen, Trung Thanh; Rothe, Jörg (1 de enero de 2023). "Asignación justa y eficiente con pocos tipos de agentes, pocos tipos de elementos o niveles de valor pequeños". Inteligencia artificial . 314 : 103820. doi :10.1016/j.artint.2022.103820. ISSN  0004-3702. S2CID  253430435.
6. Camacho, Franklin; Fonseca Delgado, Rigoberto; Pino Pérez, Ramón; Tapia, Guido (07-11-2022). "Funciones de utilidad binarias generalizadas y asignaciones justas". Ciencias Sociales Matemáticas . 121 : 50–60. doi :10.1016/j.mathsocsci.2022.10.003. ISSN  0165-4896. S2CID  253411165.
7. Dror, Amitay; Feldman, Michal; Segal-Halevi, Erel (24 de abril de 2022). "Sobre la división justa bajo restricciones matroidales heterogéneas". arXiv : 2010.07280 [cs.GT].
8. Kelso, AS; Crawford, VP (1982). "Emparejamiento laboral, formación de coaliciones y sustitutos brutos". Econometrica . 50 (6): 1483. doi :10.2307/1913392. JSTOR  1913392.
9. Lehmann, Benny; Lehmann, Daniel; Nisan, Noam (14 de octubre de 2001). "Subastas combinatorias con utilidades marginales decrecientes". Actas de la 3.ª conferencia de la ACM sobre comercio electrónico . EC '01. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 18–28. arXiv : cs/0202015 . doi :10.1145/501158.501161. ISBN . 978-1-58113-387-5.S2CID2241237  .​
10. Khot, Subhash; Lipton, Richard J.; Markakis, Evangelos; Mehta, Aranyak (1 de septiembre de 2008). "Resultados de inaproximabilidad para subastas combinatorias con funciones de utilidad submodulares". Algorithmica . 52 (1): 3–18. doi :10.1007/s00453-007-9105-7. ISSN  1432-0541. S2CID  7600128.
11. Mirrokni, Vahab; Schapira, Michael; Vondrak, Jan (8 de julio de 2008). "Límites inferiores teóricos de información estricta para la maximización del bienestar en subastas combinatorias". Actas de la 9.ª conferencia de la ACM sobre comercio electrónico . EC '08. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 70–77. doi :10.1145/1386790.1386805. ISBN 978-1-60558-169-9.S2CID 556774  .
12. Fisher, ML; Nemhauser, GL; Wolsey, LA (1978), Balinski, ML; Hoffman, AJ (eds.), "Un análisis de aproximaciones para maximizar funciones de conjuntos submodulares—II", Combinatoria poliédrica: Dedicado a la memoria de DR Fulkerson , Berlín, Heidelberg: Springer, págs. 73–87, doi :10.1007/bfb0121195, ISBN 978-3-642-00790-3, consultado el 26 de febrero de 2023
13. Dobzinski, Shahar; Schapira, Michael (22 de enero de 2006). "Un algoritmo de aproximación mejorado para subastas combinatorias con postores submodulares". Actas del decimoséptimo simposio anual ACM-SIAM sobre algoritmos discretos - SODA '06 . SODA '06. EE. UU.: Society for Industrial and Applied Mathematics. págs. 1064–1073. doi :10.1145/1109557.1109675. ISBN 978-0-89871-605-4. Número de identificación del sujeto  13108913.
14. Vondrak, Jan (17 de mayo de 2008). "Aproximación óptima para el problema de bienestar submodular en el modelo de oráculo de valores". Actas del cuadragésimo simposio anual de la ACM sobre teoría de la computación . STOC '08. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 67–74. doi :10.1145/1374376.1374389. ISBN 978-1-60558-047-0.S2CID 170510  .
15. Calinescu, Gruia; Chekuri, Chandra; Pál, Martín; Vondrák, enero (1 de enero de 2011). "Maximización de una función submodular monótona sujeta a una restricción matroide". Revista SIAM de Computación . 40 (6): 1740-1766. doi : 10.1137/080733991. ISSN  0097-5397.
16. Feige, Uriel; Vondrák, Jan (9 de diciembre de 2010). "El problema del bienestar submodular con consultas de demanda". Theory of Computing . 6 : 247–290. doi : 10.4086/toc.2010.v006a011 .
17. Feige, Uriel (21 de mayo de 2006). "Sobre la maximización del bienestar cuando las funciones de utilidad son subaditivas". Actas del trigésimo octavo simposio anual de la ACM sobre teoría de la computación . STOC '06. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 41–50. doi :10.1145/1132516.1132523. ISBN 978-1-59593-134-4.S2CID11504912  .​
18. Hazan, Elad; Safra, Shmuel; Schwartz, Oded (2006). "Sobre la complejidad de la aproximación del empaquetamiento de conjuntos k ". Computational Complexity . 15 (1): 20–39. CiteSeerX 10.1.1.352.5754 . doi :10.1007/s00037-006-0205-6. MR  2226068. S2CID  1858087. . Véase en particular la pág. 21: "La camarilla máxima (y por lo tanto también el conjunto independiente máximo y el empaquetamiento máximo del conjunto) no se pueden aproximar a menos que NP ⊂ ZPP". ${\displaystyle O(n^{1-\epsilon })}$
19. Halldórsson, Magnus M.; Kratochvíl, Jan; Telle, Jan Arne (1998). Conjuntos independientes con restricciones de dominación . 25.° Coloquio Internacional sobre Autómatas, Lenguajes y Programación. Apuntes de clase en Ciencias de la Computación. Vol. 1443. Springer-Verlag. págs. 176–185.
20. Lehmann, Daniel; Oćallaghan, Liadan Ita; Shoham, Yoav (1 de septiembre de 2002). "Revelación de la verdad en subastas combinatorias aproximadamente eficientes". Revista de la ACM . 49 (5): 577–602. doi :10.1145/585265.585266. ISSN  0004-5411. S2CID  52829303.
21. Sandholm, Tuomas; Suri, Subhash (30 de julio de 2000). "Algoritmos mejorados para la determinación óptima del ganador en subastas combinatorias y generalizaciones". Actas de la Decimoséptima Conferencia Nacional sobre Inteligencia Artificial y la Duodécima Conferencia sobre Aplicaciones Innovadoras de la Inteligencia Artificial . AAAI Press: 90–97. ISBN 978-0-262-51112-4.