IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v26y2013i4d10.1007_s10878-012-9486-7.html
   My bibliography  Save this article

A note on anti-coordination and social interactions

Author

Listed:
  • Zhigang Cao

    (Chinese Academy of Sciences)

  • Xiaoguang Yang

    (Chinese Academy of Sciences)

Abstract

This note confirms a conjecture of (Bramoullé in Games Econ Behav 58:30–49, 2007). The problem, which we name the maximum independent cut problem, is a restricted version of the MAX-CUT problem, requiring one side of the cut to be an independent set. We show that the maximum independent cut problem does not admit any polynomial time algorithm with approximation ratio better than n 1−ϵ , where n is the number of nodes, and ϵ arbitrarily small, unless $\mathrm{P} = \mathrm{NP}$ . For the rather special case where each node has a degree of at most four, the problem is still APX-hard.

Suggested Citation

  • Zhigang Cao & Xiaoguang Yang, 2013. "A note on anti-coordination and social interactions," Journal of Combinatorial Optimization, Springer, vol. 26(4), pages 811-818, November.
    • Handle: RePEc:spr:jcomop:v:26:y:2013:i:4:d:10.1007_s10878-012-9486-7
    DOI: 10.1007/s10878-012-9486-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-012-9486-7
    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-012-9486-7?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. Bramoulle, Yann, 2007. "Anti-coordination and social interactions," Games and Economic Behavior, Elsevier, vol. 58(1), pages 30-49, January.
    Full references (including those not matched with items on IDEAS)

    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. Carlos Gracia-Lázaro & Luis Mario Floría & Yamir Moreno, 2017. "Cognitive Hierarchy Theory and Two-Person Games," Games, MDPI, vol. 8(1), pages 1-18, January.
    2. Zhigang Cao & Cheng-zhong Qin & Xiaoguang Yang & Boyu Zhang, 2019. "Dynamic matching pennies on networks," International Journal of Game Theory, Springer;Game Theory Society, vol. 48(3), pages 887-920, September.
    3. Dunia López-Pintado & Duncan J. Watts, 2008. "Social Influence, Binary Decisions and Collective Dynamics," Rationality and Society, , vol. 20(4), pages 399-443, November.
    4. Jérôme Stuck & Tom Broekel & Javier Revilla Diez, 2016. "Network Structures in Regional Innovation Systems," European Planning Studies, Taylor & Francis Journals, vol. 24(3), pages 423-442, March.
    5. Heydari, Babak & Mosleh, Mohsen & Dalili, Kia, 2015. "Efficient Network Structures with Separable Heterogeneous Connection Costs," MPRA Paper 63968, University Library of Munich, Germany.
    6. Miranda del Corral, 2015. "Why do people keep their promises? An overview of strategic commitment," Revista Cuadernos de Economia, Universidad Nacional de Colombia, FCE, CID, March.
    7. Zhigang Cao & Xujin Chen & Xiaodong Hu & Changjun Wang, 2017. "Approximation algorithms for pricing with negative network externalities," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 681-712, February.
    8. Yann Bramoullé & Rachel Kranton, 2015. "Games Played on Networks," Working Papers halshs-01180657, HAL.
    9. Ushchev, Philip & Zenou, Yves, 2020. "Social norms in networks," Journal of Economic Theory, Elsevier, vol. 185(C).
    10. Jackson, Matthew O. & Zenou, Yves, 2015. "Games on Networks," Handbook of Game Theory with Economic Applications,, Elsevier.
    11. Michael Foley & Rory Smead & Patrick Forber & Christoph Riedl, 2021. "Avoiding the bullies: The resilience of cooperation among unequals," PLOS Computational Biology, Public Library of Science, vol. 17(4), pages 1-18, April.
    12. Grabisch, Michel & Poindron, Alexis & Rusinowska, Agnieszka, 2019. "A model of anonymous influence with anti-conformist agents," Journal of Economic Dynamics and Control, Elsevier, vol. 109(C).
    13. König, Michael D. & Battiston, Stefano & Napoletano, Mauro & Schweitzer, Frank, 2012. "The efficiency and stability of R&D networks," Games and Economic Behavior, Elsevier, vol. 75(2), pages 694-713.
    14. Hiller, Timo, 2017. "Peer effects in endogenous networks," Games and Economic Behavior, Elsevier, vol. 105(C), pages 349-367.
    15. Chatterjee, Arko & Rao, K.S. Mallikarjuna & Sarangi, Sudipta, 2023. "Evolutionary stability for games played on networks," Economics Letters, Elsevier, vol. 229(C).
    16. Abele, Susanne & Stasser, Garold & Chartier, Christopher, 2014. "Use of social knowledge in tacit coordination: Social focal points," Organizational Behavior and Human Decision Processes, Elsevier, vol. 123(1), pages 23-33.
    17. Dotan Persitz, 2009. "Power in the Heterogeneous Connections Model: The Emergence of Core-Periphery Networks," Working Papers 2009.42, Fondazione Eni Enrico Mattei.
    18. Debapriya Sen, 2018. "Potential games, path independence and Poisson’s binomial distribution," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 88(1), pages 125-146, August.
    19. Heydari, Babak & Mosleh, Mohsen & Dalili, Kia, 2015. "Efficient network structures with separable heterogeneous connection costs," Economics Letters, Elsevier, vol. 134(C), pages 82-85.

    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:26:y:2013:i:4:d:10.1007_s10878-012-9486-7. 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.