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. 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.
    2. 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.
    3. 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.
    4. Molinero, Xavier & Riquelme, Fabián & Serna, Maria, 2015. "Cooperation through social influence," European Journal of Operational Research, Elsevier, vol. 242(3), pages 960-974.
    5. Karray, Salma, 2015. "Cooperative promotions in the distribution channel," Omega, Elsevier, vol. 51(C), pages 49-58.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. Lightfoot, JM & Spinetto, RD, 1993. "An algorithm for sharing costs of operating a computer network," Omega, Elsevier, vol. 21(5), pages 585-592, September.
    14. 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.
    15. 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.
    16. 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.
    17. Fang, Lei, 2015. "Centralized resource allocation based on efficiency analysis for step-by-step improvement paths," Omega, Elsevier, vol. 51(C), pages 24-28.
    18. 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.
    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. 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.
    21. 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.
    22. Chen, Haoxun, 2018. "Average lexicographic efficiency for data envelopment analysis," Omega, Elsevier, vol. 74(C), pages 82-91.
    23. 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.
    24. 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.
    25. 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.
    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. Ye, Qing Chuan & Zhang, Yingqian & Dekker, Rommert, 2017. "Fair task allocation in transportation," Omega, Elsevier, vol. 68(C), pages 1-16.
    28. Á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.
    29. 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.
    30. 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.
    31. 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.
    32. 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).
    33. 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.
    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. Sylvain Béal & Marc Deschamps & Mostapha Diss & Rodrigue Tido Takeng, 2024. "Cooperative games with diversity constraints," Working Papers hal-04447373, HAL.
    4. 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).
    5. 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.
    6. Albizuri, M.J. & Goikoetxea, A., 2022. "Probabilistic Owen-Shapley spatial power indices," Games and Economic Behavior, Elsevier, vol. 136(C), pages 524-541.
    7. 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).
    8. 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.
    9. Basso, Franco & Guajardo, Mario & Varas, Mauricio, 2020. "Collaborative job scheduling in the wine bottling process," Omega, Elsevier, vol. 91(C).
    10. Meng, Fanyong & Xiong, Beibei, 2021. "Logical efficiency decomposition for general two-stage systems in view of cross efficiency," European Journal of Operational Research, Elsevier, vol. 294(2), pages 622-632.
    11. 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.
    12. 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.
    13. 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.
    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. M. J. Albizuri & A. Goikoetxea, 2021. "The Owen–Shapley Spatial Power Index in Three-Dimensional Space," Group Decision and Negotiation, Springer, vol. 30(5), pages 1027-1055, October.
    16. 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.
    17. 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.
    18. 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.
    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. 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.

    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.