Seminars

View all Seminars  |  Download ICal for this event

Algorithms for Achieving Fairness and Efficiency in Matching Problems

Series: Ph.D. Thesis Oral Examination

Speaker: Shivika Narang, Ph.D (Engg.) student Dept. of CSA

Date/Time: Jun 28 11:30:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Faculty Advisor: Prof. Y. Narahari

Abstract:
Matching problems arise in numerous practical settings. Fairness and efficiency are two desirable properties in most such real-world settings. This dissertation work presents new approaches and algorithms to identify fair and/or efficient matchings. The thesis is organised into two logical parts: two sided preferences and single sided preferences.


Part 1: Two Sided Preferences

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.

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 reasonable 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 preferences are 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. We show that the leximin optimal stable matching can be efficiently computed in the special case of two colleges.


Part 2: Single Sided Preferences

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 jointly 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.


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.