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:

Applications

Some examples of algorithms using demand oracles are:

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