Single-parameter utility: Difference between revisions

Revision as of 14:32, 7 January 2016

Latest revision as of 21:55, 2 October 2022

(17 intermediate revisions by 6 users not shown)

Line 1:

In [[mechanism design]], aan agent is said to have '''single-parameter mechanismutility''' isif ahis mechanismvaluation in whichof the preferencespossible ofoutcomes eachcan agent arebe represented by a single number. For example, in an [[auction]] for a single item is single-parameter, since the preferencesutilities of eachall agentagents are single-parametric, since they can be represented by histheir monetary evaluation of the item. In contrast, in a [[combinatorial auction]] for two or more related items, isthe utilities are usually not single-parameterparametric, since thethey preferencesare of each agent areusually represented by histheir evaluationevaluations to all possible bundles of items.

== Notation ==

There is a set <math>X</math> of possible outcomes.

There are <math>n</math> agents which have different valuations for each outcome.

This is a very special case of the theIn general case (handled e.g. by [[VCG mechanism]]s) in which, each agent can assign a different and unrelated value to every outcome in <math>X</math>.

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

ForIn everythe agentspecial case of '''single-parameter utility''', thereeach isagent <math>i</math> has a numberpublicly known outcome [[Subset|proper subset]] <math>v_iW_i \subset X</math> which representsare the "winning-value outcomes" offor agent <math>i</math> (e.g., Thein agent'sa valuationsingle-item of the outcomes inauction, <math>XW_i</math> cancontains takethe oneoutcome ofin twowhich values:<refagent name=agt07<math>{{Cite Algorithmic Game Theory 2007}}i</refmath>{{rp|228-230}} 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>.

This is a very special case of the the general case (handled e.g. by [[VCG mechanism]]s) in which each agent can assign a different value to every outcome in <math>X</math>.

The vector of the winning-values of all agents is denoted by <math>v</math>.

Line 17 ⟶ 18:

For every agent <math>i</math>, the vector of all winning-values of the ''other'' agents is denoted by <math>v_{-i}</math>. So <math>v \equiv (v_i,v_{-i})</math>.

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>\text{Outcome}(v)</math> or <math>\text{Outcome}(v_i,v_{-i})</math>.

== Monotonicity ==

<div id="monotonicity" ></div>

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>\text{Outcome}(v_i, v_{-i}) \in W_i</math> and

: <math>v'_i \geq v_i > 0</math> then:

: <math>\text{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).

The monotonicity property can be generalized to randomized mechanisms, which return a probability-distribution over the space <math>X</math>.<ref name=agt07/>{{rp|334}} The WMON property implies that for every agent <math>i</math> and every <math>v_i,v_i',v_{-i}</math>, the function:

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

is a weakly-increasing function of <math>v_i</math>.

=== Critical value ===

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

In single-parameter environments, deterministic truthful mechanisms have a very specific format.<ref name=agt07/>{{rp|334}} Any deterministic truthful mechanism is fully specified by the set of functions c. Agent <math>i</math> wins if and only if his bid is at least <math>c_i(v_{-i})</math>, and in that case, he pays exactly <math>c_i(v_{-i})</math>.

== Deterministic implementation ==

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

* Ask the agents to reveal their valuations, <math>v</math>.

* Select the outcome based on the social-choice function: <math>x = \text{Outcome}[v]</math>.

* Every winning agent (every agent <math>i</math> such that <math>x \in W_i</math>) pays a price equal to the critical value: <math>\text{Price}_i(x, v_{-i}) = -c_i(v_{-i})</math>.

* Every losing agent (every agent <math>i</math> such that <math>x \notin W_i</math>) pays nothing: <math>\text{Price}_i(x, v_{-i}) = 0</math>.

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.

== 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[\text{Outcome}(v_i,v_{-i})\in W_i]</math>

and an expected payment, defined as:

: <math>\mathbb{E}[\text{Payment}_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>\mathbb{E}[\text{Payment}_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.

== Single-parameter vs. multi-parameter domains ==

When the utilities are not single-parametric (e.g. in [[combinatorial auction]]s), 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 ==

Line 24 ⟶ 78:

== References ==

{{reflist}}

[[Category:Mechanism design]]