Content area
Abstract
The issue of how to optimally allocate a set of indivisible goods among a group of agents who have preferences over them is a common question posed in the disciplines of operations research and economics. These types of problems are referred to as matching problems under preferences. In this dissertation, we extend the Capacitated House Allocation with Ties problem (also known as the Weighted Bipartite b- Matching problem) to include conflict constraints and precedence ordering among the set of agents (denoted as CHAT-C). In our application, the agents are military members, and the goods are duty station assignments.
Ideally, when solving these problems, we would like to use an optimality criterion known as a “fair”, or lexicographic minimum (leximin), matching. This criterion, which has close ties to the difference principle for distributive justice proposed by John Rawls, emphasizes the notion of fairness from a group perspective; the matching is only as good as the worst outcome for any agent. We also aim to minimize the degree of justified envy in the matching. This criterion emphasizes the notion of fairness from an individual perspective; no agent should prefer the assignment of another agent she has higher precedence than.
In the first part of our work, we propose an iterative integer programming algorithm that finds solutions to CHAT-C when agents have precedence, which we call the “fair-precedence” mechanism. Using the fair matching criterion, we show that our mechanism produces fairer matches for a group of agents than the serial dictatorship mechanism without causing a significant increase in justified envy among the agents. Furthermore, we investigate how our mechanism may mitigate bias within the precedence rankings against a subset of agents.
In the second part of our work, we consider a stochastic optimization variant of CHAT-C, which occurs in two stages. A match is constructed between the agents and goods in the first stage. In the second stage, a subset of the goods becomes unavailable, and the agents matched to those goods must be reassigned. Our objective is to find an initial matching such that its cost, plus the average associated cost of reassignments that may occur in the second stage, is minimized. We develop a novel variant of the sample average approximation technique for this problem that utilizes instance parameters to identify “important” second-stage scenarios which are likely to occur and significantly impact any high-quality, first-stage solution. In our studies, our algorithm quickly constructed solutions to the stochastic variant of CHAT-C that were within 5% of optimal for 67% of our problem instances and within 10% of optimal for 92% of our problem instances.
