Exact and heuristic methods for solving Boolean games

Boolean games are a framework for reasoning about the rational behavior of agents whose goals are formalized using propositional formulas. Compared to normal form games, a well-studied and related game framework, Boolean games allow for an intuitive and more compact representation of the agents’ goals. So far, Boolean games have been mainly studied in the literature from the Knowledge Representation perspective, and less attention has been paid on the algorithmic issues underlying the computation of solution concepts. Although some suggestions for solving specific classes of Boolean games have been made in the literature, there is currently no work available on the practical performance. In this paper, we propose the first technique to solve general Boolean games that does not require an exponential translation to normal-form games. Our method is based on disjunctive answer set programming and computes solutions (equilibria) of arbitrary Boolean games. It can be applied to a wide variety of solution concepts, and can naturally deal with extensions of Boolean games such as constraints and costs. We present detailed experimental results in which we compare the proposed method against a number of existing methods for solving specific classes of Boolean games, as well as adaptations of methods that were initially designed for normal-form games. We found that the heuristic methods that do not require all payoff matrix entries performed well for smaller Boolean games, while our ASP based technique is faster when the problem instances have a higher number of agents or action variables.

Using Answer Set Programming for Solving Boolean Games

Boolean games are a framework for reasoning about the rational behaviour of agents, whose goals are formalized using propositional formulas. They offer an attractive alternative to normal-form games, because they allow for a more intuitive and more compact encoding. Unfortunately, however, there is currently no general, tailor-made method available to compute the equilibria of Boolean games. In this paper, we introduce a method for finding the pure Nash equilibria based on disjunctive answer set programming. Our method is furthermore capable of finding the core elements and the Pareto optimal equilibria, and can easily be modified to support other forms of optimality, thanks to the declarative nature of disjunctive answer set programming. Experimental results clearly demonstrate the effectiveness of the proposed method.

Decentralized Computation of Pareto Optimal Pure Nash Equilibria of Boolean Games with Privacy Concerns

In Boolean games, agents try to reach a goal formulated as a Boolean formula. These games are attractive because of their compact representations. However, few methods are available to compute the solutions and they are either limited or do not take privacy or communication concerns into account. In this paper we propose the use of an algorithm related to reinforcement learning to address this problem. Our method is decentralized in the sense that agents try to achieve their goals without knowledge of the other agents’ goals. We prove that this is a sound method to compute a Pareto optimal pure Nash equilibrium for an interesting class of Boolean games. Experimental results are used to investigate the performance of the algorithm.

Synthesis of novel pyrophosphorothiolate-linked dinucleoside cap analogues in a ball mill

Michaelis–Arbuzov reactions of S-aryl disulfide derivatives of 3′-thiothymidine or 5′-thioadenosine with tris(trimethylsilyl) phosphite proceeded in high yields to the corresponding phosphorothiolate monoesters. Subsequent hydrolytic desilylation and phosphate coupling were effected in one-pot using liquid-assisted grinding in a vibration ball mill. Novel 3′,5′- and 5′,5′-pyrophosphorothiolate-linked dinucleoside cap analogues were thereby prepared.

Think, code, succeed: The Programming Studio as a games-based collaboration:Paper published in the Proceedings of the Association for Teacher Education in Europe conference: Teacher Education through Partnerships and Collaborative Learning Communities, Glasgow, UK. ATEE, 2015

This paper investigates the profile of teachers in the island of Ireland who declared themselves willing to undertake professional development activities in programming, in particular to master programming by taking on-line courses involving the design of computer games. Using the Technology Acceptance Model (TAM), it compares scores for teachers “willing” to undertake the courses with scores for those who declined, and examines other differences between the groups of respondents. Findings reflect the perceived difficulties of programming and the current low status accorded to the subject in Ireland. The paper also reviews the use of games-based learning as a “hook” to engage learners in programming and discusses the role of gamification as a tool for motivating learners in an on-line course. The on-line course focusing on games design was met with enthusiasm, and there was general consensus that gamification was appropriate for motivating learners in structured courses such as those provided.

Scaled Heavy-Ball Acceleration of the Richardson-Lucy Algorithm for 3D Microscopy Image Restoration

The Richardson–Lucy algorithm is one of the most important in image deconvolution. However, a drawback is its slow convergence. A significant acceleration was obtained using the technique proposed by Biggs and Andrews (BA), which is implemented in the deconvlucy function of the image processing MATLAB toolbox. The BA method was developed heuristically with no proof of convergence. In this paper, we introduce the heavy-ball (H-B) method for Poisson data optimization and extend it to a scaled H-B method, which includes the BA method as a special case. The method has a proof of the convergence rateof O(K^2), where k is the number of iterations. We demonstrate the superior convergence performance, by a speedup factor off ive, of the scaled H-B method on both synthetic and real 3D images.

Comparing lateral bias in dogs and humans using the KongTM ball test

The KongTM ball test has been used extensively to assess lateral bias in the domestic dog. Implicit in this challenge is the assumption that dogs use their dominant paw to stabilise the ball. This study examined whether or not this is the case. A comparative approach was adopted, exploring limb use in dogs and humans. In Experiment 1, the paw preference of 48 dogs was assessed on the KongTM ball test. Analysis revealed an equal distribution of paw use, although significantly more dogs were paw-preferent than ambilateral. Significantly more male dogs were classified as right-pawed, while more females were ambilateral. There was no significant effect of canine sex or castration status on the dogs’ paw preferences. In Experiment 2, 94 adult humans were assessed on their ability to remove a piece of paper from a KongTM ball with their mouth, using their left, right or both hands to stabilise the ball. 76% of the right-handed people used their left hand, and 82% of the left-handed participants used their right hand, to hold the KongTM steady. It is concluded that dogs, like humans, are most likely using their non-dominant limb to stabilise the KongTM ball and their dominant side for postural support. This has potential applied implications from an animal welfare perspective.