**Monday, 15:15 - 15:40 h, Room: H 3004**

**Marc Uetz**

Mechanism design for single machine scheduling by ILP

**Coauthors: Jelle Duives, Ruben Hoeksma**

**Abstract:**

We consider the classical single machine scheduling problem to minimize total weighted completion times *∑ w*_{j}C_{j}. The problem is easily solved in polynomial time, but here we assume that data is private information to the jobs. This gives rise to a situation where jobs may strategize by misreporting their private data. In order to do optimization in such a setting, also incentive constraints have to be taken into account. Since Myerson's seminal work on optimal auction design, it is well known how such mechanism design problems can be solved when private data is single-dimensional, but not much is known for multi-dimensional mechanism design problems, neither in general nor for the scheduling problem at hand. In the spirit of what is called automated mechanism design, we use integer linear programming models to find optimal scheduling mechanisms for the 2-dimensional mechanism design problem. So far, this approach is prohibitive for all but toy problems, yet it allows to generate and test hypotheses. This way, we gain new insights into optimal mechanisms for the scheduling problem at hand.

Talk 1 of the invited session Mon.3.H 3004

**"Interactions between optimization and game theory in scheduling"** [...]

Cluster 2

**"Combinatorial optimization"** [...]