Fair Division: Asymmetry, Dynamics, and Constraints

Abstract

Fair division studies how to fairly allocate items to a group of agents with heterogeneous preferences, which has been a hot topic in the research fields of computer science, economics, and mathematics. This thesis presents the results of fair division with a focus on asymmetry, constraints, and dynamics in four parts.

In Chapter 3, we consider one novel fairness definition named maximin-aware (MMA) in the chores setting. We first generalize MMA and its relaxations to the asymmetric setting when the items are chores. Then, we build a clear relationship graph between MMA-related notions and other classic fairness concepts. Finally, we design polynomial time algorithms to approximate them.

In Chapter 4, we propose a novel restricted setting where items are distributed in multiple regions, and each agent can only pick items from one region. In this setting, we consider two kinds of fairness concepts: envy-based and share-based. On the negative side, we show some hardness and inapproximability results about the notions above. On the positive side, we propose several algorithms to approximate them.

In Chapter 5, we study the envy-based notion - EFX in graphs where the vertices and edges represent agents and items, respectively. We extend the previous work on goods setting to the mixed one and provide an almost complete landscape of this problem, including hardness and existence results with respect to different variants of EFX.

In Chapter 6, we focus on online indivisible items allocation, expanding on the classic offline setting. In particular, we explore this problem where valuation functions are not restricted to binary ones and adopt envy-based and share-based notions. For two kinds of notions, we present a series of positive results regarding the existence of fair and efficient allocations. Additionally, we complement our results by constructing some counterexamples to establish our results as among the best guarantees possible.

Date of Award	11 Sept 2025
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Minming LI (Supervisor)