Prior-Tailored Honest Picking Protocols for Fair Division

When a school, a family or a lab divides indivisible items (course seats, heirlooms, equipment time) among people who report their own preferences, two goals collide. The first is fairness, such as "no one envies another's bundle once a single item is removed," a guarantee called EF1. The second is honesty: the rule should make it in everyone's interest to report their true preferences. Without money these goals are sharply incompatible. For two players with additive values, every rule that is honest regardless of what others do is known to have a rigid "pick from a menu, then swap" structure, and EF1 becomes impossible once there are five or more items (Truthful Allocation Mechanisms Without Payments). The known escape is to ask for honesty only on average over a known belief about everyone's preferences, called Bayesian incentive compatibility (BIC). Under that weaker requirement, round-robin picking with an option to pass achieves EF1. The catch is that the proof needs a "neutral" prior, in which every item is equally likely to be anyone's favorite (Getting More by Knowing Less). Real priors are rarely neutral: everyone knows the car is worth more than the toaster.

This note proposes to treat that gap as a design problem for automated mechanism design, the practice of having an algorithm synthesize the rules of interaction for a specific distribution of participant preferences instead of deriving one rule for all environments (Complexity of Mechanism Design). Concretely, we search over a structured family of pick-or-pass protocols, parameterized by picking order, pass permissions and publicly known item priorities, to find the protocol that maximizes expected fairness under a given skewed prior. The search keeps a protocol only if an exact best-response oracle certifies that truth-telling is Bayes-optimal. In two sentences: round-robin-with-passing is honest only when items are interchangeable ex ante, and we show that searching this protocol's own family against the actual prior restores honesty and fairness when items are not. An exact linear program over randomized rules, solvable on small instances, measures how much the interpretable family gives up.

Core Claim

For skewed priors in which some items are predictably more valuable, we conjecture three things. First, the passing round-robin of Getting More by Knowing Less has a measurable expected gain from misreporting that grows with prior skew. Second, a prior-tailored member of an enlarged pick-or-pass family has zero such gain and satisfies EF1 on nearly as many realized instances as the neutral-prior guarantee promises. Third, the remaining fairness gap to the best randomized BIC rule, computed exactly for small instances, is small. The new element is neither "use a prior" nor "use an optimizer" on its own. It is a certified, interpretable synthesis procedure for BIC fair division in exactly the non-neutral regime where the analytical results say nothing, together with an exact frontier that says how good that procedure is.

The honesty requirement we certify is the standard one. Let $v_i$ be agent $i$'s additive valuation, drawn from the prior $D$. Let $M$ be the protocol and $\sigma_i$ any strategy for $i$ in it, including misreported rankings and strategic passes. Truthful play $\tau$ must satisfy, for every $v_i$ and every $\sigma_i$,

$$ \mathbb{E}_{v_{-i}\sim D\mid v_i}\big[v_i(M(\tau(v_i),\tau(v_{-i})))\big] \;\ge\; \mathbb{E}_{v_{-i}\sim D\mid v_i}\big[v_i(M(\sigma_i,\tau(v_{-i})))\big] - \epsilon . $$

We report the smallest $\epsilon$ that works, called the BIC regret, and we certify protocols at $\epsilon=0$.

Research Program

The work has three components. The first is a manipulation oracle. For a fixed protocol and prior, each agent faces a finite game tree: a sequence of pick or pass decisions under uncertainty about the opponent's valuation. We compute the exact best response by backward induction, conditioning beliefs on the opponent's observed picks and averaging over valuations sampled or enumerated from the prior. For two agents and up to about ten items this is exact and cheap. For three to five agents we use sampled opponents and report confidence intervals on regret. The oracle plays the role that manipulation-finding plays in Incremental Mechanism Design, which patches a naive rule until no profitable misreport remains. We borrow that loop. We avoid its path-dependence and "whack-a-mole" failure, where fixing one manipulation opens another, because every candidate stays inside a family whose members can each be checked globally.

The second component is the protocol family and search. The family generalizes passing round-robin in three ways: an arbitrary picking sequence rather than strict alternation, item-specific rules about when passing is allowed, and priority reservations on publicly known high-value tiers. An example of the last is "the first picker may not take a top-tier item on turn one." All of these are functions of the public prior only, never of private reports, so they do not create new channels for manipulation. We search this discrete space with local search seeded at passing round-robin. The objective is expected EF1 satisfaction and expected maximin-share ratio, where the maximin share is the value an agent could guarantee by splitting the items into $n$ bundles and taking the worst. The oracle rejects any candidate with positive regret.

This design responds to two constraints on the literature. The divisible-goods resource-burning rule of Mechanism design for fair division and the single-parameter auctions of Fair Division of Indivisible Goods Among Strategic Agents both need divisibility or money, and we have neither. The supervised learning of median and matching rules in Automated Mechanism Design without Money via Machine Learning fits rules to designer-labeled target outcomes. It optimizes neither fairness axioms nor combinatorial bundles directly, which is what we do.

The third component is an exact frontier. For two agents, five or six items, and valuations restricted to a small discrete support, the randomized-mechanism linear program of Complexity of Mechanism Design is tractable. Its variables are allocation probabilities per reported profile, subject to BIC constraints, and its objective is expected fairness. That paper shows randomization can strictly beat determinism (expected welfare 5.5 versus 5.0 in its example). Our linear program gives the best fairness any BIC rule can reach on these instances, and the gap between it and our synthesized protocol is the price of interpretability. Because EF1 is not linear in allocation probabilities, the linear-program objective uses the expected maximin-share ratio. We compute the maximin-share values per profile offline, which is feasible at this size and sidesteps the inner-loop hardness noted in Almost Envy-Freeness with General Valuations.

Baselines

The naive reference points are serial dictatorship and plain round-robin. Serial dictatorship is honest but, as Getting More by Knowing Less stresses, gives leftovers to later agents. Plain round-robin is fair when everyone reports truthfully, but agents can manipulate it. We report its BIC regret and its EF1 rate under truthful play and under best-response play, so that its apparent fairness is not overstated.

The strongest existing method is passing round-robin, RR^pass from Getting More by Knowing Less. It is the only indivisible-goods rule in the file that is both BIC and EF1, and our search starts from it. It will be run on the same priors, instance sizes and oracle as our protocols. No reported result found on Lacuna for RR^pass's regret or EF1 rate under non-neutral priors. Our first experiment produces that number. Beating it means zero certified regret where RR^pass has positive regret, with an EF1 rate and expected maximin-share ratio within a pre-set tolerance of RR^pass's truthful-play values.

A second competitor is Plant-and-Steal from Plant-and-Steal. It is honest regardless of what others do, and it gets a factor-2 maximin-share approximation when its preference predictions are accurate. We feed it the prior's modal ranking as its prediction. It is the strongest dominant-strategy alternative, and it is limited by that paper's proof that no such rule beats a factor of 6/5 while keeping a finite worst-case guarantee. We also search over dominant-strategy pick-and-exchange rules with the same budget, to show what dropping to average-case honesty buys.

Three ablations isolate the proposal's key ingredients. The first reruns the search against a neutral prior and deploys the result on the skewed prior, which tests whether tailoring to the prior matters. The second restricts the search to picking-order changes only, which tests whether the pass and priority rules are needed. The third is the exact randomized linear program, which serves as an upper bound. Every searched method gets the same number of oracle calls.

Why not just…?

Why not just run passing round-robin on skewed priors and accept a small manipulation gain? This is the most serious threat. If RR^pass's exact regret stays negligible, for example under 1% of expected bundle value, across realistic skews, then the practical case for synthesis weakens. The contribution would shrink to a certification tool plus a map of where neutrality matters. Experiment one measures exactly this before any search is run, and we will report it honestly either way.

Why not just solve the randomized linear program and deploy its solution? Its size grows exponentially with the number of agents and items (Complexity of Mechanism Design). Its output is also an opaque table of lottery probabilities that no school or estate would adopt. We therefore use it as a yardstick on small instances, not as the method.

Why not just use Plant-and-Steal with predictions taken from the prior? It demands honesty regardless of others' reports and is therefore capped by the 6/5 bound and by the pick-and-exchange rigidity of Truthful Allocation Mechanisms Without Payments. It also uses only ordinal predictions and cannot exploit cardinal tier structure. Running it as a baseline shows directly whether average-case honesty buys fairness in practice.

Proposed Experiments

The priors come from the High-Med-Low tiered-valuation model used in Plant-and-Steal, which is non-neutral by construction. We add one skew parameter that interpolates from neutral (equal tiers) to strongly tiered, and one correlation parameter that controls how much agents agree on rankings. We cover two agents with 4 to 10 items using the exact oracle, three to five agents with up to 12 items using the sampled oracle, and the exact linear-program frontier for two agents with 5 to 6 items. Metrics are BIC regret, EF1 rate, expected maximin-share ratio, utilitarian welfare, and search cost in oracle calls. Spliddit (Spliddit) motivates the estate-division setting, but the file lists no released preference data, so we do not claim a real-data evaluation.

Three checks decide the outcome. The first is whether RR^pass's regret rises measurably with skew; if it does not, the premise fails. The second is whether the prior-tailored protocols reach zero certified regret while keeping EF1 rates close to the neutral-case values, and whether the neutral-trained ablation fails on skewed priors. The third is whether the gap to the exact randomized frontier stays small at 5 to 6 items. If it is large, interpretable families leave real fairness on the table, and randomized protocol families become the natural next step.