Chapter 5: Mechanism design and Social choices

Mechanism design basics

In mechanism design, a Vickrey–Clarke–Groves (VCG) mechanism is a generic truthful mechanism for achieving a socially-optimal solution. It is a generalization of a Vickrey–Clarke–Groves auction. A VCG auction performs a specific task: dividing items among people. A VCG mechanism is more general: it can be used to select any outcome out of a set of possible outcomes.

In a game rules are given and we have to find an equilibrium. The inverse problem is to design the rules of the game so that the equilibrium have good properties.

The main issue is to create incentives to make convenient for the player to tell the truth, in order to achieve a socially efficient outcome. This means that VCG mechanism (Vickrey-Clarke-Groves mechanisms) are truthful and efficient.

Note about agent utility

If in a VCG mechanism all valuations are non negative, then no agent will have negative utility.

Example: second-price auction

In a auction the set of actions $A=\{1, ..., n\}$ corresponds to the possible assignments of the objects to the different players. The valuation of player $i$ is, given his valuation $w_i$:

$$v_{i}(a)=\left\{\begin{array}{cl} w_{i} & \text { if } a=i \\ 0 & \text { if not } \end{array}\right.$$

Which means that a player which partecipates to the auction will either get what he values the object in the case he wins the auction, or zero otherwise.

A second-price auction works in a sligtly different manner: each player bids an offer $\tilde{w}_{i}$, and the item is assigned to the maximum bidder. The winner pays the second highest bid, and the loser pay nothing with zero utility. For example, if we have 4 bidders with valuations $w_{1}=100, w_{2}=80, w_{3}=75, w_{4}=50$, the object is assigned to bidder 1 and he will pay 80.

Note that the second price auction is what we get if we apply the VCG mechanism to single item auctions.

Social choice

The main ingredients of the theory of Social Choice are:

• A set $A$, the set of the alternatives

• A set $N$, the set of the agents

• Preferences $\succcurlyeq_{i}$ of every agent $i \in N$ over the set $A$ of the alternatives

Given these data, the goal of the theory is to study rules that, to any $\left(A, N, \succcurlyeq_{i}\right)$ associate either an alternative of $A$ (the selected one) or a ranking over the alternatives of $A$. Example of social choice are elections, ranking athletes in some Olympic sports, like skating, etc. Preference profile: $\succcurlyeq=\left(\succcurlyeq_{1}, \ldots, \succcurlyeq_{n}\right)$ is called a preference profile. with symbols $\succ,>, \supset \ldots$ Thus $x \succeq y$ means that $x$ is either indifferent or preferred to $y$, while $x \succ y$ means that $x$ is (strictly) preferred to $y$.

Voting example

Preference list:

# voters	1st preference	2nd preference	3rd preference
6 voters	C	B	A
1 voter	A	B	C
7 voters	A	C	B
7 voters	B	C	A

We will different results if we apply different methods:

• Pairwise comparison

  • $C \succ A$ for 13 voters

  • $C \succ B$ for 13 voters

  • $B \succ A$ for 13 voters

  • $B \succ C$ for 8 voters

  • $A \succ B$ for 8 voters

  • $A \succ C$ for 8 voters

  $C$ is elected, beating both $A$ and $B$ 13 to 8.

• Winners is the candidate with more votes

  $A$ wins with 8 votes. $B$ has 7 and $C$ has 6.

• Two round process

  Two candidates who have more votes goes to a second round contest. $A$ and $B$ wins the first round, and $B$ wins the second round, 13 to 8.

Social welfare function vs social choice function

Social welfare function:

$$F: \mathcal{S P}^{n} \rightarrow \mathcal{P}$$

Social choice function:

$$f: \mathcal{S P}^{n} \rightarrow A$$

Which means that given a strict preference profile $\left(\succ_{1}, \succ_{2}, \ldots, \succ_{n}\right)$, in the first case we get a preference, i.e. a ranking over alternatives, while in the second case we get an alternative (i.e. the best alternative)

Anonimity rule (social welfare function)

How do we choose the most suitable function? The property of anonimity means that all voters share the same importance, i.e. if two agents exchange their preferences the result does not change.

Neutrality rule (social welfare function)

The neutrality property is the equivalent of anonymity as far as the alternatives are concerned.

Monotonicity rule (social choice function)

Basically if the alternative $x$ is selected by $f$ according to a given preference profile $\succ$, it will be selected for every other preference profile $\supset$ under which $x$ is, for every agent $i$, ranked not worse than in $\succ$.

Note that if $|A|=2$, this applies also to the social welfare function.

Simple majority rule

if $|A| = 2$ (and there are an odd number of voters), then the simple majority rule is the unique social choice-welfare function fulfilling anonymity, neutrality and monotonicity. It works by simply choosing the alternative with more votes. Example>

10 professors, 4 students (A, B, C, D):

# professors	1st choice	2nd choice	3rd choice	4th choice
4	A	B	D	C
3	D	C	B	A
2	B	D	C	A
1	C	D	B	A

According to the simple majority rule, A is the winner since 4 professors choosed him as 1st choice, which is more than B (2 professors), C (1 professor) and D (3 professors).

Condorcet method

If we have more than two alternatives, it is convenient to extend the majority rule and to make pairwise comparisons, since the majority rule cannot be extended to more than two alternatives. This is called Condorcet method.

Borda method

Works by giving points to alternatives according to rankings. Each alternative gets a score equal to the sum of the position in each ranking multiplied by the number of voters that support that ranking.

Unanimity

$$\left[\forall i \quad x \succ_{i} y\right] \Longrightarrow\left(x \succ_{N} y\right)$$

If alternative $x$ is better than alternative $y$ for every agent, this must be the same for the collective ranking.

Dictatorship

There exists $j \in N$ such that

$$F\left(\succ_{1}, \ldots, \succ_{i}, \ldots, \succ_{n}\right)=\succ_{j}$$

for each $\left(\succ_{i}\right)_{i} \in \mathcal{P}^{n}$.

About the properties of social choice functions

• If $|A|\ge3$, a social choice function $f$ which satisfies unanimity and monotonicity is also dictatorial.

  (unanime & (monotonic | non manipulable)) => dictatorial.