2 papers
cs.GT2026
Universally truthful mechanisms for scheduling
Georgios Anastasiadis, George Christodoulou, Elias Koutsoupias +2
We consider universally truthful randomized mechanisms for the problem of scheduling jobs on unrelated machines. We prove a lower bound on the expected approximation ratio…
cs.CC2025
Complexity of Unambiguous Problems in
Matan Gilboa, Paul W. Goldberg, Elias Koutsoupias +1
Various practical problems within the class possess an unambiguity property, meaning that yes-instances correspond with a unique witness. The semantic class containing al…