Search

An acyclic coloring of a graph is a proper coloring of the graph, for which every cycle uses at least three colors. Let G 4 be the set of maximal planar graphs of minimum degree 4, such that each graph in G 4 contains exactly four odd-vertices and the subgraph induced by the four odd-vertices contains a quadrilateral. In this article, we show that every acyclic 4-coloring of a maximal planar graph with exact four odd-vertices is locally equitable with regard to its four odd-vertices. Moreover, we obtain a necessary and sufficient condition for a graph in G 4 to be acyclically 4-colorable, and give an enumeration of the acyclically 4-colorable graphs in G 4 . [ABSTRACT FROM AUTHOR]

In games especially large scale extensive games, players’ actual views of the game might be different from the real one, because of the limit of their computational power. Moreover, players’ views on the underlying game vary from person to person. Based on some existing work on modelling players’ limited foresight in games, we study several interesting types of players in terms of the characteristics of their actual views. The underlying model is closely connected to the well-known algorithm called α − β pruning, and an algorithmic procedure refining classical backward-induction is designed for strategy choosing in the actual process of playing such games. Further, we study the dynamic evolution of players’ foresight and show the resulting preference change. [ABSTRACT FROM AUTHOR]

We study preference dynamics in extensive games with short sight. To do so, first, we represent the priority structure as a partial-ordered priority graph instead of a linear-ordered sequence. By introducing priority graph to extensive games, we obtain the definition of prioritized games and graph-induced preference. Second, in order to deal with the situation in which a player only has incomplete information about the relevant properties and she has to decide her preference, we introduce beliefs and define belief-based preference. We propose an algorithm for such games and further explore its relationship with heuristic search algorithm in AI. Third, we investigate preference dynamics in games with regard to the changes in three kinds of triggers: priority graph, belief, and sight. We show how these changes lead to changes in preference. [ABSTRACT FROM AUTHOR]

With an increasing demand for ensuring the reliability and efficiency of distributed and interactive systems, the model-checking technique has been studied extensively, for which a game-based modeling of the system and a logical specification of the desired properties are two essential parts. Existing studies mainly focused on ideal systems that always guarantee optimal responses and have not considered several realistic aspects, for instance, the fact that actions can only be performed under sufficient resources. In this paper, we propose a game model with resource constraints and thereby a novel logic named LRC for such games. This logic enables the strategic reasoning of the likely strategies of the other participating entities and thus supports not only the characterization of the equilibrium of games with limited resources, but also strategic exploitation in multi-agent systems in which the available resources are restricted. Interesting properties of this logic are investigated, and a model-checking algorithm is presented. Being built upon the alternating-time temporal logic (ATL), LRC is shown to be more expressive than ATL without bringing additional complexity. In addition to determining the existence or absence of a collaborative strategy, we explore the generation of the team plan when a certain protocol is supposed to be followed. [ABSTRACT FROM AUTHOR]