An Algorithmic Framework for Approximating Maximin Share Allocation of Chores

Xin Huang · Pinyan Lu

49 citations0/0 files storedACM Conference on Economics and Computation (EC)

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Game Theory and Voting Systems Complexity and Algorithms in Graphs Optimization and Search Problems

Abstract

We consider the problem of fairly dividing m indivisible chores among n agents. The fairness measure we consider here is the maximin share. The previous best known result is that there always exists a 4/3-approximation maximin share allocation[3]. With our algorithm, we can always find a 11/9-approximation maximin share allocation for any instance. We also discuss how to improve the efficiency of the algorithm and its connection to the job scheduling problem. The full paper can be found at https://arxiv.org/abs/1907.04505.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 49 citations exist upstream.

References

1967Resource allocation and the public sector 2003Fair Division and Collective Welfare 2011The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes 2004On approximately fair allocations of indivisible goods 1948The problem of fair division 2016The Unreasonable Fairness of Maximum Nash Welfare 2000Cake-Cutting Algorithms: Be Fair if You Can.1998Cake-Cutting Algorithms

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.