Single-parameter utility: Difference between revisions

Revision as of 14:56, 7 January 2016

Revision as of 15:29, 7 January 2016

Line 31:

For example, in a [[second-price auction]], the critical value for agent <math>i</math> is the highest bid among the other agents.

== Deterministic implementation ==

== Implementability ==

It is known that, in any ___domain, [[Monotonicity (mechanism design)#wmon|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:<ref name=agt07/>{{rp|229}}

Line 46:

* 0 if he loses.

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

: <math>w_i(v_i,v_{-i}) := \Pr[Outcome(v_i,v_{-i})\in W_i]</math>

and an expected payment, defined as:

: <math>E[p_i(v_i,v_{-i})]</math>

In a single-parameter ___domain, a randomized mechanism is truthful-in-expectation if-and-only if:<ref name=agt07/>{{rp|232}}

* The probability of winning, <math>w_i(v_i,v_{-i})</math>, is a weakly-increasing function of <math>v_i</math>;

* The expected payment of an agent is:

: <math>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</math>

Note that in a deterministic mechanism, <math>w_i(v_i,v_{-i})</math> 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.

== See also ==