Selfish Bin Coloring

  • We introduce a new game, the so-called bin coloring game, in which selfish players control colored items and each player aims at packing its item into a bin with as few different colors as possible. We establish the existence of Nash and strong as well as weakly and strictly Pareto optimal equilibria in these games in the cases of capacitated and uncapacitated bins. For both kinds of games we determine the prices of anarchy and stability concerning those four equilibrium concepts. Furthermore, we show that extreme Nash equilibria, those with minimal or maximal number of colors in a bin, can be found in time polynomial in the number of items for the uncapcitated case.

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Leah Epstein, Sven O. Krumke, Asaf Levin, Heike Sperber
URN (Permalink):urn:nbn:de:hbz:386-kluedo-16242
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (123)
Dokumentart:Bericht
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:2009
Jahr der Veröffentlichung:2009
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):16.10.2009
Freies Schlagwort / Tag:Nash equilibria; algorithmic game theory; bin coloring; price of anarchy; price of stability; strong equilibria; weakly/ strictly pareto optima
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011

$Rev: 13581 $