A selfish allocation heuristic in scheduling: equilibrium and inefficiency bound analysis

Jac Braat, Herbert Hamers, Flip Klijn, Marco Slikker

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

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.

LanguageEnglish
Pages634-645
Number of pages12
JournalEuropean Journal of Operational Research
Volume273
Issue number2
DOIs
StatePublished - 1 Mar 2019

Fingerprint

Scheduling
Heuristics
Costs
Decision problem
Nash Equilibrium
Performance Analysis
Planning
Upper bound
Price of Anarchy
Worst-case Analysis
Cost Analysis
Production Planning
Completion Time
Inefficiency
Sequencing
Efficient Algorithms
Optimization Problem
Framework
Simulation
Profile

Keywords

  • Equilibrium
  • Game theory
  • Heuristic
  • Outsourcing
  • Sequencing situations

Cite this

@article{30ae22917bdf4565a47606dd555e978d,
title = "A selfish allocation heuristic in scheduling: equilibrium and inefficiency bound analysis",
abstract = "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.",
keywords = "Equilibrium, Game theory, Heuristic, Outsourcing, Sequencing situations",
author = "Jac Braat and Herbert Hamers and Flip Klijn and Marco Slikker",
year = "2019",
month = "3",
day = "1",
doi = "10.1016/j.ejor.2018.08.024",
language = "English",
volume = "273",
pages = "634--645",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "2",

}

A selfish allocation heuristic in scheduling : equilibrium and inefficiency bound analysis. / Braat, Jac; Hamers, Herbert; Klijn, Flip; Slikker, Marco.

In: European Journal of Operational Research, Vol. 273, No. 2, 01.03.2019, p. 634-645.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - A selfish allocation heuristic in scheduling

T2 - European Journal of Operational Research

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

VL - 273

SP - 634

EP - 645

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -