Lucas' Method of Markers

N Players Linear Arrangement Marker Placement O(N²) Operations

Overview

Developed by William F. Lucas in the 1990s, the Method of Markers provides a fair division procedure for goods that can be arranged in a linear fashion. This applies to both continuous resources (like a gold chain to be cut) and collections of discrete indivisible items (like books arranged on a shelf). The algorithm builds on ideas from the Last-Diminisher procedure but adapts them for indivisible or semi-divisible goods.

Each player places markers to indicate segments they would accept as fair, with the algorithm ensuring everyone receives a proportional share according to their own valuation.

Mathematical Framework

Formal Setup: Let $G$ be the set of goods arranged linearly, and let $v_i: \mathcal{P}(G) \rightarrow \mathbb{R}_+$ be player $i$'s valuation function where $\mathcal{P}(G)$ represents all possible subsets (segments) of $G$.

Marker Constraint: For each player $i$, their markers $m_i^1 < m_i^2 < \ldots < m_i^{n-1}$ must satisfy: $$v_i(\text{segment}_j) \geq \frac{v_i(G)}{n} \text{ for all segments } j \in \{1, 2, \ldots, n\}$$

Allocation Function: The algorithm produces allocation $A = (A_1, A_2, \ldots, A_n)$ where $A_i$ is the segment received by player $i$.

Fairness Properties

Proportionality

Every player receives at least their proportional share according to their own valuation.

Formal Statement: $\forall i, v_i(A_i) \geq \frac{v_i(G)}{n}$ ▼

Proof: By the marker placement constraint, each player values every segment they create as worth at least $\frac{1}{n}$ of the total.

When player $i$ is selected in any round, they receive a segment that:

  • Ends at one of their own markers, and
  • Contains at least one complete segment they originally marked

Since player $i$ valued this segment as $\geq \frac{v_i(G)}{n}$ when placing markers, and they may receive additional goods beyond their marker, we have $v_i(A_i) \geq \frac{v_i(G)}{n}$.

Strategy-Proofness

Truth-telling when placing markers is a dominant strategy.

Intuition: Misreporting preferences cannot improve outcomes ▼

Players cannot benefit from placing markers dishonestly:

  • Over-claiming: Placing markers to claim segments worth less than $\frac{1}{n}$ risks receiving an inadequate allocation
  • Under-claiming: Being overly conservative may result in receiving less desirable segments
  • Optimal strategy: Place markers to create segments of exactly equal value $\frac{v_i(G)}{n}$

Remainder Efficiency

The algorithm may leave surplus goods that are distributed to the remaining players, improving overall efficiency.