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

$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})$ .

Monotonicity

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

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

and

v'_{i}\geq v_{i}>0

then:

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

I.e, if agent $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 $i$ and for every vector $v_{-i}$ , there is a critical value $c_{i}(v_{-i})$ , such that agent $i$ wins if-and-only-if his bid is at least $c_{i}(v_{-i})$ .

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

Deterministic implementation

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

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

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

Hence, the agent prefers to win if $v_{i}>c_{-i}$ and to lose if $v_{i}<c_{-i}$ , 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 $i$ has a probability of winning, defined as:

w_{i}(v_{i},v_{-i}):=\Pr[Outcome(v_{i},v_{-i})\in W_{i}]

and an expected payment, defined as:

E[p_{i}(v_{i},v_{-i})]

In a single-parameter domain, a randomized mechanism is truthful-in-expectation if-and-only if:^[1]^: 232

The probability of winning, $w_{i}(v_{i},v_{-i})$ , is a weakly-increasing function of $v_{i}$ ;
The expected payment of an agent is:

E[p_{i}(v_{i},v_{-i})]=v_{i}\cdot w_{i}(v_{i},v_{-i})-\int _{0}^{v_{i}}w_{i}(t,v_{-i})dt

Note that in a deterministic mechanism, $w_{i}(v_{i},v_{-i})$ 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.

References

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

[agt07-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.

[1]