CS Paper Radar

The Fixed Server Locality Gap of Count Load Assignment Games

Hao Li, Mengfan Ma

cs.GT ·submitted 2026-09-11 08:17 UTC · v2
theory

Abstract

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.

Comment
The manuscript is incomplete and requires substantial additional work before it is ready for dissemination

Closest papers

Nearest neighbours by meaning across the whole index.

MMS Allocation for Chores with Online Agent Arrivals

cs.GT ·2026-09-10 ·Haolong Li, Zehan Lin, Huahua Miao, Xiaowei Wu
theory similarity 0.65
Abstract

We study the fair allocation of $m$ indivisible chores to $n$ agents with subadditive cost functions arriving online in an arbitrary order. Upon an agent's arrival, we are informed of her cost function and must irrevocably assign her a set of chores. We focus on the Maximin Share (MMS) fairness notion and aim to compute an allocation in which all items are assigned, and no agent incurs a cost more than $α$ times her MMS. Without any prior information about the instance (other than $n$ and $m$), we design an algorithm with a competitive ratio of $O(\min\{n, k\log^{1+ε}k, \log m\})$ for any constant $ε> 0$, where $k$ denotes the number of cost function types. Our bound matches the best known offline approximation guarantees for MMS under subadditive costs and is nearly optimal with respect to all three parameters: we show that even for binary additive cost functions, no online algorithm can achieve a competitive ratio of $o(\min\{n, k\log k, \log m\})$. We then consider the setting in which the $k$ cost function types are known in advance (though the realized types of arriving agents are not). For additive cost functions, we provide an algorithm with a competitive ratio of $O(\min\{\log k, \log(kn)/\log\log(kn)\})$, and show that constant-competitive algorithms do not exist for general $k$, even for the binary additive setting. For binary additive functions when $k \le n$, we propose a $3$-competitive algorithm and establish a lower bound of $2$.

0.38

Exact Locality Gaps for Matchable Semi-Matchings

cs.DS cs.DM ·2026-10-01 ·Marek Gałązka, Hanna Wdowicka
code/data similarity 0.63
Abstract · 11 pages. Verification code and data: https://github.com/mgalazka84/semimatching-locality-gaps

An assignment of tasks to servers can resist every small improvement and still make tasks wait longer than necessary. We determine exactly how inefficient such an assignment can be when each task requires one unit of service and the eligibility constraints permit all tasks to use distinct servers. For every move size $r$ and maximum current server load $K$, we give a closed formula for the worst ratio between locally optimal and globally optimal total completion time. Local optimality here allows every feasible reassignment changing at most $r$ tasks. Every finite-cap bound is attained on a tree where each task has at most two eligible servers. Thus the worst behavior already occurs under simple eligibility constraints. At load cap two, the exact ratio is $1+1/(r+2)$, attained on a path with $r+2$ tasks. Without a load cap, the worst-case supremum is $3/2$ for single-task moves and approximately $1.294503159$ for two-task moves; its excess above one is $1/(r+2)+O(2^{-r}/r)$ as $r$ grows. The proof uses an explicit rational potential on a comparison graph and matching extremal constructions. These results give sharp guarantees for bounded-size local search on matchable semi-matchings, including exact guarantees under degree bounds.

0.30

Weighted Fair Division of Indivisible Mixed Manna

cs.GT ·2026-09-01 ·Nicholas Teh
highly cited similarity 0.62
Abstract

We study weighted fair division of indivisible mixed manna under additive valuations. First, we resolve the general existence open question for weighted envy-freeness up to one item (WEF1), and show that every instance with arbitrary positive entitlements admits a complete WEF1 allocation computable in polynomial time. We then show that existence does not imply any welfare guarantee, i.e., the utilitarian price of WEF1 is infinite, even for two unweighted agents with normalized valuations, common item signs, and singleton values in a fixed four-value set; a welfare-maximizing WEF1 allocation in the construction is fractionally Pareto optimal. Second, suppose each agent $i$ has a number $a_i>0$ such that their valuation for any item is $-a_i$, $0$, or $a_i$. Then, for arbitrary entitlements, a weighted maximin share (WMMS) allocation always exists, is computable in polynomial time, and can be chosen to be fractionally Pareto optimal. An exact formula for each WMMS value leads to a polynomial-time flow algorithm. In this class, every WEF1 allocation satisfies a best possible additive WMMS guarantee whose loss depends on the agent's entitlement relative to the largest entitlement. Thus maximum entitlement agents receive exact WMMS and, under equal entitlements, every WEF1 allocation is also MMS-fair. Allowing a second positive magnitude can violate exact WMMS, while unrestricted entitlement ratios rule out any fixed multiplicative WMMS guarantee compatible with WEF1 for chores.

0.44

How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?

cs.GT cs.AIcs.DSmath.OC ·2026-10-31 ·Yu Cheng, Tianle Jiang
similarity 0.61
Abstract

We study approximate Nash equilibria in nonatomic congestion games, with the goal of understanding how much the social cost can change when the equilibrium condition is relaxed. We consider $ε$-approximate Nash equilibria ($ε$-NE), in which each player uses a strategy whose cost is at most $1 + ε$ times the minimum available cost. We compare the social costs of $ε$-NE and exact Nash equilibria. This lets us quantify, for example, how much a navigation app can reduce total travel time when drivers tolerate routes slightly slower than the fastest available route. For degree-$d$ polynomial latencies in both general nonatomic congestion games and single-commodity routing games on series-parallel networks, we give tight lower and upper bounds on the relative change in social cost from an exact Nash equilibrium to any $ε$-NE, with matching instances for every $ε$. For small $ε$, the largest possible relative reduction and increase in general congestion games are both $Θ(\sqrt{dε})$, independently of the number of resources and populations. In contrast, on series-parallel networks of depth $h$, the largest possible relative reduction is $Θ(hε)$, while the largest possible relative increase is known to be $ε$. For the classes of games we study, these results give a tight and quantitative characterization of the possible changes in social cost and establish a separation between general and series-parallel networks.

0.13

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

cs.GT ·2026-09-29 ·Yunpeng Lou, Junjie Luo
publishedbenchmarktheory similarity 0.61
Abstract · Accepted to WINE 2026. Version 1 corresponds to the conference version; Version 2 includes improved results

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.

0.25

Exact Hill Shares Are Simultaneous Guarantees

cs.GT ·2026-09-18 ·Bo Li, Hanyu Li, Chenghua Liu
benchmarktheory similarity 0.61
Abstract

Fair division of indivisible bads seeks allocations that guarantee every agent a bundle whose cost is no larger than a meaningful fairness benchmark. The canonical minimax share has widely been used; unfortunately, it is not a simultaneous guarantee. Hill (Ann. Probab., 1987) initiated a complementary approach in which the share depends only on the number of agents and the largest possible single-item value. Li et al. (ACM Trans. Econ. Comput., 2024) gave the exact Hill formula and proved that its monotone closure is a simultaneous guarantee. The closure treats the largest-item cost only as an upper bound and can be strictly larger than the share conditioned on the \emph{actual} largest item. They asked whether this smaller exact share is itself simultaneously guaranteed for three or more agents. We resolve this open question affirmatively. For any number of agents and arbitrary heterogeneous largest-item costs, there is one allocation that satisfies every agent's exact Hill's share. We further provide a polynomial-time algorithm computes such an allocation. Our algorithm combines an ordered moving knife with a tail-domination invariant, and a one-sided trimmed subset-sum routine for the two-agent endpoint without computing an exact minimax partition.

0.16

Improving the Bounds on Approximating Weighted Maximin Share for Chores

cs.GT cs.AI ·2026-10-11 ·Trung Thanh Nguyen, Khaled Elbassioni, Jörg Rothe
similarity 0.61
Abstract

We investigate the problem of allocating indivisible chores among agents with arbitrary positive weights and additive nonnegative cost functions. An allocation is said to be $α$-weighted-maximin-share (WMMS) fair if the cost incurred by each agent is at most $α$ times her weighted maximin share. We establish that every instance admits a $4.124234528$-WMMS allocation. Moreover, for instances in which all weights and costs are rational numbers represented in binary, we give an algorithm that computes a $4.12424$-WMMS allocation in time polynomial in the number of agents, the number of chores, and the total binary encoding length of the input. Complementing these upper bounds, we construct a family of instances with strictly positive, identically ordered costs for which the optimal WMMS approximation factors converge to $e$. Together, our results substantially narrow the previously best-known gap of $[2,12]$ established by Li et al.~\cite{LWX26} to $[e,4.12424]$.

0.15

Online Fair Division under Eligibility Constraints

cs.GT ·2026-10-06 ·Joes Biburger, Nicole Megow, Golnoosh Shahkarami
theory similarity 0.60
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