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


Marc Uetz
Mechanism design for single machine scheduling by ILP

Coauthors: Jelle Duives, Ruben Hoeksma


We consider the classical single machine scheduling problem to minimize total weighted completion times ∑ wjCj. 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" [...]


  cash advance . Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.