Equitable division of a path

Show simple item record

dc.contributor.author Misra, Neeldhara
dc.contributor.author Sonar, Chinmay
dc.contributor.author Vaidyanathan, P. R.
dc.contributor.author Vaish, Rohit
dc.date.accessioned 2021-02-05T14:54:03Z
dc.date.available 2021-02-05T14:54:03Z
dc.date.issued 2021-01
dc.identifier.citation Misra, Neeldhara; Sonar, Chinmay; Vaidyanathan, P. R. and Vaish, Rohit, "Equitable division of a path", arXiv, Cornell University Library, DOI: arXiv:2101.09794, Jan. 2021 en_US
dc.identifier.uri http://arxiv.org/abs/2101.09794
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/6267
dc.description.abstract We study fair resource allocation under a connectedness constraint wherein a set of indivisible items are arranged on a path and only connected subsets of items may be allocated to the agents. An allocation is deemed fair if it satisfies equitability up to one good (EQ1), which requires that agents' utilities are approximately equal. We show that achieving EQ1 in conjunction with well-studied measures of economic efficiency (such as Pareto optimality, non-wastefulness, maximum egalitarian or utilitarian welfare) is computationally hard even for binary additive valuations. On the algorithmic side, we show that by relaxing the efficiency requirement, a connected EQ1 allocation can be computed in polynomial time for any given ordering of agents, even for general monotone valuations. Interestingly, the allocation computed by our algorithm has the highest egalitarian welfare among all allocations consistent with the given ordering. On the other hand, if efficiency is required, then tractability can still be achieved for binary additive valuations with interval structure. On our way, we strengthen some of the existing results in the literature for other fairness notions such as envy-freeness up to one good (EF1), and also provide novel results for negatively-valued items or chores
dc.description.statementofresponsibility by Neeldhara Misra, Chinmay Sonar, P. R. Vaidyanathan and Rohit Vaish
dc.language.iso en_US en_US
dc.publisher Cornell University Library en_US
dc.subject Computer Science en_US
dc.subject Game Theory en_US
dc.title Equitable division of a path en_US
dc.type Pre-Print en_US
dc.relation.journal arXiv

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account