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.