Source-linked AI summary
Decoupling Procedural and Outcome Fairness in Seed Allocation for Influence Maximization
Xiaojing Du, Chunlei Meng, Wentao Gao, Ke Sun, Feiyu Yang
TL;DR
Equal seed access can leave groups with unequal outcomes because spillovers depend on social structure, and equal outcomes may require unequal access. The paper derives an allocation–structure characterisation and develops DPA, which achieves the smallest mean outcome gap among compared methods at common access tolerances on both suites. On Pokec, DPA nearly equalises modelled gender outcomes while preserving aggregate benefit.
Problem
Equal seed access can yield unequal group outcomes through social spillovers, so access audits alone do not capture outcome disparities.
Source: §1 · p. 1Method
The paper derives an exact allocation–structure decomposition and sharp first-moment floor, then uses DPA to combine group quotas with contribution-based seed selection and evaluates propagation variants.
Source: §1 · pp. 1–2, §3 · p. 2Results
DPA yields the smallest mean gap at common access tolerances on both suites with near-optimal band-constrained total outcome, and nearly equalises modelled gender outcomes on Pokec while preserving aggregate benefit.
Source: §7 · p. 8Takeaways & Limitations
Quotas, seed composition, and propagation shape both access and spillover benefits.
Source: §7 · p. 8
Abstract
from arXiv · showhide
On online social platforms, equal seed access to interventions can yield unequal group outcomes through social spillovers, so an access audit alone can miss outcome disparities. We characterise this trade-off through an exact allocation-structure decomposition and a sharp first-moment floor for graph-independent seeding under additive spillovers on stochastic block networks. Decoupled Procedural Allocation (DPA) combines group quotas with selection by seeds' contributions to each group's outcome. Rankings balance total outcome against disparity, and within-quota exchanges reduce the gap. Computable bounds quantify retained total outcome. DPA achieves the smallest mean outcome gap among the compared methods at the common access tolerances on both development and prospective suites. Exposure and independent-cascade studies show how the propagation mechanism changes this trade-off. On Pokec, DPA nearly equalises modelled gender outcomes at the closest access-parity quota while preserving most of the degree-based allocation's total outcome.
1 Introduction
Equal per-capita seed access can still produce unequal group outcomes through network spillovers, while outcome parity may require unequal access. The paper characterises this trade-off and introduces DPA to choose access-feasible quotas and seeds.
1 Introduction
- The paper quantifies attainable outcome disparity under access constraints and the total-outcome cost of reducing it.The motivating tension is that equal access can leave one group with fewer opportunities to receive spillovers, while equal outcomes can require unequal initial access.Source: §1 · p. 1
- On the illustrated graph, equal seed counts yield group means of 1 and 2/3, and equalising outcomes requires giving group B more direct access.No nonempty seed set on this graph achieves both allocation parity and outcome parity.Source: §1 · p. 1
- An exact allocation–structure decomposition yields a sharp first-moment floor for outcome disparity under access constraints in graph-independent seeding on stochastic block networks.The analysis also distinguishes count exposure, which accumulates seeded-neighbour contributions, from fraction exposure, which averages them and reduces structural disparity.Source: §1 · p. 1
- DPA combines group quotas with seed selection by contributions to group outcomes, using tilted rankings, within-group exchanges, and bounds on retained total outcome.An exact envelope excludes quotas that cannot meet the outcome tolerance.Source: §1 · pp. 1–2
- The contributions span theoretical bounds, quota and seed-selection methods, and comparisons on synthetic and Web graphs, including a prospective suite and million-user Pokec.The experiments compare recent seed-level methods and exact integer-programming references across quotas, seed composition, and exposure.Source: §1 · p. 2
2 Related Work
Prior fair influence maximization work addresses group outcomes through coverage, welfare, and seed constraints, while network interference and procedural fairness provide complementary frames. This paper connects access criteria to outcomes under spillovers.
2 Related Work
- Fair influence maximization studies group equity through maximin objectives [31], group welfare [22], and proportional seed constraints.Prior approaches also include time-critical coverage, randomised policies [6], and scalable optimisation.Source: §2 · p. 2
- Network-interference research includes exposure mappings, graph-cluster randomisation [32], linear peer-effects models, and work on misspecification.The paper uses planner-supplied direct and spillover coefficients to derive an explicit fairness decomposition and compares count with fraction exposure.Source: §2 · p. 2
- Procedural justice concerns decision processes and distributive justice their benefits; here, equal per-capita treatment operationalises access in network seed allocation.The paper characterises how that access criterion relates to group outcomes under spillovers.Source: §2 · p. 2
3 Problem Formulation
The formulation allocates a fixed seed budget across groups and measures both access and outcome gaps. Outcomes follow an additive neighbourhood-exposure model, with separate graph-independent population analysis and observed-graph selection.
3 Problem Formulation
- A graph is partitioned into nonempty groups, and a seed set has fixed size k with treatment indicators marking selected users.The setup defines each user’s neighbours and group-specific neighbour counts.Source: §3 · p. 2
- The additive neighbourhood-exposure model gives seeds a direct gain β and each seeded neighbour a spillover gain γ, with planner-specified coefficients.Outcomes are scores that can exceed one; fraction exposure and independent-cascade activation are studied separately.Source: §3 · p. 2
- For a fixed graph and seed set, group means and total outcome are available in closed form, while the SBM analysis also averages over graphs and independent seed randomisation.Population analysis assumes graph-independent allocation, whereas observed-graph selection uses exact group contributions.Source: §3 · pp. 2–3
- Access and outcome gaps measure differences across groups, with tolerances τ and ε constraining seed-rate and outcome disparities.For more than two groups, each gap is the maximum over group pairs; τ = 0.1 permits at most a ten-percentage-point difference between two seed rates.Source: §3 · p. 2
- When the outcome band is infeasible, the formulation minimises the gap and uses total outcome to break ties; if no integer quota meets access tolerance, it reports the minimum attainable access gap.The outcome tolerance sets the planner’s parity resolution, and its sensitivity is evaluated experimentally.Source: §3 · p. 2
4 Structural Characterisation
For graph-independent seeding on balanced stochastic block networks, expected outcome disparity separates into allocation and structural components. The resulting first-moment floor identifies the least disparity permitted by an access tolerance, with exposure definitions and group structure shaping the result.
4 Structural Characterisation
- In the balanced two-block SBM, graph-independent seed identities and group counts are independent of the sampled graph, and no spillover makes outcome disparity equal β times access disparity.The exact decomposition separates allocation and structural terms, and relates the signed first moment to the absolute gap used for evaluation.Source: §4 · p. 3
- The sharp first-moment floor lower-bounds expected outcome disparity for every graph-independent allocation meeting the access tolerance.It minimises the continuous first-moment gap over rates satisfying budget, capacity, and access constraints; the proof uses the range of the signed expected difference and Jensen’s inequality.Source: §4 · p. 3
- At access parity, structural disparity depends on within-group density asymmetry; offsetting it requires a higher seed rate in B when c is positive, but the direction reverses when c is negative.When c = 0, reallocation leaves the first moment unchanged.Source: §4 · p. 3
- Under fraction exposure, equal seed rates give equal expected exposure at non-isolated vertices, leaving isolation as the structural source of difference.The isolation coefficient vanishes as the sparser group’s expected degree diverges, while the absolute gap also includes graph fluctuations.Source: §4 · p. 3
- For multiple groups, a third block contributes to a pairwise difference when its cross-block probabilities differ across the pair.Uniform cross-block probabilities remove these third-block terms.Source: §4 · p. 3
5 Decoupled Procedural Allocation
DPA separates quota choice from seed selection, using model-based quota rules and observed-graph contributions to balance access, outcome disparity, and total outcome. Its guarantees and selection procedures quantify which quotas can meet an outcome band and how seed exchanges can improve disparity within a quota.
5 Decoupled Procedural Allocation
- DPA derives model-based quotas from the structural decomposition and selects observed-graph seeds using group contributions and quota-preserving exchanges.Source: §5 · p. 3
5.1 Closed-Form Quotas
- The closed-form quota rule minimizes the predicted gap over feasible continuous rates using estimated structural coefficients.Estimating coefficients from observed group edge densities takes O(|E|) time.Source: §5.1 · p. 3
5.2 Within-Group Selection and Guarantees
- Degree ranking maximizes fixed-quota total outcome, while DPA-r randomizes within groups and, with oracle coefficients, attains the first-moment floor up to rounding.The expected absolute gap adds at most r_n; rounded access disparity is bounded by the tolerance plus 1/n_A + 1/n_B.Source: §5.2 · p. 4
5.3 Within-Quota Selection on an Observed Graph
- At each quota, the within-quota envelope bounds every seed set’s signed outcome gap and rules out quotas whose interval misses the target band.When every interval excludes zero, extreme contribution prefixes attain the minimum-gap bound.Source: §5.3 · p. 4
- Tilted rankings trade total outcome against signed gap, while within-group exchanges preserve the quota and change the gap by the exchanged seeds’ contributions.The ranking maximizes total outcome minus the tilt times the signed gap, and its signed gap is non-increasing with the tilt.Source: §5.3 · p. 4
6 Experiments
The experiments compare allocation and outcome fairness across synthetic and Web graphs, test the structural floor and propagation effects, and assess runtime and Pokec outcomes.
6.1 Setup
- Development combines ten SBM graphs, five BA graphs, BlogCatalog, Flickr, and Pokec; prospective evaluation adds ten SBM, five BA, and Amherst41.Methods share each graph, budget, and outcome model; real-network outcomes are modelled scores.Source: §6.1 · p. 5
6.2 Compared Methods
- The comparison spans aggregate-outcome, access-parity, and group-outcome baselines, plus LP/greedy seed-level methods and DPA variants.DPA variants include density-estimated quotas, degree-ranked or random selection, and degree-prefix searches across feasible quotas.Source: §6.2 · p. 5
6.4 Fairness Trade-offs on Synthetic and Web Graphs
- DPA has the smallest access-feasible mean gap across development and all three prospective settings, reaching at most 3.2 × 10−4 on four small development settings at τ=0.1.On Amherst41, it nearly equalises modelled gender outcomes at the closest access-parity quota while retaining 99.8% of the degree-based allocation’s total outcome.Source: Table 2 · p. 6, Table 3 · p. 6, §6.4 · p. 6
- Within-quota contribution-based selection narrows gaps beyond degree prefixes; at parity, DPA retains more than 90% on BlogCatalog and Flickr and 66.4% on BA-Synth.On BA-Synth, DPA reaches a 3.2 × 10−4 gap with 1.7% less total outcome than LP-Greedy-q.Source: §6.4 · p. 6
6.5 Outcome Tolerance and Exposure
- All 102 outcome-tolerance evaluations meet their requested bands; count-exposure gaps rise with heterogeneity while fraction-exposure gaps remain around 10−3.On seven small-graph settings, tightening tolerance to 10−4 reduces mean total outcome by at most 0.303%.Source: §6.5 · p. 6
6.3 Bound Tightness and Allocation Tolerance
- At access parity, oracle gaps differ from the structural floor by 2.1%, 2.5%, and 0.3% at n=400, 1000, and 2000.At n=1000 and H=0.04, increasing τ from 0 to 0.05 lowers the randomised gap from 0.586 to 0.291; the floor reaches zero near τ=0.096.Source: §6.3 · pp. 5–6, Figure 3 · p. 7
6.6 Access Constraints under Multi-Hop Diffusion
- Under fixed within-group degree rankings, activation gaps meet the persistence criterion on SBM-Synth, BA-Synth, and Flickr at pIC=0.05, but not at 0.01.The reported quotas vary to isolate access constraints under independent-cascade diffusion.Source: §6.6 · pp. 6–7, Table 4 · p. 8
6.7 Computational Scale and the Pokec Case Study
- On Pokec, at the closest parity quota DPA cuts the gap from 0.100 to 2.4 × 10−7 while retaining 99.14% of the degree allocation’s total outcome.At that quota, DPA-r retains 12.04%; a small positive outcome tolerance permits substantially higher total benefit than exact parity. DPA runs in 20.9 s on Pokec versus 79.6 s for LP-Greedy.Source: §6.7 · pp. 7–8, Table 6 · p. 8
7 Conclusion
The paper concludes that DPA reduces outcome gaps under common access tolerances while retaining near-optimal total outcome. Its certificates bound possible improvement, and its Pokec results nearly equalise modelled gender outcomes while preserving aggregate benefit.
7 Conclusion
- DPA yields the smallest mean gap at common access tolerances on both suites, with near-optimal band-constrained total outcome.The certificates bound remaining total-outcome improvement within each quota and, after a full quota scan, over all access-feasible allocations.Source: §7 · p. 8
- On Pokec, DPA nearly equalises modelled gender outcomes while preserving aggregate benefit.The conclusion also notes that quotas, seed composition, and propagation shape access and spillover benefits.Source: §7 · p. 8
- The exact decomposition and sharp first-moment floor relate access to propagated benefits under graph-independent seeding.Source: §7 · p. 8
- Future work could learn intervention-specific spillover effects and extend the sharp floor to multiple groups.Source: §7 · p. 8