In this paper, we study cooperative games on a graph in which the vertices represent the players, and the characteristic function is defined using the maximum packing of the graph by connected coalitions. Simple paths in the graph are considered coalitions. In particular, coalitions can be pairs of vertices connected by edges.
In real life, there are many examples of paired relationships: supplier–customer, man–woman, predator– prey, source–sink, and so forth. Moreover, agents can interact with each other via vehicles, mobile devices, or social networks, forming paired communications. For example, in a mobile network, the vertices of the corresponding graph represent mobile devices, and the connections between them occur within the network coverage.
In practice, it is important to find the maximum load on a mobile network under which any two devices can simultaneously communicate with one another. In sociology and various TV shows, it is important to divide the participants into the maximum number of pairs (see, for example, the popular show “Speed Dating”, https://en.wikipedia.org/wiki/Speed_dating (accessed on 10 July 2021); https://www.imdb.com/find?q=speed+dating&ref_=nv_sr_sm (accessed on 10 July 2021).
The same problems arise in electrical and radio networks or the physics of magnetic structures of solid crystals. The maximum packing is not necessarily realized through pairs of connected vertices. For example, simple paths of a fixed length can be chosen as packing coalitions.
Such problems arise when laying fiber-optic lines to connect urban areas to the Internet. Another application is the development of transportation networks in a city or between cities. The network packing determines a partition of the set of players into coalitions.
After defining the characteristic function, an imputation can be found to rank the graph vertices by their value for organizing links in the network or transmitting data, depending on the problem under consideration. In the papers [1,2], a general class of such cooperative games was formulated and called combinatorial optimization games.
This class includes packing games as well. In such games, the characteristic function is defined as follows. Let a matrix A(m × n) ofzeros and ones, and integer vector c be given. The value of a coalition K ⊆ N is a solution of the integer linear programming problem max{(y, c) : y TAK ≤ 1K, y ∈ {0, 1} m}, where the matrix AK is a submatrix of A with the columns from the set K.
This problem is known as the set packing problem [3]. In a similar form, such games were investigated in [4] as linear production games. In the cooperative game of this type, the core (if it exists) is a solution of the dual problem. The balancedness (non-emptiness of the core) of the cooperative game is closely related to solving both problems.
As some applications, games with maximum flows on a graph, and graph packing games with pairs of connected vertices, were considered.
In packing games, other allocation principles can be adopted as imputations. Since the cooperative game is defined on a graph, the most natural approach to determine the significance of a particular graph vertex is the Myerson value [5,6]. In the papers [7,8], the Owen value [9–11] was used as an allocation principle in the cover game. In the paper [12], the nucleolus was proposed, including an algorithm for its construction.
The paper [13] was dedicated to the Shapley value: its properties were investigated and an algorithm for calculating this value was proposed. There are other games related to packing undirected graphs. For example, in graph coloring problems, the chromatic number of a graph can be taken as the characteristic function [1,14–16].
Graph clustering problems can be treated as cooperative games with a Nash stable coalition partition when none of the players benefit from changing the coalition structure. In this case, the Myerson value is used as an allocation principle; see [17,18]. In packing by pairs of connected vertices, two approaches to graph packing problems are well known: vertex cover and edge cover [1,19]. A vertex cover of a graph is any subset U of its vertex set N, such that any edge of this graph is incident to at least one vertex of the set U.
Here, the characteristic function is defined using the vertex cover with the minimum number of vertices (the so-called minimum vertex cover of the graph). Given an edge cover, the characteristic function is defined as the maximum number of edges in a graph without shared vertices. This paper deals with cooperative games on graphs in which the characteristic function is defined as the maximum number of independent simple paths of a fixed length. Note that we are interested in the paths without shared vertices.
This feature distinguishes the current statement from the cooperative game in which the characteristic function is defined as the number of all simple paths of a fixed length. The latter definition of a game is often used for determining the centrality of graph vertices.
Here, it will be convenient to use “graph packing” for referring to the coalitions (paths) included in a corresponding coalition partition. The remainder of this paper is organized as follows: In Section 2, we define a cooperative packing game. Section 3 considers the graph packing problem with pairs of connected vertices. In Section 4, these results are extended to the general case. Section 5 presents the explicit-form solution of the cooperative graph packing game for several particular graphs.
Selengkapnya : https://www.mdpi.com/2227-7390/9/14/1683
Posts
0 comments:
Post a Comment