Fairness and Efficiency in Allocation Problems

The field of allocation problems is witnessing significant developments, with a focus on fairness and efficiency. Researchers are exploring new notions of fairness, such as proportionality up to one good (PROP1) and local envy-freeness, and designing algorithms to achieve these fairness concepts. The study of fair division among groups of agents is also gaining traction, with results showing that efficient and fair allocations can be found for certain types of valuations and group structures. Furthermore, the development of approximation algorithms for fairness concepts like envy-freeness up to any good (EFX) is advancing the field. Noteworthy papers include: Computing Approximately Proportional Allocations of Indivisible Goods, which presents efficient algorithms for computing PROP1 allocations for non-additive valuations; Almost and Approximate EFX for Few Types of Agents, which shows the existence of approximate EFX allocations for any number of agents with a limited number of distinct valuations; and A New Relaxation of Fairness in Two-Sided Matching Respecting Acquaintance Relationships, which introduces the concept of local envy-freeness and analyzes its achievability in Pareto-efficient matchings.

Sources

Computing Approximately Proportional Allocations of Indivisible Goods: Beyond Additive and Monotone Valuations

Group Fair Matchings using Convex Cost Functions

Weighted Partition Vertex and Edge Cover

Fair Division Among Couples and Small Groups

The Multi-Stage Assignment Problem: A Fairness Perspective

Algorithms for Stable Roommate with Externalities

A New Relaxation of Fairness in Two-Sided Matching Respecting Acquaintance Relationships

Almost and Approximate EFX for Few Types of Agents

Built with on top of