Result: On the structure and complexity of worst-case equilibria

Title:
On the structure and complexity of worst-case equilibria
Authors:
FISCHER, Simon, VÖCKING, Berthold
Source:
Internet and Network EconomicsTheoretical computer science. 378(2):165-174
Publisher Information:
Amsterdam: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 11 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Divers, Miscellaneous, Logiciel, Software, Performances des systèmes informatiques. Fiabilité, Computer systems performance. Reliability, Addition, Adicción, Algorithme, Algorithm, Algoritmo, Allocation ressource, Resource allocation, Asignación recurso, Calcul automatique, Computing, Cálculo automático, Complexité, Complexity, Complejidad, Coût, Costs, Coste, Equilibrage charge, Load balancing, Equilibrio de carga, Equilibre, Equilibrium, Equilibrio, Informatique théorique, Computer theory, Informática teórica, Maximum, Máximo, Ordonnancement, Scheduling, Reglamento, Ressource, Resource, Recurso, Validité, Validity, Validez, 68M20, 68Wxx, Pire cas, Balls and bins processes, Fully mixed Nash equilibrium, Job scheduling, Price of Anarchy
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
RWTH Aachen, Computer Science 1, 52056 Aachen, Germany
ISSN:
0304-3975
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18799220
Rights:
Copyright 2008 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.18799220
Database:
PASCAL Archive

Further Information

In the resource allocation game introduced by Koutsoupias and Papadimitriou, n jobs of different weights are assigned to m identical machines by selfish agents. For this game, it has been conjectured by several authors that the fully mixed Nash equilibrium (FMNE) is the worst possible w.r.t. the expected maximum load over all machines. Assuming the validity of this conjecture, computing a worst-case Nash equilibrium for a given instance was trivial, and approximating the Price of Anarchy for this instance would be possible by approximating the expected social cost of the FMNE by applying a known FPRAS. We present a counter-example to this conjecture showing that fully mixed Nash equilibria cannot be used to approximate the Price of Anarchy. We show that the factor between the social cost of the worst Nash equilibrium and the social cost of the FMNE can be as large as the Price of Anarchy itself, up to a constant factor. In addition, we present an algorithm that constructs so-called concentrated equilibria that approximate the worst-case Nash equilibria within constant factors.