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

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

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

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

References
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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. Cham: Springer International Publishing. 12495: 401–415. arXiv:2005.01496. doi:10.1007/978-3-030-64946-3_28. ISBN 978-3-030-64946-3. S2CID 218487768.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.