CS Paper Radar

The Price of Strategyproofness in Fair Multi-Resource Allocation for Cloud Computing

Yunpeng Lou, Junjie Luo

cs.GT ·submitted 2026-09-29 17:10 UTC · v2
publishedbenchmarktheory

Abstract

We study fair and strategy-proof allocation of multiple divisible resources with Leontief utilities, motivated by cloud computing. The canonical mechanism, Dominant Resource Fairness (DRF), satisfies sharing incentive (SI), envy-freeness (EF), strategy-proofness (SP), and Pareto optimality (PO), but can be highly inefficient in terms of utilitarian social welfare. Under the classical approximation benchmark, no mechanism satisfying even one of SI, EF, and SP can improve on the trivial worst-case guarantee. We therefore adopt the recently introduced \emph{fair-ratio} benchmark, which compares a mechanism only with the welfare-maximizing allocation that itself satisfies SI and EF. For two resources, we first introduce Adaptive-Speed Fairness (ASF), a unified parametric framework that captures previous mechanisms as special or boundary cases. Every ASF mechanism satisfies SI, EF, and PO, and we derive a general sufficient condition that guarantees SP. Optimizing within this framework yields a strategy-proof mechanism with asymptotic fair-ratio $2/(2\sqrt{2}-1)\approx 1.094$, substantially improving the previous best guarantee $3-\sqrt{3}\approx1.268$. We complement this upper bound with a lower bound of $1.0789$ for all ASF mechanisms. To overcome this limitation, we introduce Corrected Resource Balancing (CRB), which uses the full resource-load structure together with a one-agent incentive correction. CRB satisfies SI, EF, SP, and PO and achieves fair-ratio at most $1+1/n$. Together with a general $1+Ω(1/n)$ lower bound, this establishes the optimal asymptotic order $1+Θ(1/n)$ for two resources. Finally, for every $m\ge3$, any deterministic mechanism satisfying SI and SP has fair-ratio exactly $m$. The same lower bound holds for randomized mechanisms satisfying ex-post SI and truthfulness in expectation.

Comment
Accepted to WINE 2026. Version 1 corresponds to the conference version; Version 2 includes improved results

Closest papers

Nearest neighbours by meaning across the whole index.

Tight Worst-Case Completion-Time Bounds for Dominant Resource Fairness

cs.DS ·2026-11-05 ·Mugen Blue, Sungjin Im, Alexander Lindermayr
theory similarity 0.72
Abstract

Dominant Resource Fairness (DRF) is an influential policy for sharing multiple resources among jobs with heterogeneous demands. It combines sharing incentive, strategy-proofness, envy-freeness, and Pareto efficiency, making it particularly attractive for shared computing systems. DRF has been implemented in major resource-management frameworks, including Apache Mesos and Hadoop YARN. DRF is also nonclairvoyant: it requires no advance knowledge of job sizes, making it practical when processing requirements are difficult to predict. This motivates understanding its completion-time performance relative to an optimal schedule that knows all job sizes. However, elementary arguments can only give an $Ω(\sqrt D)$ lower bound and an $O(D)$ upper bound for total completion time, where $D$ is the number of resource types. In this paper, we close this gap by proving that DRF is $Θ(\sqrt D)$-competitive. More generally, for every fixed real $q\geq1$, we show that DRF is $Θ(D^{1/(q+1)})$-competitive for the $\ell_q$ norm of completion times, with larger $q$ placing greater emphasis on late-finishing jobs. These bounds hold with arbitrary release times. We also give a refined analysis of total completion time for small $D$.

0.17

Polynomial Algorithms for Simultaneous Share-Based and Envy-Based Guarantees

cs.GT ·2026-10-11 ·Hannaneh Akrami, Arash Ashuri, Kurt Mehlhorn
similarity 0.66
Abstract

We study the simultaneous achievement of share-based and envy-based fairness in the allocation of indivisible goods with nonnegative additive valuations. The AnyPrice share (APS) is a strengthening of the maximin share (MMS). A polynomial-time algorithm is known to guarantee a $2n/(3n-1)$ approximation of APS, but without an accompanying envy-based guarantee. Separately, allocations simultaneously satisfying minimum EFX share (MXS) and envy-freeness up to one less-preferred good (EFL), and subsequently the stronger requirement of residual maximin share (RMMS) together with EFL, have been shown to exist. However, the known constructions do not provide pseudopolynomial-time guarantees. We develop algorithms that combine these share-based and envy-based fairness requirements. First, for every $\varepsilon \in (0,1)$, we give an algorithm that computes an allocation satisfying exact EFL, $(1-\varepsilon)$-MXS, and $2n/(3n-1)$-APS. Its running time is polynomial in the binary input length and $1/\varepsilon$. Thus, we match the previously established polynomial-time APS approximation while simultaneously guaranteeing exact EFL and an arbitrarily close approximation to MXS. Second, we provide a pseudopolynomial-time algorithm that simultaneously guarantees exact MXS, exact EFL, and $2n/(3n-1)$-APS. Third, for every fixed number of agents, we obtain a pseudopolynomial-time algorithm that simultaneously achieves exact RMMS and exact EFL. Finally, we establish that computing a numerical threshold between MXS and RMMS is weakly NP-hard, even for additive valuations. This identifies a computational barrier to extending our polynomial-time approach to exact MXS through independently computed residual-valid share thresholds.

0.38

Online Fair Division under Eligibility Constraints

cs.GT ·2026-10-06 ·Joes Biburger, Nicole Megow, Golnoosh Shahkarami
theory similarity 0.63
Abstract

We study fair division of indivisible items under eligibility constraints: each item may be assigned only to a subset of eligible agents. This model coincides with restricted assignment in scheduling, with agents as machines and items as jobs, and captures settings where work or resources must be split among parties with different capabilities. Eligibility makes the usual fairness benchmarks inadequate, as agents should not be measured against items they could never receive. We therefore use eligibility-aware versions of proportionality and envy-freeness, where an agent's proportional share splits each item equally among its eligible agents, and envy comparisons discount items the agents are not eligible for. Our main finding is a sharp chore--goods separation for proportionality. We focus on identical valuations: under arbitrary valuations, no online algorithm can guarantee even an $o(m)$-approximation for chores. For chores, Prop1 is achievable offline, whereas exact proportionality and proportionality up to any item are not. For online chores, the optimal approximation factor for Prop1 for deterministic algorithms is $Θ(\sqrt m)$, with the lower bound holding even for unit-size jobs. For goods, Prop1 is again achievable offline, but the tight online bound drops to $Θ(\log m)$. For envy-based fairness, the picture is different. Goods and chores are equivalent under eligibility-aware envy notions, while the choice of notion is decisive. Strong EF1 may fail to exist even offline and cannot be approximated online. In contrast, weak EF1 can be maintained online, while weak EFX separates offline from online. Together, these results give a systematic study of online proportional and envy-based fairness in restricted assignment and show which fairness guarantees remain achievable under eligibility constraints.

0.35

Closing Gaps in Online Fair Division

cs.GT ·2026-09-04 ·Tzeh Yuan Neoh, Nicholas Teh
theoryhighly cited similarity 0.63
Abstract

We study the online fair division of indivisible items, where items arrive one at a time and must be allocated immediately and irrevocably. We address three central open questions in the literature. First, we show that for every $n\ge 2$ agents, every fixed $k\ge 1$, and every $α\in(0,1]$, no online algorithm can guarantee $α$-PROP$k$ against an adaptive adversary. This remains true even when the total number of goods is known in advance, all values lie in $[0,1]$, and every good is positively valued by at most two agents. The impossibility extends to a broad range of standard envy-based, proportionality-based, and share-based fairness notions. We also establish an analogous impossibility for chores. Second, in the setting with predictions, a lightweight form of future information, the maximum item value, was previously known to guarantee only $1/n$-PROP1, leaving open whether the dependence on $n$ is necessary. We give a deterministic $19/30$-PROP1 algorithm against adaptive adversaries that does not require knowing the total number of goods. Given an additional upper bound $κ\in[2,n]$ on the number of agents who value any good positively, the guarantee improves to $\max \{ 19/30, n/(n+κ) \}$. The guarantee remains a positive constant under any fixed one-sided prediction error below one. When predictions are exact and the total number of goods $m\ge n\log n$ is known in advance, a deterministic algorithm achieves the same $19/30$-PROP1 factor together with $O(\sqrt{m\log n/n})$ maximum additive envy after normalizing each agent's values by their maximum item value. Third, against a non-adaptive adversary, we determine the tight high-probability PROP1 guarantee of the classical Like rule, which assigns each good uniformly among the agents who value it positively. Its guarantee improves when fewer agents value the same good, unlike uniform random allocation.

0.43

Simultaneous Envy and Equitability Guarantees

cs.GT cs.AIecon.TH ·2026-08-26 ·Hadi Hosseini, Shraddha Pathak, Lirong Xia, Chengkai Zhang
similarity 0.63
Abstract · 43 pages

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.

0.41

Randomized Online Fair Division: High-Probability and Expected Realized Fairness

cs.GT ·2026-09-20 ·Tianqi Chen, Jingxiao Long
similarity 0.62
Abstract · 22 pages. Improved high-probability and expected realized PROP1 guarantees; revised proofs and exposition

We study randomized algorithms for the fully online allocation of indivisible goods among $n\ge2$ agents with nonnegative additive valuations. Goods arrive sequentially and must be allocated immediately and irrevocably, with only $n$ known in advance. Since exact ex-ante envy freeness and proportionality are readily achievable, while no positive ex-post approximation is possible for the fairness notions considered here, we study the intermediate notions of high-probability fairness and expected realized fairness. Against a non-adaptive adversary, we give a randomized algorithm for proportionality up to one good (PROP1) whose parameter depends only on $n$ and that preserves exact ex-ante envy-freeness and proportionality. At confidence $1-δ$, its PROP1 guarantee improves on independent uniform allocation (Rand) by a factor of $Ω(\log n)$, uniformly over $δ\in(0,1/2]$. As $n\to\infty$, its expected realized PROP1 factor is at least $\frac{3-\sqrt5}{2}-o(1)$. We also show that the expected realized PROP1 factor of Rand is $(1+o(1))/\log n$, yielding an improvement of at least $\bigl(\frac{3-\sqrt5}{2}-o(1)\bigr)\log n$ for our algorithm. For every randomized online algorithm and every positive approximation factor, the success probability can be made arbitrarily small for envy freeness up to any good (EFX) and at most $\frac{n+1}{2n}$ for envy freeness up to one good (EF1). Consequently, every randomized fully online algorithm has an expected realized EFX guarantee of zero and an expected realized EF1 guarantee of at most $\frac{n+1}{2n}$.

0.43

The Fixed Server Locality Gap of Count Load Assignment Games

cs.GT ·2026-09-11 ·Hao Li, Mengfan Ma
theory similarity 0.61
Abstract · The manuscript is incomplete and requires substantial additional work before it is ready for dissemination

Marginal-contribution pricing makes the social objective an exact potential, but does not ensure that every stable assignment is efficient. We study indivisible clients with heterogeneous workloads, arbitrary nonnegative assignment costs, and private eligibility menus over a fixed number of shared servers and optional local execution. Each server's social cost is its occupancy multiplied by its aggregate workload and a server-specific coefficient. For every fixed server cap $M$, we prove that the price of anarchy over this class is $Θ_M(κ^{1-2^{-M}})$ as the workload-ratio cap $κ$ grows. The upper bound applies to every equilibrium and every feasible comparison, without an acyclic-comparison or strongly-connected-component restriction. Its proof combines a common-multiplier certificate, a source-weighted residual inequality and an ordered moment recurrence. A matching chain family has a realization by mobile unmanned aerial vehicle (UAV) clients and fixed ground servers, with positive altitude, positive-width coverage and an explicitly paid wireless baseline. We prove exact waypoint elimination and give an input-computable component refinement. Scheduling and congestion identities delimit which established bounds transfer. Exact enumeration of 2,800 synthetic games identifies inefficient equilibria, while 270 primary-parameterized synthetic instance-budget records evaluate incremental latency relative to a feasible multistart reference. Tightness concerns the heterogeneity exponent for fixed $M$, not matching leading constants or measured frequency of the worst-case configurations.

0.27

Reconfiguration in Fair Division Revisited

cs.GT cs.DM ·2026-09-14 ·Fabian Frank, Warut Suksompong
theory similarity 0.60
Abstract

We revisit reconfiguration in the fair allocation of indivisible goods, where the goal is to transform one fair allocation into another through a sequence of exchanges while preserving fairness at every step. Our focus is on the hierarchy of envy-freeness up to $k$ goods (EF$k$). We show that for any fixed $k$, two EF1 allocations with the same size vector need not admit a reconfiguration path whose intermediate allocations satisfy EF$k$. This impossibility persists even when the two allocations arise from standard EF1 approaches: the envy cycle elimination algorithm or the maximum Nash welfare solution. In contrast, we prove that allocations with the same size vector produced by recursively balanced picking sequences, including round-robin, are always connected via a path that maintains EF2. We also show that deciding whether an EF1 reconfiguration path exists is NP-hard for any fixed number of agents. Furthermore, we complement these exchange-based results by studying a more permissive model that also allows transfers, establishing additional connectivity guarantees.

0.11