Fairness and Efficiency in Allocation and Scheduling

The field of allocation and scheduling is moving towards developing more efficient and fair algorithms for various problems. Researchers are exploring new approaches to achieve better trade-offs between resource efficiency and fairness in networked systems, fair allocation of resources, and scheduling tasks. Notably, there is a growing interest in studying fairness notions such as maximin share fairness and envy-free allocations. Recent works have made significant progress in developing approximation algorithms for these problems, pushing the frontier on the maximin share fairness and achieving constant-factor approximations for weighted maximin share.

Some noteworthy papers in this area include: Fair Minimum Labeling, which introduces a new problem of designing a minimum-cost temporal edge activation plan that ensures each group of nodes in a network has sufficient access to a designated target set. Constant Weighted Maximin Share Approximations for Chores, which presents the first constant-factor approximate WMMS algorithm, advancing the state of the art in weighted fair division. A Fixed Point Framework for the Existence of EFX Allocations, which establishes a new approach to establishing the existence of EFX allocations through fixed point theorems and DC programming.

Sources

Reach together: How populations win repeated games

Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity

Bin Packing and Covering: Pushing the Frontier on the Maximin Share Fairness

Fairness in Repeated Matching: A Maximin Perspective

A Fixed Point Framework for the Existence of EFX Allocations

A Computer-Assisted Proof of the Optimal Density Bound for Pinwheel Covering

Constant Weighted Maximin Share Approximations for Chores

Built with on top of