IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v305y2023i1p438-450.html
   My bibliography  Save this article

Set-weighted games and their application to the cover problem

Author

Listed:
  • Gusev, Vasily V.

Abstract

The cover of a transport, social, or communication network is a computationally complex problem. To deal with it, this paper introduces a special class of simple games in which the set of minimal winning coalitions coincides with the set of least covers. A distinctive feature of such a game is that it has a weighted form, in which weights and quota are sets rather than real numbers. This game class is termed set-weighted games. A real-life network has a large number of least covers, therefore this paper develops methods for analyzing set-weighted games in which the weighted form is taken into account. The necessary and sufficient conditions for a simple game to be a set-weighted game were found. The vertex cover game (Gusev, 2020) was shown to belong to the set-weighted game class, and its weighted form was found. The set-weighted game class has proven to be closed under operations of union and intersection, which is not the case for weighted games. The sample object is the transport network of a district in Petrozavodsk, Russia. A method is suggested for efficiently deploying surveillance cameras at crossroads so that all transport network covers are taken into account.

Suggested Citation

  • Gusev, Vasily V., 2023. "Set-weighted games and their application to the cover problem," European Journal of Operational Research, Elsevier, vol. 305(1), pages 438-450.
    • Handle: RePEc:eee:ejores:v:305:y:2023:i:1:p:438-450
    DOI: 10.1016/j.ejor.2022.05.026
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221722004003
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2022.05.026?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. Deineko, Vladimir G. & Woeginger, Gerhard J., 2006. "On the dimension of simple monotonic games," European Journal of Operational Research, Elsevier, vol. 170(1), pages 315-318, April.
    2. Veremyev, Alexander & Sorokin, Alexey & Boginski, Vladimir & Pasiliao, Eduardo L., 2014. "Minimum vertex cover problem for coupled interdependent networks with cascading failures," European Journal of Operational Research, Elsevier, vol. 232(3), pages 499-511.
    3. Li, Yuchao & Yang, Zishen & Wang, Wei, 2017. "Complexity and algorithms for the connected vertex cover problem in 4-regular graphs," Applied Mathematics and Computation, Elsevier, vol. 301(C), pages 107-114.
    4. Berghammer, Rudolf & Bolus, Stefan & Rusinowska, Agnieszka & de Swart, Harrie, 2011. "A relation-algebraic approach to simple games," European Journal of Operational Research, Elsevier, vol. 210(1), pages 68-80, April.
    5. David S. Johnson & Lee Breslau & Ilias Diakonikolas & Nick Duffield & Yu Gu & MohammadTaghi Hajiaghayi & Howard Karloff & Mauricio G. C. Resende & Subhabrata Sen, 2020. "Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs," Operations Research, INFORMS, vol. 68(3), pages 896-926, May.
    6. Freixas, Josep & Puente, Maria Albina, 2008. "Dimension of complete simple games with minimum," European Journal of Operational Research, Elsevier, vol. 188(2), pages 555-568, July.
    7. Alonso-Meijide, J.M. & Casas-Méndez, B. & Fiestras-Janeiro, M.G., 2015. "Computing Banzhaf–Coleman and Shapley–Shubik power indices with incompatible players," Applied Mathematics and Computation, Elsevier, vol. 252(C), pages 377-387.
    8. Josep Freixas & Sascha Kurz, 2014. "Enumeration of weighted games with minimum and an analysis of voting power for bipartite complete games with minimum," Annals of Operations Research, Springer, vol. 222(1), pages 317-339, November.
    9. Xiaotie Deng & Toshihide Ibaraki & Hiroshi Nagamochi, 1999. "Algorithmic Aspects of the Core of Combinatorial Optimization Games," Mathematics of Operations Research, INFORMS, vol. 24(3), pages 751-766, August.
    10. Bolus, Stefan, 2011. "Power indices of simple games and vector-weighted majority games by means of binary decision diagrams," European Journal of Operational Research, Elsevier, vol. 210(2), pages 258-272, April.
    11. Michela Chessa, 2014. "A generating functions approach for computing the Public Good index efficiently," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 22(2), pages 658-673, July.
    12. Gusev, Vasily V., 2020. "The vertex cover game: Application to transport networks," Omega, Elsevier, vol. 97(C).
    13. Freixas, Josep & Marciniak, Dorota & Pons, Montserrat, 2012. "On the ordinal equivalence of the Johnston, Banzhaf and Shapley power indices," European Journal of Operational Research, Elsevier, vol. 216(2), pages 367-375.
    14. Monroy, Luisa & Fernández, Francisco R., 2011. "The Shapley-Shubik index for multi-criteria simple games," European Journal of Operational Research, Elsevier, vol. 209(2), pages 122-128, March.
    15. Lawrence Diffo Lambo & Joël Moulen, 2002. "Ordinal equivalence of power notions in voting games," Theory and Decision, Springer, vol. 53(4), pages 313-325, December.
    16. Abbas Bazzi & Samuel Fiorini & Sebastian Pokutta & Ola Svensson, 2019. "No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 147-172, February.
    17. Crama, Yves & Leruth, Luc, 2007. "Control and voting power in corporate networks: Concepts and computational aspects," European Journal of Operational Research, Elsevier, vol. 178(3), pages 879-893, May.
    18. Peker, Meltem & Kara, Bahar Y., 2015. "The P-Hub maximal covering problem and extensions for gradual decay functions," Omega, Elsevier, vol. 54(C), pages 158-172.
    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. Vasily V. Gusev, 2021. "Set-weighted games and their application to the cover problem," HSE Working papers WP BRP 247/EC/2021, National Research University Higher School of Economics.
    2. Gusev, Vasily V., 2020. "The vertex cover game: Application to transport networks," Omega, Elsevier, vol. 97(C).
    3. Freixas, Josep & Kurz, Sascha, 2013. "The golden number and Fibonacci sequences in the design of voting structures," European Journal of Operational Research, Elsevier, vol. 226(2), pages 246-257.
    4. Yuto Ushioda & Masato Tanaka & Tomomi Matsui, 2022. "Monte Carlo Methods for the Shapley–Shubik Power Index," Games, MDPI, vol. 13(3), pages 1-14, June.
    5. Cheung, Wai-Shun & Ng, Tuen-Wai, 2014. "A three-dimensional voting system in Hong Kong," European Journal of Operational Research, Elsevier, vol. 236(1), pages 292-297.
    6. Molinero, Xavier & Riquelme, Fabián & Serna, Maria, 2015. "Cooperation through social influence," European Journal of Operational Research, Elsevier, vol. 242(3), pages 960-974.
    7. Frits Hof & Walter Kern & Sascha Kurz & Kanstantsin Pashkovich & Daniël Paulusma, 2020. "Simple games versus weighted voting games: bounding the critical threshold value," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(4), pages 609-621, April.
    8. Josep Freixas & Montserrat Pons, 2017. "Using the Multilinear Extension to Study Some Probabilistic Power Indices," Group Decision and Negotiation, Springer, vol. 26(3), pages 437-452, May.
    9. Pongou, Roland & Tchantcho, Bertrand & Tedjeugang, Narcisse, 2014. "Power theories for multi-choice organizations and political rules: Rank-order equivalence," Operations Research Perspectives, Elsevier, vol. 1(1), pages 42-49.
    10. Sascha Kurz & Nikolas Tautenhahn, 2013. "On Dedekind’s problem for complete simple games," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(2), pages 411-437, May.
    11. Chameni Nembua, C. & Miamo Wendji, C., 2016. "Ordinal equivalence of values, Pigou–Dalton transfers and inequality in TU-games," Games and Economic Behavior, Elsevier, vol. 99(C), pages 117-133.
    12. Freixas, Josep & Tchantcho, Bertrand & Tedjeugang, Narcisse, 2014. "Achievable hierarchies in voting games with abstention," European Journal of Operational Research, Elsevier, vol. 236(1), pages 254-260.
    13. Josep Freixas & Sascha Kurz, 2014. "Enumeration of weighted games with minimum and an analysis of voting power for bipartite complete games with minimum," Annals of Operations Research, Springer, vol. 222(1), pages 317-339, November.
    14. Freixas, Josep & Kurz, Sascha, 2016. "The cost of getting local monotonicity," European Journal of Operational Research, Elsevier, vol. 251(2), pages 600-612.
    15. Joseph Armel Momo Kenfack & Bertrand Tchantcho & Bill Proces Tsague, 2019. "On the ordinal equivalence of the Jonhston, Banzhaf and Shapley–Shubik power indices for voting games with abstention," International Journal of Game Theory, Springer;Game Theory Society, vol. 48(2), pages 647-671, June.
    16. Josep Freixas & Sascha Kurz, 2014. "On $${\alpha }$$ α -roughly weighted games," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(3), pages 659-692, August.
    17. Bhattacherjee, Sanjay & Chakravarty, Satya R. & Sarkar, Palash, 2022. "A General Model for Multi-Parameter Weighted Voting Games," MPRA Paper 115407, University Library of Munich, Germany.
    18. Somdeb Lahiri, 2021. "Pattanaik's axioms and the existence of winners preferred with probability at least half," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 31(2), pages 109-122.
    19. Molinero, Xavier & Riquelme, Fabián & Serna, Maria, 2015. "Forms of representation for simple games: Sizes, conversions and equivalences," Mathematical Social Sciences, Elsevier, vol. 76(C), pages 87-102.
    20. Molinero, Xavier & Riquelme, Fabián & Roura, Salvador & Serna, Maria, 2023. "On the generalized dimension and codimension of simple games," European Journal of Operational Research, Elsevier, vol. 306(2), pages 927-940.

    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:eee:ejores:v:305:y:2023:i:1:p:438-450. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.