Content deleted Content added
Erel Segal (talk | contribs) ←Created page with '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,...' |
Erel Segal (talk | contribs) No edit summary |
||
Line 8:
For every agent <math>i</math>, there is a publicly-known subset <math>W_i \subset X</math> which are the "winning outcomes" for agent <math>i</math> (e.g, in a single-item auction, <math>W_i</math> contains the outcome in which agent <math>i</math> wins the item).
For every agent, there is a number <math>v_i</math> which represents the "winning-value" of <math>i</math>. The agent's valuation of the outcomes in <math>X</math> can take one of two values:<ref name=agt07>{{Cite Algorithmic Game Theory 2007}}</ref>{{rp|228
* <math>v_i</math> for each outcome in <math>W_i</math>;
* 0 for each outcome in <math>X\setminus W_i</math>.
Line 18:
A [[social choice]] function is a function that takes as input the value-vector <math>v</math> and returns an outcome <math>x\in X</math>. It is denoted by <math>Outcome(v)</math> or <math>Outcome(v_i,v_{-i})</math>.
== Monotonicity ==
The [[Monotonicity (mechanism design)#wmon|'''weak monotonicity''' property]] has a special form in single-parameter domains. A social choice function is weakly-monotonic if for every agent <math>i</math> and every <math>v_i,v_i',v_{-i}</math>, if:
: <math>Outcome(v_i, v_{-i}) \in W_i</math> and
: <math>v'_i \geq v_i > 0</math> then:
: <math>Outcome(v'_i, v_{-i}) \in W_i</math>
I.e, if agent <math>i</math> 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 <math>i</math> and for every vector <math>v_{-i}</math>, there is a '''critical value''' <math>c_i(v_{-i})</math>, such that agent <math>i</math> wins if-and-only-if his bid is at least <math>c_i(v_{-i})</math>.
For example, in a [[second-price auction]], the critical value for agent <math>i</math> is the highest bid among the other agents.
== 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 [[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}}
* Ask the agents to reveal their valuations, <math>v</math>.
* Select the outcome based on the social-choice function: <math>x = Outcome[v]</math>.
* Every winning agent (every agent <math>i</math> such that <math>x in W_i</math>) pays the critical value <math>c_i(v_{-i})</math>.
* Every losing agent pays 0.
This mechanism is truthful, because the net utility of each agent is:
* <math>v_i - c_i(v_{-i})</math> if he wins;
* 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.
== See also ==
| |||