Arpita Biswas, Rutgers University

Abstract

The problem of fair allocation of indivisible items becomes more challenging when certain item pairs conflict with each other, rendering those pairs incompatible while allocating them to the same agent. This problem setting finds its relevance in scenarios such as course allocation, where students (the agents) express preferences for courses (the items), and courses may possess conflicting schedules which is represented by an interval conflict graph. Additionally, courses have finite seat capacities, and students may have constraints on the number of courses they can enroll in. The goal is to obtain a fair and feasible allocation of items among the agents while ensuring that each allocated bundle constitutes an independent set within the interval conflict graph. While the problem is NP-hard for a general conflict graph, we devise efficient solutions when items are represented as intervals, that is, considering an interval conflict graph. In this talk, I’ll discuss various fairness notions, such as maximin fairness and almost envy freeness, that are pertinent to this problem setting and present solutions using a number of interesting techniques that are tailored to different assumptions on the agents’ preferences over a bundle of items.

See: https://theory.cs.rutgers.edu/theory_seminar