algorithmic game theory Algorithmic game theory (AGT) is an interdisciplinary field at the intersection of game theory and computer science, focused on understanding and designing algorithms for environments where multiple strategic agents interact. This research area com ...

, a branch of both

computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

and

economics Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goods and services. Economics focuses on the behaviour and interac ...

, a demand oracle is a function that, given a price-vector, returns the

demand In economics, demand is the quantity of a goods, good that consumers are willing and able to purchase at various prices during a given time. In economics "demand" for a commodity is not the same thing as "desire" for it. It refers to both the desi ...

of an agent. It is used by many algorithms related to

pricing Pricing is the Business process, process whereby a business sets and displays the price at which it will sell its products and services and may be part of the business's marketing plan. In setting prices, the business will take into account the ...

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. Suppose the agent's utility function is

additive Additive may refer to: Mathematics * Additive function, a function in number theory * Additive map, a function that preserves the addition operation * Additive set-function see Sigma additivity * Additive category, a preadditive category with fin ...

(= 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; other algorithms use also a ''demand oracle''. *

Envy-free pricing Envy-free pricing is a kind of fair item allocation. There is a single seller that owns some items, and a set of buyers who are interested in these items. The buyers have different valuations to the items, and they have a quasilinear utility functi ...

: 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. *''Learning strong-substitutes demand''.

References

{{reflist Computational economics

Demand

Oracle

Applications

See also

References