Search the digital library catalog

Abstract: We propose a new coloring game on a graph, called the independence coloring game, which is played by two players with opposite goals. The result of the game is a proper coloring of vertices of a graph G, and Alice’s goal is that as few colors as possible are used during the game, while Bob wants to maximize the number of colors. The game consists of rounds, and in round i, where i = 1, 2,, … , the players are taking turns in selecting a previously unselected vertex of G and giving it color i (hence, in each round the selected vertices form an independent set). The game ends when all vertices of G are selected (and thus colored), and the total number of rounds during the game when both players are playing optimally with respect to their goals, is called the independence game chromatic number, χig(G), of G. In fact, four different versions of the independence game chromatic number are considered, which depend on who starts a game and who starts next rounds. We prove that the new invariants lie between the chromatic number of a graph and the maximum degree plus 1, and characterize the graphs in which each of the four versions of the game invariant equals 2. We compare the versions of the independence game chromatic number among themselves and with the classical game chromatic number. In addition, we prove that the independence game chromatic number of a tree can be arbitrarily large.
Keywords: graph, coloring, coloring game, competition-independence game, game chromatic number, tree
Published in DKUM: 09.08.2024; Views: 99; Downloads: 5
Full text (852,33 KB)
This document has many files! More...

Abstract: Reputation and reciprocity are key mechanisms for cooperation in human societies, often going hand in hand to favor prosocial behavior over selfish actions. Here we review recent researches at the interface of physics and evolutionary game theory that explored these two mechanisms. We focus on image scoring as the bearer of reputation, as well as on various types of reciprocity, including direct, indirect, and network reciprocity. We review different definitions of reputation and reciprocity dynamics, and we show how these affect the evolution of cooperation in social dilemmas. We consider first-order, second-order, as well as higherorder models in well-mixed and structured populations, and we review experimental works that support and inform the results of mathematical modeling and simulations. We also provide a synthesis of the reviewed researches along with an outlook in terms of six directions that seem particularly promising to explore in the future.
Keywords: pattern formation, Monte Carlo method, complex network, evolutionary game theory, cooperation, social physics
Published in DKUM: 20.06.2024; Views: 154; Downloads: 12
Full text (4,71 MB)
This document has many files! More...

Abstract: In this paper, we define characteristic axioms for 3D matrix games and extend the definitions of the decision criteria under uncertainty to three dimensions in order to investigate the simultaneous effect of two different states on the decision process. We first redefine the Laplace, Wald, Hurwicz, and Savage criteria in 3D. We present a new definition depending on only the ∞-norm of the 3D payoff matrix for the Laplace criterion in 3D. Then, we demonstrate that the Laplace criterion in 3D explicitly satisfies all the proposed axioms, as well as the other three criteria. Moreover, we illustrate a fundamental example for a three-dimensional matrix with 3D figures and show the usage of each criterion in detail. In the second example, we model a decision process during the COVID-19 pandemic for South Korea to show the applicability of the 3D decision criteria using real data with two different states of nature for individuals’ actions for the quarantine. Additionally, we present an agricultural insurance problem and analyze the effects of the hailstorm and different speeds of wind on the harvest by the 3D criteria. To the best of our knowledge, this is the first study that brings 3D matrices in decision and game theories together.
Keywords: game theory, decision criteria, matrix game, common goods, characteristic axioms, multi-state games, three-dimensional matrix games, game against nature, COVID-19, insurance problem
Published in DKUM: 27.05.2024; Views: 229; Downloads: 12
Full text (474,80 KB)
This document has many files! More...

Abstract: In this paper, we extend and apply the Matrix Norm (MN) approach to the nonzero-sum bimatrix games. We present preliminary results regarding the convergence of the MN approaches. We provide a notation for expressing nonzero-sum bimatrix games in terms of two matrix games using the idea of separation of a bimatrix game into two different matrix games. Next, we prove theorems regarding boundaries of the game value depending on only norms of the payoff matrix for each player of the nonzero-sum bimatrix game. In addition to these, we refine the boundaries of the game value for the zero/nonzero sum matrix games. Therefore, we succeed to find an improved interval for the game value, which is a crucial improvement for both nonzero and zero-sum matrix games. As a consequence, we can solve a nonzero-sum bimatrix game for each player approximately without solving any equations. Moreover, we modify the inequalities for the extrema of the strategy set for the nonzero-sum bimatrix games. Furthermore, we adapt the min-max theorem of the MN approach for the nonzero-sum bimatrix games. Finally, we consider various bimatrix game examples from the literature, including the famous battle of sexes, to demonstrate the consistency of our approaches. We also show that the repeated applications of Extended Matrix Norm (EMN) methods work well to obtain a better-estimated game value in view of the obtained convergence results.
Keywords: game theory, nonzero sum game, bimatrix game, matrix norms, battle of sexes, convergence
Published in DKUM: 15.04.2024; Views: 317; Downloads: 244
Full text (838,66 KB)
This document has many files! More...

Abstract: Pursuit-evasion games study the number of cops needed to capture therobber in a game played on a graph, in which the cops and the robber movealternatively to neighbouring vertices, and the robber is captured if a copsteps on the vertex the robber is in. A common tool in analyzing this copnumber of a graph is a cop moving along a shortest path in a graph, thuspreventing the robber to step onto this path. We generalize this approach byintroducing a shadow of the robber, the maximal set of vertices from whichthe cop parries the protected subgraph. In this context, the robber becomesan intruder and the cop becomes the guard. We show that the shadow canbe computed in polynomial time, implying polynomial time algorithms forcomputing both a successful guard as well as a successful intruder, whicheverexists. Furthermore, we show that shadow function generalizes the conceptof graph retractions. In some cases, this implies a polynomially computablecertification of the negative answer to the NP-complete problem of existenceof a retraction to a given subgraph.
Keywords: pursuit-evasion game, graph searching, guarding, shadow function, graph retraction
Published in DKUM: 17.08.2023; Views: 423; Downloads: 35
Full text (377,93 KB)
This document has many files! More...