Algorithms for Achieving Fairness and Efficiency in Matching Problems

Abstract

Matching problems arise in numerous practical settings. Fairness and efficiency are two desirable properties in most such real world scenarios. This dissertation work presents new approaches and models for capturing and solving fairness issues in different practical settings and develops algorithms to identify fair and/or efficient matchings. The thesis is organised into two logical parts: one-sided preferences and two-sided preferences.

Part 1: One-Sided Preferences

Fair and Efficient Delivery

Motivated by the classical delivery problem, we introduce a novel model of fair division where delivery tasks must be fairly distributed among a set of agents. The delivery tasks are placed on the vertices of a given acyclic graph. The cost incurred by the agents is determined by the distance they travel from the hub where they start to service their assigned tasks. We study the existence of fair and efficient allocations of tasks to agents. We choose the fairness notions: EF1 and MMS and efficiency notions: Pareto optimality and Social optimality. We find that while all these notions can be satisfied independently, the only combination of fairness and efficiency that can always be guaranteed is MMS and PO. For the remaining combinations, we provide characterisations of the space of instances for which they can be achieved. We find that most of the relevant problems are NP-Hard. We provide an XP-algorithm which finds the different combinations of fairness and efficiency whenever they exist.

Repeated Matchings

We propose a novel repeated matching model where the valuations of agents may change with how often they have received an item in the past. We study achieving fairness and efficiency separately as well as in conjunctions in this setting. We find that optimizing for social welfare is NP-Hard for general valuations and tractable when the valuations are monotone with time. We also prove that maximizing for social welfare over the space of EF1 repeated matchings is NP-Hard. Further, we provide algorithms and non-existence results for EF1 and EFX repeated matchings in different settings.

Part 2: Two Sided Preferences

Fairness and Stability in Many-to-One Matchings

We seek to optimize a fairness measure over the space of stable many-to-one matchings, motivated by a college admissions setting. With leximin optimality as the fairness notion, we first show the intractability of this problem. We identify a minimal set of assumptions that makes this problem solvable in polynomial time. This requires that the agents on either side have the same ordinal rankings over the agents on the other side and that these must be strict. We show that on relaxing to weak rankings, the problem becomes APX-Hard. When we remove the ranking assumption but maintain strict preferences, the problem is NP-Hard. Additionally, we show that the leximin optimal stable matching can be efficiently computed in the special case of two colleges.

Incentive Compatibility in Stable Fractional Matchings

We investigate the existence of incentive compatible mechanisms that find stable fractional matchings. We show, for general settings, that no incentive compatible mechanism can be stable. We characterise the space of instances that have a unique stable fractional matching. We prove for this set of instances that any stable matching mechanism will be incentive compatible