Single-parameter utility explained

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

X of possible outcomes.

There are

n agents which have different valuations for each outcome.

In general, each agent can assign a different and unrelated value to every outcome in

X .

In the special case of single-parameter utility, each agent

i has a publicly known outcome proper 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:v _{i} for each outcome in W _{i} ;

• 0 for each outcome in

X\setminus W _{i} .

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} andv' _{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).

The monotonicity property can be generalized to randomized mechanisms, which return a probability-distribution over the space

X . The WMON property implies that for every agent i and every v _{i,v} _{i',v} _{-i} , the function:\Pr[ Outcome (v _{i,} v _{-i} ) \in W _{i]} is a weakly-increasing function of v _{i} .

Critical value

For every weakly-monotone 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.

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

i wins if and only if his bid is at least c _{i(v} _{-i} ) , and in that case, he pays exactly c _{i(v} _{-i} ) .

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:

• 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 x \in W _{i} ) pays a price equal to the critical value: Price _{i(x,} v _{-i} ) = - c _{i(v} _{-i} ) .

• Every losing agent (every agent

i such that x \notin W _{i} ) pays nothing: Price _{i(x,} v _{-i} ) = 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 [ Payment _{i(v} _{i,v} _{-i} )]

In a single-parameter domain, a randomized mechanism is truthful-in-expectation if-and-only if:

• 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 [ Payment _{i(v} _{i,v} _{-i} )] = v _{i ⋅} w _{i(v} _{i,v} _{-i} ) - \int ^{v _{i}} _{0} 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.

Single-parameter vs. multi-parameter domains

When the utilities are not single-parametric (e.g. in combinatorial auctions), the mechanism design problem is much more complicated. The VCG mechanism is one of the only mechanisms that works for such general valuations.

See also

• Single peaked preferences