IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v97y2020ics0305048319303421.html
   My bibliography  Save this article

The vertex cover game: Application to transport networks

Author

Listed:
  • Gusev, Vasily V.

Abstract

As communications are progressing, transport networks need to be monitored, more specifically, camera surveillance of violations is needed. Standards are being developed on how to install cameras, and the question of efficiently distributing surveillance devices across the road network ensue. This task is addressed in this paper by using the methods of the cooperative game theory. The vertex cover game is introduced, and its properties are studied. Since surveillance cameras are to cover all areas of the network, the characteristic function depends on the vertex covers of the graph. The Shapley–Shubik index is used as the measure of centrality. The Shapley–Shubik index is shown to be efficient in a vertex cover game for the allocation of cameras in a transport network. Proceeding from the Shapley–Shubik indices calculated in this study, recommendations were given for the allocation of surveillance cameras in a specific transport network in a district of the City of Petrozavodsk, Russia.

Suggested Citation

  • Gusev, Vasily V., 2020. "The vertex cover game: Application to transport networks," Omega, Elsevier, vol. 97(C).
    • Handle: RePEc:eee:jomega:v:97:y:2020:i:c:s0305048319303421
    DOI: 10.1016/j.omega.2019.08.009
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048319303421
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2019.08.009?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. René Brink & Agnieszka Rusinowska & Frank Steffen, 2013. "Measuring power and satisfaction in societies with opinion leaders: an axiomatization," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 41(3), pages 671-683, September.
    2. Hadas, Yuval & Gnecco, Giorgio & Sanguineti, Marcello, 2017. "An approach to transportation network analysis via transferable utility games," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 120-143.
    3. Lightfoot, JM & Spinetto, RD, 1993. "An algorithm for sharing costs of operating a computer network," Omega, Elsevier, vol. 21(5), pages 585-592, September.
    4. Dariush Khezrimotlagh & Yao Chen, 2018. "Data Envelopment Analysis," International Series in Operations Research & Management Science, in: Decision Making and Performance Evaluation Using Data Envelopment Analysis, chapter 0, pages 217-234, Springer.
    5. Fang, Lei, 2015. "Centralized resource allocation based on efficiency analysis for step-by-step improvement paths," Omega, Elsevier, vol. 51(C), pages 24-28.
    6. René van den Brink & Agnieszka Rusinowska & Frank Steffen, 2009. "Measuring Power and Satisfaction in Societies with Opinion Leaders: Dictator and Opinion Leader Properties," Tinbergen Institute Discussion Papers 09-052/1, Tinbergen Institute.
    7. Varsei, Mohsen & Polyakovskiy, Sergey, 2017. "Sustainable supply chain network design: A case of the wine industry in Australia," Omega, Elsevier, vol. 66(PB), pages 236-247.
    8. Chen, Haoxun, 2018. "Average lexicographic efficiency for data envelopment analysis," Omega, Elsevier, vol. 74(C), pages 82-91.
    9. An, Qingxian & Wen, Yao & Ding, Tao & Li, Yongli, 2019. "Resource sharing and payoff allocation in a three-stage system: Integrating network DEA with the Shapley value method," Omega, Elsevier, vol. 85(C), pages 16-25.
    10. Samadi, Mohammadreza & Nikolaev, Alexander & Nagi, Rakesh, 2016. "A subjective evidence model for influence maximization in social networks," Omega, Elsevier, vol. 59(PB), pages 263-278.
    11. Ye, Qing Chuan & Zhang, Yingqian & Dekker, Rommert, 2017. "Fair task allocation in transportation," Omega, Elsevier, vol. 68(C), pages 1-16.
    12. Álvarez-Mozos, M. & Alonso-Meijide, J.M. & Fiestras-Janeiro, M.G., 2017. "On the externality-free Shapley–Shubik index," Games and Economic Behavior, Elsevier, vol. 105(C), pages 148-154.
    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. AUMANN, Robert J. & DREZE, Jacques H., 1974. "Cooperative games with coalition structures," LIDAM Reprints CORE 217, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    15. Blanquero, Rafael & Carrizosa, Emilio & G.-Tóth, Boglárka, 2016. "Maximal Covering Location Problems on networks with regional demand," Omega, Elsevier, vol. 64(C), pages 77-85.
    16. 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.
    17. 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.
    18. Shabtay, Dvir & Steiner, George & Zhang, Rui, 2016. "Optimal coordination of resource allocation, due date assignment and scheduling decisions," Omega, Elsevier, vol. 65(C), pages 41-54.
    19. 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.
    20. Li, Susan X. & Huang, Zhimin & Zhu, Joe & Chau, Patrick Y. K., 2002. "Cooperative advertising, game theory and manufacturer-retailer supply chains," Omega, Elsevier, vol. 30(5), pages 347-357, October.
    21. 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.
    22. Bhadury, Joyendu & Mighty, E. Joy & Damar, Hario, 2000. "Maximizing workforce diversity in project teams: a network flow approach," Omega, Elsevier, vol. 28(2), pages 143-153, April.
    23. Francesc Carreras & Antonio Magaña, 2008. "The Shapley–Shubik index for simple games with multiple alternatives," Annals of Operations Research, Springer, vol. 158(1), pages 81-97, February.
    24. Einy, Ezra & Haimanko, Ori, 2011. "Characterization of the Shapley–Shubik power index without the efficiency axiom," Games and Economic Behavior, Elsevier, vol. 73(2), pages 615-621.
    25. 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.
    26. Rosenthal, Edward C., 2017. "A cooperative game approach to cost allocation in a rapid-transit network," Transportation Research Part B: Methodological, Elsevier, vol. 97(C), pages 64-77.
    27. Selto, Fh & Grove, Hd, 1982. "Voting Power Indexes And The Setting Of Financial Accounting Standards - Extensions," Journal of Accounting Research, Wiley Blackwell, vol. 20(2), pages 676-688.
    28. Molinero, Xavier & Riquelme, Fabián & Serna, Maria, 2015. "Cooperation through social influence," European Journal of Operational Research, Elsevier, vol. 242(3), pages 960-974.
    29. Karray, Salma, 2015. "Cooperative promotions in the distribution channel," Omega, Elsevier, vol. 51(C), pages 49-58.
    30. Dong, Yucheng & Liu, Yating & Liang, Haiming & Chiclana, Francisco & Herrera-Viedma, Enrique, 2018. "Strategic weight manipulation in multiple attribute decision making," Omega, Elsevier, vol. 75(C), pages 154-164.
    31. Wu, Qiong & Ren, Hongbo & Gao, Weijun & Ren, Jianxing, 2017. "Benefit allocation for distributed energy network participants applying game theory based solutions," Energy, Elsevier, vol. 119(C), pages 384-391.
    32. Dubey, Pradeep & Einy, Ezra & Haimanko, Ori, 2005. "Compound voting and the Banzhaf index," Games and Economic Behavior, Elsevier, vol. 51(1), pages 20-30, April.
    33. Li, Feng & Zhu, Qingyuan & Chen, Zhi, 2019. "Allocating a fixed cost across the decision making units with two-stage network structures," Omega, Elsevier, vol. 83(C), pages 139-154.
    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. Pelegrín, Mercedes & Xu, Liding, 2023. "Continuous covering on networks: Improved mixed integer programming formulations," Omega, Elsevier, vol. 117(C).
    2. 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.
    3. Gusev, Vasily V., 2021. "Nash-stable coalition partition and potential functions in games with coalition structure," European Journal of Operational Research, Elsevier, vol. 295(3), pages 1180-1188.
    4. Kameng Nip & Tianning Shi & Zhenbo Wang, 2022. "Some graph optimization problems with weights satisfying linear constraints," Journal of Combinatorial Optimization, Springer, vol. 43(1), pages 200-225, January.
    5. Luo, Chunlin & Zhou, Xiaoyang & Lev, Benjamin, 2022. "Core, shapley value, nucleolus and nash bargaining solution: A Survey of recent developments and applications in operations management," Omega, Elsevier, vol. 110(C).
    6. Sergei Dotsenko & Vladimir Mazalov, 2021. "A Cooperative Network Packing Game with Simple Paths," Mathematics, MDPI, vol. 9(14), pages 1-18, July.
    7. 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.

    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., 2023. "Set-weighted games and their application to the cover problem," European Journal of Operational Research, Elsevier, vol. 305(1), pages 438-450.
    3. Chu, Junfei & Wu, Jie & Chu, Chengbin & Zhang, Tinglong, 2020. "DEA-based fixed cost allocation in two-stage systems: Leader-follower and satisfaction degree bargaining game approaches," Omega, Elsevier, vol. 94(C).
    4. Li, Yongjun & Wang, Lizheng & Li, Feng, 2021. "A data-driven prediction approach for sports team performance and its application to National Basketball Association," Omega, Elsevier, vol. 98(C).
    5. Basso, Franco & Guajardo, Mario & Varas, Mauricio, 2020. "Collaborative job scheduling in the wine bottling process," Omega, Elsevier, vol. 91(C).
    6. Sylvain Béal & Marc Deschamps & Mostapha Diss & Rodrigue Tido Takeng, 2024. "Cooperative games with diversity constraints," Working Papers hal-04447373, HAL.
    7. repec:hal:journl:hal-04834011 is not listed on IDEAS
    8. Xiong, Beibei & Chen, Haoxun & An, Qingxian & Wu, Jie, 2019. "A multi-objective distance friction minimization model for performance assessment through data envelopment analysis," European Journal of Operational Research, Elsevier, vol. 279(1), pages 132-142.
    9. Albizuri, M.J. & Goikoetxea, A., 2022. "Probabilistic Owen-Shapley spatial power indices," Games and Economic Behavior, Elsevier, vol. 136(C), pages 524-541.
    10. Antônio Francisco Neto, 2019. "Generating Functions of Weighted Voting Games, MacMahon’s Partition Analysis, and Clifford Algebras," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 74-101, February.
    11. Shabani, Amir & Visani, Franco & Barbieri, Paolo & Dullaert, Wout & Vigo, Daniele, 2019. "Reliable estimation of suppliers’ total cost of ownership: An imprecise data envelopment analysis model with common weights," Omega, Elsevier, vol. 87(C), pages 57-70.
    12. Qiang Du & Hongyu Zhu & Youdan Huang & Qiaoyu Pang & Jinzhao Shi, 2024. "Profit allocation of carbon emission reduction in the construction supply chain," Environment, Development and Sustainability: A Multidisciplinary Approach to the Theory and Practice of Sustainable Development, Springer, vol. 26(8), pages 20531-20560, August.
    13. Kong, Qianqian & Peters, Hans, 2023. "Power indices for networks, with applications to matching markets," European Journal of Operational Research, Elsevier, vol. 306(1), pages 448-456.
    14. René Brink & Agnieszka Rusinowska & Frank Steffen, 2013. "Measuring power and satisfaction in societies with opinion leaders: an axiomatization," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 41(3), pages 671-683, September.
    15. Hans Peters & José M. Zarzuelo, 2017. "An axiomatic characterization of the Owen–Shapley spatial power index," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(2), pages 525-545, May.
    16. René van den Brink & Frank Steffen, 2012. "On the Measurement of Success and Satisfaction," Tinbergen Institute Discussion Papers 12-030/1, Tinbergen Institute.
    17. Borrás, Fernando & Ruiz, José L. & Sirvent, Inmaculada, 2023. "Peer evaluation through cross-efficiency based on reference sets," Omega, Elsevier, vol. 114(C).
    18. Karray, Salma & Sigué, Simon Pierre, 2015. "A game-theoretic model for co-promotions: Choosing a complementary versus an independent product ally," Omega, Elsevier, vol. 54(C), pages 84-100.
    19. Dai, Qianzhi & Li, Yongjun & Lei, Xiyang & Wu, Dengsheng, 2021. "A DEA-based incentive approach for allocating common revenues or fixed costs," European Journal of Operational Research, Elsevier, vol. 292(2), pages 675-686.
    20. An, Qingxian & Wang, Ping & Emrouznejad, Ali & Hu, Junhua, 2020. "Fixed cost allocation based on the principle of efficiency invariance in two-stage systems," European Journal of Operational Research, Elsevier, vol. 283(2), pages 662-675.
    21. Karos, Dominik & Peters, Hans, 2015. "Indirect control and power in mutual control structures," Games and Economic Behavior, Elsevier, vol. 92(C), pages 150-165.

    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:jomega:v:97:y:2020:i:c:s0305048319303421. 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/wps/find/journaldescription.cws_home/375/description#description .

    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.