A lower bound for scheduling mechanisms

George Christodoulou · Elias Koutsoupias · Angelina Vidali

55 citations0/0 files storedMax Planck Institute for Plasma Physics

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

Game Theory and Voting Systems Game Theory and Applications Auction Theory and Applications

Abstract

We study the mechanism design problem of scheduling tasks on n unrelated machines in which the machines are the players of the mechanism. The problem was proposed and studied in the seminal paper of Nisan and Ronen, where it was shown that the approximation ratio of mechanisms is between 2 and n. We improve the lower bound to 1 + √2 for 3 or more machines.

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 — 55 citations exist upstream.

References

1981Optimal Auction Design 2001Algorithmic Mechanism Design 2001Truthful mechanisms for one-parameter agents 1999Algorithmic mechanism design (extended abstract)2004Towards a characterization of truthful combinatorial auctions 2003Incentive compatible multi unit combinatorial auctions 2006Truthful randomized mechanisms for combinatorial auctions 2005Weak monotonicity suffices for truthfulness on convex domains

Cited by

2008A Lower Bound for Scheduling Mechanisms 2009On 2-Player Randomized Mechanisms for Scheduling

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.