ΑΙhub.org

Consider a large piece of land that is to be split in a fair manner among several farmers, who all have an equal entitlement to a share of this land. They all have different plans for their allotted pieces – growing a variety of crops, using the land as a pasture, or putting up a solar farm – so each of them has their own preferences over the land, depending on the type of soil, incline, access to water, etc. There may also be constraints on the shape of each individual piece: e.g., it is probably a bad idea to partition the land into pieces that are 800m long and 2m wide, even if such a partition is perfectly fair.

The problem of allocating the land in a fair manner under these constraints has been considered in prior work (Segal-Halevi *et al.*, Fair and square: Cake-cutting in two dimensions, Journal of Mathematical Economics 2017; Segal-Halevi *et al.*, Envy-free division of land, Mathematics of Operations Research 2020), for two classic notions of fairness, namely, **proportionality** (if there are *N* agents, each of them should value their piece at least as highly as *V/N*, where *V* is the value they assign to the entire piece of land) and **envy-freeness** (no agent considers another agent’s piece to be more valuable than their own).

In our work, we consider a variant of this problem where, in addition to geometric constraints on the shapes of the individual pieces, we require the pieces to be *separated*: there is a separation parameter *s* such that any two pieces belonging to two different agents have to be at distance at least *s* from each other. Such a constraint is motivated by practical considerations, e.g., providing access or avoiding cross-pollination; if the “land” to be divided is, say, an exhibition hall or a market square, the separation requirement can be used to capture social distancing constraints. In our earlier paper, which was published in AAAI’21, we considered this question in the context of dividing a one-dimensional resource, commonly referred to as “cake”; however, it turns out that we need an entirely new set of techniques to handle the two-dimensional scenario.

Under the separation constraint, proportionality and envy-freeness become very challenging, so we focus on another fairness concept, known as **maximin fair share**. This notion of fairness is based on the following idea, which is a generalisation of the classic cut-and-choose protocol. Each of the *N* agents executes the following mental experiment: she splits the land into *N* pieces that are *s-*separated, and then lets the other *N-1* agents pick a piece for themselves, so that she ends up with the last piece. Her goal is to maximise the value of the piece she gets in the worst-case scenario, i.e., when she ends up with the piece that she finds the least valuable among the *N* pieces in her partition. The value that she can guarantee to herself in this fashion is called her maximin fair share. Then, an allocation is considered fair if each agent receives a piece that she values at least as much as her maximin fair share.

Maximin fair share is generally viewed as a less demanding concept than proportionality or envy-freeness, but it turns out that, in the setting with separation, an allocation that guarantees each agent her maximin fair share may fail to exist. Therefore, we further relax this solution concept by asking agents to divide the land into *k > N* pieces when running their mental experiment for computing their share. Naturally, we expect the least valuable of the *k* pieces to be less valuable than the least valuable of the *N* pieces, so the larger *k* is, the easier it is to satisfy all agents. (Of course, in the actual allocation we still divide the land into *N* pieces.)

We refer to the resulting solution concept as **1-out-of-k fair share**.

In our work, we ask what is the smallest value of *k* such that we can guarantee to each agent her 1-out-of-k fair share, in the presence of separation constraints. Now, it turns out that the answer to this question depends on the constraints on the shapes of individual pieces. In particular, if each agent is to receive a square-shaped piece of land, it suffices to set *k = 4N – 5*. However, if agents’ pieces can be arbitrary axis-aligned rectangles (and the land itself is an axis-aligned rectangle), we get a much weaker upper bound of *k = 2 ^{N+2}*, and converting it into a finite algorithm comes at an additional cost. The proof is constructive, in the sense that, given agents’ fair shares, we explicitly construct an allocation that satisfies all agents; however, the fair shares themselves are difficult to compute, so we need to use an approximation algorithm.

We do not know if our bounds on *k* (as a function of *N*) are tight; improving them, or, alternatively, proving matching lower bounds, is a challenge for future work.

Edith Elkind, Erel Segal-Halevi and Warut Suksompong recently won an **IJCAI 2021 distinguished paper award** for the work covered in this post. The title of their winning paper is *Keep your distance: land division with separation*.

tags: IJCAI2021

Edith Elkind
is a Professor of Computer Science at University of Oxford.

Edith Elkind
is a Professor of Computer Science at University of Oxford.

The winners of an outstanding paper award at ICLR 2022 tell us about their work on understanding deep neural networks.

18 May 2022, by
AIhub Editor

In this blog post, we aim to understand if, when and why offline RL is a better approach for tackling a variety of sequential decision-making problems.

17 May 2022, by
BAIR blog

The recordings of the sessions from the AI UK conference are now available for all to watch.

16 May 2022, by
Lucy Smith

The standard aims to guide AI practitioners in dealing with malicious attacks on AI systems.

13 May 2022, by
Nanyang Technological University, Singapore

A computational tool developed to predict the structure of protein complexes is providing new insights into the biomolecular mechanisms of their function.

12 May 2022, by
Machine Learning Center at Georgia Tech

We talk to Nicolo' Brandizzi about his work on human-AI collaboration.

11 May 2022, by
Joe Daly

©2021 - ROBOTS Association