Research map / Learning theory and algorithms / Submodular and game algorithms
Learning Social Welfare Functions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Learns weighted power mean social welfare functions from cardinal welfare values or pairwise comparisons, giving PAC/sample-complexity bounds and practical gradient-plus-grid-search algorithms evaluated on semi-synthetic food-donation data.
Problem
Learning the implicit social welfare function (weighted power mean family) a decision maker uses, from past decisions given as utility vectors with cardinal welfare values or as pairwise comparisons, with noisy labels.
Approach
Treats the power mean exponent p and weights w as learnable parameters, proves pseudo-dimension and VC bounds for the family (polynomial sample complexity, O(1) or O(d log d) in d), and exploits quasilinearity in w for fixed p to run gradient descent inside a grid search over p.
Key results
- Cardinal case: sample complexity O(1) in d for known weights and O(d log d) for unknown weights under l2 loss, with PAC bounds derived via pseudo-dimension (Pdim = 1 for known weights).
- Ordinal (pairwise) case: VC dimension bounded by 2(log2 d + 1) for known weights and 8(d log2 d + 1) for unknown weights, with matching lower bounds for the known-weight case.
- Empirically, KL divergence between learned and true weights decreases with more samples and lower noise, and learned p approaches true p.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase the number of training samples | power-mean learning, cardinal food-allocation simulations · Food resource allocation simulations | test loss | Helped |
| reduce added Gaussian noise | power-mean learning, cardinal food-allocation simulations · Food resource allocation simulations | test loss | Helped |
| increase the number of training samples | power-mean learning, cardinal food-allocation simulations · Food resource allocation simulations | KL divergence between learned and true weights | Helped |
| reduce added Gaussian noise | power-mean learning, cardinal food-allocation simulations · Food resource allocation simulations | KL divergence between learned and true weights | Helped |
| increase the number of training samples | power-mean learning, cardinal food-allocation simulations · Food resource allocation simulations | learned p similarity to true p | Helped |
| reduce logistic-noise temperature | power-mean learning, ordinal food-allocation simulations · Food resource allocation simulations | test loss | Mixed |
| increase the number of training samples | power-mean learning, ordinal food-allocation simulations · Food resource allocation simulations | test accuracy on noiseless data | Helped |
| increase logistic-noise temperature | power-mean learning, ordinal food-allocation simulations · Food resource allocation simulations | test accuracy on noiseless data | Helped |
| increase the number of training samples | power-mean learning, ordinal food-allocation simulations · Food resource allocation simulations | KL divergence between learned and true weights | Helped |
| reduce logistic-noise temperature | power-mean learning, ordinal food-allocation simulations · Food resource allocation simulations | KL divergence between learned and true weights | Helped |
Surprising findings
- The known-weight VC dimension is superconstant and scales with log d, which the authors found surprising.
- Learning p is harder for negative p than for positive p in the ordinal case, since changes in p cause smaller loss changes for negative p.
Limitations
- Dataset is not publicly available, so results depend on semi-synthetic simulations.
- Non-convex loss; no global optimality guarantees for the gradient-based algorithm.
- Assumes utility vectors are exact; estimation error in utilities is not handled.
Experimental setup
Datasets: WeBuildAI food donation stakeholder utility dataset (not publicly available)
Metrics: test loss KL divergence between learned and true weights learned p vs true p test accuracy on noiseless data
Builds on: WeBuildAI Bradley-Terry-Luce model Talagrand contraction lemma
Closest papers by meaning
- Navigating the Social Welfare Frontier: Portfolios for Multi-objective Reinforcement Learning (ICML 2025 · similarity 0.85)
- Decongestion by Representation: Learning to Improve Economic Welfare in Marketplaces (ICLR 2024 · similarity 0.82)
- Policy Aggregation (NeurIPS 2024 · similarity 0.82)
- Multidimensional Bayesian Utility Maximization: Tight Approximations to Welfare (NeurIPS 2025 · similarity 0.82)
- Weak Strategyproofness in Randomized Social Choice (AAAI 2025 · similarity 0.82)
- Preference Learning of Latent Decision Utilities with a Human-like Model of Preferential Choice (NeurIPS 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.