4 papers
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…
On the Complexity of the Minimum-()-Shortcut Problem
Tatiana Rocha Avila, Julian Christoph Brinkmann, Alexander Leonhardt +1
We consider the Minimum-- problem (), where the goal is to find the smallest set of shortcut edges such that every ver…
Designing Exploration Contracts
Martin Hoefer, Conrad Schecker, Kevin Schewior
We study a natural application of contract design in the context of sequential exploration problems. In our principal-agent setting, a search task is delegated to an agent. The age…
Delegated Online Search
Pirmin Braun, Niklas Hahn, Martin Hoefer +1
In a delegation problem, a principal P with commitment power tries to pick one out of options. Each option is drawn independently from a known distribution. Instead of inspecti…