CS Paper Radar

Sharp Bounds for Truthful-in-Expectation Scheduling

Yunpeng Li

cs.GT ·submitted 2026-11-03 16:15 UTC · v1
theory

Abstract

We study randomized mechanisms for scheduling indivisible jobs on $n$ unrelated machines. Each machine is controlled by a selfish agent who privately knows its processing time for each job. A mechanism assigns every job to a machine and makes payments. We require truthfulness in expectation: no agent can increase its expected payment minus its expected processing cost by misreporting, regardless of the other agents' reports. The makespan is the maximum total processing time assigned to a machine; the objective is to minimize its expectation. We prove that the optimal approximation ratio is $(n+1)/2$ for every $n\ge7$, relative to the minimum makespan of an integral assignment. The lower bound holds for every $n$ and allows unrestricted computation and arbitrary correlations among assignments, assuming finite expected payments and a guarantee uniform over all finite job counts. The matching mechanism uses correlated rounding and runs in expected polynomial bit time on rational inputs. These guarantees hold for all finite nonnegative processing times. For two machines, we characterize the optimal approximation ratio exactly as an analytic constant, approximately $1.505995705434$, and give a mechanism attaining it. For three machines the optimal ratio is $2$. For four, five, and six machines we obtain upper bounds of $3$, $105/32$, and $29/8$, respectively, compared with the general lower bound $(n+1)/2$. The proofs for $n\ge7$ do not rely on computer-assisted certificates; the two- and three-machine results use exact rational computer-assisted certificates.

Closest papers

Nearest neighbours by meaning across the whole index.

Universally truthful mechanisms for scheduling

cs.GT ·2026-09-11 ·Georgios Anastasiadis, George Christodoulou, Elias Koutsoupias, Annamaria Kovacs, Conrad Schecker
theory similarity 0.79
Abstract

We consider universally truthful randomized mechanisms for the problem of scheduling $m$ jobs on $n$ unrelated machines. We prove a lower bound on the expected approximation ratio of every such mechanism whose probability distribution has discrete support. We show that no universally truthful randomized mechanism in this class can achieve approximation ratio smaller than $n/12 - o(n)$ with respect to the optimal makespan. We match this, up to a constant factor, by a mechanism with approximation ratio $n/2 + o(n)$.

0.49

Tight bounds for fractional and randomized truthful scheduling

cs.GT ·2026-11-04 ·Georgios Anastasiadis, George Christodoulou, Elias Koutsoupias, Annamaria Kovacs, Conrad Schecker
theory similarity 0.78
Abstract

We resolve one of the longest-standing open problems in algorithmic mechanism design by showing that randomization cannot yield a sublinear approximation for truthful scheduling on unrelated machines, even when truthfulness is required only in expectation. Our main technical result concerns fractional scheduling, where tasks may be split among machines. We prove that every deterministic truthful fractional mechanism on $n$ unrelated machines has worst-case approximation ratio at least $(n+1)/2$, even against the optimal integral makespan. This matches the known upper bound exactly and settles the optimal approximation ratio of truthful fractional scheduling. Since the expected allocations and payments of a truthful-in-expectation mechanism define a truthful fractional mechanism, the same lower bound applies to all truthful-in-expectation mechanisms and, in particular, to all universally truthful mechanisms. On the positive side, we give a universally truthful mechanism with approximation ratio $n/2+o(n)$. Together, these results establish the optimal leading constant $1/2$ for randomized truthful scheduling. Thus, randomization improves on the optimal deterministic approximation ratio by an asymptotic factor of two, and no more.

0.18

Tight Analysis of Randomized Truthful Scheduling: An $(m+1)/2$ Lower Bound

cs.GT ·2026-11-03 ·Wenqian Wang, Chenyang Xu, Yuhao Zhang
theory similarity 0.72
Abstract · 42 pages, 2 figures

The Nisan-Ronen conjecture, a central problem in algorithmic game theory, asserts that no deterministic truthful mechanism for makespan minimization on $m$ unrelated machines can achieve an approximation ratio better than $m$. Christodoulou, Koutsoupias, and Kovács resolved it in 2023, but the optimal approximation ratio achievable by randomized truthful mechanisms remained open. Recently, Anastasiadis, Christodoulou, Koutsoupias, Kovács, and Schecker extended techniques from the deterministic proof to establish a $(3/2-\sqrt{2})(m-1)$ lower bound for universally truthful mechanisms with discrete support and gave a universally truthful mechanism with approximation ratio $m/2+o(m)$. For the broader class of truthful-in-expectation (TIE) mechanisms, however, the gap remained large: the best known upper bound was $(m+5)/2$, while the lower bound was only $2-1/m$. We prove a lower bound of $(m+1)/2$, determining the optimal TIE approximation ratio up to an additive constant as $m/2+Θ(1)$. Our result also improves the leading constant in the lower bound for universally truthful mechanisms from $3/2-\sqrt{2} \approx 0.0858$ to $1/2$. Together with their $m/2+o(m)$ upper bound, our result determines the optimal approximation ratio for universally truthful mechanisms up to lower-order terms.

0.20

Randomized Algorithm for MMS Allocation of Chores with Online Agent Arrivals

cs.GT ·2026-10-11 ·Haolong Li, Fangxiao Wang, Xiaowei Wu
similarity 0.71
Abstract

We study the fair allocation of $m$ indivisible chores among $n$ agents in the agent-arrival model against an oblivious adversary. The chore set and the number of agents are known in advance. When agent $i$ arrives, her nonnegative additive cost function $c_i$ is revealed, and the algorithm must immediately and irrevocably assign her a subset of the unallocated chores. We focus on the notion of maximin share (MMS) and measure the fairness of the realized allocation $X$ by the ex-post MMS approximation ratio $ρ(X)$. We measure an algorithm's performance by its expected ratio, and also the guarantees that hold with high probability. For binary additive costs, we achieve an expected ex-post MMS ratio of $3/2+o(1)$, and show that every randomized online algorithm has an expected ratio of at least $3/2-o(1)$. For every $n$, the expected ratio is at most $1.755$. A variant of our algorithm guarantees an approximation ratio of $2$ with high probability, which is optimal. % For general additive costs, we present a weighted-rounding algorithm that achieves an expected ratio of $2+o(1)$, which also holds with high probability. The expected ratio is at most $2.594$ for every $n$. We also show that similar algorithms extend to additive goods, achieving a constant expected ex-post MMS ratio and guaranteeing every agent an $x$-fraction of her MMS with probability at least $1-85x^2$ for every $x\le1/15$.

0.39

Truthful-in-Expectation MMS Allocations for Chores

cs.GT cs.DS ·2026-09-28 ·Zehan Lin, Biaoshuai Tao, Xiaowei Wu, Yuhao Zhang
theory similarity 0.71
Abstract · 35 pages, 6 figures

We study truthful-in-expectation (TIE) mechanisms for allocating indivisible chores alongside ex-post maximin share (MMS) guarantees. For goods, Bu and Tao (FOCS 2025) established a (1/n)-approximation for TIE mechanisms, and this was substantially improved by Babaioff, Feige, and Manaker Morag (FOCS 2026), who established an Ω(1/\log n) approximation, where n is the number of agents. The corresponding problem for chores has received less attention. The best-known result is due to Aziz, Li, and Wu (MAPR 2024), who gave a TIE mechanism with an O(\sqrt{\log n}) MMS approximation guarantee that holds only in expectation. They also established a 6/5 lower bound for TIE mechanisms for two agents. In this paper, we present the first TIE mechanism for chores that achieves a constant ex-post MMS approximation guarantee. Specifically, our mechanism guarantees an ex-post ratio of 1.97 for any number of agents n, which improves to 4/3 for n=2 and 3/2 for n=3. On the hardness side, we tighten the two-agent lower bound to 4/3, showing that our mechanism is optimal for n=2. More generally, we establish a lower bound of 13/12 on the ex-post MMS approximation ratio achievable by TIE mechanisms for every n\ge 3.

0.29

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.69
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

A QPTAS for Stochastic Scheduling of Bernoulli Jobs

cs.DS cs.CCmath.OC ·2026-10-08 ·Junho Hwang
benchmark similarity 0.68
Abstract · 23 pages, 1 figure

We study the classical problem of scheduling jobs with random processing times on $m$ identical machines to minimize the expected sum of completion times, for Bernoulli jobs: job $j$ takes time $p_j$ with probability $q_j$ and time $0$ otherwise, and its outcome is revealed when it starts. The benchmark is an optimal adaptive policy. We give a quasi-polynomial-time approximation scheme for every number of machines. Previously, quasi-polynomial time was known to give an $O(\log N)$-approximation, and approximation schemes were known only for a constant number of distinct sizes. The scheme rests on a simple observation: it suffices to round the times at which machines become free, rather than the times at which jobs start, to a grid whose width is proportional to the job size, and an optimal policy stretched by a factor close to one already respects such grids. We also show that every policy that fixes the order of the jobs in advance loses a factor $Ω(\log N)$, already on two machines, so a constant factor requires adapting the order to the observed outcomes. Further results include a polynomial-time adaptive rule with ratio $\min\{m,1+\sum_j q_j\}$, a simpler approximation scheme for a constant number of sizes, and #P-hardness of computing the optimal expected cost on two machines.

0.25

Polynomial-Time Approximate EFX for Chores via Flow and Matching

cs.GT ·2026-11-05 ·Genjie Qin, Qizhi Fang, Minming Li, Wenjing Liu, Xin Chen
theory similarity 0.68
Abstract

We study approximate EFX allocations of indivisible chores under nonnegative additive costs. Exact EFX allocations need not exist in general. We develop a polynomial-time algorithm that computes a complete $(3+\varepsilon)$-EFX allocation for any rational $0<\varepsilon\leq1$, improving the previous approximation guarantee from a factor depending on the number of agents to a constant. The algorithm extends to EF$k$X, achieving a $(2+1/k+\varepsilon)$-approximation for every integer $k\geq1$. For instances with relatively few chores, the polynomial-time BRBI algorithm gives stronger guarantees. It finds exact EF$k$X allocations when $m\leq2kn$ and achieves a factor of at most $2-1/k$ when $m\le(3k-1)n$. In particular, $k=1$ and $m\leq2n$ give exact EFX. We further show that the approximation factor \(2+1/k\) is asymptotically tight for our main algorithm. We also construct a four-agent, ten-chore instance in which every complete allocation has EFX approximation factor at least $11/10$, improving upon the $20/19$ lower bound for submodular costs even under additive costs.

0.40