Demand oracle explained

In algorithmic game theory, a branch of both computer science and economics, a demand oracle is a function that, given a price-vector, returns the demand of an agent. It is used by many algorithms related to pricing and optimization in online market. It is usually contrasted with a value oracle, which is a function that, given a set of items, returns the value assigned to them by an agent.

Demand

The demand of an agent is the bundle of items that the agent most prefers, given some fixed prices of the items. As an example, consider a market with three objects and one agent, with the following values and prices.

	Value	Price
Apple	2	5
Banana	4	3
Cherry	6	1

Suppose the agent's utility function is additive (= the value of a bundle is the sum of values of the items in the bundle), and quasilinear (= the utility of a bundle is the value of the bundle minus its price). Then, the demand of the agent, given the prices, is the set, which gives a utility of (4+6)-(3+1) = 6. Every other set gives the agent a smaller utility. For example, the empty set gives utility 0, while the set of all items gives utility (2+4+6)-(5+3+1)=3.

Oracle

With additive valuations, the demand function is easy to compute - there is no need for an "oracle". However, in general, agents may have combinatorial valuations. This means that, for each combination of items, they may have a different value, which is not necessarily a sum of their values for the individual items. Describing such a function on m items might require up to 2^m numbers - a number for each subset. This may be infeasible when m is large. Therefore, many algorithms for markets use two kinds of oracles:

• A value oracle can answer value queries: given a bundle, it returns its value.
• A demand oracle can answer demand queries: given a price-vector, it returns a bundle that maximizes the quasilinear utility (value minus price).

Applications

Some examples of algorithms using demand oracles are:

• Welfare maximization: there are n agents and m items. Each agent is represented by a value-oracle and a demand-oracle. It is required to allocate the items among the agents such that the sum of values is maximized. In general the problem is NP-hard, but approximations are known for special cases, such as submodular valuations (this is called the "submodular welfare problem"). Some algorithms use only a value oracle;^[1] other algorithms use also a demand oracle.^{[2] [3]}
• Envy-free pricing

there are n agents and m items. Each agent is represented by a value-oracle and a demand-oracle. It is required to find a price-vector and an allocation of the items, such that no agent is envious, and subject to that, the seller's revenue is maximized.

• Market equilibrium computation.^[4]
• Learning strong-substitutes demand.^[5]

See also

• Oracle machine
• Demand curve
• Robertson-Webb query model - a similar query model in the domain of cake-cutting.

Notes and References

1. Book: Vondrak, Jan. Proceedings of the fortieth annual ACM symposium on Theory of computing . Optimal approximation for the submodular welfare problem in the value oracle model . 2008-05-17. https://doi.org/10.1145/1374376.1374389. STOC '08. Victoria, British Columbia, Canada. Association for Computing Machinery. 67–74. 10.1145/1374376.1374389. 978-1-60558-047-0. 170510 .
2. Book: Dobzinski. Shahar. Schapira. Michael. Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 . An improved approximation algorithm for combinatorial auctions with submodular bidders . 2006-01-22. https://dl.acm.org/doi/abs/10.5555/1109557.1109675. SODA '06. Miami, Florida. Society for Industrial and Applied Mathematics. 1064–1073. 10.1145/1109557.1109675. 978-0-89871-605-4. 13108913 .
3. Feige. Uriel. Vondrák. Jan. 2010-12-09. The Submodular Welfare Problem with Demand Queries. Theory of Computing. EN. 6. 1. 247–290. 10.4086/toc.2010.v006a011. 1557-2862. free.
4. Book: Codenotti. Bruno. McCune. Benton. Varadarajan. Kasturi. Proceedings of the thirty-seventh annual ACM symposium on Theory of computing . Market equilibrium via the excess demand function . 2005-05-22. https://doi.org/10.1145/1060590.1060601. STOC '05. Baltimore, MD, USA. Association for Computing Machinery. 74–83. 10.1145/1060590.1060601. 978-1-58113-960-0. 15453505 .
5. Goldberg. Paul W.. Lock. Edwin. Marmolejo-Cossío. Francisco. 2020. Chen. Xujin. Gravin. Nikolai. Hoefer. Martin. Mehta. Ruta. Learning Strong Substitutes Demand via Queries. Web and Internet Economics. Lecture Notes in Computer Science. 12495 . en. Cham. Springer International Publishing. 401–415. 10.1007/978-3-030-64946-3_28. 978-3-030-64946-3. 2005.01496. 218487768 .