Metraipolis › archive › dc_10ed286eb673

Sharp Bounds for Truthful-in-Expectation Scheduling — arXiv:2611.05134

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.05134
License (as archived): CC0-1.0
Archived: 2026-11-04T21:46:24.439Z
SHA-256 of the archived text: 2d1bb1a9fcfca863ce09c76545fd4a59fd254d5a9b21d127c69f6139574cc62f
Stable URL of this page: https://metraipolis.com/documento/dc_10ed286eb673

How to cite

Sharp Bounds for Truthful-in-Expectation Scheduling — arXiv:2611.05134 — arXiv (en), https://arxiv.org/abs/2611.05134 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_10ed286eb673 (Metraipolis archive dc_10ed286eb673, sha256 2d1bb1a9fcfca863ce09c76545fd4a59fd254d5a9b21d127c69f6139574cc62f)

BibTeX

@misc{dc10ed286eb673,
  title = {Sharp Bounds for Truthful-in-Expectation Scheduling — arXiv:2611.05134},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05134},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_10ed286eb673; sha256 2d1bb1a9fcfca863ce09c76545fd4a59fd254d5a9b21d127c69f6139574cc62f},
  year = {2026}
}

Archived text

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

We study randomized mechanisms for scheduling indivisible jobs on $n$ unrelated machines. Each machine is controlled by a selfish agent who privately knows its processing time for each job. A mechanism assigns every job to a machine and makes payments. We require truthfulness in expectation: no agent can increase its expected payment minus its expected processing cost by misreporting, regardless of the other agents' reports. The makespan is the maximum total processing time assigned to a machine; the objective is to minimize its expectation. We prove that the optimal approximation ratio is $(n+1)/2$ for every $n\ge7$, relative to the minimum makespan of an integral assignment. The lower bound holds for every $n$ and allows unrestricted computation and arbitrary correlations among assignments, assuming finite expected payments and a guarantee uniform over all finite job counts. The matching mechanism uses correlated rounding and runs in expected polynomial bit time on rational inputs. These guarantees hold for all finite nonnegative processing times. For two machines, we characterize the optimal approximation ratio exactly as an analytic constant, approximately $1.505995705434$, and give a mechanism attaining it. For three machines the optimal ratio is $2$. For four, five, and six machines we obtain upper bounds of $3$, $105/32$, and $29/8$, respectively, compared with the general lower bound $(n+1)/2$. The proofs for $n\ge7$ do not rely on computer-assisted certificates; the two- and three-machine results use exact rational computer-assisted certificates.

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.05134 — 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-04T21:37:19.379Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).