Preference Elicitation for Policy Optimization and Application to Aligning Heart Transplantation with Human Values
Authors: Itai Zilberstein, Ioannis Anagnostides, Zachary W Sollie, Arman Kilic, Tuomas Sandholm
Organizations: Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA · Department of Surgery, Division of Cardiothoracic Surgery, Medical University of South Carolina, Charleston, SC · Strategy Robot, Inc., Strategic Machine, Inc., Optimized Markets, Inc.
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 human-value-aligned utility function. We evaluate the linear representation against LLM-based methods supplied with users' natural language explanations, finding that none of these methods is more accurate than the learned linear utilities. We use the resulting utility function 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.66, while our method is near-optimal with a competitive ratio of 0.95.
Figures & tables
Figure 1: Our human-aligned policy optimization framework. We use preference elicitation to learn what stakeholders want the allocation system to achieve; optimization determines how best to achieve it.
Algorithm 1 Hybrid ACCPM and sieving preference elicitation
Figure 2: Queries as a function of ϵ using random weight vectors with a max budget of 250 queries. Shaded area shows standard deviation across 20 trials per ϵ .
Figure 3: ℓ2 error when using a noisy oracle parameterized by δ with random weight vectors and a max budget of 250 queries. Shaded area shows standard deviation across 20 trials per δ .
Figure 4: Elicitation interface used in our stakeholder study. Participants compare two outcome profiles and may indicate which profile they prefer or that the profiles are too close to call.
Sample size
Mean queries
Std queries
Max queries
Min queries
26
39.8
12.7
74
17
Table 1: Distribution of queries asked with real users. Values indicate the queries asked by Algorithm 1 and do not include the 10 validation queries.
Tolerance ( δ )
Mean accuracy (no TCC)
Std accuracy (no TCC)
Exact
75.8% (80.0%)
16.3% (16.4%)
0.01
77.5% (81.7%)
15.1% (15.1%)
0.05
83.3% (87.1%)
12.8% (12.4%)
0.1
91.2% (93.6%)
9.3% (8.8%)
Table 2: Accuracy of the learned linear utility model on validation queries with varying tolerances δ . In parentheses we show the results on the validation queries where we exclude queries answered with ”too close to call” (TCC) .
Backend
Linear
Basic LLM
Heuristic LLM
Gated
gpt-5.4-mini
82.3%
64.6%
72.3%
74.6%
mistral:7B
82.3%
70.8%
78.5%
77.7%
gpt-6-luna
82.3%
73.1%
79.2%
77.7%
Table 3: Accuracy of the linear utility model and LLM methods on validation queries for users who supplied natural language explanations.
Dimension
Mean weight
Std weight
Avg life years gained per donor
0.37
0.17
One year waitlist survival rate
0.28
0.20
One year waitlist tx rate
0.12
0.09
Socio-economically disadv tx rate
0.09
0.08
Biologically disadv tx rate
0.10
0.16
Avg miles per donor
0.04
0.04
Table 4: Distribution of user weights.
Figure 5: Average weight vector of user utility functions.
Metric
Status quo
Greedy
Ours
Hindsight OPT
Avg life years gained per donor
4.53
10.21
10.10
10.06
One year waitlist survival rate
87.3%
87.4%
87.4%
87.6%
One year waitlist tx rate
45.4%
47.8%
47.5%
50.3%
Socio-economically disadv tx rate
58.8%
60.8%
66.2%
67.3%
Biologically disadv tx rate
58.5%
56.2%
59.5%
60.0%
Avg miles per donor
610
745
731
322
Table 5: Average results for policies in simulation from April to December 2019.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Figure A1 : Results with a noisy oracle parameterized by δ , using random weight vectors with a max budget of 250 queries. Shaded area shows standard deviation across 20 trials per δ .
Sample size
Mean queries
Std queries
22
8.3
11.2
Appendix
Table A1: Distribution of queries asked among users who did not complete the elicitation.
Characteristic
Category
N (%)
Age
18-25
8 (30.8%)
26-35
8 (30.8%)
56+
6 (23.1%)
36-45
2 (7.7%)
46-55
2 (7.7%)
Education
Doctorate
14 (53.8%)
Appendix
Table A2 : Demographics of survey participants.
Hyperparameter
Symbol
Value
Target Euclidean accuracy
ϵ
0.05
ACCPM query budget
T
30
ACCPM query separation
γ
0.3
ACCPM constraint slack
δ
0.01
Iterative sieving sampling constant
c
0.5
Iterative sieving ∥α∥1 bound
B
4.0
Appendix
Table A3 : Hyperparameters for the hybrid cutting plane and sieving algorithm.
Category
Hyperparameter
Value
Architecture
Hidden layers
(128, 64, 32)
Activation function
Leaky ReLU
Leak coefficient
1×10−2
Output activation
Identity
Input features
11
Training
Optimizer
Adam
Appendix
Table A4: Hyperparameters for the neural network potential function.
Machine learning predictors have become essential tools for guiding automated decision making. However, a major misalignment persists: predictive models are typically optimized in terms of standard statistical metrics in isolation from the algorithmic tasks they inform. We highlight this incongruity in the high-stakes domain of organ allocation by demonstrating that any algorithm relying on (even highly accurate) survival predictors optimized for standard metrics -- such as the Concordance index (C-index) -- can yield arbitrarily poor outcomes when used for allocation, failing to guarantee utility better than a uniform random selection. To bridge the gap between survival analysis and policy optimization, we introduce a decision-focused learning approach based on optimizing normalized discounted cumulative gain (NDCG), a mainstay metric in information retrieval. We establish the utility of NDCG in survival analysis by proving that it translates to guarantees on the performance of allocation. Empirically, we propose a bootstrapping approach to optimize the NDCG of existing survival models. Unlike prior work, we also address the challenge of right censorship when evaluating ranking. On historical heart transplant data from the US, our method dramatically boosts the NDCG of baseline models by 50-100%, which translates to tens of thousands of additional life years gained annually when deployed for transplant allocation. We anticipate that our framework will find broader applications in decision making with predictions.
Itai Zilberstein, Ioannis Anagnostides, Tuomas Sandholm
Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA · Additional affiliations: Strategy Robot, Inc., Strategic Machine, Inc., Optimized Markets, Inc.
Pluralistic alignment needs to accommodate diverse preferences under limited human feedback. Using AI simulators to label preference comparisons reduces annotation costs, but variation in simulation accuracy across individuals can leave some people's preferences poorly represented in training. We study how to allocate human feedback across people to construct training data for pluralistic alignment, and how this allocation affects the trained policy. To make this allocation explicit and controllable, we define a social welfare objective over individual supervision utilities that measure label quality. Each query's marginal welfare gain depends on its expected supervision improvement, the recipient's current utility, and application-designated priority. Welfare-Aware Preference Acquisition (WAPA) uses auxiliary reference models to estimate query gains and individual utilities, then selects queries by estimated marginal welfare gain while updating recipient utilities. We prove exact optimality of the acquisition algorithm for the estimated welfare objective under a fixed query budget and model predictions. Experiments on six Roleplay collections and four OpinionQA regions demonstrate improved supervision and controllable allocation tradeoffs. Policy training on four Roleplay collections improves preference prediction for both seen and unseen individuals. When prioritizing a designated group and poorly represented individuals, acquiring human labels for 20% of comparisons recovers 75-86% of the average predictive utility gap between policies trained entirely on AI-generated labels and entirely on ground-truth labels.
When an AI algorithm makes decisions that affect more than one person, aligning it becomes a problem of social choice: how should people's divergent preferences about system behavior be reconciled and aggregated into a single coherent model? The standard approach to aligning frontier AI models\unicodex2013reinforcement learning from human feedback\unicodex2013largely sidesteps this question and has poor social choice guarantees. However, it remains unclear what alternative should replace it. We show that, by focusing directly on an algorithm's welfare consequences, the alignment problem can be reformulated as linear optimization over a convex impact space, which makes it amenable to the standard toolkit of welfare economics and mechanism design. This reformulation clarifies how alignment protocols translate into welfare consequences and, conversely, how a social planner's desired constraints on welfare consequences can be translated back into alignment protocols. We apply this transformation to show that voting-by-issues and random-dictatorship mechanisms are strategyproof and unanimous. Demonstrating the reverse direction, we also apply the impact representation to derive a family of alignment protocols that maximize utilitarian social welfare subject to various social desiderata, such as bounds on individual or group harm. We illustrate the welfare implications of these alignment protocols empirically using real human preferences over kidney allocation, charitable food distribution, LLM responses, and trolley problems.
Zachary Wojtowicz, Michelle Si, Finale Doshi-Velez +1
MIT Cambridge, MA 02139 · Harvard University Cambridge, MA 02138