pipette
ENEnglish

Maximin share allocations for two types of items

Yu Chen, Kai Jie Wong, Xiaorui Zhang

Preprint

En palabras de los autores

We study the fair allocation of indivisible items among agents with additive valuations (or costs) using the fairness notion of maximin share (MMS). Since MMS allocations do not always exist when , one direction in the literature has been to identify special classes of instances in which exact MMS allocations can be guaranteed. We show that, when items can be divided into two types of chores, MMS allocations always exist and can be computed in polynomial time using a novel geometric approach inspired by prior work in job scheduling. We further discuss how our technique extends to instances with two types of goods, as well as mixed instances consisting of one type of objective good and one type of objective chore.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 15 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: A preliminary version was presented at the Fourth IJCAI Workshop on Computational Fair Division [Aug 2026]