Prajakta Nimbhorkar

Harish Chandramouleeswaran, Prajakta Nimbhorkar, Nidhi Rathi

We study fair division of indivisible items under a variable input setting, where the set of agents or items may change over time. Starting from an arbitrary allocation, the goal is to restore envy-freeness up to one item (EF1) through item transfers while causing as little disruption as possible. We formalize this via `valid transfers' and introduce the EF1-Restoration problem. We give efficient algorithms for EF1-Restoration when agents have identical monotone valuations and the items are either all goods or all chores. In contrast, even for identical additive valuations, we prove that optimizing the number of valid transfers is NP-hard. For the stronger notion of EFX, we show that deciding whether EFX-Restoration admits any positive solution is weakly NP-hard for identical additive valuations. We also show that, unlike the pure goods and pure chores cases, EF1-Restoration may be impossible for mixed manna. For additive binary valuations, we prove that deciding whether EF1-Restoration is possible is NP-hard, and so is finding the minimum number of valid transfers when restoration is possible. We complement these hardness results with a polynomial-time algorithm for the subclass of additive binary valuations defined using multigraphs, introduced by Christodoulou et al. (EC 2023), when allocations are required to be orientations. Finally, for monotone binary valuations, we prove that deciding whether EF1-Restoration is possible is PSPACE-complete. Together, our results give a broad complexity landscape for restoring EF1 under variable inputs across several natural valuation classes.

Atasi Panda, Anand Louis, Prajakta Nimbhorkar

We study the probabilistic assignment of items to platforms that satisfies both group and individual fairness constraints. Each item belongs to specific groups and has a preference ordering over platforms. Each platform enforces group fairness by limiting the number of items per group that can be assigned to it. There could be multiple optimal solutions that satisfy the group fairness constraints, but this alone ignores item preferences. Our approach explores a `best of both worlds fairness' solution to get a randomized matching, which is ex-ante individually fair and ex-post group-fair. Thus, we seek a `probabilistic individually fair' distribution over `group-fair' matchings where each item has a `high' probability of matching to one of its top choices. This distribution is also ex-ante group-fair. Users can customize fairness constraints to suit their requirements. Our first result is a polynomial-time algorithm that computes a distribution over `group-fair' matchings such that the individual fairness constraints are approximately satisfied and the expected size of a matching is close to OPT. We empirically test this on real-world datasets. We present two additional polynomial-time bi-criteria approximation algorithms that users can choose from to balance group fairness and individual fairness trade-offs. For disjoint groups, we provide an exact polynomial-time algorithm adaptable to additional lower `group fairness' bounds. Extending our model, we encompass `maxmin group fairness,' amplifying underrepresented groups, and `mindom group fairness,' reducing the representation of dominant groups.'

Keshav Ranjan, Meghana Nasre, Prajakta Nimbhorkar

We consider the Hospitals/Residents (HR) problem in the presence of ties in hospital preferences. Among the three notions of stability, namely weak stability, strong stability, and super-stability, we focus on the notion of strong stability. Strong stability has many desirable properties, both theoretically and in practice; however, its existence is not guaranteed. In this paper, our objective is to optimally increase the quotas of hospitals to ensure that a strongly stable matching exists in the modified instance. We explore two natural optimization criteria: (i) minimizing the total capacity increase across all hospitals (MINSUM) and (ii) minimizing the maximum capacity increase for any hospital (MINMAX). We show that the MINSUM problem admits a polynomial-time algorithm. We also establish an analog of the well-known rural hospitals theorem [Gale & Sotomayor, 1985; Roth, 1986], adapted to the MINSUM augmentation setting. We consider a generalization of the MINSUM problem in which each hospital incurs a cost per unit increase in its quota. We show that the cost version of the MINSUM problem is NP-hard and inapproximable within any multiplicative factor, even if the costs are zero or one. For the MINSUM objective with a set of forced edges, we give a polynomial-time algorithm. In contrast to the above results for the MINSUM problem, we show that the MINMAX problem is NP-hard. When hospital preference lists have ties of length at most $\ell+1$, we give a polynomial-time algorithm that increases each hospital's quota by at most $\ell$, ensuring the resulting instance admits a strongly stable matching. Moreover, among all such augmentations, our algorithm outputs the best strongly stable matching from the residents' perspective.