We consider a setting where agents take action by following their role models in a social network, and study strategies for a social planner to help agents by revealing whether the role models are positive or negative. Specifically, agents observe a local neighborhood of possible role models they can emulate, but do not know their true labels. Revealing a positive label encourages emulation, while revealing a negative one redirects agents toward alternative options. The social planner observes all labels, but operates under a limited disclosure budget that it selectively allocates to maximize social welfare (the expected number of agents who emulate adjacent positive role models). We consider both algorithms and hardness results for welfare maximization, and provide a sample-complexity guarantee when the planner observes a sampled subset of agents. We also consider fairness guarantees when agents belong to different groups. It is a technical challenge that the ability to reveal negative role models breaks submodularity. We thus introduce a proxy welfare function that remains submodular even when revealed targets include negative ones. When each agent has at most a constant number of negative target neighbors, we use this proxy to achieve a constant-factor approximation to the true optimal welfare gain. When agents belong to different groups, we also show that each group's welfare gain is within a constant factor of the optimum achievable if the full budget were allocated to that group. Beyond this basic model, we also propose an intervention model that directly connects high-risk agents to positive role models, and a coverage radius model that expands the visibility of selected positive role models. Lastly, we conduct extensive experiments on four real-world datasets to support our theoretical results and assess the effectiveness of the proposed algorithms.
Figures & tables
Figure 1: An unweighted bipartite graph in which the LHS nodes {x1,x2} represent agents, the RHS nodes {t1,t2,t3} represent targets, and edges connect agents to targets they can emulate. Initially, agents do not know whether a target is positive or negative.
Figure 2: Comparative social welfare returned by random F(Sr) and classical greedy F(Sg) algorithms on Adult dataset for K={1,5} . Black lines mark the maximum F(Sfull) and minimum F(So) welfare. Classic greedy consistently outperforms random when executed at the same target reveal budget K .
Figure 3: Comparison of pre-reveal ( ΔF(ig,g) ) and post-reveal ( ΔF(gi,g)) ) intervention gains, for K=5 with B={1,3} across k NN graphs on the Productivity dataset. Gains increase with decrease in K , and pre-reveal gains may be negative.
Figure 4: Analysis of the training ( tr ) and testing ( ts ) performance (Perf2,Perf3) scores when Algorithm 1 is run under budget K={1,5} on k NN graphs (see Appendix Table 3 ) from the Math dataset. When each agent in train/test sets has at most one neighbor, Perf3 is zero ( 4(b) ). Both Perf2 and Perf3 increase with K .
Appendix figures & tables18 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: A bipartite graph where n=4,\mneg=2 and \mpos=4 .
Figure 6: A bipartite graph example with statistics: n=⌊2κ2⌋+κ+1,\mneg=2κ+2, and \mpos=n . Algorithm 1 achieves an approximation ratio of 2n3
Figure 7: A bipartite graph example with statistics: n=κ2,\mneg=κ+1, and \mpos=n . Algorithm 1 achieves an approximation ratio of n+22 .
agent
neighborhood
x0
{t8−,t9−}
x1
{t3+,t6−,t9−}
x2
{t0+,t6−,t7−,t8−,t9−}
x3
{t5+,t9−}
x4
{t7−}
x5
{t6−,t7−,t9−}
Appendix
Table 1: A bipartite graph where each agent (first column) is connected to its neighborhood of targets (second column) with labels initially unknown to the agents.
Param
value
(m−,m+)
avg.LHS
only+Ns
only-Ns
emptyNs
uni+
kmax
1
(36,10)
1.0
70
258
0
0
2
(37,12)
2.0
15
184
0
0
3
(37,12)
3.0
4
121
0
0
4
(37,12)
4.0
2
86
0
0
5
(37,12)
5.0
1
61
0
0
6
(37,12)
6.0
0
44
0
0
Appendix
Table 2: Statistics of bipartite graphs generated from the Adult ( ρ=14 ) dataset. For all graphs, n=328 .
Param
value
(m−,m+)
avg.LHS
only+Ns
only-Ns
emptyNs
uni+
kmax
1
(19, 16)
1.0
106
100
0
0
2
(21, 17)
2.0
60
52
0
0
3
(22, 17)
3.0
21
30
0
0
4
(22, 17)
4.0
13
14
0
0
5
(22, 17)
5.0
5
8
0
0
6
(22, 17)
6.0
5
6
0
0
Appendix
Table 3: Statistics of bipartite graphs generated from the Math ( ρ=30 ) dataset. For all graphs, n=206 .
Param
value
(m−,m+)
avg.LHS
only+Ns
only-Ns
emptyNs
uni+
kmax
1
(26, 20)
1.0
109
115
0
0
2
(28, 20)
2.0
70
74
0
0
3
(28, 20)
3.0
38
36
0
0
4
(28, 21)
4.0
26
22
0
0
5
(28, 22)
5.0
17
13
0
0
6
(28, 22)
6.0
12
8
0
0
Appendix
Table 4: Statistics of bipartite graphs generated from the Portuguese ( ρ=30 ) dataset. For all graphs, n=224 .
Param
value
(m−,m+)
avg.LHS
only+Ns
only-Ns
emptyNs
uni+
kmax
1
(8, 24)
1.0
77
35
0
0
2
(11, 33)
2.0
62
11
0
0
3
(11, 34)
3.0
52
0
0
0
4
(11, 35)
4.0
28
0
0
0
5
(11, 37)
5.0
16
0
0
0
6
(11, 37)
6.0
9
0
0
0
Appendix
Table 5: Statistics of bipartite graphs generated from the Productivity ( ρ=11 ) dataset. For all graphs, n=112 .
Figure 8: Comparative analysis of the social welfare generated from running the random F(Sr) and the classic greedy F(Sg) algorithms across k NN graphs ( 8(a) – 8(d) ) and the threshold graphs ( 8(e) – 8(h) ) from the 4 datasets (Tables 2 – 5 ). Except on the Adult dataset, when the graphs are nearly complete, budgets K={1,5} have a low effect and social welfare returned by both algorithms is almost equal ( 8(f) – 8(h) ). In contrast, in sparser settings, at similar budget levels, F(Sg) is consistently higher than F(Sr) ( 8(a) – 8(d) ).
Figure 9: Comparative analysis of the social welfare generated from running the heuristic random F(Shr) and heuristic greedy F(Shg) algorithms across k NN graphs ( 9(a) – 9(d) ) and the threshold graphs ( 9(e) – 9(h) ) from the 4 datasets (Tables 2 – 5 ). In general, when the graphs are nearly complete, across budget levels K={1,5} , social welfare returned by both heuristic algorithms is almost equal ( 9(e) – 9(h) ). In sparser settings, at similar budget levels, F(Shg) is consistently higher than F(Shr) ( 9(a) – 9(d) ).
Figure 10: Comparison of social welfare obtained via brute-force F(S⋆) , classic greedy F(Sg) , and heuristic greedy F(Shg) on the Adult and Productivity datasets. Top row are k NN graphs and bottom row are threshold graphs. Across target reveal budgets K={1,5} , in both datasets and graphs, both greedy variants get exact solutions ( F(S⋆) ). As connectivity increases (cf. Tables 2 and 5 ), both greedy variants closely approximate the optimum F(Sfull) (Figures 10(e) – 10(h) where ℓ>6 ). Although we show only the Adult and Productivity datasets, we observe similar patterns on the Math and Portuguese datasets.
Figure 11: Comparative analysis of the average group social welfare generated from running the classic greedy approach across k NN graphs ( 11(a) – 11(c) ) and the threshold graphs ( 11(d) – 11(f) ) from the 3 datasets (Tables 2 – 4 ) on the whole graph . When the graph connectivity is high, there is no disparity in social welfare generated for the 2 groups.
Figure 12: Comparative analysis of the average group social welfare generated from running the classic greedy approach across k NN graphs ( 12(a) – 12(c) ) and the threshold graphs ( 12(d) – 12(f) ) from the 3 datasets (Tables 2 – 4 ) separately on each group . That is, when we run greedy at a budget K/2 solely on each group’s graph. When the groups’ graph connectivity is high, there is no disparity in social welfare generated for the 2 groups.
Figure 13: Pre- and post-reveal intervention gains ( ΔF(ig,g) and ΔF(gi,g) ) across datasets, target reveal budgets K∈{1,5} , intervention budgets B∈{1,3} , and graph generation methods ( k NN and threshold) (Tables 2 and 3 ). For both datasets, lower K often yields larger intervention gains. A high B can sometimes be redundant when agents have all-positive neighborhoods, and/or very few agents have empty or all-negative neighborhoods and greedy is optimal ( 13(b) , 13(d) , 13(e) , 13(g) ). When the number of agents with all-negative neighborhoods is at least B , both pre- and post-reveal interventions gains ΔF(ig,g) and ΔF(gi,g) are atmost B ( 13(a) , 13(c) ).
Figure 14: Pre- and post-reveal intervention gains ( ΔF(ig,g) and ΔF(gi,g) ) across datasets, target reveal budgets K∈{1,5} , intervention budgets B∈{1,3} , and graph generation methods ( k NN and threshold) (Tables 4 and 5 ). For both datasets, lower K often yields larger gains. A high B can be redundant when many agents have all-positive neighborhoods ( 14(e) , 14(b) , 14(d) ). Pre-reveal intervention can yield negative gains (Figure 14(g) , kmax={9,10} ) but may also sometimes outperform post-reveal intervention (Figure 14(c) , kmax=10 ).
Figure 15: Performance of the greedy coverage radius algorithm (Algorithm 8 ) on the Adult, Math, Portuguese, and Productivity datasets. Number of agents reached increases with the radius budget.
Figure 16: Performance of Algorithm 1 in the learning setting on the Adult and Math datasets under three metrics ( Perf1,Perf2,Perf3 ) for k NN and threshold generated graphs (Tables 2 and 3 ). Across both datasets, larger budget K lead to weakly higher performance. Increasing graph connectivity raises overall scores while reducing the performance gap between budgets (e.g., in Figures 16(d) – 16(f) ). Compared to Figures 16(j) and 16(l) , the performance scores cluster more tightly across budgets in Figure 16(k) because unlike them, denominator in Perf2 includes all sampled agents.
Figure 17: Performance of Algorithm 1 in the learning setting on the Portuguese and Productivity datasets under three metrics ( Perf1,Perf2,Perf3 ) for k NN and threshold generated graphs (Tables 4 and 5 ). Across both datasets, larger budget K lead to weakly higher performance. Increasing graph connectivity raises overall scores while reducing the performance gap between budgets (e.g., in Figures 17(j) – 17(l) ). Because of presence of unhelpable agents in the graphs (Table 5 ), Perf2 can remain below 100 even when the algorithm is optimal (cf. Figure 17(k) ). Lastly, because the Math and Portuguese datasets were curated in a similar manner [ 9 ] , learning setting results on the generated graphs are closely similar.
A planner in a network of strategic agents faces three entangled challenges: the optimum depends on agents' private information, queried agents may misreport to steer the outcome, and exact computation does not scale. We study these challenges in multi-activity network games with heterogeneous private technologies, in which the planner sets non-discriminatory prices. We show that the optimal prices admit a centrality-based decomposition of the welfare kernel: each agent's contribution scales with its squared centrality in a network reweighted by agents' preferences across activities. This decomposition motivates Poll, a polling algorithm in which the planner samples one agent per round, walks briefly through the agent's neighborhood, and updates the price from a local report. From the same decomposition flow three forms of efficiency: computationally, Poll uses significantly fewer operations than exact computation and other distributed methods, requiring up to three orders of magnitude less communication on a real-world network with over 300,000 agents; statistically, its query complexity scales with topology and preference heterogeneity rather than explicitly with population size; and economically, it converges to welfare-maximizing prices while admitting behavior-specific implementations that induce truthful reports and detect adversarial deviations.
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
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.