# 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

There is a set $X$ of possible outcomes.
There are $n$ agents which have different valuations for each outcome.
In general, each agent can assign a different and unrelated value to every outcome in $X$.
In the special case of single-parameter utility, each agent $i$ has a publicly known outcome proper subset $W_{i}\subset X$ which are the "winning outcomes" for agent $i$ (e.g., in a single-item auction, $W_{i}$ contains the outcome in which agent $i$ wins the item).
For every agent, there is a number $v_{i}$ which represents the "winning-value" of $i$. The agent's valuation of the outcomes in $X$ can take one of two values:$^{:228}$
* $v_{i}$ for each outcome in $W_{i}$;
* 0 for each outcome in $X\setminus W_{i}$.
The vector of the winning-values of all agents is denoted by $v$.
For every agent $i$, the vector of all winning-values of the other agents is denoted by $v_{-i}$. So $v\equiv (v_{i},v_{-i})$.
A social choice function is a function that takes as input the value-vector $v$ and returns an outcome $x\in X$. It is denoted by ${\text{Outcome}}(v)$ or ${\text{Outcome}}(v_{i},v_{-i})$.

## Monotonicity

The weak monotonicity property has a special form in single-parameter domains. A social choice function is weakly-monotonic if for every agent $i$ and every $v_{i},v_{i}',v_{-i}$, if:
    ${\text{Outcome}}(v_{i},v_{-i})\in W_{i}$ and
    $v'_{i}\geq v_{i}>0$ then:
    ${\text{Outcome}}(v'_{i},v_{-i})\in W_{i}$
I.e, if agent $i$ 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 $X$.$^{:334}$ The WMON property implies that for every agent $i$ and every $v_{i},v_{i}',v_{-i}$, the function:
    $\Pr[{\text{Outcome}}(v_{i},v_{-i})\in W_{i}]$
is a weakly-increasing function of $v_{i}$.

### Critical value

For every weakly-monotone social-choice function, for every agent $i$ and for every vector $v_{-i}$, there is a critical value $c_{i}(v_{-i})$, such that agent $i$ wins if-and-only-if his bid is at least $c_{i}(v_{-i})$.
For example, in a second-price auction, the critical value for agent $i$ is the highest bid among the other agents.
In single-parameter environments, deterministic truthful mechanisms have a very specific format.$^{:334}$ Any deterministic truthful mechanism is fully specified by the set of functions c. Agent $i$ wins if and only if his bid is at least $c_{i}(v_{-i})$, and in that case, he pays exactly $c_{i}(v_{-i})$.

## Deterministic implementation

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:$^{:229}$
* Ask the agents to reveal their valuations, $v$.
* Select the outcome based on the social-choice function: $x={\text{Outcome}}[v]$.
* Every winning agent (every agent $i$ such that $x\in W_{i}$) pays a price equal to the critical value: ${\text{Price}}_{i}(x,v_{-i})=-c_{i}(v_{-i})$.
* Every losing agent (every agent $i$ such that $x\notin W_{i}$) pays nothing: ${\text{Price}}_{i}(x,v_{-i})=0$.
This mechanism is truthful, because the net utility of each agent is:
* $v_{i}-c_{i}(v_{-i})$ if he wins;
* 0 if he loses.
Hence, the agent prefers to win if $v_{i}>c_{-i}$ and to lose if $v_{i}<c_{-i}$, 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 $i$ has a probability of winning, defined as:
    $w_{i}(v_{i},v_{-i}):=\Pr[{\text{Outcome}}(v_{i},v_{-i})\in W_{i}]$
and an expected payment, defined as:
    $\mathbb {E} [{\text{Payment}}_{i}(v_{i},v_{-i})]$
In a single-parameter domain, a randomized mechanism is truthful-in-expectation if-and-only if:$^{:232}$
* The probability of winning, $w_{i}(v_{i},v_{-i})$, is a weakly-increasing function of $v_{i}$;
* The expected payment of an agent is:
    $\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$
Note that in a deterministic mechanism, $w_{i}(v_{i},v_{-i})$ 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 auctions), the mechanism design problem is much more complicated. The VCG mechanism is one of the only mechanisms that works for such general valuations.