Single-parameter utility: Difference between revisions

Revision as of 15:15, 30 June 2016

Latest revision as of 21:55, 2 October 2022

(4 intermediate revisions by 4 users not shown)

Line 8:

In general, each agent can assign a different and unrelated value to every outcome in <math>X</math>.

In the special case of '''single-parameter utility''', each agent <math>i</math> has a publicly- known outcome [[Subset|proper 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}}

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

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

Line 46:

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>Price_i\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>Price_i\text{Price}_i(x, v_{-i}) = 0</math>.

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

Line 59:

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}[Payment_i\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}[Payment_i\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.