An optimal lower bound for anonymous scheduling mechanisms

Itai Ashlagi A · Shahar Dobzinski · Ron Lavi

30 citations0/0 files storedACM Conference on Electronic Commerce (EC)

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Auction Theory and Applications Complexity and Algorithms in Graphs Game Theory and Voting Systems

Abstract

We consider the problem of designing truthful mechanisms to minimize the makespan on m unrelated machines. In their seminal paper, Nisan and Ronen [14] showed a lower bound of 2, and an upper bound of m, thus leaving a large gap. They conjectured that their upper bound is tight, but were unable to prove it. Despite many attempts that yield positive results for several special cases, the conjecture is far from being solved: the lower bound was only recently slightly increased to 2.61 [5,10], while the best upper bound remained unchanged.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 30 citations exist upstream.

References

2001Algorithmic Mechanism Design 2001Truthful mechanisms for one-parameter agents 1999Algorithmic mechanism design (extended abstract)2004Towards a characterization of truthful combinatorial auctions 2006Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation 2005Weak monotonicity suffices for truthfulness on convex domains 2012A Lower Bound of 1+φ for Truthful Scheduling Mechanisms 2007Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.