Axioms and setup

In Root's Paper:

Setup in Root

We have the following elements:

A set of agents: $N$
A set of objects: $O$
The set of all possible allocations: $A\equiv O^{|N|}$. ($a_i$ denotes the object allocated to agent $i$)
A nonempty constraint $C\subset A$, which exogenously specifies the set of feasible allocations.
Each agent's strict preferences over objects: $\succsim_i \in P$, where $P$ is the set of linear orders on $O$.
A feasible mechanism mapping profiles of preferences to specific feasible allocations: $f: P^{|N|}\to C$

Mechanism Properties in Root

The following are some properties that mechanisms might have:

A mechanism is Strategy Proof if truth-telling is a weakly dominant strategy when every other agent is truth-telling. That is, for every agent $i\in N$, every preference profile $\succsim \in P^{|N|}$, and every alternate ranking this agent could lie about having $\succsim^\prime_i\in P^{|N|}$, the outcome that the agent gets from telling the truth is at least as good as the outcome if they lie: \[f_i(\succsim) \succsim_i f_i(\succsim^\prime_i, \succsim_{-i})\]
A mechanism is Group Strategy Proof if a group of agents can never benefit by collectively lying. That is, for every preference profile $\succsim \in P^{|N|}$, and every subset of agents $M\subset N$, there is no falsely reported preferences for the group $\succsim^\prime_M$ which results in a Pareto Improvement for the group: \[\begin{gather*} f_j(\succsim^\prime_M, \succsim_{-M}) \succsim_j f_j(\succsim) \text{ for all } j\in M \\ f_j(\succsim^\prime_M, \succsim_{-M}) \succ_j f_j(\succsim) \text{ for at least one } j\in M. \end{gather*}\]
A mechanism is Weakly Group Strategy Proof if there is no group lie which strictly benefits every member of the group. That is, for every $\succsim \in P^{|N|}$, and every $M\subset N$, there is no $\succsim^\prime_M$ such that:\[f_j(\succsim^\prime_M, \succsim_{-M}) \succ_j f_j(\succsim) \text{ for all }j\in M \]
A mechanism is Pareto Efficient or Unanimous if there is no feasible allocation $a\in C$ and preference profile $\succsim$ such that $a \neq f(\succsim)$ but $a_j \succsim_j f(\succsim)$ for all $j$.
A mechanism is "Nonbossy" if an agent cannot lie about their own preferences in a way that changes another agent's allocation without also changing their own. That is, for all $\succsim$ and $\succsim^\prime_i$, \[f_i(\succsim^\prime_i, \succsim_{-i}) = f_i (\succsim) \implies f(\succsim^\prime_i, \succsim_{-i}) = f(\succsim)\]
A mechanism is Maskin Monotonic if increasing the ranking that each agent places on the object they are allocated never results in the mechanism instead giving them a different object. ("You get chocolate." "Oh, good. I recently found out that I love chocolate." "Oh, nevermind then. You get strawberry instead.") That is, for all $succsim, \succsim^\prime$, \[\{o \in O | o \succ_i f(\succsim) \} \subset \{o \in O | o \succ^\prime_i f(\succsim) \} \text{ for all } i \implies f(\succsim) = f(\succsim^\prime)\]

Local Dictatorship

Let $\bar{C^*}$ be the set of infeasible allocations in which each agent's object is individually given to them in some feasible allocation. Let The blocks of $\bar{C^*}$, $E_1,...E_p$ be a partition formed by equivocating any two allocations in $\bar{C^*}$ which assign the same object to at least one person.

$f: P^2 \to C$ is called a Local Dictatorship if each block $E_i$ is assigned a local dictator $d_i$ so that for any $\succsim$, if agent one ranks object $a$ the highest and agent two ranks object $b$ the highest, then: $$f(\succsim) =\begin{cases} (a,b), & (a,b)\in C\\ (a,\max_{\succsim_2}\{y|(a,y)\in C\}), & (a,b)\in E_k \text{ and } d_k=1 \\ (\max_{\succsim_1}\{x|(x,b)\in C\}, b), & (a,b)\in E_k \text{ and } d_k=2 \\ \end{cases}$$

Theorems in Root

The following are equivalent:
- $f$ is group strategy proof.
- $f$ is strategy proof and nonbossy.
- $f$ is Maskin monotonic.
If $f$ is group strategy proof, then it is Pareto Efficient on its image.
$f:P^2 \to C $ is strategy proof and Pareto efficient iff it is a local dictatorship.
The mechanism $f$ is group strategy proof iff for every pair of agents and preference profile for all other agents, the marginal mechanism is group strategy proof. In other words, no group of agents can team up to cheat the system iff no pair of agents can team up to cheat the system. TODO: Clean up.
For any constraint $C$, the generalized serial dictatorship mechanism are group strategy proof and pareto efficient.
A roommates mechanism is a group strategy-proof and Pareto efficient iff it is a generalized serial dictatorship.
Gibbard-Saitherwaite: If $|O| > 2 $, $C$ is the diagonal, and $f$ is surjective and strategy proof, then $f$ is dictatorial
Converse to GS
...

Root's GS proof

Look at marginal mechanisms, show that there is some pair of agents and profile of preferences such that the marginal mechanism has at least three allocations in its option set.

Next, in this marginal mechanism, we have a dictator.

In Standard Gibbard-Saitherwaite:

There is a set of social outcomes, $O$, and a set of individuals $N$, with individual $i$ having ordinal preferences $\succsim_i\in P$ over these outcomes. A social choice function is a map from the profiles $\succsim \equiv (\succsim_1, ... \succsim_{|N|})$ of everyone's preferences onto specific social outcomes: $f: P^{|N|} \to O $

The rule is unanimous if $f(\succsim)=a$ whenever $a\succsim_i b$ for each $i\in N$ and $b\in A$.
The rule is called dictatorial if there is some individual $i$ such that $f(\succsim) \succsim_i b \ \ \forall b \in O$
The rule is called strategy proof if for every $i, \succsim_{-i}, \succsim_i, \succsim_i^\prime, $ we have that $f(\succsim) \succsim_i f(\succsim_i^\prime, \succsim_{-i})$
The rules is called monotonic if for any pair of preference profiles, $\succsim, \succsim^\prime$\[ \{b : f(\succsim) \succsim_i b \} \subset \{b : f(\succsim) \succsim^\prime_i b\} \; \forall i \in N \; \implies \; f(\succsim)=f(\succsim^\prime) \]

The theorem states that if $|O| > 2 $, the domain of $f$ is unrestricted, and $f$ is onto and strategy proof, then $f$ is dictatorial .

GS Compared to Root's Setup

In both setups, each agent has preferences $\succsim_i\in P$ over $O$. And the social mechanism $f$ has domain $P^{|N|}$. In both theorems, $|O|\geq 3$

GS	Root
The mechanism selects an option from $O$	The mechanism selects an option from $O^{\|N\|}$
The codomain of $f$ is $O$.	The codomain of $f$ is $ O^{\|N\|}$.
The image of $f$ is the entire set of social options $O$.	The image of $f$ is some feasible subset of the set of profiles of societal options $C \subset O^{\|N\|}$. In this case, $C$ is the diagonals.
Requires that $\|O\|>2$ and $f$ surjective.	Technically only requires that the image of $f$ has more than two elements.
strategy-proofness: \[f(\succsim) \succsim_i f(\succsim^\prime_i, \succsim_{-i})\]	strategy-proofness: \[f_i(\succsim) \succsim_i f_i(\succsim^\prime_i, \succsim_{-i})\] (Agent only cares about the part of the social allocation given to them)
Dictatorial	Concerned more generally with mechanisms which are serial dictatorships. In the diagnonals, the first dictator happens to be a full dictator.

Standard Arrow

Modify Arrow for Root's $C$:

So standard social choice has a mapping from preference profiles to a single object. Root maps profiles of preferences to a profile of outcomes and says social choice is the specific case where only diagonals are feasible.

Standard Arrow maps prefence profiles to a social preference ordering. To apply the same generalization, we need to map preference profiles to a profile of preference profiles???

GS	Root
The mechanism selects an option from \(O\)	The mechanism selects an option from \(O^{\|N\|}\)
The codomain of \(f\) is \(O\).	The codomain of \(f\) is \( O^{\|N\|}\).
The image of \(f\) is the entire set of social options \(O\).	The image of \(f\) is some feasible subset of the set of profiles of societal options \(C \subset O^{\|N\|}\). In this case, \(C\) is the diagonals.
Requires that \(\|O\|>2\) and \(f\) surjective.	Technically only requires that the image of \(f\) has more than two elements.
strategy-proofness: \[f(\succsim) \succsim_i f(\succsim^\prime_i, \succsim_{-i})\]	strategy-proofness: \[f_i(\succsim) \succsim_i f_i(\succsim^\prime_i, \succsim_{-i})\] (Agent only cares about the part of the social allocation given to them)
Dictatorial	Concerned more generally with mechanisms which are serial dictatorships. In the diagnonals, the first dictator happens to be a full dictator.