ΑΙhub.org
 

Allocating fair shares of land


by
21 September 2021



share this:
Fields

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.

image-distance2D

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 = 2N+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:


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




            AIhub is supported by:


Related posts :



Exploring counterfactuals in continuous-action reinforcement learning

  20 Jun 2025
Shuyang Dong writes about her work that will be presented at IJCAI 2025.

What is vibe coding? A computer scientist explains what it means to have AI write computer code − and what risks that can entail

  19 Jun 2025
Until recently, most computer code was written, at least originally, by human beings. But with the advent of GenAI, that has begun to change.

Gearing up for RoboCupJunior: Interview with Ana Patrícia Magalhães

  18 Jun 2025
We hear from the organiser of RoboCupJunior 2025 and find out how the preparations are going for the event.

Interview with Mahammed Kamruzzaman: Understanding and mitigating biases in large language models

  17 Jun 2025
Find out how Mahammed is investigating multiple facets of biases in LLMs.

Google’s SynthID is the latest tool for catching AI-made content. What is AI ‘watermarking’ and does it work?

  16 Jun 2025
Last month, Google announced SynthID Detector, a new tool to detect AI-generated content.

The Good Robot podcast: Symbiosis from bacteria to AI with N. Katherine Hayles

  13 Jun 2025
In this episode, Eleanor and Kerry talk to N. Katherine Hayles about her new book, and discuss how the biological concept of symbiosis can inform the relationships we have with AI.

Preparing for kick-off at RoboCup2025: an interview with General Chair Marco Simões

  12 Jun 2025
We caught up with Marco to find out what exciting events are in store at this year's RoboCup.

Graphic novel explains the environmental impact of AI

  11 Jun 2025
EPFL’s Center for Learning Sciences has released Utop’IA, an educational graphic novel that explores the environmental impact of artificial intelligence.



 

AIhub is supported by:






©2025.05 - Association for the Understanding of Artificial Intelligence


 












©2025.05 - Association for the Understanding of Artificial Intelligence