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.
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
can take one of two values:[1]: 228 The vector of the winning-values of all agents is denoted by
, the vector of all winning-values of the other agents is denoted by
The weak monotonicity property has a special form in single-parameter domains.
A social choice function is weakly-monotonic if for every agent
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
For every weakly-monotone social-choice function, for every 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
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 This mechanism is truthful, because the net utility of each agent is: Hence, the agent prefers to win if
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 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.
When the utilities are not single-parametric (e.g. in combinatorial auctions), the mechanism design problem is much more complicated.