We study the fair allocation of indivisible items to groups of agents from the perspectives of both the agents and a centralized allocator. In our setting, the centralized allocator aims to ensure that the allocation is fair both among the groups and between individual agents. This setting applies to many real-world scenarios, such as when a school administrator allocates resources (e.g., office spaces and supplies) to staff members within departments or when a city council allocates limited housing units to families in need across different communities. To ensure fairness between agents, we consider the classical notion of envy-freeness (EF). To ensure fairness among groups, we introduce the notion of centralized group equitability (CGEQ), which captures fairness for groups from the centralized allocator’s perspective. Because an EF or CGEQ allocation does not always exist in general, we consider their natural relaxations: envy-freeness to one item (EF1) and centralized group equitability up to one item (CGEQ1). For different classes of valuation functions of the agents and the centralized allocator, we show that allocations satisfying both EF1 and CGEQ1 always exist, and we design efficient algorithms to compute such allocations. We also consider the centralized group maximin share (CGMMS) from the centralized allocator's perspective as a group-level fairness objective with EF1 for agents, and present several results.

In an online fair allocation problem, a sequence of indivisible items arrives online and needs to be allocated to offline agents immediately and irrevocably. In our paper, we study the online allocation of either goods or chores. We employ popular fairness notions, including envy-freeness up to one item (EF1) and maximin share fairness (MMS) to capture fairness, and utilitarian social welfare (USW) to measure efficiency. For both settings of items, we present a series of positive results regarding the existence of fair and efficient allocations with widely studied classes of additive binary and personalized bi-valued valuation/cost functions. Furthermore, we complement our results by constructing counterexamples to establish our results as among the best guarantees possible.

We initiate the study of fair allocation with the set of divisible or indivisible items distributed in multiple regions. The key requirement is that each agent can only obtain items from one region. In this work, we consider two kinds of fairness concepts: envy-based notions including envy-freeness (EF) and envy-freeness up to one/any item (EF1/EFX), and share-based notions including proportionality (PROP) and proportionality up to one/any item (PROP1/PROPX). On the negative side, we show NP-hardness and inapproximability results about the aforementioned fairness notions. On the positive side, we propose several algorithms to compute the partial allocations that satisfy envy-based notions and allocations that approximate the above fairness notions.

The real-world deployment of fair allocation algorithms usually involves a heterogeneous population of users, which makes it challenging for the users to get complete knowledge of the allocation except for their own bundles. Recently, a new fairness notion, maximin-awareness (MMA) was proposed and it guarantees that every agent is not the worst-off one, no matter how the items that are not allocated to this agent are distributed. We adapt and generalize this notion to the case of indivisible chores and when the agents may have arbitrary weights. Due to the inherent difficulty of MMA, we also consider its up to one and up to any relaxations. A string of results on the existence and computation of MMA related fair allocations, and their connections to existing fairness concepts is given.