# ECG 708 Class Notes (2)
###### tags: `NC State ISE`
Spring 2024 ECG-708 Advanced Microeconomic Theory
Instructor: Dr. Umut Dur
Venue: Nelson Hall 4210
Topics:
3. Object allocation
4. School choice

### Class Announcement
1. Feb 26 Midterm Release
- Serial dictactorship mechanism is Pareto efficient (no own)
- Serial dictactorship mechanism is strategyproof (no own)
- Top trading cycle mechanism is IR, PE and SP (full own)
- Rochester (Random SD) mechanism and analysis
2. Feb 27 no class

# House Allocation
In one-to-one and many-to-one matching markets, both side consist of agents, along with their preferences. In particular, the concept of equilibrium is realized by stability, which is characterized by agents' preferences. In this topic, we study housing allocation, where one side do not demonstrate preferences.
## Models
- Individuals $I=\{i_1,i_2,\cdots,i_n\}$
- Houses $H=\{h_1,h_2,\cdots,h_m\}$
- Preferences of individual $i$ over $H\cup\{\emptyset\}$
- Owner of house $h$: $o_h\in I\cup\{\emptyset\}$, where $o_h=\emptyset$ means that nobody owns the house $h$ (Ownership is not necessary for housing assignment)
- An **allocation** $\mu:I\rightarrow H\cup\{\emptyset\}$ is a function such that $|\mu^{-1}(h)|\leq1$. In particular, an individual can be matched with at most one house, and a house can be allocated to at most one individual.
- An allocation $\mu$ is **Pareto efficient** if there does not exist another allocation $\nu$ such that for every individual $i\in I$, $\nu(i)R_i\mu(i)$, and for some $j\in I$, $\nu(j)P_j\mu(j)$.
(Every assignment $\nu(i)$ is weakly preferred to $\mu(i)$, and for some assignment $\nu(j)$ is strongly preferred to $\mu(j)$)
- An allocation $\mu$ is **individually rational** if $\mu(i)R_i\pi(i)$, where $\pi(i)$ denotes the initial houses of $i$.
### No Ownership Example
This means that for every house $h\in H$, $o_h=\emptyset$.

| $P_{i_1}$ | $P_{i_2}$ | $P_{i_3}$ |
| --------- | --------- | --------- |
| $h_1$ (1) | $h_1$ (2) | $h_2$ (1) |
| $h_2$ (2) | $h_3$ (1) | $h_3$ (2) |
| $h_3$ (3) | $h_2$ (3) | $h_1$ (3) |

Assignment (1) and (2) are Pareto efficient, while assignment (3) is not.
### Full Ownership Example
This means that $\forall h\in H, o_h\in I$. Furthermore, we assume that $o_h\neq o_{h'}$ for every $h\neq h'\in H$, which implies that $|I|=|H|$. We consider $I=\{i_1,i_2,i_3\}$, $H=\{h_1,h_2,h_3\}$ as well as the following preferences, and we further suppose that $o_{h_x}=i_x$ for $x=1,2,3$.

| $P_{i_1}$ | $P_{i_2}$ | $P_{i_3}$ |
| --------- | --------- | --------- |
| $h_3$ | $h_3$ (@) | $h_1$ (@) |
| $h_1$ | $h_1$ | $h_3$ |
| $h_2$ (@) | $h_2$ | $h_2$ |

In this example, Pareto efficient allocation may not be better than initial allocation (ownership). Although assignment (@) is Pareto efficient, $i_1$ is assigned to a house worse than her initial house, driving her out of the market.
Consider the case $i_1$ does not participate, as well as the following preference

| $P_{i_2}$ | $P_{i_3}$ |
| ---------- | ---------- |
| $h_3$ | $h_3$ (@@) |
| $h_2$ (@@) | $h_2$ |

Notice that if $i_3$ is assigned to $h_2$, she will also leave the market, since she gets a house worse than her initial one. To encourage individuals to stay in the market, we need some guarantees preventing them from matched to houses worse than their initial ones, which can be captured by **individual rationality**. Unfortunately, SD is not individually rational.

## Serial Dictactorship (SD) Mechanism
To find a Pareto efficient allocation, we define the following class of mechanisms.

0. Pick an order over the individuals, and let $i_k$ be the $k$-th individual in that order.
1. Individual $i_1$ picks her best house under $P_{i_1}$, and remove that house and $i_1$.
2. (General setp $k$) Individual $i_k$ picks her best remaining house under $P_{i_k}$, and remove that house and $i_k$.
3. Termination: all individuals are removed from the list.

In fact, the order we select in step 0 may change the outcome and we can define a new mechanism for each other.
**Theorem**: SD is Pareto efficient and strategyproof.
(MIDTERM: Prove by induction)

## Top Trading Cycles (TTC) Mechanism
**Initialization**: (Graph construction) Denote every house and individual as nodes, and let every house pointed to its owner and every inividual $i$ points to her most preferred house.
**Step 1**: If there is a cycle, execute it by assigning individuals in that cycle to the houses they are pointing to. Remove assigned houses and individuals.
(**Remark**: due to finite individuals and houses, cycles are guaranteed)
**Step $t$**: Every remaining house points to its owners and remaining individual points to her most preferred house among the remaining ones. Repeat the same cycle execution in step 1.
**Termination**: the mechanism stops when all individuals and houses are removed.

**Theorem**:
1. TTC mechanism is individually rational, Pareto efficient and strategy-proof.
2. TTC mechanism is the unique individually rational, Pareto efficient and strategy-proof mechanism in housing market with ownership.
Idea: if there is another $\psi$, distinct from TTC($\mu$), then there exists a problem such that they produce different outcomes. We consider the individuals in the first step of TTC and assume that $\psi(i)\neq\mu(i)$. This implies that $\mu(i)P_i\psi(i)R_i h_i$
### Example
Let $I=\{i_1,i_2,i_3,i_4,i_5\}$ and $H=\{h_1,h_2,h_3,h_4,h_5\}$, we assume ownership $o_{h_k}=i_k, \forall k\in I$. Consider the following preference:

| $P_{i_1}$ | $P_{i_2}$ | $P_{i_3}$ | $P_{i_4}$ | $P_{i_5}$ |
| --------- | --------- | --------- | --------- | --------- |
| $h_2$ | $h_3$ | $h_2$ | $h_1$ | $h_1$ |
| $h_3$ | $h_1$ | $h_4$ | $h_2$ | $h_2$ |
| $h_1$ | $h_4$ | $h_1$ | $h_3$ | $h_3$ |
| $h_4$ | $h_2$ | $h_3$ | $h_5$ | $h_4$ |
| $h_5$ | $h_5$ | $h_5$ | $h_4$ | $h_5$ |

We implement TTC mechanism step by setp (shown in the figure below).

## Hybrid Ownership
- The set of houses can be divided into vacant and occupied houses $H=H^V\cup H^O$ with $H^V\cap H^O=\emptyset$.
- Similarly, the set of individuals can also be divided into new and existing individuals $I=I^N\cup I^E$
- For ownership, we set up the following:
- $o(i)$ denotes the houses owned by individual $i$. In particular, $o(i)\subseteq H^O$ if $i\in I^E$ and $o(i)=\emptyset$ if $i\in I^N$.
- $o(h)$ denotes the owner of the house. Specifically, $o(h)\in I^E$ if $h\in H^O$ and $o(h)=\emptyset$ if $h\in H^V$.
* Objective: individual rationality, Pareto efficiency and strategy-proofness
### Modified TTC Mechanism
0. Transfer the houses and individuals into nodes. *Select an order over individuals* (denoted by $\pi$)
1. Every individual points to her top choices. Every occupied house points to its ownership $o(h)$, and every vacant house points to top-rated individual under $\pi$. Due to finiteness, there is always cycles in this di-graph. Select a cycle and assign individuals in that cycle to the houses they are pointing to. Remove the houses and individuals in that cycle. *The initially occupied houses whose owners are removed are treated as vacant houses in the following iterations.*
2. (General step) Every individual points to her top available choices. Every occupied house points to its ownership $o(h)$, and every vacant house points to top-rated individual under $\pi$. Select a cycle and assign individuals in that cycle to the houses they are pointing to. Remove the houses and individuals in that cycle. *The initially occupied houses whose owners are removed are treated as vacant houses in the following iterations.*
### Example
Let $H^O=\{h_1,h_2,h_3,h_4\}$, $H^V=\{h_5,h_6\}$, $I^E=\{i_1,i_2,i_3,i_4\}$, and $I^N=\{i_5,i_6\}$, we assume the ownership $o(h_k)=i_k$ for $k=1,2,3,4$ and consider $\pi=(1,2,3,5,4,6)$, as well as the following preferences:

| $i_1$ | $i_2$ | $i_3$ | $i_4$ | $i_5$ | $i_6$ |
| ----------------- | ----------------- | ----------------- | ----------------- | ----- | ----- |
| $h_2$ | $h_5$ | $h_2$ | $h_5$ | $h_4$ | $h_2$ |
| $h_4$ | $h_1$ | $h_1$ | $h_3$ | $h_3$ | $h_1$ |
| $h_5$ | $\underline{h_2}$ | $\underline{h_3}$ | $\underline{h_4}$ | $h_2$ | $h_3$ |
| $h_3$ | $h_3$ | $h_4$ | $h_2$ | $h_1$ | $h_6$ |
| $\underline{h_1}$ | $h_4$ | $\emptyset$ | $h_1$ | $h_6$ | $h_5$ |
| $h_6$ | $h_6$ | $\emptyset$ | $\emptyset$ | $h_5$ | $h_4$ |

Although we may construct a cycle using complete information, this conventional approach may take more effort. In fact, we can construct the cycle starting from a single house-node. (The tie breaking rule should be embedded in the choice of the starting node.)

**Theorem**: TTC under hybrid settings is individually rational, Pareto efficient and strategy-proof.
# School Choice
The priorities of schools are **exogenously determined**. (Important in welfare analysis)
## Elements
1. Set of schools $S$
2. Set of students $I$
3. School capacity $q_s$, $s\in S$
4. Student's (strict) preference over schools and being unassigned option $\emptyset$ is denoted $P_i$
5. Each school $s$ has strict priority order over students $\succ_s$
6. The outcome is a matching $\mu:I\rightarrow S\cup\{\emptyset\}$, satisfying $|\mu^{-1}(s)|\leq q_s,\forall s\in S$.
7. A **mechanism** $\Psi$ is a procedure selecting a matching for any problem $(S,I,q,\succ,P)$, and the outcome matching by $\Psi$ is denoted by $\Psi(P)$.
### Stability Characterization
1. **Individual rationality**: $\mu(i)R_i\emptyset$, $\forall i\in I$.
2. **Non-wasteful**: whenever there exists student-school pair $(i,s)$ such that $sP_i\mu(i)$, then $|\mu^{-1}(s)|=q_s$.
3. Under matching $\mu$, student $i$ has justified envy student $j$ if $\mu(j)P_i\mu(i)$ and $i\succ_{\mu(j)}j$.
4. **Fairness**: no justified envy. ($\approx$ no blocking pair)
5. **Pareto efficiency**: there is no another matching $\nu$ such that
- $\nu(i)R_i\mu(i),\forall i\in I$
- $\nu(j)P_j\mu(j)$ for some $j\in I$
6. **Strategy-proof**: $\Psi$ is strategy-proof if there does not exist $i\in I$ and $P_i'\neq P_i$ such that $$\Psi_i(P_i',P_{-i})P_i\Psi_i(P).$$
## Solution Mechanism
### Student-proposing Deferred Acceptance
> Is student proposing DA Pareto efficient, stable (IR+non-wasteful) and strategy-proof?

Stability in school choice problem and stability in college admission are equivalent. Moreover, strategyproof for students in college admission implies strategyproof in school choice. Therefore, student-proposing DA is strategyproof and stable.
**Example**
- We consider a three-school and three-student example: $S=\{s_1,s_2,s_3\}$, $I=\{i_1,i_2,i_3\}$, $q_s=1,\forall s\in S$.
- The preferences are given as following:

| $P_{i_1}$ | $P_{i_2}$ | $P_{i_3}$ | $\succ_{s_1}$ | $\succ_{s_2}$ | $\succ_{s_3}$ |
|:---------:|:---------:|:---------:|:-------------:|:-------------:|:-------------:|
| $s_1$ | $s_1$ | $s_2$ | $i_3$ | $i_1$ | $i_1$ |
| $s_2$ | $s_3$ | $s_1$ | $i_2$ | $i_2$ | $i_2$ |
| $s_3$ | $s_2$ | $s_3$ | $i_1$ | $i_3$ | $i_3$ |

Applying student-proposing DA yields

| | $s_1$ | $s_2$ | $s_3$ |
| ------ | ----------------- | ----------------- | ----- |
| Step 1 | $i_1$(X),$i_2$(V) | $i_3$ | |
| Step 2 | $i_2$ | $i_1$(V),$i_3$(X) | |
| Step 3 | $i_2$(X),$i_3$(V) | $i_1$ | |
| Step 4 | $i_3$ | $i_1$ | $i_2$ |

In this example, since $s_1$ and $s_2$ are matched with their top priority, the outcome matching $\mu$ is stable. However, if we swap the assignment between $i_1$ and $i_3$ (that is, define a new matching $\nu$ such that $\nu(i_1)=s_1,\nu(i_2)=s_3,\nu(i_3=s_2)$), then we obtain $$s_1=\nu(i_1)P_{i_1}\mu(i_1)=s_2,\ s_2=\nu(i_3)P_{i_3}\mu(i_3)=s_1.$$ Therefore, student-proposing DA is NOT Pareto efficient.

**Remark**:
Since student-proposing is the best stable mechanism for students but not Pareto efficient, no stable mechanism is Pareto efficient. As a result, there is no mechanism that is both stable and Pareto efficient, so there is no perfect mechanism in this matching market.
## Current Mechanism in Practice
Consider there is only one school $s$, having priority $\succ_s$ over $I$ and capacity $q_s$, all students in $I$ would like to be assigned to $s$. We may select the first $q_s$ students under $\succ_s$.

We extend to a two-school case $s,s'$. As students apply to one school, we divide the students into two parts: $I_s$ apply to $s$, $I_{s'}$ apply to $s'$ ($|I_s|+|I_{s'}|\leq q_s+q_{s'}$), and select the first $q_s$ and $q_{s'}$ students under $\succ_s$ and $\succ_{s'}$ from $I_s$ and $I_{s'}$ respectively. The rejected students, if any, apply to the other school. Since there is sufficient capacity , all will be accepted.

### Boston Mechanism
1. Every student $i$ applies to her top choice, and every school $s$ **permanently** accepts top $q_s$ applicants based on $\succ_s$. All the other applicants are rejected.
2. Students who are rejected in step 1 apply to their second choice, and every school permanently accepts top applicants based on $\succ_s$ until its seats are filled. All other applicants are rejected.

$\vdots$

**Example**:
$S=\{s_1,s_2,s_3\}, I=\{i_1,i_2,i_3\}$, $q_{s_k}=1,k=1,2,3$

| $P_{i_1}$ | $P_{i_2}$ | $P_{i_3}$ | $\succ_{s_1}$ | $\succ_{s_2}$ | $\succ_{s_3}$ |
|:---------:|:---------:|:---------:|:-------------:|:-------------:|:-------------:|
| $s_1$ | $s_1$ | $s_2$ | $i_3$ | $i_1$ | $i_2$ |
| $s_2$ | $s_3$ | $s_1$ | $i_2$ | $i_3$ | $i_3$ |
| $s_3$ | $s_2$ | $s_3$ | $i_1$ | $i_2$ | $i_1$ |

We implement Boston mechanism as floowing:

| | $s_1$ | $s_2$ | $s_3$ |
| ------ | ----------------- | ----- | ----- |
| Step 1 | $i_1$(X),$i_2$(V) | $i_3$ | |
| Step 2 | $i_2$ | $i_3$ | $i_1$ |

* Not fair: $(i_1,s_2)$ "blocks" the matching
* Not strategyproof

Since $i_1$ has incentives to misreport her preference, she can submit her preference $s_2\rightarrow s_1\rightarrow s_3$. Under this misreported preference, we have the following outcome (Boston mechanism): (where $i_1$ gets a better assignment)

| | $s_1$ | $s_2$ | $s_3$ |
| ------ | -------- | ----------------- | ----- |
| Step 1 | $i_2$(V) | $i_1$(V),$i_3$(X) | |
| Step 2 | $i_2$ | $i_1$ | $i_3$ |

**Theorem**:
Boston mechanism is not fair and strategyproof, but is Pareto efficient, non-wasteful and individually rational.

*Proof*:
> PE $\Rightarrow$ NW & IR
> If it is PE but not NW, which means that there is a student who can be moved to an empty seat and thus be better off (without hurting other students), this leads to contradiction

As the assignment procedure is permanent, we adopt a similar inductive approach (to those in serial dictatorship and TTC). Consider students who are assigned in step 1, there is no way making them better off. Suppose there is no way making students better off in step $2,\cdots,k-1$, we consider students assigned in step $t$. They can only obtain a better result by making students in the previous steps worse off. (c)

Although Boston mechanism is Pareto efficient, its non-strategyproofness makes it not as appealing as TTC and serial dictatorship.

## Preference Revelation Game
> Is it easy to manipulate/misreport preferences for a better outcome?
-> YES. Since the stucture of Boston mechanism is simple, it is not difficult for parents to strategize their preference.

Consider again the example before, suppose that $i_3$ knows that $i_1$ is going to misreport, he will also manipulate. Say $\succ_{i_1}:s_2,s_1,s_3$ and $\succ_{i_3}:s_1,s_2,s_3$, we apply Boston mechanism

| | $s_1$ | $s_2$ | $s_3$ |
| ------ | ----------------- | ----- | ----- |
| Step 1 | $i_2$(X),$i_3$(V) | $i_1$ | |
| Step 2 | $i_3$ | $i_1$ | $i_2$ |

We note that since $i_1$ and $i_3$ can swap their assignment, this outcome is NOT Pareto efficient. This outcome is, in fact, the same with student-proposing DA and constitutes a *Nash equilibrium*:
| | $s_1$ | $s_2$ | $s_3$ |
| ------ | ----------------- | ----------------- | ----- |
| Step 1 | $i_1$(X),$i_2$(V) | $i_3$ | |
| Step 2 | $i_2$ | $i_1$(V),$i_3$(X) | |
| Step 3 | $i_2$(X),$i_3$(V) | $i_1$ | |
| Step 4 | $i_3$ | $i_1$ | $i_2$ |

The equilibrium outcome of the Boston mechanism corresponds to the dominant strategy outcome of the deferred acceptance mechanism. Specifically, the dominant strategy of DA means to report true preference, since DA is strategyproof.

Here we define a simple game, called **preference revelation game**, with the following elements:
- Players: students
- Actions for strategies: all possible preference orders over schools
- Outcome: payoffs consistent with true preferences, for instance, the utility/return of the top choice > utility of the second...

Let $\sigma=(\sigma(1),\sigma(2),\sigma(3))$ be a pure strategy profile, $\sigma$ is **Nash equilibrium** if there does not exist $i$ and $\sigma'_i$ such that $U_i(\sigma'_i,\sigma_{-i})>U_i(\sigma)$.

**Theorem**:
Under Boston mechanism and complete information, every Nash equilibrium outcome is a stable matching. Every stable matching can be supported by a Nash equilibrium.

Recall that DA is strategyproof and student-optimal stable matching. The outcome under dominant strategy is student strategy is student optimal stable matching. When we consider equilibrium outcomes, DA is superior than Boston mechanism in terms of welfare.

**Example**
We consider $S=\{s_1,s_2\},I=\{i_1,i_2\},q_{s_1}=q_{s_2}=1$ as well as the following preference:
| $P_{i_1}$ | $P_{i_2}$ | $\succ_{s_1}$ | $\succ_{s_2}$ |
|:---------:|:---------:|:-------------:|:-------------:|
| $s_2$ | $s_1$ | $i_1$ | $i_2$ |
| $s_1$ | $s_2$ | $i_2$ | $i_1$ |

There are two stable matchings: $(i_1\rightarrow s_1,i_2\rightarrow s_2)$ and $(i_1\rightarrow s_2,i_2\rightarrow s_1)$, while the later is the dominant equilibrium under DA. The theorem says that both outcomes are Nash equilibrium outcome of Boston mechanism.
# Reading Notes
## House Allocation with Existing Tenants
> Abdulkadiroglu and Sonmez 1999: *House allocation problem with existing tenants*

* **Random serial dictatorship mechanism** randomly sorts/orders/ranks the agents and the first agent in the order is assigned his top choice, the next agent is assigned his top choice among the remaining houses, and so on.
* Unfortunately random SD cannot capture the existence of tenants who already live in a house and who can keep on doing so.
### Top Trading Cycles Mechanism
1. Pareto efficient
2. Individually rational
3. Strategy-proof
4. Simple and direct: agents report their preferences and the outcome is obtained using one of the two algorithms
5. Applicable: accommodate any hierarchy of seniorities (as in the case of random serial dictatorship).

---
- House allocation model
* Individuals are divided into existing tenants and new applicants $I=I_E\cup I_N$
* Houses are also divided into occupied and vacant ones $H=H_O\cup H_V$, where $H_O=\{h_i\}_{i\in I_E}$.
* Preferences $P=(P_i)_{i\in I}$.
* We assume that the null house $h_0$ ($\emptyset$) is the last choice for each agent.
- Outcome
* House matching/allocation/assignment
* Housing lottery - a probability distribution over all matchings.

Step 1: Define the set of *available houses* for this step to be the set of vacant houses. Each agent $i$ points to his or her favorite house under his or her announced preference $Q_i$ , each occupied house points to its occupant, and each available house points to the agent with highest priority
$\vdots$
Step $t$:
## Market Design Approach to School Choice
Abdulkadiroglu and Sonmez 2003 (AER)
## Game theory notions in Boston Mechabism
Ergin and Sonmez 2006 (JPubE)
Pathak and Sonmez 2008 (AER)

## Matching with Contract
Hatfield and Milgrom 2005 (AER)
* College admission problem
* Kelso-Crawford labor market matching model
* Ascending package auction
### Model Frameworks
1. Doctors: $D$
2. Hospitals $H$
3. Contracts $\mathbf{X}=D\times H\times W$ ($W$ denotes the wages)
4. Preferences of doctor $P_d$ over possible contracts
5. Allocation is a collection of contracts that determines the payoffs to the participants

* **Chosen set** (most-preferred contract) of a doctor $d\in D$/ a hospital $h\in H$ is denoted by $C_d(X)$/$C_h(X)$, where $X\subset\mathbf{X}$.
* **Rejected set** of $D$ is denoted by $R_D(X)=X-C_D(X)$, $C_D(X):=\cup_{d\in D}C_d(X)$
* **Stability**
### Roth-Sotomayor Substitutable Preferences
* **Substitutes** for hospital $h$: for every $X'\subset X\subset\mathbf{X}$, $R_h(X')\subset R_h(X)$.

## Slot-Specific Matching
Kominers and Sonmez 2016
### Model Framework
1. Set of agents $I$
2. Set of branches $B$
3. Set of contracts $X$, each contract $x\in X$ specifies the agent $i(x)\in I$ and the branch $b(x)\in B$
4. Preference of agent $i\in I$: $P^i$ over contracts $X_i=\{x\in X:i(x)=i\}\cup\{\emptyset\}$.
5. Sets of slots for branch $b\in B$: $S_b$
6. Priority order of each slot $s$: $\Pi^{s}$
7. Best available contract $C^i(Y),C^b(Y)$ from a contract set $Y\subseteq X$