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

In this work, we revisit the problem of fairly allocating a number ofindivisible items that are located on a line to multiple agents. A feasibleallocation requires that the allocated items to each agent are connected on theline. The items can be goods on which agents have non-negative utilities, orchores on which the utilities are non-positive. Our objective is to understandthe extent to which welfare is inevitably sacrificed by enforcing theallocations to be fair, i.e., price of fairness (PoF). We study bothegalitarian and utilitarian welfare. Previous works by Suksompong [Discret.Appl. Math., 2019] and H\"ohne and van Stee [Inf. Comput., 2021] have studiedPoF regarding the notions of envy-freeness and proportionality. However, thesefair allocations barely exist for indivisible items, and thus in this work, wefocus on the relaxations of maximin share fairness and proportionality up toone item, which are guaranteed to be satisfiable. For most settings, we give(almost) tight ratios of PoF and all the upper bounds are proved by designingpolynomial time algorithms.

On the Price of Fairness of Allocating Contiguous Blocks