Seminars

View all Seminars  |  Download ICal for this event

Algorithms for Individual and Collective Fairness Measures

Series: Ph.D. Thesis Colloquium

Speaker: Anand Krishna Ph.D (Engg.) student Dept. of CSA

Date/Time: May 19 16:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Faculty Advisor: Prof. Siddharth Barman and Prof. Y. Narahari

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. The algorithms presented in this thesis provide new tools to address fair allocation problems in practice and offer insights into the design of efficient procedures for resource allocation. This thesis is structured into two parts, each focusing on a distinct type of fairness measure: collective criteria and individual criteria.


Part-I: Collective Fairness

Algorithms for maximizing p-mean welfare

We propose a polynomial-time algorithm for allocating indivisible goods among agents with subadditive valuations. We consider p-mean welfare objectives, where the latter 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/8n 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

We present 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

We provide 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.