Oráculo de demanda

En la teoría de juegos algorítmica , una rama tanto de la informática como de la economía , un oráculo de demanda es una función que, dado un vector de precios, devuelve la demanda de un agente. Se utiliza en muchos algoritmos relacionados con la fijación de precios y la optimización en el mercado online . Generalmente se contrapone a un oráculo de valor , que es una función que, dado un conjunto de artículos, devuelve el valor que un agente les ha asignado.

La demanda de un agente es la cesta de artículos que prefiere, dados unos precios fijos para dichos 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 una cesta es la suma de los valores de los artículos que la componen) y cuasilineal (la utilidad de una cesta es el valor de la cesta menos su precio). Entonces, la demanda del agente, dados los precios, es el conjunto {Plátano, Cereza}, que proporciona una utilidad de (4+6)-(3+1) = 6. Cualquier otro conjunto proporciona al agente una utilidad menor. Por ejemplo, el conjunto vacío proporciona una utilidad de 0, mientras que el conjunto de todos los artículos proporciona una utilidad de (2+4+6)-(5+3+1)=3.

Con valoraciones aditivas, la función de demanda es fácil de calcular; no se necesita un "oráculo". Sin embargo, en general, los agentes pueden tener valoraciones combinatorias . Esto significa que, para cada combinación de artículos, pueden tener un valor diferente, que no es necesariamente la suma de sus valores para los artículos individuales. Describir dicha función en m artículos podría requerir hasta 2m ^números , un número para cada subconjunto. Esto puede ser inviable cuando m es grande. Por lo tanto, muchos algoritmos para mercados utilizan dos tipos de oráculos:

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

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

• Maximización del bienestar : hay n agentes y m artículos. Cada agente está representado por un oráculo de valor y un oráculo de demanda. Se requiere asignar los artículos entre los agentes de manera que se maximice la suma de los valores. En general, el problema es NP-difícil, pero se conocen aproximaciones para casos especiales, como las valoraciones submodulares (esto se denomina el "problema de bienestar submodular"). Algunos algoritmos utilizan solo un oráculo de valor; ^{[ 1 ]} otros algoritmos también utilizan un oráculo de demanda . ^{[ 2 ] [ 3 ]}
• Fijación de 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. Se requiere encontrar un vector de precios y una asignación de los artículos que evite la envidia entre los agentes, maximizando así los ingresos del vendedor.
• Cálculo del equilibrio de mercado . ^{[ 4 ]}
• El aprendizaje de sustitutos fuertes exige . ^{[ 5 ]}

• 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.