Single-parameter utility
In mechanism design, an agent is said to have single-parameter utility if his valuation of the possible outcomes can be represented by a single number. For example, in an auction for a single item, the utilities of all agents are single-parametric, since they can be represented by their monetary evaluation of the item. In contrast, in a combinatorial auction for two or more related items, the utilities are usually not single-parametric, since they are usually represented by their evaluations to all possible bundles of items.
Notation
[edit]There is a set of possible outcomes.
There are agents which have different valuations for each outcome.
In general, each agent can assign a different and unrelated value to every outcome in .
In the special case of single-parameter utility, each agent has a publicly known outcome proper subset which are the "winning outcomes" for agent (e.g., in a single-item auction, contains the outcome in which agent wins the item).
For every agent, there is a number which represents the "winning-value" of . The agent's valuation of the outcomes in can take one of two values:[1]: 228
- for each outcome in ;
- 0 for each outcome in .
The vector of the winning-values of all agents is denoted by .
For every agent , the vector of all winning-values of the other agents is denoted by . So .
A social choice function is a function that takes as input the value-vector and returns an outcome . It is denoted by or .
Monotonicity
[edit]The weak monotonicity property has a special form in single-parameter domains. A social choice function is weakly-monotonic if for every agent and every , if:
- and
- then:
I.e, if agent wins by declaring a certain value, then he can also win by declaring a higher value (when the declarations of the other agents are the same).
The monotonicity property can be generalized to randomized mechanisms, which return a probability-distribution over the space .[1]: 334 The WMON property implies that for every agent and every , the function:
is a weakly-increasing function of .
Critical value
[edit]For every weakly-monotone social-choice function, for every agent and for every vector , there is a critical value , such that agent wins if-and-only-if his bid is at least .
For example, in a second-price auction, the critical value for agent is the highest bid among the other agents.
In single-parameter environments, deterministic truthful mechanisms have a very specific format.[1]: 334 Any deterministic truthful mechanism is fully specified by the set of functions c. Agent wins if and only if his bid is at least , and in that case, he pays exactly .
Deterministic implementation
[edit]It is known that, in any domain, weak monotonicity is a necessary condition for implementability. I.e, a social-choice function can be implemented by a truthful mechanism, only if it is weakly-monotone.
In a single-parameter domain, weak monotonicity is also a sufficient condition for implementability. I.e, for every weakly-monotonic social-choice function, there is a deterministic truthful mechanism that implements it. This means that it is possible to implement various non-linear social-choice functions, e.g. maximizing the sum-of-squares of values or the min-max value.
The mechanism should work in the following way:[1]: 229
- Ask the agents to reveal their valuations, .
- Select the outcome based on the social-choice function: .
- Every winning agent (every agent such that ) pays a price equal to the critical value: .
- Every losing agent (every agent such that ) pays nothing: .
This mechanism is truthful, because the net utility of each agent is:
- if he wins;
- 0 if he loses.
Hence, the agent prefers to win if and to lose if , which is exactly what happens when he tells the truth.
Randomized implementation
[edit]A randomized mechanism is a probability-distribution on deterministic mechanisms. A randomized mechanism is called truthful-in-expectation if truth-telling gives the agent a largest expected value.
In a randomized mechanism, every agent has a probability of winning, defined as:
and an expected payment, defined as:
In a single-parameter domain, a randomized mechanism is truthful-in-expectation if-and-only if:[1]: 232
- The probability of winning, , is a weakly-increasing function of ;
- The expected payment of an agent is:
Note that in a deterministic mechanism, is either 0 or 1, the first condition reduces to weak-monotonicity of the Outcome function and the second condition reduces to charging each agent his critical value.
Single-parameter vs. multi-parameter domains
[edit]When the utilities are not single-parametric (e.g. in combinatorial auctions), the mechanism design problem is much more complicated. The VCG mechanism is one of the only mechanisms that works for such general valuations.
See also
[edit]References
[edit]- ^ a b c d e Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.