Single-parameter utility

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

edit

There is a set   of possible outcomes.

There are   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   which are the "winning outcomes" for agent   (e.g., in a single-item auction,   contains the outcome in which agent   wins the item).

For every agent, there is a number   which represents the "winning-value" of  . The agent's valuation of the outcomes in   can take one of two values:[1]: 228 

  •   for each outcome in  ;
  • 0 for each outcome in  .

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

For every agent  , the vector of all winning-values of the other agents is denoted by  . So  .

A social choice function is a function that takes as input the value-vector   and returns an outcome  . It is denoted by   or  .

Monotonicity

edit

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

  and
  then:
 

I.e, if agent   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  .[1]: 334  The WMON property implies that for every agent   and every  , the function:

 

is a weakly-increasing function of  .

Critical value

edit

For every weakly-monotone social-choice function, for every agent   and for every vector  , there is a critical value  , such that 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   wins if and only if his bid is at least  , and in that case, he pays exactly  .

Deterministic implementation

edit

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,  .
  • Select the outcome based on the social-choice function:  .
  • Every winning agent (every agent   such that  ) pays a price equal to the critical value:  .
  • Every losing agent (every agent   such that  ) pays nothing:  .

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

  •   if he wins;
  • 0 if he loses.

Hence, the agent prefers to win if   and to lose if  , which is exactly what happens when he tells the truth.

Randomized implementation

edit

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   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 

  • The probability of winning,  , is a weakly-increasing function of  ;
  • The expected payment of an agent is:
 

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.

Single-parameter vs. multi-parameter domains

edit

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

edit

References

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