Algortihms for Individual and Collective Fairness Measures

Abstract

The problem of fair allocation has been a central topic in economic theory, and the literature on fair division has provided fundamental insights on how to allocate resources among agents in a fair manner. By drawing upon existing literature, this thesis focuses on computational challenges that arise in different settings of fair-division problems. The thesis presents efficient algorithms, including approximation algorithms where applicable, for fair resource allocation by optimizing for different types of fairness measures. We also complement these algorithms by providing matching hardness results demonstrating the tightness of the obtained approximation guarantees. This thesis is structured into two parts, based on the criteria for measuring fairness: collective and individual.

Part-I: Collective Fairness

Algorithms for maximizing p-mean welfare The first contribution of this thesis is a polynomial-time algorithm for allocating indivisible goods among agents with subadditive valuations. We consider p-mean welfare objectives, that encompasses a range of welfare functions, including utilitarian social welfare, Nash social welfare, and egalitarian welfare. Our algorithm achieves an 8n-approximation ratio for the Nash social welfare objective, which is a significant improvement over the previously known approximation ratio of O(n log n). Moreover, for any given p, our algorithm computes an allocation with p-mean welfare at least 1 times the optimal. Our results hold for the wide range of subadditive valuations, including XOS and submodular valuations. We also show that our approximation guarantees are essentially tight for XOS valuations.

Maximizing Nash social welfare for fair coverage The second contribution of this thesis is a polynomial-time algorithm for maximizing Nash social welfare in coverage problems. We consider the problem of selecting T subsets of agents that achieve fair and efficient coverage while satisfying combinatorial constraints. We propose a valuation function based on the number of subsets that contain each agent, and design an algorithm that achieves an (18 + o(1))-approximation ratio for maximizing Nash social welfare in coverage instances. Our algorithm applies to instances where an FPTAS for weight maximization exists, and we complement our algorithmic result by proving that Nash social welfare maximization is APX-hard in coverage instances.

Part-II: Individual Fairness

Fair division using subsidy under dichotomous valuations The third contribution of this thesis is a subsidy-based algorithm for achieving envy- freeness in the allocation of indivisible goods among agents with dichotomous valuations. We show that it is possible to allocate goods among agents with dichotomous valuations in an envy-free manner with a per-agent subsidy of either 0 or 1, and such an envy-free solution can be computed efficiently in the standard value-oracle model. Our results hold for general dichotomous valuations, including non-additive and non-submodular valuations, and our subsidy bounds are tight, providing a linear improvement over the bounds known for general monotone valuations.

The results presented in this thesis provide new tools to address fair allocation problems in practice and offer insights into the design of efficient procedures for fair resource allocation.