Social Welfare Maximization

Follow this topic Ask about this topic

Latest papers

20 papers3 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Oct 13, 2026

Who Should We Listen to More? Welfare-Aware Preference Acquisition for Pluralistic Alignment

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.

Ruomeng Ding, Tianwei Gao, Lianrui Geng +2

University of North Carolina at Chapel Hill

Social Welfare Maximization Preference Alignment Pluralistic Alignment Preference Elicitation

Oct 6, 2026

Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret

We study fair multi-armed bandits under the Nash Social Welfare (NSW) objective, which measures performance via the geometric mean of accumulated rewards. Existing work defines Nash regret as

\mathrm{NR}_T = μ^\star - (\prod_{t=1}^T \mathbb{E}μ_{I_t})^{1/T}

, where

μ_{I_t}

is the mean reward of the recommended arm

I_t

and

T

is the horizon. Since it applies the geometric mean to per-round marginal expectations, it ignores the joint distribution of rewards across rounds, leaving the NSW fairness motivation unaddressed at the trajectory level. We propose trajectory-wise Nash regret

\widetilde{\mathrm{NR}}_T = μ^\star - \mathbb{E}[(\prod_{t=1}^T μ_{I_t})^{1/T}]

, which computes the geometric mean over complete sample paths before taking expectations, capturing NSW fairness more faithfully. By Jensen's inequality,

\widetilde{\mathrm{NR}}_T \geq \mathrm{NR}_T

, making it a strictly stronger metric. We also introduce high probability Nash regret

\widehat{\mathrm{NR}}_T = μ^\star - (\prod_t μ_{I_t})^{1/T}

, giving the first high probability regret bounds in fair bandits. Our two-phase algorithm, Round Robin Nash Confidence Bound (RR-NCB), combines round robin exploration with a Nash confidence bound index policy. We show

\widetilde{\mathrm{NR}}_T \leq \widetilde{\mathcal{O}}(\sqrt{k\log T/T})

and, with probability

1-δ

,

\widehat{\mathrm{NR}}_T \leq \widetilde{\mathcal{O}}(\sqrt{k\log(kT/δ)/T})

, matching the optimal

\widetilde{\mathcal{O}}(\sqrt{k/T})

rate despite the stronger metrics. Optimality follows from a lower bound via AM-GM and standard

k

-armed bandit minimax arguments. Simulations validate our theory.

Avishek Ghosh

Department of Computer Science and Engineering Indian Institute of Technology, Bombay

Multi-Armed Bandits Social Welfare Maximization

Oct 3, 2026

Maximizing $p$ -Mean Social Welfare in the High-Multiplicity Setting: Few Agent Types and Few Item Types

The

p

-mean welfare objective unifies several classical social welfare criteria for the allocation of indivisible goods. We study its maximization under additive nonnegative utilities when item and agent multiplicities are encoded in binary. For every fixed finite rational

p<1

,

p\neq0

, we show that the problem is

\mathsf{NP}

-hard with only two item types. Nash welfare (

p=0

) and egalitarian welfare (

p=-\infty

) are NP-hard with three item types. These results hold both for computing an optimal allocation and for rational-threshold decision, and the utilities and threshold can be required to be positive integers. We also show that maximizing

p

-mean social welfare is strongly NP-hard with one agent type and an unrestricted number of item types, for every fixed finite rational

p<1

and for

p=-\infty

. A quantitative gap in this reduction rules out an FPTAS in the latter setting unless

\mathsf{P}=\mathsf{NP}

. On the positive side, for a fixed number of item types and an arbitrary number of agent types, we give an FPTAS for every fixed

p\in\mathbb Q\cup\{-\infty\}

. Its running time is polynomial in the compact input length and in

1/\varepsilon

, and it returns a compressed allocation. For a fixed number of agent types and an unrestricted number of item types, we give a PTAS for every fixed finite rational

p<1

, also in the fully compact model. We further give explicit compact-model proofs of the classical exact allocation algorithms for one item type, and for egalitarian welfare with two item types. These results essentially settle the complexity and approximability of

p

-mean welfare maximization with few item types and/or few agent types, leaving only the exact complexity of Nash welfare maximization with two item types unresolved in the small-item-type classification.

Trung Thanh Nguyen, Khaled Elbassioni

DataOptLab, National Economics University, Hanoi 11616, Vietnam · Khalifa University of Science and Technology, Abu Dhabi 127788, UAE

Social Welfare Maximization Fair Resource Allocation Approximation Algorithms

Sep 3, 2026

EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments

We study the allocation of indivisible goods among agents with identical additive valuations, focusing on envy-freeness up to one good (EF1) and Nash social welfare (NSW). Since every maximum-NSW allocation is EF1 under additive valuations, the associated threshold problem inherits the known strong NP-hardness of NSW maximization under identical additive valuations and is strongly NP-complete. We therefore focus on welfare guarantees satisfied by arbitrary EF1 allocations. Although every such allocation is known to achieve an

e^{-1/e}

-approximation to the unrestricted optimal NSW, we identify conditions yielding stronger guarantees. Under uniform valuations, every EF1 allocation is NSW-optimal. Under an

\varepsilon

-small-item condition, every EF1 allocation achieves an explicit approximation ratio

ρ_n(\varepsilon)

satisfying

ρ_n(\varepsilon) = 1-O(\varepsilon^2)

as

\varepsilon\to 0

for fixed

n

. We further consider the stronger sequential requirement that

\operatorname{EF1}

be maintained after every item assignment. For this setting, we introduce PriorityNet, a deep reinforcement learning framework trained with Proximal Policy Optimization (PPO) and equipped with prospective

\operatorname{EF1}

action masking, which guarantees prefix-wise

\operatorname{EF1}

by construction. Across 3,000 test instances in each of the offline full-information and random-order online regimes (

n\in[2,20]

,

m\in[5,100]

), PriorityNet achieves mean normalized

\operatorname{NSW}

values of

0.9911

and

0.9701

, respectively. Relative to the offline Longest Processing Time (LPT) heuristic and the online least-valued-bundle rule, it attains instance-wise win-minus-loss rates of

+27.10\%

and

+17.87\%

. Its aggregate welfare matches the offline LPT baseline to four decimal places and modestly improves upon the online baseline, from

0.9694

to

0.9701

.

Zih-Sian Yang, Yi-Hao Chen, Yu-Te Kuan +3

National Taiwan Ocean University, Keelung City 202301, Taiwan · National Yang Ming Chiao Tung University, Hsinchu City 300, Taiwan

Fair Resource Allocation Online Resource Allocation Social Welfare Maximization

Aug 25, 2026

Algorithmic Impact Reveals the Hidden Social Choice Structure of Alignment

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

\unicode{x2013}

reinforcement learning from human feedback

\unicode{x2013}

largely 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

Social Welfare Maximization AI Alignment Preference Alignment Social Choice Theory Mechanism Design

Aug 3, 2026

Population-Robust Feature Selection via Generalized Welfare Optimization

Choosing which features to collect is a deployment decision: the same limited questionnaire, test panel, or sensor set may need to serve several heterogeneous populations. Standard feature-selection methods typically optimize for one large population, while existing robust approaches tend to learn one shared model for every population. We introduce PopFS, a method for learning one shared, deployable feature set that is robust to population differences while letting each pop- ulation train its own model. PopFS uses a tunable welfare objective that lets practitioners balance overall predictive ben- efit against stronger protection of the populations that benefit least. To make this objective practical at scale, PopFS first uses multitask sparse learning to reduce the candidate pool, then searches directly over hard feature sets by ranking promising additions and swaps and fully refitting only a shortlist. Across eight population splits from six prediction tasks drawn from five tabular and public-health datasets, PopFS consistently achieves strong average and worst-population performance while scaling to thousands of candidate features. A 43-state COVID-19 nowcasting study further shows that changing the welfare objective can improve the least-served states with lit- tle change in average performance and yields an interpretable change in the selected symptom signals. Our code is available at https://github.com/Rachel-Lyu/PopFS.

Ruiqi Lyu, Alistair Turcan, Bryan Wilder

Carnegie Mellon University

Distribution Shift Robustness Social Welfare Maximization Feature Selection

Jun 22, 2026

Welfarist Control Design -- How to fulfill the societal mandate in multi-agent control?

At the core of most socio-technical systems lies a scarce resource that is allocated among agents: highway lanes, public transit, road space, water rights, energy access, grid capacity, user attention, pollution rights, etc. With further automation of the underlying allocation processes, control engineers are increasingly tasked to make decisive assumptions regarding what society wants. In practice to date, design choices are largely driven by industry norms and conventions rather than a result of conscientiously responsible and ethical design. In this paper, we look at tools available to control engineers to design systems in a more principled manner in order to match the societal mandate. We consider three control design paradigms: online feedback optimization, control of Markov decision processes, and model predictive control. Beginning with aggregating individual agents' preferences into control design objectives, subsequently ensuring and certifying the fulfillment of those specifications, we argue that the feedback nature of control systems enables appropriate allocation of the shared resources in ways hitherto unparalleled.

Sophie Hall, Kai Zhang, Ilia Shilov +2

Multi-Agent Control Social Welfare Maximization

Jun 19, 2026

Simultaneously Efficient Allocation of Indivisible Items Across Multiple Dimensions

Many allocation problems are intrinsically multidimensional, since an item may contribute differently to several criteria, and optimizing a single aggregate objective can hide severe losses in other dimensions. We study how much efficiency can be guaranteed simultaneously when indivisible items have multiple attributes. To this end, we introduce the multidimensional efficient allocation (MDEA) model, where each agent has an additive valuation in each dimension, and investigate simultaneous efficiency under utilitarian social welfare (USW) and egalitarian social welfare (ESW). Our results reveal a sharp worst-case frontier. For exact efficiency, maximizing the number of dimensions attaining the USW optimum admits a

c/\ell

-approximation for every fixed constant

c

, and this dependence on the number

\ell

of dimensions is essentially unavoidable; for ESW, even deciding whether two dimensions can be optimized simultaneously is NP-hard with binary valuations. For approximate simultaneous efficiency in every dimension, we identify a tight threshold of order

1/\ell

, showing that such guarantees always exist for both USW and ESW, while any asymptotically better dependence on

\ell

is impossible, even for binary valuations. Finally, we introduce three natural multidimensional Pareto notions and characterize both their relationships and their computational complexity.

Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui

Chuo University, Tokyo, Japan · Indian Institute of Technology Kharagpur, Kharagpur, India

Combinatorial Optimization Approximation Algorithms Multi-Objective Optimization Pareto Optimization Social Welfare Maximization

Jun 18, 2026

Equilibrium with Internal Transfers

Nash equilibrium (NE) arises from selfish utility maximization, yet its social welfare can be arbitrarily far from optimal. Moreover, computing an NE is intractable in general. We study augmented game models in which players use budget-balanced internal transfers to improve incentives before play. We first introduce Self-Enforcing Transfer Equilibrium (SETE), where players commit to nonnegative peer-to-peer transfers that are paid only if the recipient does not deviate from a prescribed strategy. For polymatrix games, we show that every stationary point of the social welfare function, in particular any socially optimal strategy profile, can be sustained as a SETE. This induces a Nash equilibrium in the agent normal form of the corresponding augmented game. We further propose a polynomial-time algorithm and a decentralized learning dynamic to compute such product-form equilibria. We then introduce Mediated Self-Enforcing Transfer Equilibrium (M-SETE), where a mediator makes both the payment schedule and the prescribed strategies binding offers. This additional enforcement resolves the agent-normal-form limitation: an M-SETE is a Nash equilibrium of the augmented game itself, not merely of its agent normal form, and any socially optimal strategy profile can be supported as an M-SETE in any finite game while preserving budget balance. Thus, internal transfers improve welfare and computation while preserving independent play on the equilibrium path. When full sequential-game stability is required, binding mediation provides the corresponding implementation.

Mingyang Liu, Gabriele Farina, Asuman Ozdaglar

LIDS, EECS, Massachusetts Institute of Technology

Nash Equilibrium Game Theory Social Welfare Maximization

May 29, 2026

Social welfare optimisation under institutional reward and punishment

Institutional incentives are widely used to promote cooperation among autonomous, self-regarding agents, from human societies to multi-agent and AI systems. Existing work typically treats incentive design as a bi-objective problem: minimise institutional cost while achieving a high long-run frequency of cooperation. Whether such schemes also maximise social welfare - total population payoff net of institutional expenditure - has remained largely unexplored. We develop a welfare-centric framework for institutional incentives in finite, well-mixed populations playing a social dilemma (Donation Game and Public Goods Game), considering both rewards for cooperators and punishments for defectors. For each mechanism, we derive explicit expressions for expected social welfare and characterise how it depends on incentive efficiency and selection intensity. Analytically, we identify parameter regimes where social welfare has a single optimal incentive level and regimes with qualitative phase transitions, in which welfare becomes non-monotonic with multiple local optima. We prove that any welfare-maximising incentive is either zero or concentrated around a simple closed-form target, and we provide an efficient algorithm to compute these optima. Comparing reward and punishment, we further derive close-formed conditions under which reward outperform punishment in terms of social welfare for any given budget. Overall, our results reveal a systematic gap between incentives optimised for cost or cooperation frequency and those that maximise welfare.

Van An Nguyen, Vuong Khang Huynh, Huu Loi Bui +8

Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology (HCMUT), Vietnam · 2Vietnam National University - Ho Chi Minh City (VNU-HCM), Vietnam · School of Computing, Engineering and Digital Technologies, Teesside University,2026 United Kingdom +1

Social Dilemmas Mechanism Design Social Welfare Maximization Evolutionary Game Theory

May 19, 2026

Multi-Dimensional Matching in Market Design

This paper proposes a computationally efficient mechanism for multi-dimensional matching markets where agents report preferences over object features rather than complete utility assessments. We use Singular Value Decomposition (SVD) to identify the principal direction of variation in feature space and match agents to objects along this dimension, reducing a complex multi-dimensional problem to an effectively one-dimensional problem solvable in

O(N \log N)

time. We show that when data exhibit low effective dimensionality, our mechanism approximately maximizes Nash Social Welfare, satisfies distributional truthfulness, and achieves symmetry. We establish a novel connection between Nash Social Welfare and Geometric Distributionally Robust Optimization, providing robustness guaranties. Numerical experiments demonstrate that our approach achieves 99% optimal welfare while running three orders of magnitude faster than direct optimization. The framework applies naturally to school choice, labor markets, and course allocation, where feature-based elicitation reduces the cognitive burden on agents.

Irene Aldridge

Irene Aldridge

Mechanism Design Social Welfare Maximization

May 11, 2026

The Price of Proportional Representation in Temporal Voting

We study proportional representation in the temporal voting model, where collective decisions are made repeatedly over time over a fixed horizon. Prior work has extensively investigated how proportional representation axioms from multiwinner voting (e.g., justified representation (JR) and its variants) can be adapted, satisfied, and verified in this setting. However, much less is understood about their interaction with social welfare. In this work, we quantify the efficiency cost of enforcing proportionality. We formalize the welfare-proportionality tension via the worst-case ratio between the maximum achievable utilitarian welfare and the maximum welfare attainable subject to a proportionality axiom. We show that imposing proportional representation in the temporal setting can incur a growing, yet sublinear, welfare loss as the number of voters or rounds increases. We further identify a clean separation among axioms: for JR, the welfare loss diminishes as the time horizon grows and vanishes asymptotically, whereas for stronger axioms this conflict persists even with many rounds. Moreover, we prove that welfare maximization under each axiom is NP-complete and APX-hard, even under static preferences and bounded-degree approvals, and provide fixed-parameter algorithms under several natural structural parameters.

Nicholas Teh

University of Oxford

Social Choice Theory Social Welfare Maximization

May 7, 2026

Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimization

We study multi-objective multi-agent multi-armed bandits (MO-MA-MAB) under stochastic rewards, where agents observe heterogeneous reward vectors and communicate over time-varying graphs. We formulate this emerging problem setting to address efficient learning, measured by Pareto regret, and incorporate fair learning as an additional goal, captured via social welfare. To measure efficiency, we formulate Pareto regret and develop Pareto UCB1 Gossip, whose novel exploration radius explicitly separates statistical uncertainty in Pareto-based inference from consensus error. To express the fairness constraint, we formulate a Nash Social Welfare objective over preference-scalarized rewards and propose Simulated NSW UCB Gossip, which integrates preference-based reward simulation, gossip-based utility estimation, and UCB-style exploration. We prove that Pareto UCB1 Gossip achieves

\mathcal{O}(\log T)

regret and an instance-independent rate of

\mathcal{O}(\sqrt{T})

, while Simulated NSW UCB Gossip achieves an instance-independent regret bound of

\mathcal{O}(T^{3/4})

. This separation reveals the cost of imposing the fairness constraint to our efficiency objective: fairness limits information aggregation and slows convergence. Experiments show that our methods consistently outperform baselines, improving performance by approximately

100\%

and

50\%

in the efficiency and fairness settings, respectively.

John Wang, Mengfan Xu

University of Massachusetts Amherst

Multi-Armed Bandits Multi-Agent System Optimization Multi-Agent Bandits Algorithmic Fairness Multi-Objective Optimization Social Welfare Maximization

May 7, 2026

Optimizing Social Utility in Sequential Experiments

Regulatory approval of products in high-stakes domains such as drug development requires statistical evidence of safety and efficacy through large-scale randomized controlled trials. However, the high financial cost of these trials may deter developers who lack absolute certainty in their product's efficacy, ultimately stifling the development of `moonshot' products that could offer high social utility. To address this inefficiency, in this paper, we introduce a statistical protocol for experimentation where the product developer (the agent) conducts a randomized controlled trial sequentially and the regulator (the principal) partially subsidizes its cost. By modeling the protocol using a belief Markov decision process, we show that the agent's optimal strategy can be found efficiently using dynamic programming. Further, we show that the social utility is a piecewise linear and convex function over the subsidy level the principal selects, and thus the socially optimal subsidy can also be found efficiently using divide-and-conquer. Simulation experiments using publicly available data on antibiotic development and approval demonstrate that our statistical protocol can be used to increase social utility by more than

35$$\%

relative to standard, non-sequential protocols.

Ander Artola Velasco, Stratis Tsirtsis, Manuel Gomez-Rodriguez

Max Planck Institute for Software Systems, Kaiserslautern, Germany · Hasso Plattner Institute, Potsdam, Germany

Mechanism Design Sequential Decision Making Sequential Hypothesis Testing Social Welfare Maximization Sequential Experimental Design

Apr 15, 2026

First-See-Then-Design: A Multi-Stakeholder View for Optimal Performance-Fairness Trade-Offs

Fairness in algorithmic decision-making is often defined in the predictive space, where predictive performance - used as a proxy for decision-maker (DM) utility - is traded off against prediction-based fairness notions, such as demographic parity or equality of opportunity. This perspective, however, ignores how predictions translate into decisions and ultimately into utilities and welfare for both DM and decision subjects (DS), as well as their allocation across social-salient groups. In this paper, we propose a multi-stakeholder framework for fair algorithmic decision-making grounded in welfare economics and distributive justice, explicitly modeling the utilities of both the DM and DS, and defining fairness via a social planner's utility that captures inequalities in DS utilities across groups under different justice-based fairness notions (e.g., Egalitarian, Rawlsian). We formulate fair decision-making as a post-hoc multi-objective optimization problem, characterizing the achievable performance-fairness trade-offs in the two-dimensional utility space of DM utility and the social planner's utility, under different decision policy classes (deterministic vs. stochastic, shared vs. group-specific). Using the proposed framework, we then identify conditions (in terms of the stakeholders' utilities) under which stochastic policies are more optimal than deterministic ones, and empirically demonstrate that simple stochastic policies can yield superior performance-fairness trade-offs by leveraging outcome uncertainty. Overall, we advocate a shift from prediction-centric fairness to a transparent, justice-based, multi-stakeholder approach that supports the collaborative design of decision-making policies.

Kavya Gupta, Nektarios Kalampalikis, Christoph Heitz +1

Department of Computer Science, Saarland University, Germany · Zurich University of Applied Sciences, Switzerland

Social Welfare Maximization Algorithmic Fairness Group Fairness

Mar 19, 2026

Linear Social Choice with Few Queries: A Moment-Based Approach

Most social choice rules assume access to full rankings, while current alignment practice -- despite aiming for diversity -- typically treats voters as anonymous and comparisons as independent, effectively extracting only about one bit per voter. Motivated by this gap, we study social choice under an extreme communication budget in the linear social choice model, where each voter's utility is the inner product between a latent voter type and the embedding of the context and candidate. The candidate and voter spaces may be very large or even infinite. Our core idea is to model the electorate as an unknown distribution over voter types and to recover its moments as informative summary statistics for candidate selection. We show that one pairwise comparison per voter already suffices to select a candidate that maximizes social welfare, but this elicitation cannot identify the second moment and therefore cannot support objectives that account for inequality. We prove that two pairwise comparisons per voter, or alternatively a single graded comparison, identify the second moment; moreover, these richer queries suffice to identify all moments, and hence the entire voter-type distribution. These results enable principled solutions to a range of social choice objectives including inequality-aware welfare criteria such as taking into account the spread of voter utilities and choosing a representative subset.

Luise Ge, Daniel Halpern, Gregory Kehne +1

Washington University in St. Louis. · Google Research.

Social Choice Theory Preference Elicitation Social Welfare Maximization Pairwise Comparison

Mar 3, 2026

Revealing Positive and Negative Role Models to Help People Make Good Decisions

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.

Avrim Blum, Keziah Naggita, Matthew R. Walter +1

Toyota Technological Institute at Chicago

Social Welfare Maximization

Feb 11, 2026

Online Generalized-Mean Welfare Maximization: Achieving Near-Optimal Regret from Samples

We study online fair allocation of

T

sequentially arriving items among

n

agents with heterogeneous preferences, with the objective of maximizing generalized-mean welfare, defined as the

p

-mean of agents' time-averaged utilities, with

p\in (-\infty, 1)

. We first consider the i.i.d. arrival model and show that the pure greedy algorithm -- which myopically chooses the welfare-maximizing integral allocation -- achieves

\widetilde{O}(1/T)

average regret. Importantly, in contrast to prior work, our algorithm does not require distributional knowledge and achieves the optimal regret rate using only the online samples. We then go beyond i.i.d. arrivals and investigate a nonstationary model with time-varying independent distributions. In the absence of additional data about the distributions, it is known that every online algorithm must suffer

Ω(1)

average regret. We show that only a single historical sample from each distribution is sufficient to recover the optimal

\widetilde{O}(1/T)

average regret rate, even in the face of arbitrary non-stationarity. Our algorithms are based on the re-solving paradigm: they assume that the remaining items will be the ones seen historically in those periods and solve the resulting welfare-maximization problem to determine the decision in every period. Finally, we also account for distribution shifts that may distort the fidelity of historical samples and show that the performance of our re-solving algorithms is robust to such shifts.

Zongjun Yang, Rachitesh Kumar, Christian Kroer

Columbia University · Carnegie Mellon University

Fair Resource Allocation Online Resource Allocation Social Welfare Maximization

May 19, 2025

Non-Obvious Manipulability in Additively Separable and Fractional Hedonic Games

Hedonic Games are a well-established model for describing the formation of coalitions. In this work, we considered the design of Non-Obviously Manipulable (NOM) mechanisms, that are mechanisms that bounded rational agents may fail to recognize as manipulable, for two relevant classes of succinctly representable Hedonic Games, namely Additively Separable and Fractional Hedonic Games. In these classes, agents have cardinal scores towards other agents, and their preferences towards different coalitions are determined by aggregating these scores. Moreover, the quality of an outcome can also be easily evaluated through these scores by means of the utilitarian social welfare. We first prove that, when scores can be arbitrary, every welfare-maximizing mechanism is NOM, and, when scores are limited in a continuous interval, then there exist tie-breaking rules making welfare-maximizing mechanisms NOM. Next, we focus on efficient NOM mechanisms, since there is no known polynomial-time algorithm to compute welfare-maximizing outcomes in the considered classes of hedonic games. To this aim, we first prove a characterization of NOM mechanisms that simplifies the class of mechanisms of interest. Then, we design a NOM mechanism returning approximations that essentially match the best-known approximation achievable in polynomial time. Finally, we turn our attention to discrete scores, and specifically, the case that scores are

\{-x, 0, 1\}

for

x > 0

. We prove that the ability to design welfare-maximizing NOM mechanisms depends on the magnitude of the scores. In particular, for

x > 1

, we prove that a welfare-maximizing NOM mechanism exists only when

x

is very large. For

x \leq 1

, instead, we observe that a welfare-maximizing NOM mechanism always exists except when

x

lies in the interval

[a, b]

where

a \approx 2/n^2

and

b \approx 1/n

.

Diodato Ferraioli, Maria Fomenko, Giovanna Varricchio

University of Salerno, Italy · University of Calabria, Italy

Cooperative Game Theory Mechanism Design Game Theory Social Welfare Maximization

Aug 19, 2024

No Screening is More Efficient with Multiple Objects

We study the welfare-maximizing allocation of heterogeneous objects when screening uses costly effort rather than monetary transfers. No-screening mechanisms perform well as object variety increases. In a symmetric continuous market with i.i.d. values whose CDF is log-concave, the multidimensional problem reduces exactly to a single-dimensional problem in agents' best-option values. More options make low best-option values rarer, weakening the case for screening. We characterize when no screening is optimal and show it remains optimal as variety expands. Large-variety limits and numerical results for finite, correlated markets support this pattern. We apply these results to propose an invitation-based vaccine appointment system.

Shunya Noda, Genta Okada

Graduate School of Economics, the University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo, 113-0033, Japan

Mechanism Design Social Welfare Maximization