Maximización del bienestar

El problema de maximización del bienestar es un problema de optimización estudiado en economía e informática . 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 artículos que satisfaga la regla utilitarista . ^[1]

Un problema equivalente en el contexto de las 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 o ofertas deben 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. Generalmente se supone que las funciones de utilidad son funciones de conjuntos monótonos , es decir, implican . También se supone que . Junto con la monotonicidad, 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 , de modo 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 sobre 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 , hay un valor , tal que para cada conjunto Z de elementos. Cuando todos los agentes son aditivos, la maximización del bienestar se puede lograr mediante un algoritmo simple de tiempo polinómico : entregar cada elemento j a un agente para quien sea máximo (rompiendo los vínculos arbitrariamente). El problema se vuelve más desafiante cuando existen restricciones adicionales a 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-difícil cuando n es variable. Para cualquier n ≥ 2 fijo, el problema es débilmente NP-duro, ^{[2] [3]} y tiene un algoritmo de tiempo pseudopolinomial basado en programación dinámica. ^[2] Para n = 2 , el problema tiene un esquema de aproximación en tiempo totalmente polinomial . ^[4]

Existen algoritmos para resolver este problema en tiempo polinómico 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 llamada binaria generalizada . ^[6]

restricciones matroides

Otra restricción en la asignación es que los paquetes deben ser conjuntos independientes de una matroide . Por ejemplo, cada paquete debe contener como máximo k elementos, donde k es un número entero fijo (esto corresponde a una 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 una matroide de partición ). En general, puede haber una matroide diferente para cada agente, y la asignación debe darle a cada agente i un subconjunto Xi _que sea un conjunto independiente de su propia matroide.

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

Agentes sustitutos brutos

Las utilidades sustitutivas brutas son más generales que las aditivas. La maximización del bienestar con agentes sustitutos brutos se puede realizar en tiempo polinomial. Esto se debe a que, con agentes sustitutos brutos, siempre existe un equilibrio walrasiano que maximiza la suma de las utilidades. ^[8] Se puede encontrar un equilibrio walrasiano 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 sustitutivas brutas.

Dureza

La maximización del bienestar con agentes submodulares es NP-difícil. ^[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 valor de Oracle , 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 orden arbitrario):
  • Calcule, para cada agente i , su utilidad marginal para g , definida como: u _i ( X _i + g ) - u _i ( X _i ).
  • Dé el elemento g al agente con la mayor utilidad marginal.

Lehman, Lehman y Nisan ^[9] prueban que el algoritmo codicioso encuentra una aproximación de 1/2 factor (señalan que este resultado se deriva de un resultado de Fisher, Nemhauser y Wolsey ^[12] con respecto a la maximización de una valoración submodular única sobre un matroide). La idea de 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 se debe dar a otro agente, digamos k. Considere cómo cambia el bienestar si trasladamos g de i a k :

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

Entonces, 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 2 es ajustado para el algoritmo codicioso. Por ejemplo, supongamos que hay dos artículos x,y y las valoraciones son:

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

Algoritmos que utilizan un oráculo de valores

Un oráculo de valor 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 politiempo 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 politiempo aleatorio que encuentra una aproximación (1-1/e) con alta probabilidad . Su algoritmo utiliza un algoritmo codicioso continuo, un algoritmo que extiende un paquete fraccionario (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 paquetes fraccionarios, definido como el valor esperado del paquete obtenido cuando cada elemento j se selecciona de forma independiente con probabilidad p _j . En general, calcular el valor de un paquete fraccionario puede requerir llamadas de 2 ^{m 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 pueden evaluarse eficientemente (por ejemplo, cuando las funciones de utilidad son funciones de cobertura de conjuntos), el algoritmo puede hacerse determinista. ^{[15] : Sec.5} Mencionan como un problema abierto, si existe un algoritmo determinista de aproximación politemporal (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 yn agentes, construya una instancia con m * n (agente, artículo) pares, donde cada par representa la asignación de un artículo a un agente. Construya una función única 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 como máximo a un agente.

Algoritmos que utilizan un oráculo de demanda.

Otra forma de acceder a las utilidades de los agentes es utilizar 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 politime (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 sólo un valor oráculo; en los ejemplos de dureza, la demanda El propio Oracle requeriría exponencialmente muchas consultas) .

Agentes subaditivos

Cuando las utilidades de los agentes son funciones de conjuntos subaditivos (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 a una relajación LP de 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 fraccionalmente subaditivas .

Agentes superaditivos

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

Agentes decididos

Un agente decidido sólo quiere un conjunto específico de elementos. Para cada agente i _con un solo propósito , hay un conjunto demandado Di y un valor Vi _> 0, tal que . Es decir, el agente recibe una utilidad positiva fija si y sólo si su paquete contiene el 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 decididos es NP-difícil incluso cuando para todos i . En este caso, el problema es equivalente a configurar el embalaje , que se sabe que es NP duro. Además, no se puede aproximar dentro de ningún factor constante (a diferencia del 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 arbitrarias y monótonas (incluidos elementos complementarios ), la maximización del bienestar es difícil de aproximar dentro de un factor de para cualquiera . ^[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}$

Ver también

• Problema de maximización de la utilidad

Referencias

1. Vondrak, enero (17 de mayo de 2008). "Aproximación óptima al problema de bienestar submodular en el modelo de oráculo de valor". Actas del cuadragésimo simposio anual de ACM sobre teoría de la informática . STOC '08. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 67–74. doi :10.1145/1374376.1374389. ISBN 978-1-60558-047-0. S2CID  170510.
2. Aziz, Haris; Huang, Xin; Mattei, Nicolás; Segal-Halevi, Erel (13 de octubre de 2022). "Calcular el bienestar: maximizar las 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. Sol, Ankang; Chen, Bo; Doan, Xuan Vinh (2 de diciembre de 2022). "Maximización de la equidad y el 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 artículos 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 matroides heterogéneas". arXiv : 2010.07280 [cs.GT].
8. Kelso, COMO; Crawford, vicepresidente (1982). "Conjunción de empleos, formación de coaliciones y sustitutos brutos". Econométrica . 50 (6): 1483. doi : 10.2307/1913392. JSTOR  1913392.
9. Lehmann, Benny; Lehmann, Daniel; Nisán, Noam (14 de octubre de 2001). "Subastas combinatorias con utilidades marginales decrecientes". Actas de la 3ª conferencia ACM sobre Comercio Electrónico . CE '01. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 18-28. arXiv : cs/0202015 . doi :10.1145/501158.501161. ISBN 978-1-58113-387-5. S2CID  2241237.
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". Algorítmica . 52 (1): 3–18. doi :10.1007/s00453-007-9105-7. ISSN  1432-0541. S2CID  7600128.
11. Mirrokni, Vahab; Schapira, Michael; Vondrak, enero (8 de julio de 2008). "Límites inferiores estrictos de la teoría de la información para la maximización del bienestar en subastas combinatorias". Actas de la novena conferencia ACM sobre comercio electrónico . CE '08. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 70–77. doi :10.1145/1386790.1386805. ISBN 978-1-60558-169-9. S2CID  556774.
12. Pescador, 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: dedicada a la memoria de DR Fulkerson , Berlín, Heidelberg: Springer, págs. 73–87, doi :10.1007/bfb0121195 , ISBN 978-3-642-00790-3, recuperado 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 algoritmo discreto - SODA '06 . Refresco '06. Estados Unidos: Sociedad de Matemáticas Industriales y Aplicadas. págs. 1064-1073. doi :10.1145/1109557.1109675. ISBN 978-0-89871-605-4. S2CID  13108913.
14. Vondrak, enero (17 de mayo de 2008). "Aproximación óptima al problema de bienestar submodular en el modelo de oráculo de valor". Actas del cuadragésimo simposio anual de ACM sobre teoría de la informática . STOC '08. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. 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, enero (9 de diciembre de 2010). "El problema del bienestar submodular con las consultas de demanda". Teoría de la Computación . 6 : 247–290. doi : 10.4086/toc.2010.v006a011 .
17. Feige, Uriel (21 de mayo de 2006). "Sobre maximizar el bienestar cuando las funciones de utilidad son subaditivas". Actas del trigésimo octavo simposio anual de ACM sobre Teoría de la Computación . STOC '06. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 41–50. doi :10.1145/1132516.1132523. ISBN 978-1-59593-134-4. S2CID  11504912.
18. Hazán, Elad; Safra, Shmuel; Schwartz, Oded (2006). "Sobre la complejidad de aproximar el embalaje de k -set". Complejidad computacional . 15 (1): 20–39. CiteSeerX 10.1.1.352.5754 . doi :10.1007/s00037-006-0205-6. SEÑOR  2226068. S2CID  1858087. . Véase en particular la pág. 21: "La camarilla máxima (y por lo tanto también el conjunto máximo independiente y el empaquetamiento máximo del conjunto) no pueden aproximarse 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 . XXV Coloquio Internacional sobre Autómatas, Lenguajes y Programación. Apuntes de conferencias sobre informática. vol. 1443. Springer-Verlag. págs. 176–185.
20. Lehmann, Daniel; Ocallaghan, 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 generalizaciones y subastas combinatorias". Actas de la Decimoséptima Conferencia Nacional sobre Inteligencia Artificial y la Duodécima Conferencia sobre Aplicaciones Innovadoras de la Inteligencia Artificial . Prensa AAAI: 90–97. ISBN 978-0-262-51112-4.