Fair Allocation of Conflicting Courses under Additive Utilities

We investigate the problem of fair allocation of indivisible items when certain item pairs conflict, where conflicts are represented by an interval graph. In this setting, no two conflicting items may be allocated to the same agent. Our problem has practical applications specifically for course allocation where students are agents and course seats are items; courses may have conflicting schedules. We devise algorithms for finding fair, specifically envy-freeness up to one item (EF1), allocations of courses to students in the most general setting: when students have non-uniform, non-identical, additive utility functions. In this extended abstract, we provide one of the algorithms that finds a EF1 solution under identical utilities, implying that, for any course, all students have the same utility.