Allocating fair shares of land

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.

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

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