Abstract

We consider the problem of allocating ? indivisible chores to ? agents with additive disvaluation (cost) functions. It is easy to show that there are picking sequences that give every agent (that uses the greedy picking strategy) a bundle of chores of disvalue at most twice her share value (maximin share, MMS, for agents of equal entitlement, and anyprice share, APS, for agents of arbitrary entitlement). Aziz, Li and Wu (2022) designed picking sequences that improve this ratio to 5/3 for the case of equal entitlement. We design picking sequences that improve the ratio to 1.733 for the case of arbitrary entitlement, and to 8/5 for the case of equal entitlement. (In fact, computer assisted analysis suggests that the ratio is smaller than 1.543 in the equal entitlement case.) We also prove a lower bound of 3/2 on the obtainable ratio when ? is sufficiently large.

Our results trivially imply that (for additive valuation over chores) in the arbitrary entitlement case, there always is an allocation that gives every agent at most 1.733???, and in the equal entitlement case, there always is a distribution over allocations that gives every agent at most 1.6??? ex-post, and at most the proportional share ex-ante. Neither of these implications were previously known to hold.

Time

2023-12-14  10:30 - 11:30   

Speaker

Xin Huang, Postdoc at Technion

Room

Room 308