Truthful Graph Balancing

11^th March 2020, 13:00
Giorgos Christodoulou
University of Liverpool

Abstract

We study truthful mechanisms for the Unrelated Graph Balancing problem. This is the special case of the well-studied unrelated machines scheduling problem, in which every given task can be executed only by two pre-specified machines. This corresponds to a multigraph whose nodes are the machines and its edges are the tasks. We provide upper and lower bounds for incentive compatible
mechanisms for general multigraphs, as well as special classes of graphs such as stars, trees, planar graphs, k-degenerate graphs, and graphs of a given treewidth.