2022/11/02 by Haris Aziz, Jeremy Lindsay, Aziz, Haris +5 · 2 citations
Decision Sciences · Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #Decision-Making and Behavioral Economics #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2211.00879
openalex publication_date 2022/11/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of fair allocation of indivisible chores under additive valuations. We assume that the chores are divided into two types and under this scenario, we present several results. Our first result is a new characterization of Pareto optimal allocations in our setting, and a polynomial-time algorithm to compute an envy-free up to one item (EF1) and Pareto optimal allocation. We then turn to the question of whether we can achieve a stronger fairness concept called envy-free up any item (EFX). We present a polynomial-time algorithm that returns an EFX allocation. Finally, we show that for our setting, it can be checked in polynomial time whether an envy-free allocation exists or not.