English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the chore division problem where a set of agents needs to divide aset of chores (bads) among themselves fairly and efficiently. We assume thatagents have linear disutility (cost) functions. Like for the case of goods,competitive division is known to be arguably the best mechanism for the bads aswell. However, unlike goods, there are multiple competitive divisions with verydifferent disutility value profiles in bads. Although all competitive divisionssatisfy the standard notions of fairness and efficiency, some divisions aresignificantly fairer and efficient than the others. This raises two importantnatural questions: Does there exist a competitive division in which no agent isassigned a chore that she hugely dislikes? Are there simple sufficientconditions for the existence and polynomial-time algorithms assuming them?  We investigate both these questions in this paper. We show that the firstproblem is strongly NP-hard. Further, we derive a simple sufficient conditionfor the existence, and we show that finding a competitive division is PPAD-hardassuming the condition. These results are in sharp contrast to the case ofgoods where both problems are strongly polynomial-time solvable. To the best ofour knowledge, these are the first hardness results for the chore divisionproblem, and, in fact, for any economic model under linear preferences.

Dividing Bads is Harder than Dividing Goods: On the Complexity of Fair and Efficient Division of Chores