Hispanopedia Wiki
Articulo de referencia

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 repartir un conjunto de artículos entre agentes con...

Hispanopedia WikiContenido en espanolLectura gratuita

El problema de maximización del bienestar es un problema de optimización estudiado en economía e informática . Su objetivo es repartir un conjunto de artículos entre agentes con diferentes funciones de utilidad , de manera 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 manera que la suma de las ofertas ganadoras sea máxima.

Definiciones

Existe un conjunto M de m elementos y un conjunto N de n agentes. Cada agente i en N tiene una función de utilidad.túi:2METRO→R{\displaystyle u_{i}:2^{M}\to \mathbb {R} }. La función asigna un valor real a cada subconjunto posible de elementos. Por lo general, se asume que las funciones de utilidad son funciones de conjunto monótonas , es decir,Z1⊇Z2{\displaystyle Z_{1}\supseteq Z_{2}}implicatúi(Z1)≥túi(Z2){\ Displaystyle u_ {i} (Z_ {1}) \ geq u_ {i} (Z_ {2})}También se supone quetúi(∅)=0{\displaystyle u_{i}(\emptyset )=0}Junto con la monotonicidad, esto implica que todas las utilidades son no negativas.

Una asignación es una partición ordenada de los elementos en n subconjuntos disjuntos, un subconjunto por agente, denotadoincógnita=(incógnita1,…,incógnitanorte){\displaystyle \mathbf {X} =(X_{1},\ldots ,X_{n})}, de tal manera queMETRO=incógnita1⊔⋯⊔incógnitanorte{\displaystyle M=X_{1}\sqcup \cdots \sqcup X_{n}}El bienestar de una asignación es la suma de las utilidades de los agentes:W(incógnita):=∑i∈nortetúi(incógnitai){\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 dichas funciones y si existen restricciones adicionales en las asignaciones permitidas.

Agentes aditivos

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

Restricciones de equidad

Se puede buscar maximizar el bienestar entre todas las asignaciones que sean justas , por ejemplo, sin 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-difícil, [ 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 totalmente polinomial . [ 4 ]

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

Restricciones de matroid

Otra restricción en 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 número entero fijo (esto corresponde a un matroide uniforme ). O bien, los elementos pueden estar divididos 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 proporcionar a cada agente i un subconjunto X i 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 gruesos

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 puede realizarse en tiempo polinomial. Esto se debe a que, con agentes de sustitución bruta, siempre existe un equilibrio walrasiano que maximiza la suma de las utilidades. [ 8 ] Un equilibrio walrasiano puede hallarse 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 de sustitución bruta.

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 oráculo de valores , independientemente de si P=NP. [ 11 ]

Algoritmo voraz

El bienestar máximo puede aproximarse mediante el siguiente algoritmo voraz de tiempo polinomial :

  • Inicializar X 1 = X 2 = ... = X n = vacío.
  • Para cada elemento g (en un orden arbitrario):
    • Calcula, 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 al agente con la mayor utilidad marginal.

Lehman, Lehman y Nisan [ 9 ] demuestran que el algoritmo voraz encuentra una aproximación de factor 1/2 (señalan que este resultado se deriva 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 demostración es la siguiente. Supongamos que el algoritmo asigna un elemento g a algún agente i . Esto contribuye al bienestar una cantidad v , que es la utilidad marginal de g para i en ese punto. Supongamos que, en la solución óptima, g debería darse 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 v por la selección codiciosa.
  • La utilidad marginal del conjunto restante de i aumenta como máximo en v . Esto se deduce de la submodularidad: la utilidad marginal de g , cuando se añade al conjunto restante, no puede ser superior a su utilidad marginal cuando el algoritmo la procesó.

Así pues, por cada contribución de v al bienestar del algoritmo, la contribución potencial al bienestar óptimo podría ser como máximo 2v . 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 cuyas valoraciones son:

La asignación óptima es Alice: {y}, George: {x}, con un bienestar de 2. Pero si el algoritmo voraz asigna x primero, podría asignárselo a Alice. Entonces, independientemente de cómo se asigne y, el bienestar será solo de 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 dicho conjunto. En este modelo:

  • Dobzinski y Schapira [ 13 ] presentan un politiemponorte/(2norte−1){\displaystyle n/(2n-1)}-algoritmo de aproximación, 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.
  • 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-voraz, un algoritmo que extiende un paquete fraccional (un paquete que contiene una fracción p j de cada elemento j ) en una dirección voraz (similar al descenso de gradiente ). Su algoritmo necesita calcular el valor de los paquetes fraccionales, definido como el valor esperado del paquete alcanzado cuando cada elemento j se selecciona independientemente con probabilidad p j . En general, calcular el valor de un paquete fraccional podría 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 haces fraccionarios se pueden evaluar de manera eficiente (por ejemplo, cuando las funciones de utilidad son funciones de cobertura de conjuntos), el algoritmo puede hacerse determinista. [ 15 ] : Sec.5 Para funciones submodulares monótonas generales, Buchbinder y Feldman [ 16 ] describieron un algoritmo diferente basado en búsqueda local que es determinista y garantiza(1−1/mi−ϵ){\displaystyle (1-1/e-\epsilon )}-aproximación en tiempo polinomial para cualquier constanteϵ>0{\displaystyle \epsilon >0}.

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 de 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 de matroide de partición , asegurando que cada elemento se asigne a como máximo un agente.

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 [ 17 ] mejoran esto a (1-1/e+ε) para algún ε positivo pequeño (esto no contradice el resultado de dificultad anterior, ya que el resultado de dificultad utiliza solo un oráculo de valor; en los ejemplos de dificultad, el oráculo de demanda en sí requeriría exponencialmente muchas consultas) .

Agentes subaditivos

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

Feige [ 18 ] presenta un método para redondear cualquier solución fraccionaria de una relajación LP de este problema a una solución factible con un bienestar al menos igual a la mitad del valor de la solución fraccionaria. Esto proporciona una aproximación de 1/2 para agentes subaditivos generales y una aproximación de (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),(registro⁡metro)1+ϵmetro{\displaystyle {\frac {(\log m)^{1+\epsilon }}{m}}}La aproximación requeriría un número superpolinomial de consultas de valor. [ 11 ]

Agentes decididos

Un agente con una sola idea solo desea un conjunto específico de elementos. Para cada agente con una sola idea i , existe un conjunto demandado D i y un valor V i > 0, tal quetúi(Z)={ViZ⊇Di0de lo contrario{\displaystyle u_{i}(Z)={\begin{cases}V_{i}&Z\supseteq D_{i}\\0&{\text{otherwise}}\end{cases}}}. Es decir, el agente recibe una utilidad positiva fija si y solo si su cesta contiene el conjunto demandado.

La maximización del bienestar con agentes de mente única es NP-difícil incluso cuandoVi=1{\displaystyle V_{i}=1}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 (a diferencia del caso de los agentes submodulares). [ 19 ] El mejor algoritmo conocido lo aproxima dentro de un factor deO(metro){\displaystyle O({\sqrt {m}})}. [ 20 ]

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 deO(norte1/2−ϵ){\displaystyle O(n^{1/2-\epsilon })}para cualquierϵ>0{\displaystyle \epsilon >0}. [ 21 ] Sin embargo, existen algoritmos basados ​​en la búsqueda en el espacio de estados que funcionan muy bien en la práctica. [ 22 ]

Véase también

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 valor» . 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. 1 2 Aziz, Haris; Huang, Xin; Mattei, Nicholas; Segal-Halevi, Erel (2022-10-13). "Cálculo del bienestar: maximización de asignaciones justas de bienes indivisibles" . European Journal of Operational Research . 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 (2022-12-02). "Equidad y maximización del bienestar para la asignación de elementos indivisibles" . Autonomous Agents and Multi-Agent Systems . 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 (2023-01-01). "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 (2022-04-24). "Sobre la división justa bajo restricciones de matroides heterogéneas". arXiv : 2010.07280 [ cs.GT ].
  8. ↑ Kelso, AS; Crawford, VP (1982). "Job Matching, Coalition Formation, and Gross Substitutes". Econometrica . 50 (6): 1483. doi : 10.2307/1913392 . JSTOR 1913392 . 
  9. 1 2 3 Lehmann, Benny; Lehmann, Daniel; Nisan, Noam (14 de octubre de 2001). "Subastas combinatorias con utilidades marginales decrecientes" . Actas de la 3.ª conferencia 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. S2CID 2241237 . 
  10. ↑ Khot, Subhash; Lipton, Richard J.; Markakis, Evangelos; Mehta, Aranyak (2008-09-01). "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. 1 2 3 Mirrokni, Vahab; Schapira, Michael; Vondrak, Jan (2008-07-08). "Límites inferiores ajustados basados ​​en la teoría de la información para la maximización del bienestar en subastas combinatorias" . Actas de la 9.ª conferencia 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.), "An analysis of approximations for maximizing submodular set functions—II" , Polyhedral Combinatorics: Dedicated to the memory of DR Fulkerson , Berlín, Heidelberg: Springer, pp. 73–87 , doi : 10.1007/bfb0121195 , ISBN  978-3-642-00790-3, consultado el 26 de febrero de 2023{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )
  13. 1 2 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 . EE. UU.: Society for Industrial and Applied Mathematics. págs. 1064–1073 . doi : 10.1145/1109557.1109675 . ISBN  978-0-89871-605-4. S2CID 13108913 . 
  14. 1 2 Vondrak, Jan (17 de mayo de 2008). "Aproximación óptima para el problema de bienestar submodular en el modelo de oráculo de valor" . 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. 1 2 3 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. ↑ Buchbinder, Niv; Feldman, Moran (2024). Algoritmo determinista y algoritmo más rápido para la maximización submodular sujeta a una restricción de matroide . 65.º Simposio IEEE sobre Fundamentos de la Informática. IEEE. págs. 700–712 . 
  17. ↑ Feige, Uriel; Vondrák, Jan (2010-12-09). "El problema del bienestar submodular con consultas de demanda" . Theory of Computing . 6 : 247–290 . doi : 10.4086/toc.2010.v006a011 .
  18. ↑ 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. S2CID 11504912 . 
  19. ↑ Hazan, Elad; Safra, Shmuel; Schwartz, Oded (2006). "Sobre la complejidad de aproximar el empaquetamiento de k conjuntos " . Complejidad Computacional . 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 de conjuntos máximo) no se puede aproximar dentro deO(norte1−ϵ){\displaystyle O(n^{1-\epsilon })}a menos que NP ⊂ ZPP."
  20. ↑ 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. Lecture Notes in Computer Science. Vol. 1443. Springer-Verlag. pp. 176–185 .  
  21. ↑ Lehmann, Daniel; Oćallaghan, Liadan Ita; Shoham, Yoav (2002-09-01). "Revelación de la verdad en subastas combinatorias aproximadamente eficientes" . Journal of the ACM . 49 (5): 577– 602. doi : 10.1145/585265.585266 . ISSN 0004-5411 . S2CID 52829303 .  
  22. ↑ 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.
Lecturas relacionadas
6 articulos
Optimization problemIn mathematics , engineering , computer science and economics , an optimization problem is the problem of finding the best solution from all feasib...Un puerto marítimo con un barco llegandoCiencias económicasEconomía ( / ˌ ɛ k ə ˈ n ɒ m ɪ k s , ˌ iː k ə -/ ) [1] [2] es una ciencia social que estudia la producción , distribución y consumo de bienes y ser...Ciencias de la ComputaciónCiencias de la ComputaciónÁreas fundamentales de la informática La informática es el estudio de la computación , la información y la automatización . [1] [2] [3] La informát...Funciones de utilidad sobre bienes indivisiblesAlgunas ramas de la economía y la teoría de juegos se ocupan de bienes indivisibles , es decir, artículos discretos que solo pueden intercambiarse ...{\displaystyle X}regla utilitaristaEn la investigación de operaciones y elección social , la regla utilitarista (también llamada regla de suma máxima ) es una regla que dice que, ent...Auction Room, Christie's, circa 1808.Subasta combinatoriaUna subasta combinatoria es un tipo de mercado inteligente en el que los participantes pueden realizar ofertas sobre combinaciones de artículos het...