Metraipolis › archive › dc_daee2e95bd90

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

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.05142
License (as archived): CC0-1.0
Archived: 2026-11-04T18:48:28.658Z
SHA-256 of the archived text: 6d6c9d1949606c9fef9e51ff1f8d9068b78e55c5782a45544da20d028d25cfc5
Stable URL of this page: https://metraipolis.com/documento/dc_daee2e95bd90

How to cite

Tight Analysis of Randomized Truthful Scheduling: An $(m+1)/2$ Lower Bound — arXiv:2611.05142 — arXiv (en), https://arxiv.org/abs/2611.05142 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_daee2e95bd90 (Metraipolis archive dc_daee2e95bd90, sha256 6d6c9d1949606c9fef9e51ff1f8d9068b78e55c5782a45544da20d028d25cfc5)

BibTeX

@misc{dcdaee2e95bd90,
  title = {Tight Analysis of Randomized Truthful Scheduling: An $(m+1)/2$ Lower Bound — arXiv:2611.05142},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05142},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_daee2e95bd90; sha256 6d6c9d1949606c9fef9e51ff1f8d9068b78e55c5782a45544da20d028d25cfc5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05142. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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+\Theta(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.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2611.05142 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:34:07.174Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).