7 papers
MMS Allocation for Chores with Online Agent Arrivals
Haolong Li, Zehan Lin, Huahua Miao +1
We study the fair allocation of indivisible chores to agents with subadditive cost functions arriving online in an arbitrary order. Upon an agent's arrival, we are informed…
Non-Existence of PMMS Allocations and a -PMMS Guarantee for Additive Chores
Xiaohui Bei, Zehan Lin, Shengxin Liu +2
We study pairwise maximin share (PMMS) fairness for indivisible items with additive preferences. We give a polynomial-time reduction from chores to goods that preserves the existen…
Comparison-Based Fair Division of Indivisible Chores
Zehan Lin, Shengxin Liu, Biaoshuai Tao +1
We investigate the query complexity of fairly allocating indivisible chores among agents with additive cost functions. We depart from the standard cardinal model and assume…
Almost Envy-Freeness for Additive Mixed Manna with Entitlements: Deterministic and Randomized Guarantees
Zehan Lin, Shengxin Liu, Biaoshuai Tao +1
We investigate the fair allocation of indivisible items among agents with asymmetric entitlements in mixed manna settings, where the items consist of both goods and chores. For add…
Non-Existence of EFX Chore Allocations for Monotone Cost Functions with Binary Marginals
Zehan Lin, Shengxin Liu, Biaoshuai Tao +1
We study the existence of envy-free up to any item (EFX) allocations of indivisible chores when agents have monotone cost functions with binary marginals. For indivisible goods, th…
Allocating Chores with Restricted Additive Costs: Achieving EFX, MMS, and Efficiency Simultaneously
Zehan Lin, Xiaowei Wu, Shengwei Zhou
In a web-based review platform, papers from various research fields must be assigned to a group of reviewers. Each paper has an inherent cost, which represents the effort required…
Approximately EFX and PO Allocations for Bivalued Chores
Zehan Lin, Xiaowei Wu, Shengwei Zhou
We consider the computation for allocations of indivisible chores that are approximately EFX and Pareto optimal (PO). Recently, Garg et al. (2024) show the existence of -EFX and…