Preference Elicitation for Policy Optimization and Application to Aligning Heart Transplantation with Human Values

Itai Zilberstein; Ioannis Anagnostides; Zachary W Sollie; Arman Kilic; Tuomas Sandholm

Source-linked AI summary

Preference Elicitation for Policy Optimization and Application to Aligning Heart Transplantation with Human Values

Itai Zilberstein, Ioannis Anagnostides, Zachary W Sollie, Arman Kilic, Tuomas Sandholm

arXiv:2608.28620v1Jul 29, 2026cs.AIcs.LG

TL;DR

The paper addresses how to elicit stakeholder preferences for high-stakes, multi-objective allocation and connect them to policy optimization. It learns linear utilities through a two-phase comparison algorithm and applies them to heart transplantation, where the optimized policy reaches a 0.95 competitive ratio versus 0.54 for the status quo.

Problem
Preference elicitation must balance competing objectives and connect learned human preferences to downstream decisions, while prior allocation approaches can conflate decisions with outcomes.
Method
A two-phase algorithm uses cutting planes to shrink possible attribute weights, then iterative sieving to provably converge to a linear utility function for policy optimization.
Results
0.95 competitive ratio is achieved by the optimized heart-transplant policy versus 0.54 for the status quo, relative to the hindsight optimum under elicited stakeholder utility.
Takeaways & Limitations
The framework provides a practically deployable pipeline for learning stakeholder values and optimizing allocation policies to those values.
Takeaways & Limitations
The theoretical setup assumes each stakeholder has a monotone utility function and focuses on linear utilities for tractable elicitation.

Abstract

from arXiv · show

Preference elicitation is essential for aligning AI systems with human values. Prior approaches (e.g., for organ allocation) often ask stakeholders to compare the decisions of an algorithm (e.g., patient A vs. patient B). Such a decision-level approach conflates the means with the ends. Instead, we elicit preferences directly over allocation outcomes to learn a utility function for policy optimization. We construct a novel preference elicitation algorithm for linear utilities that outperforms prior techniques in practice. Our algorithm has two phases. The first phase learns cutting planes through pairwise comparisons to rapidly shrink the space of possible attribute weights and warm-starts the second phase by eliminating dominated regions. The second phase then provably converges to the user's utility function. We apply our technique to heart transplant allocation where a policy must balance competing objectives such as post-transplant outcomes, waitlist mortality, geographic ease, and equity. Using our algorithm, we conduct a user study to learn and aggregate a community-aligned utility function, and use it to optimize heart transplant policies that are significantly better aligned with human values. Compared to the hindsight optimum, the status quo policy achieves a competitive ratio of just 0.54, while our method is near-optimal with a competitive ratio of 0.95.

1 Introduction

The paper bridges preference elicitation and policy optimization by learning stakeholder preferences over allocation outcomes rather than individual decisions. It develops and applies this framework to heart transplantation, where the optimized policy substantially outperforms the status quo against the hindsight optimum.

Organ allocation requires trading off post-transplant outcomes, waitlist mortality, geographic ease, equity, and other ethical and operational objectives.
Existing approaches compare patient attributes or allocation decisions, conflating the mechanism used to allocate organs with the system outcomes stakeholders ultimately value.
The framework elicits preferences over system-level allocation outcomes and uses optimization to determine policies that achieve those goals.
The two-phase algorithm combines cutting planes that shrink possible weight vectors with iterative sieving that provably converges to the user’s linear utility function.
The heart-transplant application learns a community-aligned utility function through a user study and feeds it into policy optimization.
0.54 competitive ratio is achieved by the status quo policy, versus 0.95 for the optimized policy relative to the hindsight optimum under elicited stakeholder utility.

2 Utility functions

The paper models stakeholder preferences over allocation outcomes with monotone and, for tractable elicitation, linear utility functions. It distinguishes feasible policy outcomes from a frontier-agnostic query domain and motivates structure through an exponential lower bound for arbitrary monotone utilities.

Each heart-transplant outcome vector coordinate represents an aggregate system-level policy objective, while P contains feasible outcome profiles induced by allocation policies.
Preferences are elicited over hypothetical normalized profiles in X, which need not correspond to currently feasible policies and can be evaluated on current or future P.
Arbitrary monotone utilities make downstream optimization intractable, with welfare maximization over two such utilities requiring exponentially many bits in the number of objectives.
This lower bound motivates focusing on linear utilities, represented by nonnegative weights with u(x) = ⟨x, w⟩ and preference direction invariant to positive rescaling.
Simplex and Euclidean normalizations represent the same preference direction and support different elicitation algorithms.

3 Eliciting linear preferences

The paper develops linear-preference elicitation methods that balance practical query efficiency with formal accuracy guarantees. Its hybrid algorithm combines cutting-plane weight-space reduction with iterative sieving, then achieves strong empirical performance and robustness to noisy responses.

Problem formulation: Linear utility elicitation uses pairwise comparisons to learn a weight vector approximating the user’s latent true preferences.The formal model includes noiseless ternary comparisons and noisy responses with additive error δ.
Cutting-plane method: The cutting-plane method performs well in practice but lacks a provably bounded query complexity for prescribed accuracy.It maintains weights consistent with observed pairwise responses and can stall when high-fidelity approximations are required.
Iterative sieving: The iterative sieving method provides provable convergence and expected query complexity O(d^2 log^2(1/ϵ) log(d log(1/ϵ)))) for learning the preference direction.It maintains candidate outcome profiles and eliminates profiles certified as suboptimal.
Hybrid algorithm: The hybrid algorithm first applies cutting planes, then warm-starts sieving by using the resulting cuts to remove additional dominated regions.Positive rescaling connects the simplex-normalized cutting-plane weights with the Euclidean-normalized directions used by sieving.
Hybrid guarantees: The hybrid algorithm inherits the bounded query complexity of sieving, with expected queries at most O(d^2 log^2(1/ϵ) log(d log(1/ϵ)))) + T.The initial cutting-plane phase uses a constant number T of iterations, while additional removals cannot increase the number of sieving rounds.
Empirical evaluation: In simulation, the hybrid algorithm used fewer queries than ACCPM, iterative sieving, and minimax regret, and nearly matched AWBS.With noisy responses, it achieved ℓ2 error less than 0.35 at noise 0.1 and 30% less error than AWBS.

4 Alignment of heart transplant allocation with human values

The study elicits preferences over system-level heart-transplant outcomes, aggregates them into a community utility function, and uses that function to optimize an online allocation policy. The optimized policy is near-optimal relative to hindsight and substantially outperforms status quo and greedy baselines.

Eliciting a utility function: Stakeholders compare outcome profiles rather than patient-level priorities, covering six normalized objectives spanning effectiveness, survival, access, equity, and transport distance.The objectives include life years gained, waitlist survival and transplant rates, disadvantaged-patient transplant rates, and average miles per donor.
Eliciting a utility function: 94.8% average validation accuracy is achieved by the learned linear utilities with tolerance δ = 0.1.Without a margin for error, average accuracy is 82.7%.
Eliciting a utility function: Life years gained per donor receives nearly 0.4 weight, while disadvantaged-patient transplant rates and transport efficiency each receive weights below 0.1.The reported weights come from welfare-maximizing mean aggregation of community members’ elicited weights.
Closing the loop: Human-value-aligned policy optimization: The optimized online policy nearly Pareto dominates the status quo and greedy policies across all six objectives.The policy is trained on January–March 2019 data and evaluated on unseen April–December 2019 historical trajectories.
Closing the loop: Human-value-aligned policy optimization: 95% competitive ratio is achieved by the optimized policy, versus 54% for the status quo and 78% for greedy allocation.The ratio measures performance relative to an optimal algorithm with perfect foresight of future events.

5 Conclusions

The paper develops a two-phase elicitation algorithm for linear utilities and applies it to policy optimization in heart transplantation. It reports practical query efficiency, provable convergence, and a near-Pareto-dominating optimized allocation policy.

Conclusions: The two-phase algorithm combines cutting-plane efficiency with iterative-sieving guarantees to reduce queries and provably converge to the user’s linear utility.The first phase shrinks possible weight vectors and removes dominated regions before the second phase’s convergence procedure.
Conclusions: Approximately 40 pairwise comparison queries suffice to learn accurate utility functions in the reported user study.The conclusion describes this as the practical query burden for the heart-transplant application.
Theoretical guarantees: The iterative-sieving method halves the candidate set in expectation per iteration and uses approximate conic dimension to obtain an ε-approximate optimizer.The approximate variant returns an ε-approximate minimizer using O(k log k log |P|) comparisons.

C Further details on ACCPM

ACCPM maintains a preference-consistent weight space and queries locally around its analytic center to generate balanced cuts. It offers an ex post approximation guarantee, but no bounded query complexity for reaching a prescribed diameter.

Weight-space maintenance: The feasible weight space retains weights consistent with strict-preference and indifference responses under tolerance δ.The formulation also imposes nonnegative weights summing to one.
Query synthesis: Each query induces a cut normal xi − xj, and ACCPM chooses profile pairs by perturbing the current analytic center.The perturbation direction is orthogonal to the analytic center and produces equal current utility for the two profiles.
Guarantees and limitation: ACCPM has no bounded query complexity for reaching a prescribed weight-space diameter, despite its ex post utility certificate.The certificate assumes user responses are consistent with w∗ up to margin δ.
Guarantees and limitation: If the final weight-space diameter satisfies diam2(Wt) ≤ ϵ, the returned estimate is within ϵ in Euclidean weight distance of w∗.The paper also states an ex post utility approximation guarantee under the same termination condition.
Query synthesis: The step size targets a prescribed profile separation γ while keeping both query profiles in the nonnegative orthant.A fixed factor 0.98 prevents the query from reaching the boundary of the positive orthant.
Query synthesis: The query direction follows the smallest-curvature eigenvector of the analytic-center barrier, representing greatest local uncertainty in the remaining weight space.The intended effect is to produce cuts that reduce uncertainty around the analytic center.

D Further details on iterative sieving

Iterative sieving elicits linear preferences by sorting sampled outcome profiles and eliminating profiles certified as suboptimal. It provides an explicit approximation guarantee and expected query-complexity bound over a finite cover.

Algorithm: The algorithm maintains a finite candidate set, sorts sampled profiles through pairwise queries, and removes profiles inferred to be suboptimal from the ordering.The envelope captures certified pairwise-difference cones, while conic dimension controls how many sampled profiles are needed for broad inferences.
Algorithm: Pairwise queries occur during mergesort-based sorting and the final linear search for the maximum profile.The returned weight is guaranteed to be an ϵ-approximation of the Euclidean-normalized true weight vector.
Guarantees: The expected query complexity is O(d^2 log^2(1/ϵ) log(d log(1/ϵ))).Unlike heuristic cutting-plane methods, iterative sieving supplies both an explicit approximation guarantee and an expected query bound.
Elimination rule: The envelope test checks whether y−x can be represented by a conic combination of sorted adjacent differences, certifying y as at least as useful as x.A feasible linear program yields this certificate for every nonnegative weight vector satisfying the sorted ordering constraints.
Elimination rule: An infeasible envelope test means that some valid weight vector ranks x above y, so x cannot be safely eliminated.This preserves candidate profiles whose optimality remains possible under the consistent weight space.

D.1.1 Noisy envelope

The noisy-envelope variant limits how comparison errors accumulate in elimination certificates. Bounded conic coefficients improve robustness but can reduce eliminations and leave the original query bound inapplicable.

Noise model: Noisy comparisons relax each sorted-order inequality by δ, so large conic certificates can amplify the accumulated error.The coefficients α_i determine the amount of noise amplification.
Robust elimination: The robust test uses nonnegative coefficients with a bounded ℓ1 norm, imposing ||α||_1 ≤ B on envelope certificates.This restriction prevents unbounded error amplification and yields utility degradation proportional to Bδ.
Robust elimination: The noisy envelope removes a profile only when the bounded certificate and approximate-envelope tolerance establish its dominance.The robust elimination rule is therefore more conservative than the unrestricted noiseless rule.
Trade-off: Bounding certificate coefficients may reduce the number of points eliminated in each sieving round.The B-bounded envelope is smaller than the unrestricted envelope.
Trade-off: The original query-complexity bound does not automatically apply to the noisy envelope.A corresponding analysis would require a B-restricted approximate conic dimension.

E Discussion of minimax regret

The paper distinguishes recovering a reusable utility function from selecting a robust outcome for one feasible policy set. Minimax regret can match the weight-approximation guarantee on the full sphere, but local regret does not ensure accurate utility recovery.

Standard formulation: Minimax regret selects an outcome minimizing worst-case utility loss over feasible weights and outcomes.This is the standard decision-support formulation discussed in the paper.
Guarantee: Unlike ACCPM and the cited minimax-regret approach, the method does not rely only on an ex post regret certificate; it supplies an ex ante query bound.The comparison concerns guarantees for reaching a prescribed approximation level.
Paper objective: The paper recovers each stakeholder’s utility vector so utilities can be aggregated and reused across changing policy frontiers.A regret guarantee for one feasible set generally does not transfer, whereas an ϵ-approximation of the utility vector does.
Limitation: A small regret bound on one feasible policy set does not imply that the underlying utility vector has been accurately learned.The paper therefore treats regret over the sphere differently from regret over a particular policy frontier.
Guarantee: Reducing minimax regret over the sphere to ϵ^2/2 yields the same weight-approximation guarantee as the paper’s other elicitation algorithms.The equivalence follows from the relationship between inner product and Euclidean distance for unit-norm preference directions.

F One method for aggregating linear preferences

Stakeholder preference vectors are aggregated by arithmetic averaging under a common normalization. The resulting aggregate utility has a utilitarian welfare interpretation and can support downstream policy optimization.

Aggregation: The method averages the Euclidean-normalized preference directions elicited from the m stakeholders.The paper uses arithmetic mean aggregation after individual utility elicitation.
Interpretation: Optimizing the aggregate utility ⟨x, ū⟩ is equivalent to maximizing utilitarian social welfare over the elicited stakeholder utilities.The aggregate vector can serve as the objective for downstream allocation-policy optimization.
Guarantee: Individual ϵ-approximation guarantees transfer to the aggregate vector, yielding ||ū−ū*||_2 ≤ ϵ.The same bound gives utility error at most ϵ for every normalized outcome profile.
Scope: Other aggregation rules, including fairness-aware or strategy-proof social choice rules, could also be used.Aggregation requires fixing a common normalization; analogous aggregation can use simplex-normalized weights.

G Omitted proofs

The omitted proofs establish lower bounds for arbitrary monotone utilities and correctness, approximation, and query-complexity guarantees for the proposed elicitation algorithms.

Lower bounds: 2^Ω(d) bits are required to maximize welfare for arbitrary monotone utilities, even for binary-valued threshold utilities.The communication reduction uses set disjointness and ternary comparison transcripts to derive an exponential worst-case query lower bound.
Lower bounds: Monotonicity alone does not provide query-efficient guarantees, motivating the tractable and interpretable linear utility model.The linear model supplies objective weights while avoiding the exponential lower bound established for general monotone utilities.
Linear query complexity: Ω(d log(1/ϵ)) queries are necessary for linear elicitation when the recovered utility must achieve error at most ϵ.The proof constructs a separated packing of the weight simplex and counts the at most 3^Q possible comparison transcripts.
Algorithm guarantees: Algorithm 3 returns an ϵ-accurate weight estimate whenever the feasible weight-space diameter satisfies diam2(Wt) ≤ ϵ.The true weight and the algorithm’s estimate both remain in the feasible set, so the diameter condition directly bounds their Euclidean distance.

J Hyperparameter settings and compute details for preference elicitation

The appendix specifies experimental reproducibility details, including simulation settings, compute environments, data splits, and hyperparameter documentation.

Compute and reproducibility: Simulated experiments use an M4 Pro processor with 24GB unified memory and deterministic trial-specific random seeds.Trial i uses seeds i × 31 + 7 for weight vectors and i × 97 + 13 for noisy oracles.
Compute and reproducibility: Human experiments run on a Linux cluster with dual AMD EPYC 7252 CPUs, 32 hardware threads, and 512GB RAM.The compute environment is reported separately from the simulation hardware.
Simulation: The simulation models donor arrivals, waitlist changes, patient-condition progression, blood-type compatibility, and a 1,000-nautical-mile geographic constraint.The study is restricted to adult transplantation.
Simulation: Life-years-gained estimates use Cox proportional hazards models fitted on 1987–2022 UNOS registry data.The training data include 60,055 transplant outcomes and 120,282 waitlist survival examples, with 120 covariates for patient-donor pairs.
Policy evaluation: Policy optimization trains on January–March 2019 data and evaluates policies on unseen April–December 2019 data.Hyperparameters for the hybrid algorithm are documented in Table A2.

K.1 Potential-based allocation policy

The paper describes potential-based allocation policies that combine predicted life-years gained with learned potential values, alongside greedy and status quo baselines.

Potential-based policy: A potential-based policy assigns each waiting patient an additive score combining predicted life-years gained and potential value.The potential value is used with the immediate utility estimate to rank patients at donor arrival.
Potential-based policy: Potential functions are trained through self-supervised imitation learning to mimic hindsight-optimal life-years-gained allocations.The hindsight optimal integer program acts as the supervisor on historical training data, while potentials are used online on unseen data.
Baselines: The greedy baseline selects the patient with the largest predicted life-years gained at each donor arrival.This baseline optimizes life-years gained in isolation from the other objectives.
Baselines: The US status quo policy assigns adult heart-transplant candidates to rule-based tiers using urgency, blood type, geographic proximity, and wait time.Allocation follows lexicographic priority among the tiers and is agnostic to any utility function.
Baselines: The status quo system contains 68 total priority tiers, with tier 1 designated as the highest priority.The full tier list is provided in Table A4.