Metraipolis › archive › dc_6010dfd105ec

Universally truthful mechanisms for scheduling — arXiv:2609.12621

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.12621
License (as archived): CC0-1.0
Archived: 2026-10-16T03:09:03.577Z
SHA-256 of the archived text: 9370e45ef63c30a29fc3c87e5b68f51c500991be9ce6253034d6b1d03bee3568
Stable URL of this page: https://metraipolis.com/documento/dc_6010dfd105ec

How to cite

Universally truthful mechanisms for scheduling — arXiv:2609.12621 — arXiv (en), https://arxiv.org/abs/2609.12621 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6010dfd105ec (Metraipolis archive dc_6010dfd105ec, sha256 9370e45ef63c30a29fc3c87e5b68f51c500991be9ce6253034d6b1d03bee3568)

BibTeX

@misc{dc6010dfd105ec,
  title = {Universally truthful mechanisms for scheduling — arXiv:2609.12621},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.12621},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6010dfd105ec; sha256 9370e45ef63c30a29fc3c87e5b68f51c500991be9ce6253034d6b1d03bee3568},
  year = {2026}
}

Archived text

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

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

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-14 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.12621 — 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-10-16T03:04:07.412Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).