Fair Resource Allocation

Follow this topic Ask about this topic

Momentum

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

Jul 13Week of Sep 28

Latest papers 31

Oct 7, 2026cs.GT

Minimizing Cumulative Envy in Allocating a Sequence of Items

We study temporal fair division with indivisible goods that arrive sequentially and must be allocated irrevocably. In contrast to the usual online model, we assume that valuations and future arrivals are known in advance, and ask how unfairness evolves during the process. We introduce \emph{cumulative maximum envy}: the sum, over all rounds, of the maximum pairwise envy at that round. Equivalently, this is the area under the worst-envy curve, and it captures both the magnitude and the duration of envy. For a fixed arrival order, we show that the corresponding decision problem is strongly NP-complete and that minimizing this objective admits no constant-factor approximation unless P = NP, even under identical valuations and even under binary valuations. We complement these hardness results with a dynamic program that gives pseudopolynomial-time solvability for a constant number of agents, polynomial-time algorithms in further restricted settings, and an FPTAS for fixed

n

under identical integer valuations. We then study a sequencing variant where the algorithm may choose the arrival order. This variant remains NP-complete even for two agents with identical valuations; however, a simple greedy algorithm achieves a

3/2

-approximation for

n=2

agents, an

n/(n-1)

-approximation for any number of agents, and an additive guarantee depending on the maximum value of any good.

Paul W. Goldberg, Isaac Robinson, Nicholas Teh

University of Oxford, UK

Fair Resource Allocation Approximation Algorithms

Oct 4, 2026cs.GT

Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations

We study the problem of computing an allocation of indivisible items that maximizes egalitarian welfare, i.e., the utility of the worst-off agent, when agents' item values or marginal values belong to a small set. For additive valuations with values in

\{p,q\}

, where

q>p>0

and

\gcd(p,q)=1

, we give a polynomial-time algorithm when

p=2

and prove constant-gap hardness when

p\geq3

, already with exactly three high-valued goods per agent. We also give an

\sqrt{3/2}

-approximation for common positive bi-valued additive valuations. For mixed additive valuations in

\{-p,0,c\}

, where

p\in\{1,2\}

and

c

is a positive integer, a reduction to maximum-weight perfect matching resolves the conjectured tractability of

\{-2,0,c\}

-valuations. For submodular valuations with marginals in

\{-2,0,c\}

, where

c

is odd, we establish an exact unit-gap hardness result and exponential value-query lower bounds, even when all but one agent are additive. Finally, for

\{-1,0,1\}

-submodular valuations, we prove that no finite multiplicative approximation exists unless

\p=\np

. Together, our results resolve open questions and provide a complete picture of the computational complexity of max-min allocation with ternary valuations.

Thi Ngoc Anh Vu, Trung Thanh Nguyen, Khaled Elbassioni +1

Faculty of Computer Science, Phenikaa University, Hanoi 12116, Vietnam · DataOptLab, National Economics University, Hanoi 11616, Vietnam · Khalifa University of Science and Technology, Abu Dhabi 127788, UAE +1

Submodular Optimization Social Choice Theory Fair Resource Allocation Approximation Algorithms

Sep 24, 2026econ.EM

Multi-Dimensional Matching

We study a matching mechanism where agents and objects are described by features rather than complete rankings. A single spectral projection reduces the problem to a one-dimensional sort, computable in O(N log N) time. We prove that on descaled features and preferences, our algorithm obtains the exact Nash Social Welfare (NSW) optimum within the projected space, with an unconditional utilitarian-welfare guarantee and a conditional NSW guarantee. The proposed mechanism is stable against exogenous noise but not strategy-proof; we provide an explicit profitable misreport. On an agentic AI shopping application, the diagnostics correctly anticipate both a success and a failure case. A 100-instance robustness study confirms the findings.

Irene Aldridge

Mechanism Design Fair Resource Allocation

Sep 16, 2026cs.CY

The AR Fairness Metamodel: A Structured Framework for Fairness Measures

This paper presents the AR fairness metamodel, a framework designed to represent, analyze, and compare different fairness scenarios. The metamodel considers key elements, such as agents, resources, and their attributes, and enables the systematic definition and comparison of various fairness measures. We provide examples involving both discrete and continuous measures, including equality, equity, group fairness, individual fairness, the Gini index, the Theil index, Jain's fairness index, and a detailed fairness measure for Australia's Child Care Subsidy. We also explore relationships among group fairness, individual fairness, and envy-freeness, supported by formal proofs. At the conceptual modeling level, our approach builds on the Tiles framework, which offers modular components that can be connected to capture diverse fairness definitions. The goal is to make AR-based fairness definitions practical and adaptable across contexts, providing a clear way to define, compare, and evaluate them. An implementation of the Tiles framework is available as an open-source tool, and can support fairness modeling and evaluation across a wide range of applications.

Julian Alfredo Mendez, Timotheus Kampik

Umeå University, Umeå, Sweden

Fair Resource Allocation Algorithmic Fairness Group Fairness

Sep 14, 2026cs.NI

Proportional-Fair Resource Allocation and Dual-Threshold Early-Exit Inference for Secure Cooperative Multi-Layer Edge Intelligence

This paper proposes FREDI (Fair Resource Allocation for Edge Dual-Threshold Inference), a secure wireless edge-intelligence framework for event-triggered inference in a cooperative user equipment (UE)--edge server (ES)--cloud system. Each UE performs early-exit convolutional neural network (CNN) screening using dual confidence thresholds, while critical events are securely offloaded to an edge server for detailed classification. We formulate a proportionally-fair utility maximization problem that jointly optimizes UE--ES association, wireless and processing resources, and confidence thresholds. FREDI decomposes the problem into proportional-fair resource allocation and dual-threshold inference optimization. We prove that the detected-critical event set is set-monotone non-increasing in both thresholds, and exploit the finite empirical confidence domain for exact threshold optimization. An empirical resource--utility response envelope yields a computable global suboptimality bound and a sufficient condition for global optimality. By pre-eliminating infeasible UE--ES pairs and exactly projecting out bandwidth and transmit-power variables, the resource-allocation subproblem is reduced to a mixed-integer exponential-cone program solvable to the certified global optimality within a prescribed gap. Numerical results with early-exit MobileNetV2 and ShuffleNetV2 demonstrate near-perfect UE fairness with aggregate utility close to a Sum-Utility benchmark, reveal security-induced resource fragmentation, and demonstrate the Stage-A scalability from 6 to 144 UEs with median solving time below 0.1~s in the tested configurations.

Thai T. Vu, John Le, Tu N. Nguyen +3

School of Computing and Information Technology, University of Wollongong, Wollongong, NSW, Australia · Department of Computer Science, Kennesaw State University, Georgia, USA · CodeZX Software Company Limited, Vietnam

Edge Inference Fair Resource Allocation Wireless Resource Allocation Early-Exit Neural Networks

Sep 3, 2026cs.GT

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 \emph{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

Aug 26, 2026cs.GT

Simultaneous Envy and Equitability Guarantees

Recent work in fair division has focused on either simultaneously satisfying closely related fairness notions or achieving a single notion across the ex-ante and ex-post worlds. We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability. For indivisible goods-only and chores-only settings, we study the existence and complexity of simultaneously satisfying their relaxations, revealing sharp contrasts between the two settings. For normalized binary goods, we give a polynomial-time algorithm for computing an EF1+EQ1 allocation with at most seven agents, but also construct a normalized instance with a larger number of agents for which no such allocation exists. In sharp contrast, binary chores admit the stronger EFX+EQX guarantee for any number of agents, even without normalization. We further initiate the study of cross-notion ex-ante and ex-post guarantees, asking whether randomized allocations can provide ex-ante guarantees for one notion while preserving ex-post guarantees for another.

Hadi Hosseini, Shraddha Pathak, Lirong Xia +1

Penn State University · Rutgers University

Social Choice Theory Fair Resource Allocation

Aug 4, 2026cs.GT

EFX Allocation In (Multi)Hypergraphs

We study fair allocations of indivisible goods among agents with heterogeneous monotone valuations. As fair we consider the allocations that are envy-free-up-to-any-good (EFX). Finding if EFX alloca- tions always exist, even for agents with additive valuations, is a major open problem in Fair Division. Christodoulou et al. (2023) introduced the (multi-hyper)graph setting, where agents and goods are represented by vertices and edges of a graph, respectively, and only the endpoints of an edge may have non-zero marginal value for it. We show that for hypergraphs with girth at least 4 and agents with general monotone valuations there always exists an EFX allocation and can be constructed in polynomial time. We generalize our approach to also show that multi-hypergraphs with girth (on the simple hypergraph) at least 4 always admit an EFX allocation, as long as there exists a single vertex whose incident edges have multiplicity at most the size of that edge minus 2; our construction in this case needs pseudo-polynomial time.

Thanasis Lianeas, Alkmini Sgouritsa, Minas Marios Sotiriou

University of West Attica · Greece · Athens University of Economics and Business +1

Fair Resource Allocation

Aug 3, 2026cs.LG

Heterogeneous Multi-Agent Reinforcement Learning for Radio Resource Management under Coupled Finite-Horizon Constraints

Maximizing throughput under proportional fairness in dense wireless networks requires jointly managing user association, scheduling, base station (BS) activation, and handover control under hard finite-horizon energy and handover budgets, which induces a fundamental tension between BS-side energy management and user-side handover regulation. While multi-agent reinforcement learning (MARL) is a natural framework for such distributed sequential control, its application here faces two difficulties: finite-horizon budget constraints cannot be evaluated at each time slot, and the nonlinear proportional fairness utility admits no principled per-slot decomposition. We propose HeLyMARL, a Lyapunov-embedded heterogeneous MARL framework that resolves both via drift-plus-penalty decomposition with virtual queues. The energy and handover constraint pressures are internalized directly into a unified per-slot reward, converting the constrained finite-horizon problem into an unconstrained MARL problem. Comparison against two Lagrangian-based alternatives reveals a timescale separation: Lagrangian relaxation regulates constraints only across training episodes, whereas the virtual queues of HeLyMARL bound cumulative budget consumption at every partial horizon within an episode, a pacing guarantee beyond the reach of greedy Lyapunov-based control. Simulations show that HeLyMARL is the only method that sustains the throughput-fairness balance together with uninterrupted service throughout the horizon, outperforming conventional MARL, Lyapunov-based, and constrained MARL benchmarks without premature budget exhaustion.

Yeonseo Jeong, Wonhyeok Ko, Sungweon Hong +1

Department of Electronic Engineering, Hanyang University, Seoul, Korea · Department of AI-Semiconductor, Hanyang University, Seoul, Korea

Stochastic Optimization Fair Resource Allocation Constrained RL Wireless Resource Allocation Multi-Agent Reinforcement Learning Heterogeneous MARL

Jul 31, 2026cs.LG

End-to-End Fairness Optimization with Fair Decision-Focused Learning

Many real-world systems rely on predictive models to inform decisions, and fairness concerns arise in both the prediction and decision stages. We introduce end-to-end fairness optimization (E2EFO) as a unifying framework that integrates fairness across the prediction-to-decision pipeline. We focus on resource allocation with group-based fairness: the prediction task estimates allocation impacts while limiting accuracy disparity across groups, and the decision task distributes those impacts equitably by optimizing a group-based alpha-fairness measure. Within this framework, we propose fair decision-focused learning (FDFL), a training paradigm that jointly accounts for prediction accuracy, prediction fairness, and decision regret -- the loss in decision fairness due to imperfect predictions. FDFL trains the predictor by gradient descent, combining the objective gradients through multi-task learning techniques. The core computational challenge is the decision Jacobian with respect to the predictor parameters: we derive exact closed-form formulas for a tractable class of fair allocation and apply a differentiable optimization layer in the general case. We further establish a finite-sample generalization bound for the scalarized FDFL objective. Numerical experiments on a healthcare-based single resource allocation and a synthetic multiple resource allocation illustrate the value of jointly accounting for prediction fairness and decision fairness in prediction-informed decision-making.

Yu Wang, Violet Xinying Chen

School of Business Stevens Institute of Technology

Fair Resource Allocation Algorithmic Fairness Decision-Focused Learning Group Fairness

Jul 31, 2026cs.CL

FairFund-Bench: Evaluating Distributive Bias in LLM Resource Allocation

Large language models (LLMs) are increasingly involved in the distribution of scarce resources, raising concerns about biased allocations based on characteristics like race and gender. Recent LLM audits have produced inconsistent results, however, finding evidence of both positive and negative discrimination towards women and ethnic minorities, even for the same models. We show that this disagreement can arise from differences in audit format and introduce FairFund-Bench, a benchmark that systematically varies key features of previous audit designs: the evaluation task (rating, ranking, or allocation), comparison context (single or multi-stimulus), and whether the audit is transparent or disguised. The benchmark comprises 600 requests for financial assistance created from human-authored templates (calibrated against 1.3M real GoFundMe campaigns) across three domains, four race and two gender categories, and five causal framings of need derived from welfare deservingness theory. Across 14 models, audit format changes the direction of bias: models advantage minorities when rating claimants individually but penalize some groups when ranking them side by side. Bias magnitude, though small overall, is several times greater in disguised audits than in transparent ones, where, faced with appeals differing only in claimants' names, models overwhelmingly split funds equally. Causal framing effects, by contrast, exceed demographic effects by roughly an order of magnitude and are consistent across models and audit formats, indicating that current LLMs robustly reproduce human deservingness evaluations. The benchmark scores models on four criteria (demographic bias, deservingness alignment, cross-task consistency, and cross-context consistency), is publicly available, and can be readily adapted to other substantive domains.

Martin Lukk

University of Toronto

Benchmark Auditing LLM Auditing Fair Resource Allocation Language Model Bias Evaluation Demographic Bias in Language Models

Jul 29, 2026cs.SI

Parameterized Fair Resource Allocation under Diversity Constraints

Resource allocation across multiple agent groups arises in many applications including e-commerce recommendation systems, housing assignment, and course allocation, and is commonly formulated as an optimization problem with diversity constraints to ensure group fairness. Existing approaches typically enforce these constraints as hard conditions, which overly restrict the feasible solution space and often lead to suboptimal allocations. In this paper, we propose PRA, a parameterized framework for fair resource allocation under diversity constraints. Inspired by the use of risk-aversion parameters in economic models, PRA introduces a set of controllable inequality-aversion parameters to softly regulate group-level diversity, thereby enabling flexible trade-offs between fairness and allocation efficiency. With appropriately calibrated parameters, PRA yields fairness-optimal assignments that comply with the specified diversity constraints. To accommodate additional application-specific constraints, we further extend the framework to an adaptive variant, APRA. We establish that the optimality of both PRA and APRA holds regardless of the chosen fairness metric and the nature of the additional constraints, underscoring the generality and robustness of our approach. Extensive experiments on three real-world applications demonstrate that our proposed framework consistently outperforms existing baselines in both effectiveness and robustness.

Keke Huang, Yik Yu Ng, Laks V. S. Lakshmanan +1

Huazhong University of Science and Technology Wuhan, Hubei, China · The University of British Columbia Vancouver, BC, Canada · McGill University Montreal, Quebec, Canada +1

Fair Resource Allocation Group Fairness Constrained Optimization

Jul 26, 2026eess.SY

Outcome-Fair Restless Multi-Armed Bandits for Stochastic Deadline Scheduling

We study a restless multi-armed bandit (RMAB) problem for a stochastic deadline scheduling application. RMAB problems are solved using the Whittle index policy. The goal in RMAB is to maximize the expected cumulative discounted reward maximization. The Whittle index policy maximizes reward, but is not fair among two classes. In this paper, we introduce fairness criteria and study an outcome-fair model for RMAB which allows fairness for jobs and users structurally disadvantaged demographic classes. We formulate an outcome fair stochastic deadline scheduling problem as RMAB, and we develop the outcome fair Whittle index policy. We define a virtual queue mechanism that dynamically enforces long-term completion rate guaranties across demographic groups. We analyze a standard Whittle index policy and the outcome-fair index policy. We demonstrate the performance of our algorithms with numerical examples. We compare policies---Whittle index policy (no fairness), input-fairness Whittle index policy, outcome fair Whittle index policy. We observe that the outcome-fair Whittle index policy provides better fairness among classes compared to other policies. We demonstrate a trade off between fairness and profit. This decreases as the server capacity increases.

Shakti Sharma, Rahul Meshram

Dept. of Physics, IIT Madras, Chennai, India. · Dept. of Electrical Engineering, IIT Madras, Chennai, India.

Sequential Decision Making Fair Resource Allocation Algorithmic Fairness Group Fairness

Jul 25, 2026cs.GT

Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO

We study whether strictly positive marginal values restore the compatibility of envy-freeness up to one good (EF1) and Pareto optimality (PO) for indivisible goods. For two agents, we identify the exact threshold in the number of goods. Every instance with at most seven goods and strictly increasing valuations admits an allocation that is both EF1 and PO, without any submodularity assumption. In contrast, we construct an eight-good instance with normalized, integer-valued, strictly increasing, submodular valuations in which every EF1 allocation is strictly Pareto dominated. Thus, eight goods are necessary and sufficient for a two-agent counterexample. Finally, we strengthen the three-agent NP-hardness result of Chandramouleeswaran and Nimbhorkar (2026): deciding whether an EF1 and PO allocation exists remains NP-hard for normalized, integer-valued, monotone submodular valuations even when zero marginals are confined to eight fixed agent-good pairs, all involving a single agent.

Nicholas Teh

University of Oxford, UK

Social Choice Theory Fair Resource Allocation Pareto Optimization

Jul 25, 2026cs.GT

Online Fair Division with Budget Constraints

We study an online variant of discrete fair division under generalized assignment budget constraints. Goods arrive one at a time and must be assigned irrevocably to a feasible agent or to charity, which holds all unallocated goods, while fairness is evaluated only against budget-feasible subsets of every recipient's bundle. We first show that, without additional structure, no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness, even in highly symmetric instances. We then identify bounded density spread as a structural condition that restores meaningful guarantees, obtaining approximation algorithms for arbitrary item sizes and showing that, under common valuations and sufficiently small goods, these guarantees can be strengthened to an optimal deterministic frontier. We further study resource augmentation, where the online algorithm is allowed slightly larger budgets than the fairness benchmark, and characterize the resulting improvement in the achievable guarantees. Finally, we develop a learning-augmented framework based on predicting joint value-size types, proving consistency under perfect predictions, robustness to prediction error, and showing that separate predictions of value and size marginals are insufficient to recover strong fairness guarantees.

Saar Cohen, Nicholas Teh, Paul W. Goldberg +1

Department of Computer Science, University of Oxford, UK

Fair Resource Allocation Learning-Augmented Algorithms Approximation Algorithms Online Resource Allocation

Jul 24, 2026cs.LG

Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors

Minimum-exposure constraints arise in recommendation, content curation, and regulated allocation when each provider, arm, or group must receive guaranteed exposure inside a period rather than only in aggregate. We study stochastic bandits with exact exposure floors and show that the right object is a rounding problem: a fractional fair schedule is realized as integral pulls, and the exposure error is exactly a discrepancy vector. The main contribution is a blockwise model with time-varying floors. BDQ-UCB satisfies every block floor deterministically and has fair regret governed by the nonmandatory budget

R

, not the horizon

T

, with high-probability regret

O(\sqrt{KR\log(KT)})

. A MOSS residual variant attains

O(\sqrt{KR})

, and a matching lower bound gives the minimax rate

Θ(\sqrt{KR})

, even with positive mandatory exposure; a kl-UCB

^{++}

residual rule adds instance-dependent optimality. The formulation becomes essential for overlapping group floors: per-arm rounding can violate a group constraint by

Ω(s)

in the group size, whereas Beck--Fiala null-space rounding meets every group floor within the block budget with violation below the arm degree

t

, and composes with UCB at the same

R

-parametrized regret. For learned group plans, we close disjoint systems at

\widetildeΘ(\sqrt{KT})

, give a dual-ledger decomposition explaining why naive index rules fail under overlap, and prove a plan-sampling rule that is pathwise feasible under an initial cover-slack condition and attains a conditional

\widetilde O(\sqrt{KT})

guarantee, leaving the condition-free overlap rate open. Experiments on synthetic floors, MovieLens-100k genre exposure, and deployment stress tests show exact feasibility without penalty tuning and regret competitive with tuned Lagrangian baselines.

Ibne Farabi Shihab, Joyanta Jyoti Mondal, Anuj Sharma

Department of Computer Science, Iowa State University, USA · Department of Computer and Information Sciences, University of Delaware, USA · Department of Civil, Construction & Environmental Engineering, Iowa State University, USA

Multi-Armed Bandits Fair Resource Allocation Group Fairness

Jul 19, 2026cs.MA

The Optimization Trilemma: Efficiency, Comfort and Fairness in Decentralized Multi-agent Coordination

The problem of fair multi-agent coordination in decentralized settings is one of the most pressing challenges for building efficient collaborative systems. Resource allocation is based on optimized collective arrangements accounting for agents' needs. Such coordination should not only be computationally efficient but also account for fairness, i.e., equitable redistribution of costs incurred by all agents. Recent literature has proposed several algorithms that efficiently determine optimal plan combinations balancing system-wide efficiency and individual discomfort of agents in a centralized setting. However, these works do not address equitable resource optimization in fully decentralized scenarios, specifically, the optimized redistribution of discomfort among coordinating agents so that none experiences a discomfort level that could lead to loss of incentive or polarization that can disrupt planned operations. In this work, we study the problem of optimizing three objectives: (i) system-wide efficiency, (ii) individuals' comfort and (iii) fairness (i.e., balancing of incurred discomfort costs) in decentralized multi-agent coordination. We design a novel model to optimize those three orthogonal objectives, without any substantial increase in communication and computational overhead. Through experiments on two real-world datasets, we validate the model and demonstrate that it can achieve fairer optimization outcomes, while satisfying agents' preferences and system goals.

Jovan Nikolic, Maciej Krzysztof Zuziak, Evangelos Pournaras

Google, Zurich, 8002 Zurich, Switzerland. · School of Computer Science, University of Leeds, Leeds, UK. · School of Energy Systems, LUT University, 53850 Lappeenranta, Finland

Multi-Agent Coordination Fair Resource Allocation Group Fairness Multi-Objective Optimization Decentralized Optimization

Jul 15, 2026stat.ML

Price of Fairness in Bandits: A Tight Minimax Characterization

In bandit problems, standard regret-minimizing algorithms treat exploration as an amortized cost, which can expose early participants to unfair ex-ante losses in settings such as clinical trials. Recent work addresses this by evaluating the sequence of per-round expected rewards through the generalized

p

-mean, interpolating between utilitarian welfare (

p=1

), Nash welfare (

p\to0

), and Rawlsian fairness (

p\to-\infty

). Although tight guarantees are known for

p\ge0

, the strictly fair regime

q=-p>0

remains unresolved because negative-power means are dominated by the smallest per-round rewards. For

σ

-sub-Gaussian rewards with nonnegative means, the best prior algorithm relied on uniform early exploration and achieved regret

O(k^{(q+1)/2}/\sqrt{T})

, while the only general lower bound was the classical

Ω(σ\sqrt{k/T})

. Thus it was unclear whether the extra dependence on

k

was intrinsic to strict fairness or an artifact of uniform exploration. We close this gap by identifying the exact polynomial price of strict fairness. Using a needle-in-haystack construction, we prove an algorithm-independent lower bound

Ω(σ\sqrt{k^{\max(1,q)}/T})

; for

q>1

, this shows that the penalty

k^{q/2}

is information-theoretically unavoidable. We then introduce \textsf{UCB-HARE} (Harmonic Anchored Rank Exploration), which replaces uniform exploration with an inverse-weighted harmonic rank schedule protected by a certified positive-mean anchor. Its regret is

\widetilde{O}(σ\sqrt{k^{\max(1,q)}/T})

, matching the lower bound up to logarithmic factors. Experiments on synthetic instances confirm that \textsf{UCB-HARE} improves over uniform-exploration baselines, with gains increasing as

q

grows.

Dhruv Sarkar, Soumyadeep Dutta, Sayak Ray Chowdhury

1Indian Institute of Technology Kharagpur · 2Mohamed bin Zayed University of Artificial Intelligence · 3Indian Institute of Technology Kanpur

Multi-Armed Bandits Minimax Regret Fair Resource Allocation Algorithmic Fairness UCB Algorithms Information-Theoretic Lower Bounds

Jul 11, 2026eess.SY

Comparing Socially-Equitable Renewable Energy Budget Allocation MDP Policies in Mature and Emerging Economies

Equitable renewable-energy planning is a sequential decision problem, but the decision variables available to a public planner differ sharply between mature and emerging economies. In the former the government largely builds generation, while in the latter it steers private investment through incentives and quotas. We formulate socially-equitable renewable-energy budget allocation as a Markov Decision Process (MDP) and, using a single problem-agnostic solver interface, compare the same policies across the two settings: eight U.S. cities (a mature economy) and West Java, Indonesia (an emerging economy). The results show that across both settings, a receding-horizon value-iteration policy dominates. In the U.S., it reaches 66% renewable penetration while cutting the underserved low-income population by 96% versus a random baseline. In West Java it closes the low-access gap while crowding in the most private capital. More interestingly, a naive market-chasing heuristic, which is mildly sub-optimal in the U.S., could yield catastrophic outcomes in Indonesia, by underserving every low-access region, because chasing attractive markets and serving the underserved goals diverge once the planner acts through private developers.

Riya Kinnarkar, Mansur M. Arief, Yan Pratama Akhra +1

Management & Technology University of Pennsylvania Philadelphia, PA, USA

Fair Resource Allocation Policy Evaluation Power Systems

Jul 9, 2026cs.LG

Quota Marketplace: Dynamic Pricing for Efficient Allocation of ML Training Resources

The escalating demand for Machine Learning (ML) training resources in recent years has resulted in a substantial gap between the high demand and the available supply. Efficient allocation of these scarce and expensive resources is crucial for organizations to maximize their return on investment. Existing resource allocation mechanisms, like Karma [OSDI'23], are designed to guarantee Pareto efficiency and max-min fairness in settings with dynamic (time-varying) user demands, but fail to preserve these key properties in the presence of demands with heterogeneous values. Given the ubiquity and inevitability of heterogeneity in organizational values of different workloads, effective resource allocation policies must accommodate these variations. In this paper, we describe the design, implementation, deployment, and theoretical analysis of Quota Marketplace, a market-based mechanism to efficiently allocate ML training chips (like GPUs), explicitly addressing scenarios with demands of heterogeneous value. We detail the implementation of this mechanism within Google and present metrics that demonstrate its impact. We also discuss many business-critical requirements that the Quota Marketplace handles quite effectively, and document the gains and opportunities it has unlocked. We establish theoretically how this market-based approach achieves the essential properties of Pareto efficiency and max-min fairness by allowing the users to express the value of their workloads and enabling dynamic resource pricing based on supply and demand fluctuations. Ultimately, the market facilitates resource allocation that aligns with organizational priorities.

Balasubramanian Sivan, Renato Paes Leme, Mihai Tiuca +6

Google · Drexel University

Fair Resource Allocation Dynamic Pricing Online Resource Allocation

Jun 17, 2026cs.DS

Fair Online Resource Allocation

We study the problem of fair online resource allocation, motivated by applications such as refugee resettlement and airline scheduling, where agents arrive sequentially and must be assigned to facilities with limited capacities. We introduce a model that maximizes the overall welfare subject to resource constraints and a Lipschitz fairness requirement, which ensures that similar agents arriving in the same batch receive similar expected outcomes. We first analyze the offline problem, proving that the value of the optimal fair allocation is at least an

Ω(1/γ)

fraction of the optimal unfair allocation, where

γ

is the fairness coefficient, thereby bounding the price of fairness. For the online setting, we propose an algorithm based on dual mirror descent that enforces fairness constraints within batches while estimating optimal dual variables. We prove that this algorithm achieves sublinear regret relative to the optimal offline fluid benchmark. Finally, we validate our theoretical results using real-world data from the Refugee Economies Programme, demonstrating the algorithm's performance and examining the trade-offs between welfare maximization and fairness enforcement.

Christopher En, Yuri Faenza, Andrea Lodi +1

Columbia University, IEOR Department · Cornell Tech · Universidad de Chile

Sequential Decision Making Fair Resource Allocation Algorithmic Fairness Group Fairness Online Resource Allocation

Jun 9, 2026cs.GT

Trading Utility for Dynamic Fairness in Multiple Resource Division with Sequential Demand

Dynamic multi-resource allocation is a central problem in shared computing environments, where users' demands arrive sequentially and resources must be distributed fairly without knowledge of future demands. Existing methods emphasize fairness guarantees such as Sharing Incentive, Envy Freeness, and Dynamic Pareto Optimality, but often overlook system utility. Moreover, these fairness criteria are mutually incompatible, preventing strict enforcement of them at the same time. We propose a neural allocation mechanism that reconciles fairness with utility through multi-objective optimization during sequential rollout. We first formalize fairness in the dynamic setting via stepwise loss functions for Sharing Incentive, Envy Freeness, and Dynamic Pareto Optimality, enabling differentiable training. Leveraging non-wastefulness, we parameterized the solutions by constraining allocations to the subspace of demand while allowing elastic over-allocation when resources remain available. Empirical results demonstrate that our learned allocator achieves substantially higher utility at comparable levels of fairness, uncovering clear Pareto-frontier-like tradeoffs across metrics.

Kaiqi Jiang, Karim El Husseini, Wenzhe Fan +1

Computer Science Dept., University of Illinois Chicago, Chicago, Illinois, USA

Sequential Decision Making Fair Resource Allocation Algorithmic Fairness Online Resource Allocation

May 14, 2026cs.MA

Temporal Fair Division in Multi-Agent Systems: From Precise Alternation Metrics to Scalable Coordination Proxies

A plethora real-world environments require agents to compete repeatedly for the same limited resource, calling for a temporal notion of fairness judged across entire interaction histories. This paper advances the theory of temporal fair division by introducing Rotational Periodicity (RP), a family of lightweight metrics, alongside the ALT family of sliding-window measures, within a unified framework for repeated multi-agent resource competition. We formalise the Multi-Agent Battle of the Exes (MBoE) as a repeated fair division instance and establish Perfect Alternation (PA) as its canonical temporally fair solution, drawing connections to proportionality, envy-freeness, and n-periodic round-robin allocation. RP decomposes temporal fairness into two complementary sub-measures: Rotational Score (RS) and Waiting Periods Evaluation (WPE), achieving O(nu+n) time complexity versus the O(nu*n) of ALT, where nu is the episode count and n the agent count. Empirical evaluation across n in {2,3,5,8,10} reveals three findings. First, both RP and ALT expose a coordination failure invisible to traditional metrics: Q-learning agents perform worse than random policies by 10-73% on RP and 7-35% on CALT, while Reward Fairness remains misleadingly high (above 0.92 for n>=3). Second, RP achieves 12-25x computational speedup over ALT, growing with n. Third, the two families are complementary: ALT provides richer discrimination for small populations; RP scales reliably where ALT becomes intractable. Together they form a diagnostic toolkit for temporal fair division.

Nikolaos Al. Papadopoulos

University of Macedonia, Department of Applied Informatics, Thessaloniki, Greece

Multi-Agent Coordination Fair Resource Allocation Algorithmic Fairness Multi-Agent Systems

May 12, 2026cs.DS

Time and Supply Fairness in Electricity Distribution using $k$ -times bin packing

Given items of different sizes and a fixed bin capacity, the bin-packing problem is to pack these items into the minimum number of bins such that the sum of the item sizes in each bin does not exceed the capacity. We define a new variant, k-times bin-packing (kBP), in which the goal is to pack the items so that each item appears exactly k times in k different bins. We generalize existing approximation algorithms for bin-packing to solve kBP and analyze their performance ratios. The fair electricity division problem motivates the study of kBP. The goal is to allocate the available supply among households using some fairness criteria, such as the egalitarian principle. We prove that every electricity division problem can be solved by k-times bin-packing for some finite k, which depends only on the number of households. We implement generalizations of the First-Fit and First-Fit Decreasing bin-packing algorithms to solve kBP and apply them to real electricity demand data. We show that our generalizations outperform existing heuristic solutions to the same problem in terms of the egalitarian allocation of connection time. We study another variant of the egalitarian allocation problem, in which the goal is to maximize the minimum number of watts allocated to a household. For this variant, we prove an impossibility result: there does not exist such a k that depends only on the number of agents. This impossibility result motivates us to develop four different heuristic algorithms to solve the egalitarian allocation of watts problem. We evaluate the heuristics by summing the minimum watts allocated to any household in each hour, yielding a fairness metric that reflects the lowest watt allocation across all hours. A higher total minimum of watts indicates a more equitable distribution. Thus, we establish new benchmarks for fair allocation of watts.

Dinesh Kumar Baghel, Alex Ravsky, Erel Segal-Halevi

Ariel University, Ariel 40700, Israel · UPES, Dehradun, Uttarakhand, India · Pidstryhach Institute for Applied Problems of Mechanics and Mathematics of National Academy of Sciences of Ukraine, Lviv, Ukraine

Fair Resource Allocation Combinatorial Optimization Group Fairness Approximation Algorithms

Apr 30, 2026cs.AI

Fairness for distribution network operations and planning

The incorporation of fairness into the distribution network (DN) planning and operation has become a key goal of recent studies. The cost of implementing fairness, denominated the price of fairness (PoF), covers the efficiency that is renounced for attaining social cohesion through fair outcomes. Locational disparity makes fairness schemes emerge to level the consumers playing field. However, fairness encompasses a range of notions. From egalitarian to merit-based criteria, various metrics are implemented as a tool for measuring equitable utility distribution. These have different mathematical complexities, from linear to non-linear programming cases, which affect their overall applicability. Hence, this study compiles the overarching fairness notions and metrics, reviewing how these affect stakeholders and the inherent mathematical optimisation in resource allocation problems. The aim is to support consistent and transparent planning and decision-making within DN operations.

Pedro F. C. de Carvalho, Zijie Liu, Md Umar Hashmi +1

KU Leuven, division Electa in Leuven · & EnergyVille in Genk, Belgium

Fair Resource Allocation Algorithmic Fairness Group Fairness Power Systems

Apr 18, 2026cs.GT

From Necklaces to Coalitions: Fair and Self-Interested Distribution of Coalition Value Calculations

A key challenge in distributed coalition formation within characteristic function games is determining how to allocate the calculation of coalition values across a set of agents. The number of possible coalitions grows exponentially with the number of agents, and existing distributed approaches may produce uneven or redundant allocations, or assign coalitions to agents that are not themselves members. In this article, we present the \emph{Necklace-based Distributed Coalition Algorithm} (N-DCA), a communication-free algorithm in which each agent independently determines its own coalition value calculation allocation using only its identifier and the total number of agents. The approach builds on the notion of Increment Arrays (IAs), for which we develop a complete mathematical framework: equivalence classes under circular shifts, periodic IAs, and a rotated designation scheme with formal load-balance guarantees (tight bounds). We establish a bijection between canonical representative IAs and two-colour combinatorial necklaces, enabling the use of efficient necklace generation algorithms to enumerate allocations in constant amortised time. N-DCA is, to the best of our knowledge, the only distributed coalition value calculation algorithm for unrestricted characteristic function games to provably satisfy five desirable properties: no inter-agent communication, equitable allocation, no redundancy, balanced load, and self-interest. An empirical evaluation against DCVC (Rahwan and Jennings 2007) demonstrates that, although DCVC is faster by a constant factor, this difference becomes negligible under realistic characteristic-function evaluation costs, while N-DCA offers advantages in working memory, scalability, and the self-interest guarantee.

Terry R. Payne, Luke Riley

School of Computer Science and Informatics, University of Liverpool, Liverpool, UK. · Quant, London, UK.

Cooperative Game Theory Multi-Agent Coordination Game Theory Fair Resource Allocation Combinatorial Optimization

Feb 11, 2026cs.GT

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

Oct 4, 2025cs.SI

Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity

Balancing resource efficiency and fairness is critical in networked systems that support modern learning applications. We introduce the \emph{Fair Minimum Labeling} (FML) problem: the task of designing a minimum-cost temporal edge activation plan that ensures each group of nodes in a network has sufficient access to a designated target set, according to specified coverage requirements. FML captures key trade-offs in systems where edge activations incur resource costs and equitable access is essential, such as distributed data collection, update dissemination in edge-cloud systems, and fair service restoration in critical infrastructure. We first give a structural characterisation of the single-terminal case, showing that it is equivalent to the rooted Covering Steiner problem. We prove that FML is NP-hard and admits no

((1-ε)\ln |\mathcal{C}|)

-approximation for

|\mathcal{C}|

groups, already on a star, while for any fixed number of groups it inherits a constant-factor approximation and remains APX-hard. We then present probabilistic approximation algorithms for the two-group, single-terminal case: an algorithm whose tree subroutine is exact, hence optimal on tree-structured networks and

\mathcal{O}(\log |V|)

in expectation on general graphs, together with a faster bicriteria variant whose coverage violation degrades gracefully with the merge depth of the tree computation. For practical scalability, we additionally introduce a graph-native variant based on a shortest-path-tree reduction. Empirical results show that FML enforces group-level fairness, while the graph-native variant substantially improves scalability and achieves competitive activation cost.

Lutz Oettershagen, Othon Michail

University of Liverpool

Fair Resource Allocation Combinatorial Optimization Group Fairness Approximation Algorithms

Aug 23, 2024cs.LG

Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies

This paper considers a novel variant of the online fair division problem involving multiple agents in which a learner sequentially observes an indivisible item that must be irrevocably allocated to one of the agents to achieve a desired balance between fairness and efficiency. Existing algorithms assume a small number of items with a sufficiently large number of copies, which ensures a good utility estimation for all item-agent pairs from noisy observed utilities. However, this assumption may not hold in many real-life applications, e.g., an online platform with a large number of users (items) who use the platform's service providers (agents) only a few times (a few copies of items), making it difficult to accurately estimate utilities for all item-agent pairs. To address this limitation, we assume utility is an unknown function of item-agent features. We propose algorithms that model online fair division as a contextual bandit problem and achieve provable sublinear regret. Our experimental results further validate the effectiveness of the proposed algorithms.

Arun Verma, Indrajit Saha, Makoto Yokoo +1

Singapore-MIT Alliance for Research and Technology, Republic of Singapore · Faculty of ISEE, Kyushu University, Japan · Department of Computer Science, National University of Singapore, Republic of Singapore

Fair Resource Allocation Algorithmic Fairness

Jul 9, 2024cs.IT

DRL-AdaPart: DRL-Driven Adaptive STAR-RIS Partitioning for Fair and Efficient Resource Utilization

Efficient resource utilization is proposed for simultaneously transmitting and reflecting reconfigurable intelligent surfaces (STAR-RIS) to ensure fair and high data rates. We optimize the number of STAR-RIS elements to be allocated to each user and maximize the sum of the user rates. To promote fairness, we introduce a soft fairness mechanism that guarantees a minimum STAR-RIS element allocation to every user. Subject to this requirement, the phase shifts of the STAR-RIS elements and the remaining element assignments are jointly optimized by harnessing an appropriately tailored deep reinforcement learning (DRL) algorithm. The proposed DRL method is also compared to Dinkelbach's algorithm and to a bespoke hybrid DRL approach. A deactivation incentive is incorporated into the DRL model for enhancing resource utilization by intelligently deactivating some of the STAR-RIS elements when not required. The proposed DRL method achieves fair and high data rates for both stationary and mobile users, while ensuring efficient resource utilization. Using the proposed DRL method, up to 34% and 23% of STAR-RIS elements can be deactivated in static and mobile scenarios, respectively, with negligible degradation in the average DL data rate.

Ashok S. Kumar, Nancy Nayak, Sheetal Kalyani +2

Department of Electrical Engineering, Indian Institute of Technology Madras, Chennai, India · Department of Electrical and Electronic Engineering, Imperial College London, United Kingdom · Department of Electrical and Electronic Engineering, University of Peradeniya, Peradeniya 20400, Sri Lanka +1

Reconfigurable Intelligent Surfaces Fair Resource Allocation Wireless Communications Wireless Resource Allocation