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 $X$ of possible outcomes.

There are $n$ agents which have different valuations for each outcome.

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

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

$v_{i}$ for each outcome in $W_{i}$ ;
0 for each outcome in $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 $X$ .

The vector of the winning-values of all agents is denoted by $v$ .

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

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