Oráculo de la demanda

En la teoría algorítmica de juegos , una rama tanto de la informática como de la economía , un oráculo de la demanda es una función que, dado un vector de precios, devuelve la demanda de un agente. Es utilizado por muchos algoritmos relacionados con la fijación de precios y la optimización en el mercado en línea . Se suele contrastar con un oráculo de valores , que es una función que, dado un conjunto de elementos, devuelve el valor que les asignó un agente.

Demanda

La demanda de un agente es el conjunto de artículos que más prefiere, dados algunos precios fijos de los artículos. Como ejemplo, consideremos un mercado con tres objetos y un agente, con los siguientes valores y precios.

Supongamos que la función de utilidad del agente es aditiva (= el valor de un paquete es la suma de los valores de los artículos en el paquete) y cuasilineal (= la utilidad de un paquete es el valor del paquete menos su precio). Entonces, la demanda del agente, dados los precios, es el conjunto {Banana, Cherry}, que da una utilidad de (4+6)-(3+1) = 6. Cualquier otro conjunto le da al agente una utilidad menor. Por ejemplo, el conjunto vacío da utilidad 0, mientras que el conjunto de todos los elementos da utilidad (2+4+6)-(5+3+1)=3.

Oráculo

Con valoraciones aditivas, la función de demanda es fácil de calcular: no hay necesidad de un "oráculo". Sin embargo, en general, los agentes pueden tener valoraciones combinatorias . Esto significa que, para cada combinación de elementos, pueden tener un valor diferente, que no es necesariamente una suma de sus valores para los elementos individuales. Describir una función de este tipo en m elementos puede requerir hasta 2 ^m números: un número para cada subconjunto. Esto puede resultar inviable cuando m es grande. Por tanto, muchos algoritmos para mercados utilizan dos tipos de oráculos:

• Un oráculo de valores puede responder consultas de valores : dado un paquete, devuelve su valor.
• Un oráculo de la demanda puede responder consultas de demanda : dado un vector de precios, devuelve un paquete que maximiza la utilidad cuasilineal (valor menos precio).

Aplicaciones

Algunos ejemplos de algoritmos que utilizan oráculos de demanda son:

• Maximización del bienestar : hay n agentes ym elementos. Cada agente está representado por un oráculo de valor y un oráculo de demanda. Se requiere asignar los elementos entre los agentes de manera que se maximice la suma de valores. En general, el problema es NP-difícil, pero se conocen aproximaciones para casos especiales, como valoraciones submodulares (esto se denomina "problema de bienestar submodular"). Algunos algoritmos utilizan sólo un oráculo de valores; ^[1] Otros algoritmos también utilizan un oráculo de demanda . ^{[2] [3]}
• Precios sin envidia : hay n agentes y m artículos. Cada agente está representado por un oráculo de valor y un oráculo de demanda. Es necesario encontrar un vector de precios y una asignación de los artículos, de modo que ningún agente sienta envidia y, sujeto a ello, se maximicen los ingresos del vendedor.
• Cálculo del equilibrio del mercado . ^[4]
• Aprendizaje de la demanda de sustitutos fuertes . ^[5]

Ver también

• máquina oráculo
• Curva de demanda
• Modelo de consulta de Robertson-Webb : un modelo de consulta similar en el ámbito del corte de pasteles.

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. Victoria, Columbia Británica, Canadá: 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. 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. Miami, Florida: Sociedad de Matemáticas Industriales y Aplicadas. págs. 1064-1073. doi :10.1145/1109557.1109675. ISBN 978-0-89871-605-4. S2CID  13108913.
3. 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 (1): 247–290. doi : 10.4086/toc.2010.v006a011 . ISSN  1557-2862.
4. Codenotti, Bruno; McCune, Benton; Varadarajan, Kasturi (22 de mayo de 2005). "Equilibrio del mercado a través de la función de exceso de demanda". Actas del trigésimo séptimo simposio anual de ACM sobre teoría de la informática . STOC '05. Baltimore, MD, EE.UU.: Asociación de Maquinaria de Computación. págs. 74–83. doi :10.1145/1060590.1060601. ISBN 978-1-58113-960-0. S2CID  15453505.
5. Goldberg, Paul W.; Bloquear, Edwin; Marmolejo-Cossío, Francisco (2020). Chen, Xujin; Gravin, Nikolai; Hoefer, Martín; Mehta, Ruta (eds.). "Aprender una fuerte demanda de sustitutos a través de consultas". Economía de la Web y de Internet . Apuntes de conferencias sobre informática. 12495 . Cham: Springer International Publishing: 401–415. arXiv : 2005.01496 . doi :10.1007/978-3-030-64946-3_28. ISBN 978-3-030-64946-3. S2CID  218487768.