IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v22y2011i4d10.1007_s10878-010-9302-1.html
   My bibliography  Save this article

Selfish bin coloring

Author

Listed:
  • Leah Epstein

    (University of Haifa)

  • Sven O. Krumke

    (University of Kaiserslautern)

  • Asaf Levin

    (The Technion)

  • Heike Sperber

    (University of Kaiserslautern)

Abstract

The bin packing problem, a classical problem in combinatorial optimization, has recently been studied from the viewpoint of algorithmic game theory. In this bin packing game each item is controlled by a selfish player minimizing its personal cost, which in this context is defined as the relative contribution of the size of the item to the total load in the bin. We introduce a related game, the so-called bin coloring game, in which players control colored items and each player aims at packing its item into a bin with as few different colors as possible. We establish 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, representatives of the set of Nash equilibria with minimal or maximal number of colors in a bin, can be found in time polynomial in the number of items for the uncapacitated case.

Suggested Citation

  • Leah Epstein & Sven O. Krumke & Asaf Levin & Heike Sperber, 2011. "Selfish bin coloring," Journal of Combinatorial Optimization, Springer, vol. 22(4), pages 531-548, November.
    • Handle: RePEc:spr:jcomop:v:22:y:2011:i:4:d:10.1007_s10878-010-9302-1
    DOI: 10.1007/s10878-010-9302-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-010-9302-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-010-9302-1?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Epstein, Amir & Feldman, Michal & Mansour, Yishay, 2009. "Efficient graph topologies in network routing games," Games and Economic Behavior, Elsevier, vol. 66(1), pages 115-125, May.
    2. Andelman, Nir & Feldman, Michal & Mansour, Yishay, 2009. "Strong price of anarchy," Games and Economic Behavior, Elsevier, vol. 65(2), pages 289-317, March.
    3. Mas-Colell, Andreu & Whinston, Michael D. & Green, Jerry R., 1995. "Microeconomic Theory," OUP Catalogue, Oxford University Press, number 9780195102680.
    4. Mingen Lin & Zhiyong Lin & Jinhui Xu, 2008. "Almost optimal solutions for bin coloring problems," Journal of Combinatorial Optimization, Springer, vol. 16(1), pages 16-27, July.
    5. Holzman, Ron & Law-Yone, Nissan, 1997. "Strong Equilibrium in Congestion Games," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 85-101, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Vittorio Bilò & Francesco Cellinese & Giovanna Melideo & Gianpiero Monaco, 2020. "Selfish colorful bin packing games," Journal of Combinatorial Optimization, Springer, vol. 40(3), pages 610-635, October.
    2. Vittorio Bilò & Francesco Cellinese & Giovanna Melideo & Gianpiero Monaco, 0. "Selfish colorful bin packing games," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-26.
    3. Anna Angelucci & Vittorio Bilò & Michele Flammini & Luca Moscardelli, 2015. "On the sequential price of anarchy of isolation games," Journal of Combinatorial Optimization, Springer, vol. 29(1), pages 165-181, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Tobias Harks & Max Klimm & Rolf Möhring, 2013. "Strong equilibria in games with the lexicographical improvement property," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(2), pages 461-482, May.
    2. Xujin Chen & Zhuo Diao & Xiaodong Hu, 2022. "On weak Pareto optimality of nonatomic routing networks," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 1705-1723, October.
    3. Le Breton, Michel & Shapoval, Alexander & Weber, Shlomo, 2021. "A game-theoretical model of the landscape theory," Journal of Mathematical Economics, Elsevier, vol. 92(C), pages 41-46.
    4. György Dósa & Leah Epstein, 2019. "Pareto optimal equilibria for selfish bin packing with uniform cost sharing," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 827-847, April.
    5. Xujin Chen & Zhuo Diao & Xiaodong Hu, 0. "On weak Pareto optimality of nonatomic routing networks," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-19.
    6. Krzysztof R. Apt & Bart Keijzer & Mona Rahn & Guido Schäfer & Sunil Simon, 2017. "Coordination games on graphs," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(3), pages 851-877, August.
    7. György Dósa & Leah Epstein, 2019. "Quality of strong equilibria for selfish bin packing with uniform cost sharing," Journal of Scheduling, Springer, vol. 22(4), pages 473-485, August.
    8. Igal Milchtaich, 2021. "Internalization of social cost in congestion games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 71(2), pages 717-760, March.
    9. Satoru Fujishige & Michel X. Goemans & Tobias Harks & Britta Peis & Rico Zenklusen, 2017. "Matroids Are Immune to Braess’ Paradox," Mathematics of Operations Research, INFORMS, vol. 42(3), pages 745-761, August.
    10. Wright, Austin L. & Sonin, Konstantin & Driscoll, Jesse & Wilson, Jarnickae, 2020. "Poverty and economic dislocation reduce compliance with COVID-19 shelter-in-place protocols," Journal of Economic Behavior & Organization, Elsevier, vol. 180(C), pages 544-554.
    11. Jolian McHardy & Michael Reynolds & Stephen Trotter, 2012. "The Stackelberg Model as a Partial Solution to the Problem of Pricing in a Network," Working Paper series 19_12, Rimini Centre for Economic Analysis.
    12. Janvier D. Nkurunziza, 2005. "Reputation and Credit without Collateral in Africa`s Formal Banking," Economics Series Working Papers WPS/2005-02, University of Oxford, Department of Economics.
    13. Stephanie Rosenkranz & Patrick W. Schmitz, 2007. "Can Coasean Bargaining Justify Pigouvian Taxation?," Economica, London School of Economics and Political Science, vol. 74(296), pages 573-585, November.
    14. Vadim Borokhov, 2014. "On the properties of nodal price response matrix in electricity markets," Papers 1404.3678, arXiv.org, revised Jan 2015.
    15. Daniel Sutter & Daniel J. Smith, 2017. "Coordination in disaster: Nonprice learning and the allocation of resources after natural disasters," The Review of Austrian Economics, Springer;Society for the Development of Austrian Economics, vol. 30(4), pages 469-492, December.
    16. Hanming Fang & Peter Norman, 2014. "Toward an efficiency rationale for the public provision of private goods," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 56(2), pages 375-408, June.
    17. Gan, Li & Ju, Gaosheng & Zhu, Xi, 2015. "Nonparametric estimation of structural labor supply and exact welfare change under nonconvex piecewise-linear budget sets," Journal of Econometrics, Elsevier, vol. 188(2), pages 526-544.
    18. Peterson, Jeffrey M. & Boisvert, Richard N. & de Gorter, Harry, 1999. "Multifunctionality and Optimal Environmental Policies for Agriculture in an Open Economy," Working Papers 127701, Cornell University, Department of Applied Economics and Management.
    19. Tian, Guoqiang, 2009. "Implementation of Pareto efficient allocations," Journal of Mathematical Economics, Elsevier, vol. 45(1-2), pages 113-123, January.
    20. Ahmad Naimzada & Marina Pireddu, 2019. "The first fundamental theorem of welfare in a general equilibrium evolutionary setting," Working Papers 415, University of Milano-Bicocca, Department of Economics, revised 06 Jun 2019.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:22:y:2011:i:4:d:10.1007_s10878-010-9302-1. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.