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.