Nonpreemptive coordination mechanisms for identical machines (Q372964)

Suppose we are given \(m\) parallel machines with the same speed. Also assume that we have \(n\) weighted tasks. A game of scheduling the tasks on the machines is a pair \((c,w)\), where \(c\) is called a coordination mechanism, and it represents a set of \(m\) local scheduling policies, and \(w\) is the vector of task weights. The scheduling policy of the \(j\)th machine observes the tasks that are assigned to it and decided their completion time. In the paper, a game is considered such that every task has the set of machines (\(\{1,\dots,m\}\)) as the set of pure strategies. The set of mixed strategies represent the set of probability distributions over the set of pure strategies. Let \(p_{i,j}\) be the probability that task \(i\) is assigned to machine \(j\). Then the matrix \(p=\{p_{i,j}\}\) will be the outcome of the game. Observe that \(p\) has \(n\) rows and \(m\) columns. Suppose that \((c,w)\) is a game, and \(p\) is an outcome. Let \(t_{i,j}(c, w, p_{-i})\) be the expected completion time of the \(i\)th task, if \(i\) plays purely machine \(j\) and all other tasks play as in \(p\). Then the outcome \(p\) will be called a Nash equilibrium in the game \((c,w)\) if and only if for all pairs of \(i, j\) holds: if \(p_{i,j}>0\), then \(t_{i,j}(c, w, p_{-i})\leq t_{i,k}(c, w, p_{-i})\) for all choices of \(k\). Roughly speaking this means that the task assigns a positive probability to the machine only when it minimizes the expected completion time of the task. Observe that a task cannot improve its completion time by selecting a different probability distribution in \(p\). Let \(s(c,w,p)\) be the expected makespan of the outcome \(p\) in the game \((c,w)\), that is, the expected maximum among the task completion times. Then the price of anarchy of a coordination mechanism \(c\) will be the worst case ratio of the expected makespan in a Nash equilibrium to the optimal makespan (denoted by \(\mathrm{opt}(w,m)\)), for all possible choices of the task weights \(w\), that is \[ \mathrm{Po}A(c)=\max_{w} \max_{\mathrm{Nash }p}\frac{s(c,w,p)}{opt(w,m)}. \] In the paper, the price of anarchy of nonpreemptive coordination mechanisms is investigated when \(m\geq 2\). Recall that a policy is called to be nonpreemptive if tasks are not delayed or interrupted while they are being processed, and coordination mechanisms are called to be nonpreemptive, if all policies are nonpreemptive. The main contributions of the paper are the following results: {\parindent=6mm \begin{itemize}\item[1.] Every nonpreemptive coordination mechanism has a price of anarchy of value greater than \(\frac{3}{2}\), when \(m>2\). \item[2.] Every nonpreemptive coordination mechanism has a price of anarchy of value \(\Omega(\frac{\log \log (m)}{\log \log \log (m)})\) for \(m\) machines. \item[3.] Every nonpreemptive coordination mechanism has a price of anarchy of value at least \(\frac{7}{6}\), when \(m=2\). \end{itemize}} The starting point for the author is a model of interaction among some agents, which are supposed to share computational and communication resources. Each of the agents is assumed to have his/her own interests, and the process of interaction between them is considered as a game. It is assumed that agents are rational players and their goal is to minimize some defined personal cost. While playing the game, the players are expected to reach a situation where each of them is not willing to change its own position. Clearly, such stages remind us probably the most famous concept in game theory, which is that of Nash equilibrium. The performance of the agents, and the system, in general, is measured by a social cost, and since Nash equilibriums do not necessarily need to be the optimal behavior of the system, this inefficiency is measured by the price of anarchy. In the paper the author is interested in measuring the price of anarchy of the system. The paper is well-written. It does not contain any apparent mistakes. The discussion on the related work is reasonable. It is presented in a special section. The proofs given in the paper are correct. There is a limited originality in the paper. The results are derived via standard methods. The results of the paper are derived via a clever application of standard methods. Moreover, the contributions of the author are contrasted to the previous known results, which makes it easier to see the progress that is made by the author.