PaperlayerView exact revision on arXiv

Source-linked AI summary

Universally truthful mechanisms for scheduling

Georgios Anastasiadis, George Christodoulou, Elias Koutsoupias, Annamaria Kovacs, Conrad Schecker

arXiv:2609.12621v1cs.GT

TL;DR

Truthful scheduling on unrelated machines remains challenging for randomized mechanisms, with known O(n) guarantees and a lower bound of 2 − 1/n. The paper proves a linear lower bound for discrete-support universally truthful mechanisms and presents a mechanism with an n/2 + o(n) approximation ratio.

  • Problem

    Known randomized-mechanism guarantees are O(n), while the best lower bound is 2 − 1/n, leaving the achievable approximation for universally truthful scheduling unresolved.

    Source: §1 · p. 2

  • Method

    The paper analyzes universally truthful mechanisms as discrete distributions over deterministic truthful mechanisms and uses Yao’s Minimax Principle to prove a lower bound.

    Source: §1 · p. 2, §3.1 · p. 6

  • Results

    Universally truthful mechanisms have an Ω(n) lower bound, while the proposed mechanism achieves an approximation ratio of n/2 + o(n).

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper establishes linear-scale bounds for discrete-support universally truthful scheduling mechanisms, with the proposed guarantee matching the lower bound up to a constant factor.

    Source: §1 · p. 2

    The lower-bound analysis is restricted to discrete-support distributions; extension to uncountable support is expected but not established here.

    Source: §1 · p. 2, §2.4 · p. 6

Abstract

from arXiv · show

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)$.

1 Introduction

The paper studies randomized truthful scheduling on unrelated machines, where private processing times and a makespan objective make truthful mechanism design challenging. It establishes a linear lower bound for discrete-support universally truthful mechanisms and gives a mechanism with an n/2 + o(n) approximation ratio.

Deterministic Mechanisms.

  • Deterministic truthful mechanisms have an exact n-approximation barrier, while the VCG mechanism achieves an n-approximation by minimizing total completion time.The lower bound for deterministic mechanisms was established using specialized instances and an induction argument.Source: §1 · pp. 1–2

Randomized Mechanisms.

  • Randomized mechanisms remained unresolved: known guarantees were O(n), whereas the best lower bound was 2 − 1/n.Universally truthful mechanisms are distributions over deterministic truthful mechanisms; truthful-in-expectation mechanisms require truthfulness only in expected utility.Source: §1 · p. 2

1 Introduction

  • Every universally truthful randomized mechanism in the studied class has an approximation ratio of Ω(n).The class is defined using discrete distributions over deterministic mechanisms.Source: §1 · p. 2
  • The Exp-Bounded-Square mechanism achieves an approximation ratio of n/2 + o(n), improving on the previous 0.837n bound.The result asymptotically matches bounds for fractional and truthful-in-expectation mechanisms.Source: §1 · p. 2
  • The analysis is restricted to discrete-support mechanisms to avoid measure-theoretic technicalities, though the authors expect the approach and linear lower bound to extend to uncountable support.The paper applies Yao’s Minimax Principle to establish its lower bound.Source: §1 · p. 2

2 Preliminaries

The preliminaries define unrelated-machine scheduling and the strategic mechanism framework, then characterize truthfulness through weak monotonicity. Universally truthful randomized mechanisms are treated as discrete distributions over deterministic weakly monotone allocation rules.

2 Preliminaries

  • The scheduling objective is to assign all tasks to unrelated machines while minimizing the maximum machine completion time, or makespan.Each task has a processing time on each machine.Source: §2 · p. 4

2.1 Mechanism Design Setting

  • Machines are selfish agents with private vectors of task processing times, and direct revelation lets each agent report a vector from its type space.A report may differ from the agent’s true type if doing so serves its interests.Source: §2.1 · p. 4

2.2 Deterministic Mechanisms

  • A deterministic mechanism combines an allocation rule assigning each task to one machine and a payment scheme, with utility equal to payment minus actual processing time.Truthfulness requires truthful reporting to be a dominant strategy.Source: §2.2 · p. 4

2.3 Weak Monotonicity

  • Weak monotonicity is necessary for truthful allocation rules and sufficient for truthfulness in the scheduling domain.Fixing values on some tasks preserves weak monotonicity on the remaining tasks; graph settings with at most two possible players per task help address allocation changes among other players.Source: §2.3 · p. 5

2.4 Randomized Mechanisms

  • The paper models universally truthful randomized mechanisms as discrete distributions over deterministic weakly monotone allocation rules and evaluates their expected makespan relative to the optimum.A mechanism is β-approximate when its expected approximation ratio is at most β for every type profile.Source: §2.4 · p. 6

3 Lower Bound

This section proves a linear lower bound for discrete universally truthful randomized mechanisms for unrelated-machine scheduling. It uses Yao’s Minimax Principle on random, graph-based star instances to derive a deterministic makespan lower bound, with the analysis relying on box properties of stars.

3.1 Applying Yao’s Principle

  • An Ω(n) lower bound for universally truthful mechanisms is proved using Yao’s Minimax Principle.The argument first handles finite-support distributions with a common approximation bound, then extends the lower bound to general discrete distributions.Source: §3.1 · pp. 6–7

3.2 Graph Instances and the Box Theorem

  • The proof models tasks as multigraph edges between machines, uses nondecreasing boundary functions to describe deterministic allocations, and applies the Box Theorem to stars in trivial instances.An edge assigned outside its two endpoint machines incurs approximation ratio at least K; the Box Theorem states that the probability a randomly selected star is an ε-box tends to 1 as edge multiplicity ℓ grows.Source: §3.2 · pp. 7–9

3.3 Definition of Random Instances

  • The constructed instances use a random star whose edges have root processing time c; if every star edge goes to its leaf, the optimal makespan is at most 1.The construction starts from a multi-clique with ℓ parallel tasks per machine pair and raises the root’s costs on the selected star edges from 0 to c.Source: §3.3 · p. 9

3.4 Allocation of a Fixed Star

  • For a random star that is an ε-box, Lemma 4 relates the number of large-boundary edges to the number allocated to the root, while the root’s makespan is at least c times the latter count.The star is an ε-box with arbitrarily high probability as edge multiplicity grows, by the Box Theorem [11].Source: §3.2 · p. 9, §3.4 · p. 10

3.5 Expectations for Random Stars

  • For a random star, the expected number of edges with large boundary values is at least (n−1)/2, with expectation taken over the random instance and its edge directions.The bound is not asserted for each fixed center and instance; the argument averages over the random multi-clique as well as the root and star.Source: §3.5 · p. 12
  • For a random star conditioned to be an ε-box, the expected size of B is at least approximately (n−1)/2.The star fails to be an ε-box with probability at most ∆.Source: §3.5 · pp. 14–15
  • As ε and ∆ tend to zero, the constructed instances have expected makespan at least 1/2(1−c)·(n−1).This holds for small enough ε and sufficiently large parallel-task multiplicity ℓ.Source: §3.5 · pp. 15–16
  • For c = 1/4 or c = 1/3, every discrete universally truthful randomized mechanism has approximation ratio at least (n−1)/12.The bound follows by applying Yao’s principle to the deterministic lower bound over the constructed instance distribution.Source: §3.5 · p. 16

4 Upper Bound

Exp-Bounded-Square is universally truthful and achieves an expected approximation ratio asymptotically matching the (n + 1)/2 bound for fractional mechanisms. Its task-independent randomized assignments restrict each task to near-fastest machines and use exponential weights with quadratic processing times.

4 Upper Bound

  • Exp-Bounded-Square achieves an expected approximation ratio asymptotically matching the (n + 1)/2 bound for fractional mechanisms and the (n + 5)/2 bound for truthful-in-expectation mechanisms.The result improves on the previous best linear coefficient of 0.837n [24] and asymptotically matches the best possible bound for task-independent mechanisms.Source: §4 · p. 16

4.1 The Exp-Bounded-Square mechanism

  • For each task, the mechanism restricts assignment to machines whose processing times are within a factor of 2 of the minimum, then uses exponential random weights to choose among eligible machines.When the minimum processing time is zero, it assigns uniformly among eligible machines; otherwise it minimizes E_ij · (t_ij)^2, with independent E_ij ∼ Exp(1).Source: §4.1 · p. 17

4.2 Universal Truthfulness

  • Exp-Bounded-Square is universally truthful because, with each random draw fixed, lowering a machine’s reported time does not displace it from its task assignment.The proof establishes weak monotonicity for each task; task independence means reports for other tasks do not affect that allocation.Source: §4.2 · p. 18

4.3 Approximation

  • The approximation analysis bounds per-machine deviations above expected processing time, then applies a union bound to derive an expected-makespan guarantee.The bound is optimized by selecting q, yielding the corollary’s expected approximation guarantee.Source: §4.3 · pp. 19–21

A Adaptation of the Box Theorem of [11]

The appendix adapts the Box Theorem from [11] to deterministic weakly monotone allocations with an arbitrary fixed approximation upper bound K. The theorem’s box property supports the paper’s lower-bound argument.

A Adaptation of the Box Theorem of [11]

  • The adapted Box Theorem applies to deterministic weakly monotone allocations with a fixed approximation upper bound K, rather than requiring the bound to be below n.This generalization is needed for the randomized-mechanism lower bound.Source: A Adaptation of the Box Theorem of [11] · p. 23
  • In multi-stars with sufficiently high multiplicity, the probability that a random star is a box tends to 1 as multiplicity grows.A box is a star whose root allocation region is rectangular when the leaves’ values are fixed.Source: A Adaptation of the Box Theorem of [11] · p. 23
  • Figure 1 illustrates valid boxes when corner o lies inside the target allocation region and invalid ones when it lies outside.The examples show stars with two and three leaves.Source: Figure 1 · p. 24, A Adaptation of the Box Theorem of [11] · p. 24

A.1 Statement of the Box Theorem

The Box Theorem concerns multi-star instances with zero root values, leaf values in [ξ, 1], and equal edge multiplicity. Under its stated conditions, the probability that a random star is not a δ-box is bounded.

A.1 Statement of the Box Theorem

  • The multi-star has n nodes and ℓ parallel tasks per leaf; its edges encode tasks between the root and each leaf.Leaf values are restricted to [0, B), and the theorem considers values in (ξ, 1).Source: §A.1 · p. 24
  • A δ-box is a star for which setting each root value to its boundary value ψ_j(s_j) minus δ makes the mechanism allocate all its edges to the root.For a star with k leaves, δ = 4kν.Source: §A.1 · p. 25
  • For a multi-star satisfying the theorem’s conditions, the probability that a random star is not a δ-box is at most the theorem’s stated bound.The instance has zero root values, leaf values in [ξ, 1], equal multiplicity ℓ, and satisfies the continuity requirement.Source: §A.1 · p. 25

A.1.1 Intuition.

The proof uses induction on the number of leaves, with a separate treatment for two leaves. Its geometric argument relies on allocation regions and the characterization of two-player, two-task mechanisms.

A.1.1 Intuition.

  • The induction extends box structure from k − 1 leaves to k leaves by finding stars whose smaller sub-stars are boxes, then analyzing whether the larger star is a box or a chopped-off box.For affine-minimizer slices, linear boundaries move rectilinearly as a leaf value changes; the argument uses a stronger induction hypothesis to reach a contradiction.Source: §A.1.1 · pp. 25–26
  • The two-leaf case needs separate handling because a chopped-off one-dimensional interval is still an interval; a two-leaf, two-edge-per-leaf instance supplies a box.The proof exploits boundary linearity in two directions.Source: §A.1.1 · pp. 25–26

A.2 Further notation and preliminaries.

  • A slice mechanism fixes all task values except a selected pair, while a trivial leaf has root processing time zero for every task on that leaf.The appendix also defines standard instances by leaf-value and continuity conditions.Source: §A.2 · pp. 26–27

A.2.1 Region RP

  • For task set P, the allocation region R_P comprises root-value vectors where all tasks in P go to the root; weak monotonicity makes it a polyhedron.In two dimensions it is a rectangle or a rectangle with a −45° corner cut; boxes and chopped-off boxes are central shapes.Source: §A.2.1 · p. 27

A.2.2 Facts about two tasks.

For two tasks, the allocation is classified by how the regions for assigning both tasks to the root and neither task meet. The 2 × 2 characterization and observations distinguish task-independent mechanisms from relaxed affine minimizers through their boundary behavior.

A.2.2 Facts about two tasks.

  • Quasi-bundling means the both-task and neither-task regions share at least two boundary points, while quasi-flipping means they share none; a unique shared point is crossing.A nontrivial t1 + t2 = c facet exists exactly for quasi-bundling; half-bundling lacks a nontrivial t1 = c1 facet, and fully bundling is half-bundling at both tasks.Source: §A.2.2 · p. 28
  • The 2 × 2 characterization covers weakly monotone allocations with root values in [0, ∞)² and leaf values in [0, B)², provided each s admits root values assigning both tasks to the leaf.It classifies them as relaxed affine minimizers, relaxed task-independent mechanisms, 1-dimensional mechanisms, or constant mechanisms.Source: §A.2.2 · pp. 28–29
  • Relaxed task-independent allocations are crossing except at countably many points where both boundary functions have jump discontinuities; non-task-independent relaxed affine minimizers are non-crossing.The latter are always quasi-bundling or quasi-flipping for fixed (s1, s2).Source: §A.2.2 · p. 29
  • For relaxed affine minimizers, the slanted boundary has the same length for every sufficiently high s, may shorten as s1 or s2 decreases, and may be unbounded in degenerate cases.Such allocations are always quasi-bundling or always quasi-flipping.Source: §A.2.2 · p. 29
  • A relaxed affine minimizer’s boundary function ψ1[t2, s2](s1) is truncated linear unless the allocation is fully bundling, with a symmetric statement for ψ2.Source: §A.2.2 · p. 29
  • Relaxed task-independent mechanisms can have discontinuities, but the instances considered satisfy continuity; with bundling or flipping boundaries and three or four regions, boundary functions are affine.Source: §A.2.2 · p. 29

A.3 Proof of the main Box Theorem 5

The proof of the Box Theorem uses induction on the number of leaves, showing that a uniformly selected random star is a box with probability approaching one as task multiplicity grows.

A.3 Proof of the main Box Theorem 5

  • As multiplicity ℓ grows, the probability that a uniformly and independently selected random star of n − 1 leaves is a box approaches one.The proof inducts on k, the number of leaves, using a recurrence for the failure-probability bounds b_k.Source: §A.3 · p. 29
  • For the induction base case k = 2, the failure-probability bound is b2 ≤ 2/ℓ.Source: §A.3 · p. 29
  • Lemma 21, based on the proof of the inductive hypothesis, establishes a recurrence.Source: §A.3 · p. 29

A.3.1 Preliminary observations

For standard instances, bounded approximation ratio constrains the allocation of sibling tasks: their slice mechanism must be crossing. Quasi-bundling or quasi-flipping in such a slice instead implies infinite approximation ratio.

A.3.1 Preliminary observations

  • For a bounded-ratio mechanism on a standard instance, a task’s boundary value ψp[t−p, s̄−p](sp) is independent of its siblings’ running-time values.The continuity requirement removes discontinuities in the relaxed task-independent slice mechanism.Source: §A.3.1 · p. 30
  • The bounded-ratio conclusion applies to the whole mechanism because all other tasks are trivial in a standard instance.Source: §A.3.1 · p. 30
  • A sibling-task slice with quasi-bundling or quasi-flipping gives the mechanism infinite approximation ratio on a standard instance.The proof derives this by considering the relaxed affine minimizer cases and small leaf values.Source: §A.3.1 · p. 30

A.4 Base case

The base case establishes boxes for two leaves, first for every instance with two tasks per leaf and then probabilistically for a random two-leaf star.

A.4 Base case

  • Every standard instance with 2 leaves and 2 tasks per leaf contains a box of 2 leaves.For this two-leaf base case, multiplicity 2 is sufficient.Source: §A.4 · pp. 30–31
  • For a bounded-ratio mechanism, Theorem 9 bounds the probability that a random star of two leaves is not a box.The supplied passage does not state the bound’s complete value.Source: §A.4 · p. 31

A.5 Induction step

The induction step analyzes how a star whose smaller subsets are boxes can fail to be a box. It uses a two-player, two-task slice characterization to show such failures are uncommon among sibling replacements.

A.5 Induction step

  • A chopped-off box has every one-task-deleted subset as a box, plus additional box conditions after specified changes to one task’s values.It is strictly chopped off when it is not itself a box.Source: §A.5 · p. 31
  • Geometrically, a chopped-off box corresponds to an allocation region that is box-shaped except for a possibly empty simplex removed by a diagonal cut.Source: §A.5 · p. 31
  • The proof examines the two-player, two-task slice mechanism using input points around the allocation region and concludes that a chopped-off box is unlikely to remain non-box under sibling replacement.The section’s main result is that the probability a chopped-off box is not a box is small.Source: §A.5 · p. 31

A.5.1 General observations.

This section examines how strictly chopped-off boxes and slice allocations constrain possible mechanism behaviors, distinguishing crossing allocations from restricted non-crossing cases. It also shows that a low approximation ratio limits how many siblings can have a half-bundling slice at a given input, using a makespan lower bound against an optimum of at most 1.

General observations

  • For a strictly chopped-off box P and an instance T′ between Tν and Tν′ coordinate-wise, the point t′P obeys every linear constraint defining region R_T^P except one violated nonredundant bundling-boundary-facet constraint.Source: §A.5.1 · p. 32

Bundling-boundary behavior

  • Critical values along the bundling boundary satisfy the Lipschitz bound with equality, and equality implies intermediate inputs remain on that boundary.The associated proposition and corollary specify that inputs just below the critical value allocate all box tasks to the root, while inputs just above allocate them to the leaves.Source: §A.5.1 · p. 32

The case of non-crossing allocations

  • The analysis also bounds the number of siblings for which a slice mechanism can be a relaxed-affine minimizer [11].The section frames this as part of the non-task-independent case, after excluding almost surely affine minimizers and constant mechanisms.Source: §A.5.1 · p. 33

Task-independent (crossing) allocations

  • If a slice allocation is crossing at two distinct instances, the corresponding task set (P−k, p′k) must be a box.The crossing condition is for the root allocation in the (pk, p′k)-slice mechanism.Source: §A.5.1 · p. 33

The case of non-crossing allocations

  • For the root, non-crossing allocations of 2 × 2 mechanisms occur in the linear part (as a function of spk) of relaxed affine minimizers, or are half-bundling at pk, including completely bundling; linear boundary functions are excluded almost surely.Source: §A.5.1 · p. 33

A.5.1 General observations.

  • For p′_k ∈ Q_k of p_k, the 2 × 2 slice mechanism (p_k, p′_k) in T̂ is half-bundling at p_k.Source: §A.5.1 · p. 36
  • If at least K/ξ siblings were half-bundled, a point just above the critical boundary would assign their tasks to the same leaf, costing at least ξ per task.This would give the mechanism a makespan of at least K.Source: §A.5.1 · p. 36
  • The optimum is at most 1 because tasks outside P are trivial and the largest processing time in P is at most 1, contradicting an approximation ratio below K.Source: §A.5.1 · p. 36

A.5.3 The main inductive lemma.

The main inductive lemma bounds how often a strictly chopped-off star remains non-box after replacing one task with a sibling. Its proof rules out several slice-mechanism possibilities and establishes box structure for most sibling replacements.

A.5.3 The main inductive lemma.

  • The argument constructs instances in a prescribed relative position and uses a union bound to control the number of problematic siblings.Source: §A.5.3 · pp. 36–37
  • At least ℓ−2nK/ξ siblings avoid half-bundling boundaries across the fixed instances, and the lemma concludes that sibling replacements are boxes.Source: §A.5.3 · pp. 36–37
  • The slice analysis excludes relaxed affine minimizers, constant mechanisms, one-dimensional bundling, and discontinuities, leaving crossing allocations in the two examined instances.Source: §A.5.3 · p. 37

A.6 Many boxes of size n −1.

The appendix uses the inductive bounds to show that, with sufficiently high edge multiplicity, a random star of size n−1 is a box with arbitrarily high probability. It also specifies payments for Exp-Bounded-Square and bounds cross-machine load contributions.

A.6 Many boxes of size n −1.

  • For a standard instance and a random star of k tasks, the probability it is not a chopped-off box is at most (5K/ν −1)bk−1.The proof applies a union bound to failures of the smaller-subset box conditions and the specified task-value modifications.Source: §A.6 · p. 37
  • With sufficiently high edge multiplicity, a random star of size n−1 is a box with arbitrarily high probability.The section reaches this conclusion by induction on star size.Source: §A.6 · pp. 37–38

B.1 Payment Scheme

  • For Exp-Bounded-Square, the allocated machine receives a task payment equal to the maximum processing time it could report while retaining that task.The other machines receive zero for that task, and the summed payments form a universally truthful payment scheme.Source: §B.1 · p. 39

B.2 Bounding the Expected Load of Each Machine

  • For every machine s distinct from i and every task j assigned to s in the optimal allocation, x_ijt_ij ≤ t_sj.Source: §B.2 · p. 39
Loading 2609.12621v1…