Conformally Certified EFX: Fair Division When Valuations Are Predicted

Many real allocation systems divide indivisible things, such as course seats, reviewing assignments, shared equipment or estate items, without ever learning what each person truly wants. They ask for a few preferences and let a model fill in the rest. The fairness algorithm then treats those filled-in numbers as exact. That is a problem for the strongest fairness notion people actually try to compute, envy-freeness up to any item (EFX). EFX means no one prefers another person's bundle once any single item is taken out of it. An allocation that is EFX under predicted values can easily fail under the true ones: the certificate depends on comparisons that may sit within a few units of each other. We propose to replace each predicted value with a conformal prediction band, an interval built from held-out data that contains the truth with a user-chosen probability without any assumption about the noise distribution. We then compute allocations that are EFX for every valuation consistent with those bands. When no such allocation exists, the system asks agents for their true values on a small, targeted set of items before it falls back to setting items aside.

The output is an allocation with an explicit guarantee: with probability at least $1-\alpha$, it is EFX under the agents' true valuations. A secondary output is a measurable price for that guarantee, namely how many preference questions or set-aside items it costs. Neither exists today. The EFX literature assumes exact scalar valuations, and the only robustness-to-misreported-values work in fair division relies on money to absorb errors.

Core Claim

The claim is that a calibrated EFX certificate can be obtained cheaply in practice if two choices are made correctly. The first is to calibrate simultaneous bands over each agent's whole valuation vector, not separate per-item intervals. The second is to spend the budget of exact preference questions only on the items whose bands actually decide an envy comparison. Our hypothesis is that this costs far fewer questions than eliciting everything. We also expect it to give a much higher rate of true EFX than either allocating on point predictions or maximizing a hand-tuned safety margin.

The guarantee is easy to state for additive valuations. Suppose agent $i$'s conformal band gives lower and upper values $\ell_i(g) \le v_i(g) \le u_i(g)$ for every item $g$, all holding jointly with probability $1-\alpha$. An allocation $A$ is then robustly EFX when

$$ \sum_{h \in A_i} \ell_i(h) \;\ge\; \sum_{h \in A_j \setminus \{g\}} u_i(h) \quad \text{for all agents } i \neq j \text{ and every } g \in A_j . $$

The idea is that an agent's own bundle is judged at its worst plausible value and the other bundle at its best. Any allocation satisfying this inequality is EFX under the true valuations whenever the bands cover. The coverage guarantee therefore carries over to the allocation.

Relation to Prior Work

Three lines of work motivate the gap without filling it.

Robust Rent Division shows that the maximin rule used on Spliddit sits on a knife-edge, where small valuation noise makes envy appear. It proposes Lexislack, which maximizes utility margins, together with sampling-based robustness under assumed noise families. That work depends on divisible rent to create slack, and its guarantees are tied to the assumed noise model. We have no money, our items are indivisible, and our guarantee is distribution-free.

Online Fair Division with Additional Information analyzes how EF1 and proportionality degrade under noisy scalar predictions, and it obtains EFX only for two agents. It never models instance-level uncertainty as calibrated sets.

Robust and Consistent Ski Rental with Distributional Advice makes the general case that point predictions hide decision-relevant shape. It assumes the distribution is given rather than calibrated, and it addresses a single-agent problem.

The method comes from conformal prediction. Conformalized Quantile Regression (CQR) wraps learned quantiles in a conformal correction so that intervals adapt to how hard each prediction is. It reports an average interval length of 1.13 against 2.09 for plain split conformal on the protein benchmark at 90% coverage. That width matters here, because wide bands make the robust inequality above impossible to satisfy. The decide-or-ask structure follows the error-controlled defer policies of Act or Defer, carried over to multi-agent allocation.

The EFX theory constrains what we can promise. Complete EFX existence is open for four or more agents, as discussed in EFX Exists for Three Agents and Almost Envy-Freeness with General Valuations. Robust EFX is strictly stronger than EFX, so we cannot claim it always exists. This is exactly why the proposal includes elicitation and set-aside items, in the spirit of the charity results in Envy-freeness up to any item with high Nash welfare: The virtue of donating items and Rainbow Cycle Number and EFX Allocations: (Almost) Closing the Gap. Those results bound charity size by worst-case graph arguments on exact values. We instead measure, and for small cases bound, how charity and questions scale with band width.

Research Program

Calibration that actually supports the certificate. Per-item CQR intervals give marginal coverage for each agent-item pair. A certificate touching many pairs at once would need a union bound, which inflates widths badly. We instead give each agent one score: the largest normalized residual across that agent's predicted items, $s_i = \max_g |v_i(g) - \hat v_i(g)| / \hat\sigma_i(g)$. Here $\hat v$ is the point prediction and $\hat\sigma$ is a learned scale, such as half the CQR quantile width. We then conformalize this score over calibration agents. This gives a simultaneous band per agent. Coverage across the $n$ agents of an instance is handled either by using level $\alpha/n$ per agent, or by conformalizing the maximum over agents when whole instances are exchangeable. We will compare the two. Exchangeability between calibration agents and new agents is the assumption that matters most, and we test it directly (see below).

Computing robust EFX allocations. On Spliddit-scale instances, which have few agents and tens of items, the robust condition is a set of linear constraints over binary assignment variables. We solve it exactly as an integer program and break ties by maximizing worst-case Nash welfare. For larger instances we adapt envy-cycle elimination so that it compares lower bounds against upper bounds.

Targeted elicitation, then charity. When the program is infeasible, we find the violated or near-tight comparisons. We then ask the relevant agent for the true value of the item whose band width contributes most to closing the gap; that item's band collapses to a point. We re-solve after each answer. Only when the question budget is exhausted are the remaining blocking items set aside. We also study a theory question in the two-agent case: whether a robust cut-and-choose procedure always succeeds after a number of questions that depends only on relative band width. This gives an upper bound to compare the greedy policy against.

Baselines

The naive reference point is to allocate on point predictions. We take the same predictor's $\hat v$, compute an exact EFX allocation for it by integer program, and report how often that allocation is EFX under the true values. It receives the same data and predictor and asks no questions. This baseline shows how large the problem is. The file contains no reported EFX-under-noise rate for indivisible goods (no reported result found on Lacuna for this), so we measure it ourselves.

The strongest competitor is a margin-maximizing point allocation. This is the indivisible-goods analog of Lexislack from Robust Rent Division: among EFX allocations of $\hat v$, choose the one maximizing the smallest relative EFX slack. Given an equal question budget, it asks about the items in its tightest comparisons. It is strong because it already captures "stay off the knife-edge." The only thing it lacks is a calibrated sense of how much margin is enough. For fairness of comparison, it gets the same predictor, the same budget of exact questions, and a margin hyperparameter tuned on the calibration split to target $1-\alpha$ true-EFX rate. That tuning is the strongest version a practitioner could build. Rent division's reported finding is qualitative only: the maximin rule's envy-free probability "drops sharply" at noise 0.05, while robust rules keep much higher survival.

The parametric competitor is a chance-constrained Bayesian allocation. It uses Gaussian predictive distributions from NGBoost and the same robust inequality, but with bands taken from Gaussian quantiles. It receives the same features and budget.

The full elicitation reference asks every value and is trivially EFX whenever EFX exists. It gives the question-count ceiling.

Two ablations isolate our ingredients. The first replaces simultaneous bands with per-item CQR bands at level $\alpha$, with no joint correction; this should undercover. The second replaces targeted questions with random ones at the same budget.

We beat the margin baseline if, at matched question budgets, we reach the nominal true-EFX rate while it falls short. We also beat it if both reach the rate and we use fewer questions or set aside fewer items at equal welfare.

Why not just…?

Why not just maximize the EFX margin on point estimates and skip calibration? This is the real threat, and it is why that method is our main baseline. A margin works only if it is the right size, and the right size varies by agent and item: some predictions are tight, some are wild. A single tuned margin must be set to the worst case, which wastes questions on easy agents, or set to the average, which fails on hard ones. CQR's near-halving of interval width relative to fixed-width conformal on the protein benchmark is evidence that adaptivity matters a lot for widths. If the tuned-margin baseline matches us at every budget, the honest conclusion is that calibration adds no value here, and the experiment is designed so that this outcome is visible.

Why not just assume Gaussian noise and use chance constraints? This works when the noise really is Gaussian. Learned valuation predictors on human preference data tend to be heavy-tailed and uneven across items. In that regime, uncalibrated quantile models undercover their nominal level, which is exactly what CQR documents. The NGBoost baseline tests this directly. We expect it to match us on synthetic Gaussian noise and to undercover on real Spliddit residuals. If it does not undercover, the distribution-free machinery is unnecessary for this application.

Why not just settle for EF1, which always exists and tolerates noise better? EF1 permits the well-known failure where an agent holding a worthless item feels no envy only because one prized item is mentally removed from a neighbor's bundle. EFX exists to rule that out. We nevertheless report the robust EF1 analog as a reference. If robust EF1 is nearly free while robust EFX is expensive, that gap is itself the measured price of the stronger notion under uncertainty.

Why not just ask everyone everything? Full elicitation is our ceiling, not our competitor. The setting exists because asking is costly. The measured quantity of interest is the fraction of questions our policy saves at the same guarantee.

Proposed Experiments

The main testbed is semi-synthetic but uses real values. We take the real-world Spliddit indivisible-goods instances, the ones used in Relaxations of Envy-freeness over Graphs, and treat the reported valuations as ground truth. For each test agent we reveal a random fraction of their item values. The remaining values are predicted from the revealed ones together with other agents' reports, using quantile gradient boosting with CQR. Calibration agents come from instances disjoint from the test instances. Revealing a masked value is our "question," so elicitation is simulated exactly.

The second testbed is chores. We use the ICLR 2018 reviewer-paper similarity matrix from PeerReview4All to define restricted additive reviewing costs, following Allocating Chores with Restricted Additive Costs. We then perturb the costs with heavy-tailed noise. This lets us ask whether calibrated bands can tell which predicted zero costs are trustworthy, the "zero-cost trap" that study identifies.

The metrics are four:

  1. The realized rate at which the output allocation is EFX under true valuations, with target $1-\alpha$ for $\alpha \in \{0.05, 0.1, 0.2\}$.
  2. Questions asked per agent.
  3. Items set aside.
  4. Nash welfare under true values relative to the true maximum.

The decisive checks are three. First, the calibrated method should hit the nominal true-EFX rate while the point-prediction baseline visibly does not. Second, the per-item-band ablation should undercover, which would show the simultaneous construction is necessary. Third, the curve of questions against achieved EFX rate should dominate the tuned-margin baseline's curve.

We will also stress exchangeability. We calibrate on Spliddit instances of one size or category and test on another, and report how far coverage drifts. If it drifts substantially, the next step is weighted calibration rather than claiming the guarantee holds.