CS Paper Radar

Gaps and Augmentations in Bayesian Scheduling

Ahuva Mu'alem

cs.GT ·submitted 2026-09-27 11:38 UTC · v1
benchmarktheory

Abstract

The recent resolution of the Nisan--Ronen conjecture~\cite{NR,CKK} establishes that the optimal worst-case approximation ratio of deterministic truthful mechanisms for makespan on m unrelated machines is exactly m. We ask how prior information, Bayesian incentive compatibility (BIC), randomization, and machine-side resource augmentation change this barrier. We obtain three main results. First, we prove an asymptotic 4/3 lower bound for randomized BIC mechanisms with two machines, strengthening the previous 1.2 deterministic-BIC lower bound~\cite{MS}. Second, in the prior-free setting for two machines, randomization improves the known truthful ratio from 2 to 7/4~\cite{NR}. We show that randomized BIC scheduling mechanisms are likewise strictly more powerful than their deterministic counterparts, exhibiting an asymptotic BIC-integrality gap of 8/7. Thus, optimality in prior-dependent BIC scheduling can strictly require randomization. This parallels the role of lotteries in multidimensional revenue maximization, where randomization can strictly improve revenue~\cite{MV,BCKW}. Third, we show that when job assignments are sufficiently well spread across machines (more formally, when the pairwise collision parameter $Δ_r$ is bounded by a constant independent of both the number of machines m and the number of sampled layers r), then $O(m/\varepsilon)$ sampled layers suffice for the standard truthful MinWork mechanism to achieve a $1+\varepsilon$-approximation to the original first-best benchmark. Equivalently, $O(m/\varepsilon)$ sampled replicas per machine suffice. This resource-augmentation result parallels the Bulow--Klemperer perspective~\cite{BK,EFFTW}. As a by-product, in the standard unaugmented model, MinWork achieves a $(1+\frac{Δ_1(m-1)}{2})$-approximation to the first-best benchmark for every prior.

Closest papers

Nearest neighbours by meaning across the whole index.

Sharp Bounds for Truthful-in-Expectation Scheduling

cs.GT ·2026-11-03 ·Yunpeng Li
theory similarity 0.66
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.

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

Universally truthful mechanisms for scheduling

cs.GT ·2026-09-11 ·Georgios Anastasiadis, George Christodoulou, Elias Koutsoupias, Annamaria Kovacs, Conrad Schecker
theory similarity 0.63
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.63
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

Multi-Capacity Online Assortment Optimization with Consecutive Stays under Markov Chain Choice

cs.DM ·2026-10-20 ·Hongbin Zhang, Yanzhi Li, Woonghee Tim Huh
benchmark similarity 0.61
Abstract

We study online assortment optimization under Markov chain choice and independent Bernoulli arrivals, with each period's request type known in advance. Each product may have multiple interchangeable physical copies, and each booking reserves consecutive service slots on a single copy. Customers choose among products, while the platform assigns purchases to feasible copies. We develop a sales-based relaxation that upper-bounds the optimal online revenue and use it to design a policy with two components: independent sampling and purchase--update coupling. We generate independent copy proposals and make a product eligible whenever at least one of its copies proposes. A general revenue-extraction bound for random candidate sets with independent product inclusions shows that optimizing over eligible products recovers at least half of each period's relaxation revenue benchmark in expectation. A purchase--update coupling reproduces the interval flows through independent virtual copy updates while preserving physical feasibility. Under general Markov chain choice, the policy uses a random gate to make the coupling feasible: it offers the selected assortment with probability \(1-1/e\) and the empty assortment otherwise. No gate is needed under multinomial logit (MNL) choice. The resulting policies achieve approximation ratios of \((1-1/e)/2\) and \(1/2\), respectively, relative to the optimal nonanticipative online policy, independently of product capacities. In the single-copy MNL setting, our policy improves the guarantee of \citet{huwu2026} from \(0.271\) to \(1/2\) under the same arrival convention. The \(1/2\) static extraction factor and the \(1-1/e\) uniform scalar-gate factor are separately sharp, and the \(1/2\) MNL guarantee is tight for the proposed policy.

0.06

Improved Combinatorial Auctions with and without Samples

cs.GT cs.DS ·2026-10-13 ·Aviad Rubinstein, Sahil Singla
similarity 0.60
Abstract · Abstract shortened to fit arXiv constraints

We give new mechanisms for combinatorial auctions in the offline, secretary, and prophet-with-samples models. Specifically, we obtain the following guarantees for social welfare maximization with $m$ items and $n$ XOS buyers: * In the prophet-with-samples version, buyers arrive in adversarial order and draw their values from independent distributions. We give a universally truthful, polynomial-time $(2+\eps)$-approximation mechanism using $O(\log\!\log m)$ samples from each distribution. The approximation factor is tight even for a single item and without the incentive constraints, due to the classic prophet inequality. Compared to the previous state-of-the-art with the same guarantees [Dütting--Kesselheim--Lucier--Reiffenhäuser--Singla (FOCS 2024)], our running time is exponentially faster, and our sample complexity is doubly-exponentially lower, resolving two explicit open problems by Dütting et al. * Using the same techniques, we also obtain improved mechanisms in the secretary and offline versions, where the values are worst-case, and buyers are processed in either random order (secretary) or without any timing restrictions (offline). After a long line of works, the state of the art in both models is an $O((\log\!\log m)^2)$-approximation due to [Assadi--Kesselheim--Singla (SODA 2021)], who explicitly ask whether it can be improved to $O(\log\!\log m)$. We indeed obtain an $O(\log\!\log m)$-approximate universally truthful mechanism for the secretary and offline models.

0.08

A Combinatorial $(1/2-\varepsilon)$-Approximation for $k$-Submodular Maximization under Multiple Knapsacks

cs.DS ·2026-10-17 ·Siyuan Chen, Suixiang Gao, Zheyu Jiang, Wenguo Yang
similarity 0.59
Abstract · 23 pages

We give a randomized combinatorial \((1/2 - \varepsilon)\)-approximation for nonnegative non-monotone \(k\)-submodular maximization under a fixed number \(d\) of knapsack constraints, for \(k \ge 2 \). The algorithm selects whole elements and follows the proportional top-2 rule of Chen et al. \cite{chen2026}: it samples from the two labels with the largest marginal gains, with probabilities proportional to the positive parts of these gains. Extending their single-knapsack Bellman analysis, we construct a common resource potential and associated resource weights, with potential losses charged to greedy gains. Since these weights depend on the unknown optimum, we discretize their defining coefficients and enumerate monotone guesses over phases determined by resource consumption. This yields an algorithm using at most $\mathcal{A}(d,\varepsilon)(nk+1)^{H+2}$ value queries, where $n$ is the number of elements, $\mathcal{A}(d,\varepsilon)$ depends only on $d$ and $\varepsilon$, and $H=O(d \log(2d) / \varepsilon^2)$. The approximation ratio can be made arbitrarily close to the optimal oracle threshold for \( k=2 \) and is asymptotically tight as \(k \to \infty\).

0.21

Sample Complexity of the Second-Best Bilateral Trade

cs.GT ·2026-08-26 ·Qiaoyun Shi, Shengxin Liu, Zongqi Wan
benchmark similarity 0.58
Abstract

We study the sample complexity of learning near-optimal bilateral trade mechanisms. Unlike previous work on learning simple or fixed-price bilateral-trade mechanisms, we focus on mechanisms satisfying Bayesian incentive compatibility (BIC), interim individual rationality (IIR), and ex-ante weak budget balance (WBB). In other words, our target is to design a sample-based mechanism that achieves the second-best gains-from-trade benchmark. We give matching or nearly matching upper and lower bounds in three regimes. For regular product distributions on $[0,h]^2$, additive $\varepsilon$-approximation has sample complexity $\widetildeΘ(h^2/\varepsilon^2)$. For multiplicative $(1-α)$-approximation under the same assumptions, we find that the sample complexity is $\widetildeΘ(h/(\mathrm{SB}(D)α^2))$, which is benchmark-sensitive with unavoidable dependence on the second-best gains from trade $\mathrm{SB}(D)$. We also investigate unbounded distributions under a monotone hazard rate (MHR) assumption. The sample complexity depends on the ratio $χ_μ(D)=μ(D)/\mathrm{SB}(D)$, where $μ(D)$ is the sum of the buyer's expected value and the seller's expected cost.

0.05