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.