English   español  
Por favor, use este identificador para citar o enlazar a este item: http://hdl.handle.net/10261/173859
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:

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

AutorBraat, Jac; Hamers, Herbert; Klijn, Flip ; Slikker, Marco
Palabras claveGame theory
Sequencing situations
Fecha de publicación1-mar-2019
CitaciónEuropean Journal of Operational Research 273(2): 634-645 (2019)
ResumenFor 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.
Versión del editorhttps://doi.org/10.1016/j.ejor.2018.08.024
Aparece en las colecciones: (IAE) Artículos
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
Klijn_selfish_allocation.pdf Embargado hasta 1 de marzo de 2021683,25 kBAdobe PDFVista previa
Visualizar/Abrir     Petición de una copia
Mostrar el registro completo

NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.