A Welfare Maximizing Mechanism in the House Allocation Problem

In the house allocation (or kidney donor) problem, the top trading cycle algorithm (TTCA) is shown to have many interesting properties, such as being dominant strategy incentive compatible (or strategy-proof), Pareto optimal, and core-stable (which is stronger than individual rationality). However, TTCA is not a social welfare maximizing mechanism. Hence, even though TTCA is dominant strategy incentive compatible, there may be tremendous efficiency loss. In this article, I provide an alternative mechanism that maximizes social welfare (which is stronger than Pareto optimality) and is core-stable but is not dominant strategy incentive compatible.

Although the mechanism I provide is not dominant strategy incentive compatible, if agents do not know the preferences of others, then it can be argued that agents have no incentive to misreport their types in certain mechanisms. One way of making this argument is to consider the probability that the mechanism makes an allocation decision that is less favorable when an agent falsely reports than when an agent truthfully reports his type, and if the probability is less than 50%, then agents do not misreport their types. I will not consider this argument in this article, and I assume that agents report their types truthfully (either by the argument above or by the argument that if agents do not know the preferences of others, they default to reporting truthfully).

Model of the House Allocation Problem

I briefly review the classic model of the house allocation problem, which can be found in the paper (Shapley & Scarf, 1974) and in textbooks such as (Nisan et al., 2007).

There are $n$ agents denoted by the set $N=\{1, \ldots, n\}$. Each agent $i \in N$ owns a unique house and has a strict preference ordering denoted as $\succ_i$ over all $n$ houses (i.e. for all houses $h_1$ and $h_2$, $h_1 \succ_i h_2$ if and only if agent $i$ strictly prefers house $h_1$ over $h_2$). An allocation is a vector $a$ whose $i$‘th component, $a_i$, is the number of the house assigned to agent $i$. An allocation is feasible if for all $i \neq j, a_i \neq a_j$. The set of all feasible allocations is denoted by $A$.

In order to analyze social welfare in this context, there needs to be a function that represents these preference orderings. Given an allocation $a \in A$, the rank of $a_i$ is defined by the function $r\left(a_i\right)=1+\left|\left\{x \in N \mid x \succ_i a_i\right\}\right|$. For example, if $n=2, a=(1,2)$ and $1 \succ_i 2$ for all $i$, then $r\left(a_1\right)=1$ and $r\left(a_2\right)=2$.

Given an allocation $a \in A$, a set $S$ of agents is called a blocking coalition (for $a$) if there exists a $z \in A(S)$ such that for all $i \in S, z_i \succcurlyeq_i a_i$ and for at least one $j \in S, z_j \succ_j a_j$. A blocking coalition can, by trading among themselves, receive homes that each strictly prefers (or is equivalent) to the home she receives under $a$, with at least one agent being strictly better off. The set of allocations that is not blocked by any subset of agents is called the core. This definition of the core is from (Nisan et al., 2007). If an allocation is in the core, then the allocation is individually rational.

$\textbf{Definition. Pareto Optimal}$

An allocation in the core is Pareto optimal if no other feasible allocation in the core can make one agent better off without making another agent worse off.

$\textbf{Definition. Maximizing Social Welfare}$

An allocation $a \in A$ in the core maximizes social welfare if for every allocation $a^{\prime} \in A$ in the core,

$\sum_{i=1}^n r\left(a_i\right) \leq \sum_{i=1}^n r\left(a_i^{\prime}\right).$

An allocation mechanism maximizes social welfare if for all agents $i \in N$ and preferences $\succ_i$, the allocation decision $a\in A$, in the core, maximizes social welfare.

For an example of why TTCA does not maximize social welfare, consider when the preferences of agents are $2 \succ_1 1 \succ_1 3,3 \succ_2 2 \succ_2 1$, and $3 \succ_3 1 \succ_3 2$. TTCA assigns each agent their own house and $r(1)+r(2)+r(3)=5$. However, consider another allocation. Agent 1 receives agent 2’s house, 2 receives 3’s house, and 3 receives 1’s house. This allocation yields $r(1)+r(2)+r(3)=4$, lower than the allocation given by TTCA.

The Social Welfare Maximizing Algorithm

I describe an algorithm that maximizes social welfare by minimizing the sum of agents’ ranks.

1. For each feasible allocation $a \in A$, compute $u(a):=\sum_{i=1}^n r\left(a_i\right)$. If the feasible allocation or set of allocations $a$ associated with the smallest $u(a)$ is in the core, then choose that allocation or randomly select an allocation (if there is a set of feasible allocations).

2. If the allocation (or allocations) is not in the core, select the next best alternative $a^{\prime} \in A \setminus \{ a \}$ such that $u(a^{\prime})$ is minimized and $a^{\prime}$ is in the core.

This algorithm can be implemented by creating a weighted bipartite graph and using the Hungarian algorithm to find the minimum weight. If the output or allocation is in the core, then we are done. If not, consider the next best allocation using the Hungarian algorithm.

$\textbf{Proposition.}$ The social welfare maximizing algorithm selects a Pareto optimal and individually rational allocation that is in the core.

$\textit{Proof}$. Suppose the algorithm chose an allocation $a$ in the core such that there exists another allocation $a'$ in the core where $u(a')<u(a)$. Then immediately there is a contradiction since step 2 of the algorithm chooses such an allocation.

To show that the algorithm chooses an allocation $a$ that is Pareto optimal, suppose that $a$ is not Pareto optimal. Then there exists another allocation in the core $a'$ such that $r\left(a'_i\right) \leq r\left(a_i\right)$ for all $i \in N$, and $r\left(a'_j\right)<r\left(a_j\right)$ for at least one $j \in N$. But then we have a contradiction since $u(a')<u(a)$, which implies that the algorithm does not select the allocation that minimizes $u$.

To show that the mechanism is individually rational, consider the definition of an allocation being in the core. If an allocation is in the core, then the singleton set only consisting of himself should not be a blocking coalition. This concludes the proof.

Next is a relationship between blocking coalitions (which defines what a core is) and the rank function. This proposition can help simplify the search space for allocations that are in the core.

$\textbf{Proposition.}$ Given an allocation $a \in A$, a set $S$ of agents is a blocking coalition (for $a$) if and only if there exists $z \in A(S)$ such that for every $i \in S, r\left(z_i\right) \leq r\left(a_i\right)$ and for at least one $j \in S, r\left(z_j\right)<r\left(a_j\right)$.

$\textit{Proof}$. Apply the definition of the rank function on the relation. Specifically, $\left|\left\{x \in N \mid x \succ_i z_i\right\}\right| \leq$ $\left|\left\{x \in N \mid x \succ_i a_i\right\}\right|$ if and only if $z_i \succcurlyeq_i a_i$ and $\left|\left\{x \in N \mid x \succ_i z_i\right\}\right|<\left|\left\{x \in N \mid x \succ_i a_i\right\}\right|$ if and only if $z_i \succ_i a_i$. Then, apply this equivalence to the definition of a blocking coalition.

Further research can be done to analyze the tradeoff between social welfare and incentive compatibility. If incentive compatibility is relaxed, how much welfare can be gained? Also, if the number of agents $n$ is large, then more research on using the characterization of blocking coalitions involving the rank function to simplify the search space can be done. Also, a characterization of agents’ preferences such that the social welfare maximizing algorithm and TTCA yield the same allocations can also be researched. For now, I stop here.

References

1. Shapley, L., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23–37.
2. Nisan, N., Roughgarden, T., Tardos, E., & Vazirani, V. V. (2007). Algorithmic Game Theory. Cambridge University Press.