A note on the approximation of mean-payoff games

We consider the problem of designing approximation schemes for the values of mean-payoff games. It was recently shown that (1) mean-payoff with rational weights scaled on [−1,1]$[-1,1]$ admit additive fully-polynomial approximation schemes, and (2) mean-payoff games with positive weights admit relative fully-polynomial approximation schemes. We show that the problem of designing additive/relative approximation schemes for general mean-payoff games (i.e. with no constraint on their edge-weights) is P-time equivalent to determining their exact solution.     

Equilibria problems on games: Complexity versus succinctness

We study the computational complexity of problems involving equilibria in strategic games and in perfect information extensive games when the number of players is large. We consider, among others, the problems of deciding the existence of a pure Nash equilibrium in strategic games or deciding the existence of a pure Nash or a subgame perfect Nash equilibrium with a given payoff in finite perfect information extensive games. We address the fundamental question of how can we represent a game with a large number of players? We propose three ways of representing a game with different degrees of succinctness for the components of the game. For perfect information extensive games we show that when the number of moves of each player is large and the input game is represented succinctly these problems are PSPACE-complete. In contraposition, when the game is described explicitly by means of its associated tree all these problems are decidable in polynomial time. For strategic games we show that the complexity of deciding the existence of a pure Nash equilibrium depends on the succinctness of the game representation and then on the size of the action sets. In particular we show that it is NP-complete, when the number of players is large and the number of actions for each player is constant, and that the problem is -complete when the number of players is a constant and the size of the action sets is exponential in the size of the game representation. Again when the game is described explicitly the problem is decidable in polynomial time.     

On the small cycle transversal of planar graphs

We consider the problem of finding a k-edge transversal set that intersects all (simple) cycles of length at most s in a planar graph, where s≥3 is a constant. This problem, referred to as Small Cycle Transversal, is known to be NP-complete. We present a polynomial-time algorithm that computes a kernel of size 36s³k for Small Cycle Transversal. In order to achieve this kernel, we extend the region decomposition technique of Alber et al. (2004) [1] by considering a unique region decomposition that is defined by shortest paths. Our kernel size is a significant improvement in terms of s over the kernel size obtained under the meta-kernelization framework by Bodlaender et al. (2009) [7].     

On the computational complexity of qualitative coalitional games

We study coalitional games in which agents are each assumed to have a goal to be achieved, and where the characteristic property of a coalition is a set of choices, with each choice denoting a set of goals that would be achieved if the choice was made. Such qualitative coalitional games (qcgs) are a natural tool for modelling goal-oriented multiagent systems. After introducing and formally defining qcgs, we systematically formulate fourteen natural decision problems associated with them, and determine the computational complexity of these problems. For example, we formulate a notion of coalitional stability inspired by that of the core from conventional coalitional games, and prove that the problem of showing that the core of a qcg is non-empty is D^p₁-complete. (As an aside, we present what we believe is the first “natural” problem that is proven to be complete for D^p₂.) We conclude by discussing the relationship of our work to other research on coalitional reasoning in multiagent systems, and present some avenues for future research.     

Parameterized complexity of the induced subgraph problem in directed graphs

In this Letter, we consider the parameterized complexity of the following problem: Given a hereditary property P on digraphs, an input digraph D and a positive integer k, does D have an induced subdigraph on k vertices with property P? We completely characterize hereditary properties for which this induced subgraph problem is W[1]-complete for two classes of directed graphs: general directed graphs and oriented graphs. We also characterize those properties for which the induced subgraph problem is W[1]-complete for general directed graphs but fixed parameter tractable for oriented graphs. These results are among the very few parameterized complexity results on directed graphs.     

A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover-Delayer games

In this note we show that the asymmetric Prover-Delayer game developed in Beyersdorff et al. (2010) [2] for Parameterized Resolution is also applicable to other tree-like proof systems. In particular, we use this asymmetric Prover-Delayer game to show a lower bound of the form ²Ω(nlogn) for the pigeonhole principle in tree-like Resolution. This gives a new and simpler proof of the same lower bound established by Iwama and Miyazaki (1999) [7] and Dantchev and Riis (2001) [5].     

On the computational complexity of coalitional resource games

We study Coalitional Resource Games (crgs), a variation of Qualitative Coalitional Games (qcgs) in which each agent is endowed with a set of resources, and the ability of a coalition to bring about a set of goals depends on whether they are collectively endowed with the necessary resources. We investigate and classify the computational complexity of a number of natural decision problems for crgs, over and above those previously investigated for qcgs in general. For example, we show that the complexity of determining whether conflict is inevitable between two coalitions with respect to some stated resource bound (i.e., a limit value for every resource) is co-np-complete. We then investigate the relationship between crgs and qcgs, and in particular the extent to which it is possible to translate between the two models. We first characterise the complexity of determining equivalence between crgs and qcgs. We then show that it is always possible to translate any given crg into a succinct equivalent qcg, and that it is not always possible to translate a qcg into an equivalent crg; we establish some necessary and some sufficient conditions for a translation from qcgs to crgs to be possible, and show that even where an equivalent crg exists, it may have size exponential in the number of goals and agents of its source qcg.     

Infinite games on finitely coloured graphs with applications to automata on infinite trees

We examine a class of infinite two-person games on finitely coloured graphs. The main aim is to construct finite memory winning strategies for both players. This problem is motivated by applications to finite automata on infinite trees. A special attention is given to the exact amount of memory needed by the players for their winning strategies. Based on a previous work of Gurevich and Harrington and on subsequent improvements of McNaughton we propose a unique framework that allows to reestablish and to improve various results concerning memoryless strategies due to Emerson and Jutla, Mostowski, Klarlund.     

Piracy on the simulated seas: the computer games industry's non-legal approaches to fighting illegal downloads of games

The computer games industry suffers from high rates of piracy, with many people downloading illegal copies of games. People in the industry are aware of the problem, and the gravity of it has been acknowledged and commented on by many publishers and developers. Yet unlike the Recording Industry Association of America, Motion Picture Association of America, independent movie studios, and other rights holders, computer game developers and publishers have shied away from attempting to sue pirates or otherwise enforce their rights through the legal system. Instead, the industry has looked to a variety of self-help remedies, a fact that has largely not been commented on by legal scholars. This paper examines the successes and pitfalls of these varied non-legal approaches, broadly classifying them into four categories: digital rights management, online-only offerings, making legal easier, and community engagement.     

On the complexity of constrained Nash equilibria in graphical games

A widely accepted rational behavior for non-cooperative players is based on the notion of Nash equilibrium. Although the existence of a Nash equilibrium is guaranteed in the mixed framework (i.e., when players select their actions in a randomized manner) in many real-world applications the existence of “any” equilibrium is not enough. Rather, it is often desirable to single out equilibria satisfying some additional requirements (in order, for instance, to guarantee a minimum payoff to certain players), which we call constrained Nash equilibria.In this paper, a formal framework for specifying these kinds of requirement is introduced and investigated in the context of graphical games, where a player p may directly be interested in some of the other players only, called the neighbors of p. This setting is very useful for modeling large population games, where typically each player does not directly depend on all the players, and representing her utility function extensively is either inconvenient or infeasible.Based on this framework, the complexity of deciding the existence and of computing constrained equilibria is then investigated, in the light of evidencing how the intrinsic difficulty of these tasks is affected by the requirements prescribed at the equilibrium and by the structure of players’ interactions. The analysis is carried out for the setting of mixed strategies as well as for the setting of pure strategies, i.e., when players are forced to deterministically choose the action to perform. In particular, for this latter case, restrictions on players’ interactions and on constraints are identified, that make the computation of Nash equilibria an easy problem, for which polynomial and highly-parallelizable algorithms are presented.     

Approximating the Maximum Agreement Forest on k trees

The Maximum Agreement Forest problem (MAF) asks for the largest common subforest of a set of binary trees. This problem is known to be MAXSNP-complete for instances consisting of 2 trees. We show that it remains MAXSNP-complete for k?2 trees.     

The Compatibility of Binary Characters on Phylogenetic Networks: Complexity and Parameterized Algorithms

In a recent article, Nakhleh, Ringe and Warnow introduced perfect phylogenetic networks—a model of language evolution where languages do not evolve via clean speciation—and formulated a set of problems for their accurate reconstruction. Their new methodology assumes networks, rather than trees, as the correct model to capture the evolutionary history of natural languages. They proved the NP-hardness of the problem of testing whether a network is a perfect phylogenetic one for characters exhibiting at least three states, leaving open the case of binary characters, and gave a straightforward brute-force parameterized algorithm for the problem of running time O(3 ^k n), where k is the number of bidirectional edges in the network and n is its size. In this paper, we first establish the NP-hardness of the binary case of the problem. Then we provide a more efficient parameterized algorithm for this case running in time O(2 ^k n ²). The presented algorithm is very simple, and utilizes some structural results and elegant operations developed in this paper that can be useful on their own in the design of heuristic algorithms for the problem. The analysis phase of the algorithm is very elegant using amortized techniques to show that the upper bound on the running time of the algorithm is much tighter than the upper bound obtained under a conservative worst-case scenario assumption. Our results bear significant impact on reconstructing evolutionary histories of languages—particularly from phonological and morphological character data, most of which exhibit at most two states (i.e., are binary), as well as on the design and analysis of parameterized algorithms. Research of I.A. Kanj was supported in part by DePaul University Competitive Research Grant.     

Designing educational software with students through collaborative design games: The We!Design&Play framework

In this paper, we present a framework for the development of collaborative design games that can be employed in participatory design sessions with students for the design of educational applications. The framework is inspired by idea generation theory and the design games literature, and guides the development of board games which, through the use of adequate stimuli, rules and props, facilitate students in extracting and expressing their needs, desires and prospects regarding future educational software. To evaluate the proposed framework three studies were conducted. The first study aimed at the design of a web learning platform with the participation of 62 undergraduate higher education students in 13 design sessions; in the second study, a structured design approach was employed (12 sessions, 54 students) with the same design objective for comparison reasons; in the third study, the framework was deployed for the design of an electronic assessment application so as to examine its applicability in different learning domains (8 design sessions, 28 students). Students were very positive regarding both their participation and experience with the design games, and the needs elicited. The games favored a quick, broad exploration of the design space and facilitated the elicitation of numerous diverse needs and ideas, almost twice as many as produced by the structured approach. They also facilitated the creation of an informal atmosphere and limited the effects of common social influences on idea generation, such as social loafing, evaluation apprehension and production blocking. The three studies indicated that the proposed framework may simplify the development and employment of effective and efficient participatory design sessions in educational settings.     

The Virtual Scylla: an exploration of “serious games”, artificial life and simulation complexity

This paper addresses the integration of artificial life simulations with interactive games-based technologies and describes how the results are being exploited not only for scientific visualisation and education, but also for fundamental research into simulation complexity, focusing on the behavioural representation of species in fragile or long-vanished landscapes and ecosystems. Earlier research is described that supported the development of a virtual recreation of a submerged Mesolithic river valley, discovered during petrochemical surveys of the Southern Basin of the North Sea. Using pollen sample records and vegetation predictions from previous studies, a new alife “engine” was developed that simulated the interaction between “artificialised” vegetation and environmental factors, thus helping researchers to postulate pre-glacial melting migratory and settlement patterns of ancient civilisations from continental Europe to the British Isles. More recently, and to take advantage of the existence of a more accessible and living ecosystem, work has been conducted in collaboration with the UK’s National Marine Aquarium, this time focusing on the Scylla Artificial Reef—a Royal Navy frigate scuttled off the coast of Cornwall in South West England. The resulting “serious games”-based test beds are now providing the foundation for scientific investigations into how models and simulations of marine ecologies behave under different measures of complexity. The exploitation of the artificial life and underwater rendering efforts in others areas, including education and naval training, are also described.     

Students' attitudes toward playing games and using games in education: Comparing Scotland and the Netherlands

Games-based learning has captured the interest of educationalists and industrialists who seek to exploit the characteristics of computer games as they are perceived by some to be a potentially effective approach for teaching and learning. Despite this interest in using games-based learning there is a dearth of empirical evidence supporting the validity of the approach covering the wider context of gaming and education. This study presents a large scale gaming survey, involving 887 students from 13 different Higher Education (HE) institutes in Scotland and the Netherlands, which examines students' characteristics related to their gaming preferences, game playing habits, and their perceptions and thoughts on the use of games in education. It presents a comparison of three separate groups of students: a group in regular education in a Scottish university, a group in regular education in universities in the Netherlands and a distance learning group from a university in the Netherlands. This study addresses an overall research question of: Can computer games be used for educational purposes at HE level in regular and distance education in different countries? The study then addresses four sub-research questions related to the overall research question:

• •What are the different game playing habits of the three groups?
• •What are the different motivations for playing games across the three groups?
• •What are the different reasons for using games in HE across the three groups?
• •What are the different attitudes towards games across the three groups?

To our knowledge this is the first in-depth cross-national survey on gaming and education. We found that a large number of participants believed that computer games could be used at HE level for educational purposes and that further research in the area of game playing habits, motivations for playing computer games and motivations for playing computer games in education are worthy of extensive further investigation. We also found a clear distinction between the views of students in regular education and those in distance education. Regular education students in both countries rated all motivations for playing computer games as significantly more important than distance education students. Also the results suggest that Scottish students aim to enhance their social experience with regards to competition and cooperation, while Dutch students aim to enhance their leisurely experience with regards to leisure, feeling good, preventing boredom and excitement.     

Chameleon: online learning for believable behaviors based on humans imitation in computer games

In some video games, humans and computer programs can play together, each one controlling a virtual humanoid. These computer programs usually aim at replacing missing human players; however, they partially miss their goal, as they can be easily spotted by players as being artificial. Our objective is to find a method to create programs whose behaviors cannot be told apart from players when observed playing the game. We call this kind of behavior a believable behavior. To achieve this goal, we choose models using Markov chains to generate the behaviors by imitation. Such models use probability distributions to find which decision to choose depending on the perceptions of the virtual humanoid. Then, actions are chosen depending on the perceptions and the decision. We propose a new model, called Chameleon , to enhance expressiveness and the associated imitation learning algorithm. We first organize the sensors and motors by semantic refinement and add a focus mechanism in order to improve the believability. Then, we integrate an algorithm to learn the topology of the environment that tries to best represent the use of the environment by the players. Finally, we propose an algorithm to learn parameters of the decision model. Copyright © 2013 John Wiley & Sons, Ltd.     

Analysis of critical factors for social games based on extended technology acceptance model: a DEMATEL approach

In recent years, social games such as ‘Farmville’ and ‘Pokémon Go’ have become a major game type in the gaming industry. This study examines the importance of different factors in social games using the Technology Acceptance Model (TAM) and DEMATEL. The result shows ‘social norm’ as the most important factor overall. It is also found that ‘pleasure’ and ‘sociability’ are the most important aspects in ‘perceived enjoyment’. Regarding key aspects in each factor, ‘flow experience’ is crucial in ‘perceived attractiveness’, ‘game fairness’ largely influential in ‘social norm’, and ‘reputation of platform and service provider’ a decisive aspect in ‘platform service and corporate image’. These findings and analyses are apt references for social game providers to improve their services.