# ECG 708 Class Notes (1)
###### tags: `NC State ISE`
2024 Spring ECG-708
Instructor: Dr. Umut Dur
Venue: Nelson Hall 4210
Topics:
1. One-to-one matching: marriage market
2. Many-to-one matching: medical market

## Discussion on study
*Jan 18 Post-seminar talk*
1. Stochastic preference, stochastic variational inequality
2. MDP-based Mechanism for retailer in transshipment game
3. Application of reserve system (minimalist market design)

Umut's feedback:
- Focus on foodbank/health resource allocation, especially how disctribution is processed

# Introduction
Example:
1. Havard economic program
2. Kidney transplant
3. School assignment
4. Medical match
5. Dorm allocation
6. Public Housing
7. Marriage (one-to-one two-sided market)

Remark: Usually in markets, allocation is determined through prices, but in some cases, prices may not be sufficient to characterize allocations. In this class, we focus on those markets.

# Marriage Market
## Elements of the Formal (Cooperative) Model
- Two finite and disjoint sets: $M:=\{m_1,m_2,\cdots,m_n\}$ denotes the set of men, and $W=\{w_1,w_2,\cdots,w_K\}$ denotes the set of women.
- Each individual has a preference: each man $m$ (woman $w$) has strict preferences over $W\cup\{m\}$ (or $W\cup\{\emptyset\}$) ($M\cup\{w\}$ or $M\cup\{\emptyset\}$), where $\{m\}$ means being single.
These preferences are assumed to be **strict** and can be represented by the list of preferences $P_m=w_1,w_2,\emptyset,w_3,\cdots,w_K$. In this example, $w_1$ and $w_2$ are acceptable to $m$, while $w_3,\cdots,w_K$ are unacceptable.
- At least as good as preference relation: $R_m$. Under $P_m$, for any $w,w'\in W$, $w R_m w'$ if and only if $wP_m w'$ or $w=w'$.
- Structures of preference of an individual:
1. Completeness
2. Transitivity
3. Rantionality (completeness+transitivity)
- *Definition*: A **matching** $\mu:M\cup W\rightarrow M\cup W\cup\{\emptyset\}$ is an one-to-one mapping and satisfies
(1) $\forall m\in M,\ \mu(m)\in W\cup\emptyset$
(2) $\forall w\in W,\ \mu(w)\in M\cup\emptyset$
(3) $\mu(m)=w$ if and only if $\mu(w)=m$.
We call $\mu(m)$ the mate of $m$.
### Equilibrium Characterization
1. Equilibrium means that no woman or man wants to divorce, and can be characterized by the "**stability**," which is a conjunction of the two requirements: **individual rationality** (IR) and **no blocking pair** (NBP).
2. Individually rational matching means that each agent is acceptable to his or her mate. That is, $\mu$ is said individually rational if $\forall i\in M\cup W, \mu(i)R_i\emptyset$.
3. Given a matching $\mu$, a pair $(m,w)$ **blocks** $\mu$ if $m P_w\mu(w)$ and $w P_m\mu(m)$, then $\mu(m)\neq w$ and $\mu(w)\neq m$. That is, only matchings that do not compel individuals into unacceptable matches will occur.
4. A matching $\mu$ is **stable** if it is individually rational and there is no blocking pair.

***Example***: Suppose $M=\{m_1,m_2\}$ and $W=\{w_1,w_2\}$, with the following preferences.
$$\begin{array}{ll}
P_{m_1}=w_1,w_2,\emptyset & P_{w_1}=m_1,m_2,\emptyset \\
P_{m_2}=w_1,w_2,\emptyset & P_{w_2}=m_1,m_2,\emptyset \\
\end{array}$$
1. All partners are acceptable for every agents, so individual rationality is automatically set under any matching.
2. Consider the matching $\mu(m_1)=w_2$, $\mu(m_2)=w_1$, since $m_1$ and $w_1$ are matched with their second choices and they are preferred to be matched to each other, so $(m_1,w_1)$ is a blocking pair.
3. Consider the matching $\nu(m_1)=w_1$, $\nu(m_2)=w_2$, since there is no blocking pair, so $\nu$ is a stable matching.

***Theorem***: Every marriage market have at least one stable matching.
*Proof* by devising two mechanisms, a procedure selecting a matching for any problem: man-proposing deferred acceptance (MPDA) and woman-proposing deferred acceptance (WPDA).
## Deferred Acceptance Mechanism
> Reading: Shapley (Nobel prize) 1962
### Women-proposing deferred acceptance
1. Every woman propose to her top choice, and every man tentatively accept the best acceptable proposal, then reject the rest of the proposals.
2. Every woman propose to her top choice who has *not reject her yet*, and every man tentatively accept the best acceptable proposal, then reject the rest of the proposals.
3. Continue until no woman is rejected.
### Men-Proposing deferred acceptance
1. Every man propose to his top choice, and every woman tentatively accept the best acceptable proposal, then reject the rest of the proposals.
2. Every man propose to his top choice who has *not reject him yet*, and every woman tentatively accept the best acceptable proposal, then reject the rest of the proposals.
3. Continue until no man is rejected.

***Example***:
### Existence of Stable Matching
We will show that man-proposing deferred acceptance selects a stable matching for any problem, so the existence of stable matching is guaranteed. In particular, we show that the outcome of MPDA is individually rational(IR) and has no blocking pair(NBP):
1. IR: The coutcome of the MPDA is necessarily individually rational, since no man proposes to an acceptable woman, and no woman tentitively accepts an unacceptable man.
2. NBP: We prove this by contradiction. Suppose there exists a blocking pair under the outcome of MPDA for some problem $P$, let $\mu$ be the outcome of MPDA under $P$ and $(m,w)$ be the blocking pair. That is $$mP_w \mu(w)R_w\emptyset,\ wP_m\mu(m)R_m\emptyset.$$

Then MPDA shows that $m$ proposed $w$ before proposing to his final match $\mu(m)$.
If $m$ made further proposal after proposing $w$, he must have been rejected by $w$. The reason why $w$ rejected $m$ is that $w$ had either (1) a better proposal in the step $m$ was rejected, or (2) $m$ is unacceptable.

As $mP_w\emptyset$, excluding the possibility of (2), we only need to check (1).
We note that in each step, $w$ keeps better proposal than $m$, it is impossible to have $mP_w\mu(w)$, leading to a contradiction.(c)

### Roommate Problem: Non-Existence of Stable Matching
Given three students $i,j,k$, their preferences
| $i$ | $j$ | $k$ |
| --- |:---:| --- |
| $j$ | $k$ | $i$ |
| $k$ | $i$ | $j$ |

and a room with capacity 2, we show that there is always a blocking pair for each matching. Particularly, for matching pair $(i,j)$, there is a blocking pair $(j,k)$, which has a blocking pair $(i,k).$ Moreover, $(i,k)$ is blocked by $(i,j)$. Due to the cyclic preference structure, there is no stable matching for this problem.

### Properties of Stable Matching
***Remark***: MPDA and WPDA yield the best stable matching for man and woman side respectively.

***Definition***: **Man-optimal/pessimal** stable matching is a stable matching that is the best/worst for man side.

***Proposition 1***: Let $\mu_M$ and $\mu_W$ be the outcome of MPDA and WPDA. Each man (weakly) prefers $\mu_M$ to any other stable mathing, and each woman prefers any other stable matching to $\mu_M$($\mu_M$ is woman-pessimal).

*Proof*: To prove man-optimality, we first give a definition and prove a claim. We say that man $m$ and woman $w$ are **achievable** if there exists a stable matching $\bar{\mu}$ such that $\bar{\mu}(m)=w$, $\bar{\mu}(w)=m$

*Claim: **Under MPDA, no man can be rejected by an achievable woman.*** If the claim is right, all women preferred to the man-optimal mate are not achievable. As a result, man-optimal mate is the most preferred achievable partner for men.

We prove the claim by contradiction: suppose that there exists an achievable pair but in MPDA the woman rejects the man. Let $m$ be the first man rejected by an achievable woman $w$. That is, such rejection did not in an earlier step of MPDA.

As **$(m,w)$ is achievable (@)**, they are acceptable to each other. However, $w$ rejects $m$ because she prefers another man $m'$ $m'P_w m$ and $m'$ has proposed at the same step as $m$. (In other words, $m'$ proposes to $w$ beore, or at the same step $m$ is rejected by $w$) Since $m$ is the first man rejected by an achievable partner, all women $m'$ prefers to $w$ are not achievable for $m'$. Hence **$m'$ weakly prefers $w$ to any achievable partner (@@)**.

Let $\mu$ be the stable matching such that $\mu(m)=w$, so $\mu(m')\neq w$ and $\mu(m')$ is achievable for $m'$. Then, we have $w P_{m'}\mu(m')$ (due to (@@)) and $m'P_w m$, this shows that $(m',w)$ is a blocking pair, so $\mu$ is not stable, forming a contradiction.(c)

***Proposition 2***: Let $\mu$ and $\mu'$ be stable and suppose all men weakly prefer $\mu$ to $\mu'$, then all women weakly prefer $\mu'$ to $\mu$.
*Proof*: Suppose not: there exists a woman who prefers $\mu$ to $\mu'$. Let $m=\mu(w)$ and $m'\mu'(w)$, we have $mP_w m'$ with $m\neq m'$ and $w=\mu(m)\neq\mu'(m)$. Followed by our assumption, we have $$wP_m\mu'(m),\ mP_w\mu'(w),$$
this shows that $(w,m)$ blocks $\mu'$, so $\mu'$ is not stable, leading to a contradiction (-><-)(c)
**Remark**:
1. The first proposition says that $\mu_M$ is preferred by men to any stable matching $\mu$.
2. The second one says that any stable matching $\mu$ is preferred by women to $\mu_M$.

***Theorem***: Let $\mu$ and $\mu'$ be two stable matchings, $$\forall i\in M\cup W,\ \mu(i)=\emptyset\Leftrightarrow\mu'(i)=\emptyset.$$
This implies that the number of matched couples is the same over all stable matchings.
**Proof**:
Let $\mu_M$ and $\mu_W$ be man-optimal and woman-optimal stable matchings, if $\mu_M=\mu_W$, then there is a unique stable matching, so $\mu=\mu'$ and the result follows. We hence suppose that $\mu_M\neq\mu_W$.

Let $\overline{M}$ and $\underline{W}$ be sets of men and women matched (not single) under $\mu_M$ respectively, and let $\underline{M}$ and $\overline{W}$ be sets of men and women matched (not single) under $\mu_W$ respectively, then we derive the cardinality **(1)**\begin{equation}
|\overline{M}|=|\underline{W}|,\ |\underline{M}|=|\overline{W}|
\end{equation}
We note that, due to man-optimality, if $m\in\underline{M}$, then $m\in\overline{M}$ (since $\mu_M(m)R_m\mu_W(m)P_m\emptyset\Rightarrow\mu_M(m)P_m\emptyset$).
This yields **the inclusion $\underline{M}\subseteq\overline{M}$ and the inequality (2): $|\underline{M}|\leq|\overline{M}|$**.
Similarly, due to woman-optimality, if $w\in\underline{W}$, then $w\in\overline{W}$ (since $\mu_W(w)R_w\mu_M(w)P_w\emptyset\Rightarrow\mu_W(w)P_w\emptyset$).
Therefore, we derive **the inclusion $\underline{W}\subseteq\overline{W}$ and the inequality (3): $|\underline{W}|\leq|\overline{W}|$**. Combining (1)-(3), we derive that
$$|\overline{M}|=|\underline{W}|\leq|\overline{W}|=|\overline{M}|\leq|\overline{M}|.$$
Notice that if the first inequality holds without equality, the contradiction $|\overline{M}|<|\overline{M}|$ occurs.
In fact, the same situation happens to the second inequality, so we have **(4)** $$|\overline{M}|=|\underline{M}|,\ |\overline{W}|=|\underline{W}|.$$
Due to finite cardinality of the matched sets (namely $\underline{M},\overline{M},\underline{W}$ and $\overline{W}$), by (2)-(4) we have **(5)(6)** $$\underline{M}=\overline{M},\text{ and }\underline{W}=\overline{W}.$$

For generalization, we consider arbitrary stable matchings $\mu$ and $\mu'$.
We note that if $\mu(m)\neq\emptyset$, then $\mu_M(m)\neq\emptyset$, due to man-optimality and individual rationality of $\mu$.
By (5) this implies that $$\mu_W(m)\neq\emptyset\Rightarrow\mu'(m)\neq\emptyset\text{ (individual rationality of }\mu').$$
Following a similar argument, we get if $\mu'(m)\neq\emptyset$, then $\mu(m)\neq\emptyset$, this gives the equivalence $$\mu(m)\neq\emptyset\Leftrightarrow\mu'(m)\neq\emptyset.$$ Hence completes the proof. (c)

## Incentives: Strategy-proof Mechanism
**Incentives**: We say a mechanism $\psi$ is **strategy-proof (SP)** if no idividual can gain from misreporting: there does not exist an individual $i$ and preference order $P_i'\neq P_i$ such that $$\psi(P_i',P_{-i})P_i\psi_i(P),$$
where $P_{-i}=(P_j)_{j\neq i}$, $\psi(P_i',P_{-i})$ denotes $i$'s outcome when he reports $P_i'$ with all other report true preferences, and $\psi_i(P)$ is $i$'s outcome under true preference.

Our main goal in marriage market is stability, but if individuals misreport, then stability under "reported preferences" does not guarantee stability under "true preferences." We want a SP and stable mechanism.

**Example**: Consider $M=\{m_1,m_2\},W=\{w_1,w_2\}$ with their preferences
| ($m_1$) | ($m_2$) | ($w_1$) | ($w_2$) |
|:-----------:|:-----------:|:-----------:|:-----------:|
| $w_1$ | $w_2$ | $m_2$ | $m_1$ |
| $w_2$ | $w_1$ | $m_1$ | $m_2$ |
| $\emptyset$ | $\emptyset$ | $\emptyset$ | $\emptyset$ |

We apply both man-proposing and woman-proposing DA respectively, and derive the following assignment:

| MPDA | | WPDA | |
|:-------:|:-------:|:-------:|:-------:|
| ($w_1$) | ($w_2$) | ($m_1$) | ($m_2$) |
| $m_1$ | $m_2$ | $w_2$ | $w_1$ |

Suppose MPDA was applied, from $w_1$'s point of view, she is clearly not happy with her assignment, since she prefers $m_2$ over $m_1$. Now we consider her misreported preference $w_1:m_2,\emptyset,m_1$ and re-apply MPDA, so we have

| | ($w_1$) | ($w_2$) |
| ------ | --------- | ------------------ |
| Step 1 | $m_1$ (X) | $m_2$ |
| Step 2 | | $m_1$(V), $m_2$(X) |
| Step 3 | $m_2$ | $m_1$ |

Since $m_2 P_{w_1}m_1$, $w_1$ benifits from misreporting, so MPDA is not strategyproof. We obtain the same result for WPDA, by misreporting $m_1$'s preference $m_1:w_1,\emptyset,w_2$ and re-applying WPDA:

| | ($m_1$) | ($m_2$) |
| ------ | --------- | ------------------ |
| Step 1 | $w_2$ (X) | $w_1$ |
| Step 2 | | $w_2$(V), $w_1$(X) |
| Step 3 | $w_1$ | $w_2$ |

(Since $w_1 P_{m_1}w_2$, $m_1$ benifits from misreporting, so WPDA is not strategyproof.)

***Theorem***: In marraige market, there does not exist a stable and strategyproof mechanism.

Using the previous example, there are only two stable matchings in the original market: either $\mu_1(m_1)=w_1, \mu_1(m_2)=w_2$ or $\mu_2(m_1)=w_2,\mu_2(m_2)=w_1$. (All the other matchings are not stable.)
Let $\psi$ be SP and stable, and selects $\mu_1$ in the original market, we consider $P'_{w_1}:m_2,\emptyset,m_1$ and all others report their true preferences. Then in market $(P'_{w_1},P_{-w_1})$, there is a unique stable matching $\mu_2$. Since $\psi$ is stable and $\mu_2$ is the unique stable matching in $(P'_{w_1},P_{-w_1})$, $\psi$ must select $\mu_2$. However, due to the preference relationship $$\psi_{w_1}(P'_{w_1},P_{-w_1}) P_{w_1}\psi_{w_1}(P),$$ any stable and strategyproof mechanism cannot select $\mu_1$ in the original market.

Likewise, we adopt the similar argument to $\mu_2$. Let $\varphi$ be the stable and SP mechanism that selects $\mu_2$ in the original market, we consider $P'_{m_1}:w_1,\emptyset,w_2$ (*preference truncation*, all others report their true preferences) Then, in market $(P'_{m_1},P_{-m_1})$, there is a unique stable matching $\mu_1$. Since $\varphi$ is stable and $\mu_1$ is the unique stable matching in $(P'_{m_1},P_{-m_1})$, $\varphi$ must select $\mu_1$. However, due to the preference relationship $$\varphi_{m_1}(P'_{m_1},P_{-m_1}) P_{m_1}\varphi_{m_1}(P),$$ any stable and strategyproof mechanism cannot select $\mu_2$ in the original market. Therefore, there is no stable and SP mechanism for this marriage market. (c)

**Remark**: We can extend this result to larger marriage market, since nothing changes if these four agents are embedded in a larger case without changing their preferences.

> Can we find a stable mechanism which cannot be manipulated by a man/woman?
> Guess: If there is, then it might be MPDA/WPDA.

***Theorem***: Man-proposing/woman-proposing DA is strategy-proof for men/women. (A mechanism is SP for men if no man can benefit from misreporting in any problem)

To prove this theorem, we use the following lemma:

**Lemma** (**Blocking lemma**): Let $\mu$ be any matching and $\hat{M}\subset M$ be the set of men who prefer $\mu$ to $\mu_M$(MPDA matching), then their is a pair $(m,w)$ which blocks where $m\notin\hat{M}$ and $w\in\mu(\hat{M}):=\bigcup_{m\in\hat{M}}\mu(m)$ (If a man can benefit by misreporting under MPDA, the matching from which he benefits cannot be stable)
*Proof*: Let $\mu(\hat{M})=\bigcup_{m\in\hat{M}}\mu(m)$ and $\mu_M(\hat{M})=\bigcup_{m\in\hat{M}}\mu_M(m)$ be the collection of women matched to men in $\hat{M}$ by $\mu$ and $\mu_M$ respectively, we consider the following two cases:
1. $\underline{\mu(\hat{M})\neq\mu_M(\hat{M})}$: there exists $w:=\mu(m')$ such that $m'=\mu(w)\in\hat{M}$ but $\mu_M(w)\notin\hat{M}$. By definition of $\hat{M}$, we have $wP_{m'}\mu_M(m')$. Now let $m=\mu_M(w)$, if $m'P_wm=\mu_M(w)$, then $(m',w)$ blocks $\mu_M$ (hence cannot be the case because $\mu_M$ has no blocking pair). So we have $mP_wm'=\mu(w)$[1] with $m=\mu_M(w)\notin\hat{M}$.
We know that $\mu_M(m)=w$ but $\mu(m)\neq w=\mu(m')$, because $w=\mu_M(m)P_m\mu(m)$. This implies that $\mu_M(m)P_m\mu(m)$[2]. Combining [1] and [2] yields a blocking pair $(m,w)$ of $\mu$.

2. $\underline{\mu(\hat{M})=\mu_M(\hat{M})}$: If $w\in\mu(\hat{M}):=\hat{W}$, then $w\in\mu_M(\hat{M})$. By definition of $\hat{M}$, $\hat{m}:=\mu(w)\neq\mu_M(w):={m}$. We observe that **every woman in $\hat{W}$ rejects at least one man in $\hat{M}$, since she is preferred by at least one man $\hat{m}\in\hat{M}$ compared to $\mu_M$**. Let $w$ be the woman who receive the last proposal from an acceptable member of $\hat{M}$ in MPDA. (This means that no man in $\hat{M}$ is rejected afterwards)
Since all women in $\hat{W}$ have rejected acceptable men from $\hat{M}$, $w$ had some men engaged to her when she received this last proposal. Let $\bar{m}$ be the man who is rejected when $w$ received the last proposal. Notice that $\bar{m}\notin\hat{M}$; otherwise, $w$ would not be the last woman receiving a proposal from a man in $\hat{M}$. We claim that $(\bar{m},w)$ blocks $\mu$.
As $\bar{m}$ is the last man to be rejected by $w$, so she must have rejected $\mu(w)$ before rejecting $\bar{m}$, and $\bar{m}P_w\mu(w)$. On the other hand, since $\bar{m}\notin\hat{M}\Rightarrow\mu_M(\bar{m})R_\bar{m}\mu(\bar{m})$ and $w$ rejected $\bar{m}$ under MPDA (implies that $wP_\bar{m}\mu_M(\bar{m})$), we obtain $wP_\bar{m}\mu(\bar{m})$, proving that $(\bar{m},w)$ blocks $\mu$. (c)

***Theorem***: Let $P$ be a preference profile, then there is no set of men $\hat{M}$ and some preference profile ${P}'_\hat{M}$ such that all men in $\hat{M}$ prefer man-optimal stable matching under $\hat{P}=(P_{-\hat{M}},P'_\hat{M},P_W)$ to man-optimal stable matching under $P$.
*Remark*: Let $\varphi$ be man-proposing DA and $\hat{M}=\{m\}$, then matching by MPDA under $P$ is preferred to matching by MPDA under $\hat{P}$: $$\varphi(P)[m]P_m\varphi(P_{-m},P'_m,P_W)[m].$$
***Proof***: Let $\hat{\mu}_M$ be the man-optimal stable matching under $\hat{P}$, and $\mu_M$ be the man-optimal stable matching under ${P}$, we suppose that each man in $\hat{M}$ prefers $\hat{\mu}_M$ to $\mu_M$. By **blocking lemma** there is a blocking pair $(m,w)$ of $\hat{\mu}_M$ under $P$ and $m\notin\hat{M}$, Due to the same preference $$ P_w=\hat{P}_w,\ P_m=\hat{P}_m\Rightarrow w \hat{P}_m\hat{\mu}_M(m),\ m\hat{P}_w\hat{\mu}_M(w),$$ this means that $(m,w)$ blocks $\hat{\mu}_M$ under $\hat{P}$, so $\hat{\mu}_M$ is not stable under $\hat{P}$.
> Application: *mentor-mentee matching/dating apps/babysitting matching*

# Medical Matching Market
We study the medical matching problems, which consist of
1. a finite set of doctors $D=\{d_1,d_2,\cdots,d_n\}$
2. a finite set of hospitals $H=\{h_1,h_2,\cdots,h_m\}$
3. Each hospital $h$ has a **capacity** denoted by $q_h$
4. Each doctor can be matched with at most one hospital
5. Each doctor $d$ has **strict preference order** over $H\cup\emptyset$, denoted by $P_d$
6. Each hospital $h$ has strict preference order over the subsets of $D$ denoted by $P_h$ (preference over the power set $2^D$ with sets whose cardinality do not exceed $q_h$)
7. We assume that the hospital's preference $P_h$ is **responsive**: for any subset of doctors $\hat{D}\subset D$ (with its cardinality does not exceed the capacity $|\hat{D}|<q_h$) and two doctors $d,d'\notin\hat{D}$
- $\hat{D}\cup\{d\}P_h\hat{D}\Leftrightarrow dP_h\emptyset$
- $\hat{D}\cup\{d\}P_h\hat{D}\cup\{d'\}\Leftrightarrow dP_hd'$

**Example**: Consider a (individual) preference over a set of doctors $\{d_1,d_2,d_3,d_4\}$: $d_1P_hd_2P_hd_3P_hd_4$. Under responsiveness assumption, we can show that $$\{d_1,d_2\}P_h\{d_1,d_3\},\ \{d_1,d_2\}P_h\{d_3,d_4\}.$$
By choosing $\hat{D}=\{d_2\},\{d_3\}$ and adding, we further derive the preference $$\{d_1,d_2\}P_h\{d_3,d_2\},\ \{d_2,d_3\}P_h\{d_4,d_3\}.$$

**Remark**: If the preference is represented by the utility $U_h$ and suppose $U_h$ possesses the additive property $$U_h(\bar{D})=\sum_{d\in\bar{D}}U_h(d),$$ the preference $P_h$ reflects only the individual ranking $U_h(d_1)>U_h(d_2)>U_h(d_3)>U_h(d_4)$, not necessarily "group" preference. To see this, we consider the following two sets of utilities

| $d_1$ | $d_2$ | $d_3$ | $d_4$ |
|:--------------:|:-------------:|:-------------:|:-------------:|
| $U_h(d_1)=100$ | $U_h(d_2)=60$ | $U_h(d_3)=50$ | $U_h(d_4)=1$ |
| $U_h(d_1)=100$ | $U_h(d_2)=60$ | $U_h(d_3)=50$ | $U_h(d_4)=20$ |

The first set indicates that $U_h(\{d_2,d_3\})=110>U_h(\{d_1,d_4\})=101$, but the relationship is reversed in consideration of the second one $U_h(\{d_2,d_3\})=110<U_h(\{d_1,d_4\})=120$.

A **matching** in this market is a function $\mu:H\cup D\rightarrow H\cup D\cup\emptyset$, such that
1. for each $d\in D$, $\mu(d)\in H\cup\emptyset$
2. for each $h\in H$, $\mu(h)\subseteq D\cup\emptyset$ and $|\mu(h)|\leq q_h$.
3. $\mu(d)=h\Leftrightarrow d\in\mu(h)$

**Definition**: a matching $\mu$ is **individually rational** (IR) if
1. for each $d\in D$, $\mu(d)R_d\emptyset$
2. for each $h\in H$, $\mu(h)R_h\emptyset$.

Furthermore, a pair $(d,h)$ **block**s a matching $\mu$ if
1. $hP_d\mu(d)$
2. there exists a subset $\tilde{D}\subseteq\mu(h)\cup\{d\}$, which contains $d$ such that $\tilde{D}P_h\mu(h)$
The construction of such $\tilde{D}$ can be either by (1)adding $d$ to $\mu(h)$ without kicking outsomeone, or (2) by replacing some doctors in $\mu(h)$ with $d$. Under responsiveness, the former indicates $dP_h\emptyset$, while the latter says there exists at least one $d'\in\mu(h)$ sucht that $dP_hd'$.

A matching is said **stable** it is individually rational and there is no blocking pair.

**Example**: Let $q_{h_1}=2, q_{h_2}=1$, we consider the following preferences and matchings

| ${d_1}$ | ${d_2}$ | ${d_3}$ | | ${h_1}$ | ${h_2}$ |
| ------- | ------- | ------- | --- | ------- | ------- |
| ${h_1}$ | ${h_1}$ | ${h_1}$ | | ${d_1}$ | ${d_1}$ |
| ${h_2}$ | ${h_2}$ | ${h_2}$ | | ${d_2}$ | ${d_3}$ |
| | | | | ${d_3}$ | ${d_2}$ |

1. $\mu_1(d_1)=h_1,\mu_1(d_2)=h_2,\mu_1(d_3)=\emptyset$: $(d_2,h_1),(d_3,h_1)$ and $(d_3,h_2)$ are blocking pairs.
2. $\mu_2(d_1)=h_1,\mu_2(d_2)=h_2,\mu_2(d_3)=h_1$: since $h_1P_{d_2}\mu_2(d_2)=h_2$ and $\{d_1,d_2\}P_{h_1}\{d_1,d_3\}=\mu_2(h_1)$, $(d_2,h_1)$ blocks $\mu_2$.
3. $\mu_3(d_1)=h_1,\mu_3(d_2)=h_1,\mu_3(d_3)=h_2$: stable

**Example**: in this example, we illustrate that irresponsive preference may lead to non-existence of stable matching. We consider the previous two-hospital and three-doctor example with the following preference (responsiveness is violated)

| ${d_1}$ | ${d_2}$ | ${d_3}$ |
| ------- | ------- | ------- |
| ${h_2}$ | ${h_1}$ | ${h_1}$ |
| ${h_1}$ | ${h_2}$ | ${h_2}$ |

| $h_1$ | $h_2$ |
|:-------------:|:-----------:|
| $\{d_1,d_3\}$ | $d_3$ |
| $\{d_1,d_2\}$ | $d_1$ |
| $d_1$ | $d_2$ |
| $d_2$ | $\emptyset$ |
| $d_3$ | |
| $\emptyset$ | |

We first observe that under any stable matching, $d_1$ and $d_3$ should be matched with some hospital. ($d_2$ undetermined) If any one of them is not matched, either $(d_1,h_1)$ or $(d_3,h_2)$ would form a blocking pair. We analyze the following scenarios:
1. If $\mu(d_1)=h_1$ and $\mu(d_3)=h_2$, then $(d_2,h_1)$ and $(d_3,h_1)$ are the blocking pair.
2. If $\mu(d_3)=h_1$ and $\mu(d_1)=h_2$, then $(d_2,h_1)$ is the blocking pair.
3. If $\mu(h_1)=\{d_1,d_3\}$ and $\mu(d_2)=\emptyset$, then $(d_1,h_2)$ and $(d_2,h_2)$ are the blocking pair.
4. If $\mu(h_1)=\{d_1,d_3\}$ and $\mu(h_2)=d_2$, then $(d_1,h_2)$ is the blocking pair.
5. If $\mu(h_1)=\{d_1,d_2\}$ and $\mu(h_2)=d_3$, then since $\{d_1,d_3\}P_{h_1}\{d_1,d_2\}$, $(d_3,h_1)$ is the blocking pair.
6. If $\mu(h_1)=\{d_2,d_3\}$ and $\mu(d_2)=d_1$, then since $\emptyset P_{h_1}\{d_2,d_3\}$, this is not individually rational.

Exercise:
1. Doctor/Hospital proposing DA
2. Affirmative action in politics: reserve seats for minority (college admission)

## Solution Mechanism
### Doctor-Proposing DA
1. Every doctor $d$ propose to her most preferred hospital.
2. Every hospital $h$ consider its applicant and tentatively up to $q_h$ doctors one by one according to $P_h$ (preference over individual doctors) The rest are rejected.
3. (General step) Every doctor $d$ proposes to her most preferred hospital which has not rejected her yet, while the hospital do the same (as in step 2).
### Hospital-Proposing DA
1. Every hospital $h$ propose to its most preferred $q_h$ doctors under $P_h$.
2. Every doctor either tentatively accept her most preferred offers she receives and rejects the rest.
3. (General step) Every hospital propose to its most preferred $q_h$ doctors who have not reject it, while the doctors take the same action.

**Example:**
We consider six doctors and four hospitals with the following preferences:
| $d_1$ | $d_2$ | $d_3$ | $d_4$ | $d_5$ | $d_6$ |
| ----- | ----- | ----- | ----- | ----- | ----- |
| $h_1$ | $h_2$ | $h_4$ | $h_2$ | $h_4$ | $h_2$ |
| $h_2$ | $h_3$ | $h_2$ | $h_1$ | $h_2$ | $h_1$ |
| $h_3$ | $h_1$ | $h_1$ | $h_3$ | $h_1$ | $h_4$ |
| $h_4$ | $h_4$ | $h_3$ | $h_4$ | $h_3$ | $h_3$ |

| $P_{h_1}$ | $P_{h_2}$ | $P_{h_3}$ | $P_{h_4}$ |
|:---------:|:---------:|:---------:|:---------:|
| $d_5$ | $d_1$ | $d_1$ | $d_6$ |
| $d_3$ | $d_3$ | $d_2$ | $d_1$ |
| $d_4$ | $d_2$ | $d_3$ | $d_4$ |
| $d_2$ | $d_4$ | $d_4$ | $d_2$ |
| $d_1$ | $d_5$ | $d_5$ | $d_3$ |
| $d_6$ | $d_6$ | $d_6$ | $d_5$ |

Suppose $q_{h_1}=1=q_{h_3}$ and $q_{h_2}=2=q_{h_4}$, we run the doctor-proposing and hospital-proposing DA
| | $h_1$ | $h_2$ | $h_3$ | $h_4$ |
| ------ | ----------------- | -------------------------- | ----- | -------------------------- |
| Step 1 | $d_1$ | $d_2$(V),$d_4$(V),$d_6$(X) | | $d_3$,$d_5$ |
| Step 2 | $d_1$(V),$d_6$(X) | $d_2$,$d_4$ | | $d_3$,$d_5$ |
| Step 3 | $d_1$ | $d_2$,$d_4$ | | $d_3$(V),$d_5$(X),$d_6$(V) |
| Step 4 | $d_1$ | $d_2$(V),$d_4$(V),$d_5$(X) | | $d_3$,$d_6$ |
| Step 5 | $d_1$(X),$d_5$(V) | $d_2$,$d_4$ | | $d_3$,$d_6$ |
| Step 6 | $d_5$ | $d_1$(V),$d_2$(V),$d_4$(X) | | $d_3$,$d_6$ |
| Step 7 | $d_4$(X),$d_5$(V) | $d_1$,$d_2$ | | $d_3$,$d_6$ |
| Step 8 | $d_5$ | $d_1$,$d_2$ | $d_4$ | $d_3$,$d_6$ |

| | $d_1$ | $d_2$ | $d_3$ | $d_4$ | $d_5$ | $d_6$ |
| ------ | ----------------------- | ----- | ----- | ----- | ----- | ----- |
| Step 1 | $h_2$,$h_3$(X),$h_4$(X) | | $h_2$ | | $h_1$ | $h_4$ |
| Step 2 | $h_2$ | $h_3$ | $h_2$ | $h_4$ | $h_2$ | $h_1$ |

We note that the outcome does not distinguish positions in the hospitals, so we extend the example by constructing a "copy economy." In particular, we split each hospital into $q_h$ copies. Moreover, we modify the preference as following:
- If $hP_d\bar{h}$ then every copy of $h$ is preferred by $d$ to every copy of $\bar{h}$. Furthermore, within copies of the same hospital, a fixed order for all doctors is chosen. (Need a tie-breaking setup)
- For every hospital $h$, the copies rank the doctors in the same order with $h$.

Denote the modified preference by $\tilde{P}_H$ and $\tilde{P}_D$ and the reformulated market by $(D,\tilde{H},\tilde{P}_D,\tilde{P}_H)$. Under this formulation, the outcome matching $\tilde{\mu}$ produced by the doctor-proposing DA will be stable in $(D,\tilde{H},\tilde{P}_D,\tilde{P}_H)$. We then recover the matching $\mu$ (in the original medical market) by: assigning $\mu(d)=h$ if $\tilde{\mu}(d)$ is a copy of hospital $h$.
## Properties of Many-to-One Matchings
> Is $\mu$ stable under $(D,H,P_H,P_D)$?

If there is a blocking pair $(d,h)$ under $\mu$ in $(D,H,P_D,P_H)$, then there exists some $d'\in\mu(h)$ such that $dP_hd$, and also $hP_d\mu(d):=\bar{h}$. There also exists a copy of $h$ (say $h'$) such that $$\tilde{\mu}(d')=h'\Rightarrow h'\tilde{P}_d\tilde{\mu}(d)=\bar{h}'\text{ and that }d\tilde{P}_{h'}d'.$$ These mean that $(d,h')$ blocks $\tilde{\mu}$ under $(D,\tilde{H},\tilde{P}_D,\tilde{P}_H)$, leading to a contradiction.
(Exercise: stability proof of doctor-proposing DA)

**Remark**: by considering every seat of a hospital as an individual hospital, we can transform hospital-doctor problem to one-to-one marriage problem. However, many-to-one matching does not inherit all the merits from one-to-one matching.
**Theorem**: When hospital preferences are responsive, then there always exist at least one stable matching in a hospital-doctor matching problem.
(Proof by transformation above)
Properties

| | One-to-one | Many-to-one |
| -------------- | -------------------------------------- | -------------------------------------------------------------- |
| Optimality | Man-proposing DA is man-optimal stable | Hospital/doctor-proposing DA is hospital/doctor-optimal stable |
| Strategy-proof | Man-proposing DA is man-strategyproof | doctor-proposing DA is doctor-strategyproof |

**Example**: In this example, we illustrate that hospital-proposing DA is **NOT** hospital-strategyproof. Particularly, we consider $H=\{h_1,h_2,h_3\}$ $D=\{d_1,d_2,d_3,d_4\}$, hospital capacities $q_{h_1}=2,q_{h_2}=1=q_{h_3}$, and their preferences
| $d_1$ | $d_2$ | $d_3$ | $d_4$ | $P_{h_1}$ | $P_{h_2}$ | $P_{h_3}$ |
| ----- | ----- | ----- | ----- |:---------:|:---------:|:---------:|
| $h_2$ | $h_1$ | $h_1$ | $h_1$ | $d_1$ | $d_2$ | $d_4$ |
| $h_1$ | $h_2$ | $h_2$ | $h_3$ | $d_2$ | $d_1$ | $d_1$ |
| $h_3$ | $h_3$ | $h_3$ | $h_2$ | $d_3$ | $d_3$ | $d_2$ |
| | | | | $d_4$ | $d_4$ | $d_3$ |

Applying hospital-proposing DA yields

| | $d_1$ | $d_2$ | $d_3$ | $d_4$ |
| ------ | ----------------- | ----------------- | ----- | ----- |
| Step 1 | $h_1$ | $h_1$(V),$h_2$(X) | | $h_3$ |
| Step 2 | $h_1$(X),$h_2$(V) | $h_1$ | | $h_3$ |
| Step 3 | $h_2$ | $h_1$ | $h_1$ | $h_3$ |

However, when $h_1$ misreport its preference by $d_1,d_3,d_2,d_4$, hospital-proposing DA yields

| | $d_1$ | $d_2$ | $d_3$ | $d_4$ |
| ------ | ----- | ----- | ----- | ----- |
| Step 1 | $h_1$ | $h_2$ | $h_1$ | $h_3$ |

In conclusion, when $h_1$ misreports, the outcome matching $\{d_1,d_3\}$ is better than $\{d_2,d_3\}$, which is the outcome matching when $h_1$ reports its true preference.
### NRMP Matching
1. Hospitals post their vacancies.
2. Doctors apply to vacancies
3. Interviews are held (T. Morill and Manjunath)
4. Rankings of doctors/hospitals are submitted
5. Apply DA algorithm and obtain matching

## Affirmative Actions
* Taking care of minorities
* Exclusive reserve for minorities

Extension: UNC affirmative action

# Reading Notes
## Resident Match
> Alvin E. Roth (2003) *The Origins, History and Design of the Resident Match*
### A glimpse on US internship market:
- Hospitals began trying to hire interns earlier than their competitors, so medical students often could only consider offers from one hospital at a time, without knowing their prospects at other hospitals.
- In 1945, there was an attempt to establish and enforce **a uniform time** for intern appointments, before which there's no release of information about students, but many hospitals thus often pressured students for immediate response.
- A clearinghouse was proposed to inheriting benefits of uniform appointment dates, while relieving pressure and congestion near deadline: rank-order lists would be submitted from students and hospitals, so as to produce a matching.
### Solution Algorithms
* Boston pool algorithm (equivalent to DA) produces stable outcomes

## Interview Hoarding
> V. Manjunath and T. Morrill 2023 *Interview Hoarding*

If doctors can accept more interviews, but hospitals do not increase the number of interviews they offer, then no doctor who would have matched in the setting with more limited interviews is better off and many doctors are potentially harmed.
# ECG 702 Notes
In the first semester, we study more about individual optimization and profit maximization. In these problems, some elements are taken as given. Specifically, in utility max, prices are given and we seek "partial" equilibrium. In this semester, we focus on "general" equilibrium under a simple model.
## Pure Exchange Economy
We consider a static environment with the following elements:
- Agent: individuals or households indexed by $i=1,\cdots,I<\infty$.
- Goods: $L$ goods indexed by $l=1,\cdots,L<\infty$

Agents are characterized by:
1. **Consumption Sets** $X\equiv\mathbb{R}^L$
2. **Preference** over consumption bundle, which are represented by individual utility functions $u_i:X\rightarrow\mathbb{R},\ \forall i$. (assumed to be continuous, increasing and semi-quasi concave)
3. **Endowments**: $e_i\in\mathbb{R}^L_{++}$
4. Agents have **competitive behavior**: they take prices as "given," (their indicidual actions cannot affect prices), and are able to buy and sell every quantities of good they want (no fraction)

*Definition*: **Allocation** is a list $x=(x_1,x_2,\cdots,x_I)$, where $x_i$ denotes the consumption bundle for $i$-th agent. $x$ is said to be $feasible$ if it does not exceed the endowment: $$\sum_{i=1}^Ix_i\leq\sum_{i=1}^I e_i$$

*Definition*: **Pareto optimality** of a feasible allocation means