Demand oracle
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
[edit]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 {Banana, Cherry}, 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
[edit]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 2m 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
[edit]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
[edit]- Oracle machine
- Demand curve
- Robertson-Webb query model - a similar query model in the domain of cake-cutting.
References
[edit]- ^ Vondrak, Jan (2008-05-17). "Optimal approximation for the submodular welfare problem in the value oracle model". Proceedings of the fortieth annual ACM symposium on Theory of computing. STOC '08. Victoria, British Columbia, Canada: Association for Computing Machinery. pp. 67–74. doi:10.1145/1374376.1374389. ISBN 978-1-60558-047-0. S2CID 170510.
- ^ Dobzinski, Shahar; Schapira, Michael (2006-01-22). "An improved approximation algorithm for combinatorial auctions with submodular bidders". Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06. SODA '06. Miami, Florida: Society for Industrial and Applied Mathematics. pp. 1064–1073. doi:10.1145/1109557.1109675. ISBN 978-0-89871-605-4. S2CID 13108913.
- ^ Feige, Uriel; Vondrák, Jan (2010-12-09). "The Submodular Welfare Problem with Demand Queries". Theory of Computing. 6 (1): 247–290. doi:10.4086/toc.2010.v006a011. ISSN 1557-2862.
- ^ Codenotti, Bruno; McCune, Benton; Varadarajan, Kasturi (2005-05-22). "Market equilibrium via the excess demand function". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. STOC '05. Baltimore, MD, USA: Association for Computing Machinery. pp. 74–83. doi:10.1145/1060590.1060601. ISBN 978-1-58113-960-0. S2CID 15453505.
- ^ Goldberg, Paul W.; Lock, Edwin; Marmolejo-Cossío, Francisco (2020). Chen, Xujin; Gravin, Nikolai; Hoefer, Martin; Mehta, Ruta (eds.). "Learning Strong Substitutes Demand via Queries". Web and Internet Economics. Lecture Notes in Computer Science. 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.