Single-parameter utility

In mechanism design a single-parameter mechanism is a mechanism in which the preferences of each agent are represented by a single number. For example, an auction for a single item is single-parameter, since the preferences of each agent are represented by his evaluation of the item. In contrast, a combinatorial auction for two or more related items is not single-parameter, since the preferences of each agent are represented by his evaluation to all possible bundles of items.

Notation

There is a set ${\displaystyle X}$  of possible outcomes.

There are ${\displaystyle n}$  agents which have different valuations for each outcome.

For every agent ${\displaystyle i}$ , there is a publicly-known subset ${\displaystyle W_{i}\subset X}$  which are the "winning outcomes" for agent ${\displaystyle i}$  (e.g, in a single-item auction, ${\displaystyle W_{i}}$  contains the outcome in which agent ${\displaystyle i}$  wins the item).

For every agent, there is a number ${\displaystyle v_{i}}$  which represents the "winning-value" of ${\displaystyle i}$ . The agent's valuation of the outcomes in ${\displaystyle X}$  can take one of two values:^[1]: 228

• ${\displaystyle v_{i}}$  for each outcome in ${\displaystyle W_{i}}$ ;
• 0 for each outcome in ${\displaystyle X\setminus W_{i}}$ .

This is a very special case of the the general case (handled e.g. by VCG mechanisms) in which each agent can assign a different value to every outcome in ${\displaystyle X}$ .

The vector of the winning-values of all agents is denoted by ${\displaystyle v}$ .

For every agent ${\displaystyle i}$ , the vector of all winning-values of the other agents is denoted by ${\displaystyle v_{-i}}$ . So ${\displaystyle v\equiv (v_{i},v_{-i})}$ .

A social choice function is a function that takes as input the value-vector ${\displaystyle v}$  and returns an outcome ${\displaystyle x\in X}$ . It is denoted by ${\displaystyle Outcome(v)}$  or ${\displaystyle Outcome(v_{i},v_{-i})}$ .

Monotonicity

The weak monotonicity property has a special form in single-parameter domains. A social choice function is weakly-monotonic if for every agent ${\displaystyle i}$  and every ${\displaystyle v_{i},v_{i}',v_{-i}}$ , if:

${\displaystyle Outcome(v_{i},v_{-i})\in W_{i}}$  and

${\displaystyle v'_{i}\geq v_{i}>0}$  then:

${\displaystyle Outcome(v'_{i},v_{-i})\in W_{i}}$ 

I.e, if agent ${\displaystyle i}$  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).

Critical value

For every social-choice function, for every agent ${\displaystyle i}$  and for every vector ${\displaystyle v_{-i}}$ , there is a critical value ${\displaystyle c_{i}(v_{-i})}$ , such that agent ${\displaystyle i}$  wins if-and-only-if his bid is at least ${\displaystyle c_{i}(v_{-i})}$ .

For example, in a second-price auction, the critical value for agent ${\displaystyle i}$  is the highest bid among the other agents.

Implementability

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 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, ${\displaystyle v}$ .
• Select the outcome based on the social-choice function: ${\displaystyle x=Outcome[v]}$ .
• Every winning agent (every agent ${\displaystyle i}$  such that ${\displaystyle xinW_{i}}$ ) pays the critical value ${\displaystyle c_{i}(v_{-i})}$ .
• Every losing agent pays 0.

This mechanism is truthful, because the net utility of each agent is:

• ${\displaystyle v_{i}-c_{i}(v_{-i})}$  if he wins;
• 0 if he loses.

Hence, the agent prefers to win if ${\displaystyle v_{i}>c_{-i}}$  and to lose if ${\displaystyle v_{i}<c_{-i}}$ , which is exactly what happens when he tells the truth.

See also

• Single peaked preferences

References

1. Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.