Set-weighted games and their application to the cover problem

Vasily Gusev ()
Additional contact information
Vasily Gusev: National Research University Higher School of Economics

HSE Working papers from National Research University Higher School of Economics

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.

Keywords: simple games; set-weighted games; vertex covergame; cover problem; cooperative generating functions; power indexes (search for similar items in EconPapers)
JEL-codes: C70 C71 (search for similar items in EconPapers)
Pages: 31 pages
Date: 2021
New Economics Papers: this item is included in nep-cis, nep-gth, nep-net, nep-ore and nep-tra
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in WP BRP Series: Economics / EC, June 2021, pages 1-31

Downloads: (external link)
https://wp.hse.ru/data/2021/06/23/1429589966/247EC2021.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hig:wpaper:247/ec/2021

Access Statistics for this paper

More papers in HSE Working papers from National Research University Higher School of Economics
Bibliographic data for series maintained by Shamil Abdulaev () and Shamil Abdulaev ().