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
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 subset which are the "winning outcomes" for agent . 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:
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
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: I.e, if agent wins by declaring a certain value, then he can also win by declaring a higher value. The monotonicity property can be generalized to randomized mechanisms, which return a probability-distribution over the space. The WMON property implies that for every agent and every, the function: is a weakly-increasing function of.
Critical value
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. 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
It is known that, in any domain, weak monotonicity is a necessarycondition 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:
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
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:
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
When the utilities are not single-parametric, the mechanism design problem is much more complicated. The VCG mechanism is one of the only mechanisms that works for such general valuations.
