Invited Session Mon.3.H 3004

Monday, 15:15 - 16:45 h, Room: H 3004

Cluster 2: Combinatorial optimization [...]

Interactions between optimization and game theory in scheduling


Chair: Neil Olver



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

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.



Monday, 15:45 - 16:10 h, Room: H 3004, Talk 2

Ruben Hoeksma
Price of anarchy for minsum related machine scheduling

Coauthor: Marc Uetz


We consider related machine scheduling to minimize the total completion time ∑ Cj. This problem is well known to be solved in polynomial time by a classical algorithm of Horowitz and Sahni. Instead of the centralized optimal solution, however, we are interested in the situation where each job individually chooses the machine on which it is processed. We analyze the quality of the resulting Nash equilibria in relation to the objective value in the optimal solution, also known as the price of anarchy. Complementing recent results by Cole et al. on the unrelated machine problem where the price of anarchy equals exactly 4, we show that the local SPT rule results in a price of anarchy between e/(e-1) and 2. To obtain the upper bound of 2, we use a smoothness argument in the flavor of recent work of Roughgarden, blended with a new characterization of the structure of optimal solutions.



Monday, 16:15 - 16:40 h, Room: H 3004, Talk 3

Neil Olver
Approximation algorithms for scheduling via coordination mechanisms

Coauthors: Richard Cole, Jose R. Correa, Vasilis Gkatzelis, Vahab Mirrokni


We investigate the problem of scheduling on multiple unrelated machines, where the goal is to minimize the weighted sum of completion times. We primarily consider the game-theoretic version of the problem, where each job is an agent aiming to minimize its own completion time. However, as one outcome of our work we obtain the first combinatorial constant factor approximation algorithm for the NP-hard optimization problem.
We consider a number of different policies; rules specifying the scheduling on a machine for a given assignment. The most obvious choice is Smith's rule; for a given assignment of jobs to machines, this yields the optimal schedule. However, we show that other policies that give a suboptimal scheduling actually have much better equilibrium schedules, due to better incentives. By finding an approximate Nash equilibrium for one such policy via local search, we obtain a factor 2+ε approximation algorithm.
These results are obtained by the application of a common technique: a mapping of the strategy vectors into a carefully chosen inner product space. Once this structure is in place, the proofs are relatively short and elegant.


  personal loan . But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra No RX influence on blood clots.