TY - JOUR
T1 - A selfish allocation heuristic in scheduling
T2 - equilibrium and inefficiency bound analysis
AU - Braat, Jac
AU - Hamers, Herbert
AU - Klijn, Flip
AU - Slikker, Marco
PY - 2019/3/1
Y1 - 2019/3/1
N2 - For single decision maker optimization problems that lack time efficient algorithms to determine the optimum, there is a need for heuristics. In the context of coordinated production planning, the seminal paper of Graham (1969) provided a performance analysis of heuristics and obtained a bound in relation to the centralized optimum. This paper introduces a framework that includes a performance analysis of a so-called equilibrium heuristic in the setting of multiple decision maker problems. The framework consists of three steps: a heuristic for each player that leads to a strategy profile, the verification that this strategy profile is a Nash equilibrium, and finally a worst case cost analysis to obtain a bound on the performance of the heuristic in terms of the aggregate cost in the obtained Nash equilibrium in relation to the centralized optimum. We implement our general framework in a setting of sequencing situations with selfish agents, multiple identical machines, and the sum of completion times as cost criterion. We provide a tight upper bound for the performance of our equilibrium heuristic. Simulations show that the equilibrium heuristic generally performs much better than the derived tight upper bound. Finally, the relation with the price of anarchy is discussed.
AB - For single decision maker optimization problems that lack time efficient algorithms to determine the optimum, there is a need for heuristics. In the context of coordinated production planning, the seminal paper of Graham (1969) provided a performance analysis of heuristics and obtained a bound in relation to the centralized optimum. This paper introduces a framework that includes a performance analysis of a so-called equilibrium heuristic in the setting of multiple decision maker problems. The framework consists of three steps: a heuristic for each player that leads to a strategy profile, the verification that this strategy profile is a Nash equilibrium, and finally a worst case cost analysis to obtain a bound on the performance of the heuristic in terms of the aggregate cost in the obtained Nash equilibrium in relation to the centralized optimum. We implement our general framework in a setting of sequencing situations with selfish agents, multiple identical machines, and the sum of completion times as cost criterion. We provide a tight upper bound for the performance of our equilibrium heuristic. Simulations show that the equilibrium heuristic generally performs much better than the derived tight upper bound. Finally, the relation with the price of anarchy is discussed.
KW - Equilibrium
KW - Game theory
KW - Heuristic
KW - Outsourcing
KW - Sequencing situations
UR - http://www.scopus.com/inward/record.url?scp=85052985830&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2018.08.024
DO - 10.1016/j.ejor.2018.08.024
M3 - Article
AN - SCOPUS:85052985830
SN - 0377-2217
VL - 273
SP - 634
EP - 645
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 2
ER -