The bounded core for games with restricted cooperation

A game with restricted (incomplete) cooperation is a triple (N, v, Ω), where N represents a finite set of players, Ω ? 2^N is a set of feasible coalitions such that N ∈ Ω, and v: Ω → R denotes a characteristic function. Unlike the classical TU games, the core of a game with restricted cooperation can be unbounded. Recently Grabisch and Sudhölter [9] proposed a new solution concept—the bounded core—that associates a game (N, v,Ω) with the union of all bounded faces of the core. The bounded core can be empty even if the core is nonempty. This paper gives two axiomatizations of the bounded core. The first axiomatization characterizes the bounded core for the class G^r of all games with restricted cooperation, whereas the second one for the subclass G_bc^r ? G^r of the games with nonempty bounded cores.     

Procedural content generation for platformers: designing and testing FUN PLEdGE

Video games are a peculiar medium, standing at the crossing point between art and software application, and characterized by an active involvement of its audience. The complexity of the product generates a huge challenge for the companies that develop video games. In the development process, level designers play a crucial role: they are in charge of declining the theoretical framework developed by the game designer into game levels, which contain the actual gameplay scenarios. Hence, the final goal of any level designer is to valorize the game design by creating enjoyable gaming experiences while, at the same time, respecting several constraints. To lighten the burden on level designers, several semi-automated approaches to level generation have appeared in time, but the majority of these tools suffer from several drawbacks. In the present work, we tackle the issue of designing, prototyping and testing FUN PLEdGE, a general-purpose automated levels generator and editor for platform video games. Its main goal is to shrink development time while producing – unassisted – levels that are both playable and fun. Moreover, our tool provides the maximum freedom to the level designer, by avoiding to impose unnecessary constraints on the structure of the levels and by guaranteeing the possibility to modify and personalize by hand the generated levels. During this process, the generator assists the designer by suggesting corrections functional to the quality of the player experience. To prove the effectiveness of our prototypal application we have also developed and tested with players a platform game. In the same vein, we asked to a group of game developers to test FUN PLEdGE.     

On the effect of quantum noise in a quantum prisoner’s dilemma cellular automaton

The disrupting effect of quantum noise on the dynamics of a spatial quantum formulation of the iterated prisoner’s dilemma game with variable entangling is studied in this work. The game is played in the cellular automata manner, i.e., with local and synchronous interaction. It is concluded in this article that quantum noise induces in fair games the need for higher entanglement in order to make possible the emergence of the strategy pair (Q, Q), which produces the same payoff of mutual cooperation. In unfair quantum versus classic player games, quantum noise delays the prevalence of the quantum player.     

Star reduction among minimal length addition chains

An addition chain for a natural number n is a sequence \({1=a_0 < a_1 < \cdots < a_r=n}\) of numbers such that for each 0 < i ≤ r, a _i  = a _j  + a _k for some 0 ≤ k ≤ j < i. The minimal length of an addition chain for n is denoted by ?(n). If j = i ? 1, then step i is called a star step. We show that there is a minimal length addition chain for n such that the last four steps are stars. Then we conjecture that there is a minimal length addition chain for n such that the last \({\lfloor\frac{\ell(n)}{2}\rfloor}\)-steps are stars. We verify that the conjecture is true for all numbers up to 2¹⁸. An application of the result and the conjecture to generate a minimal length addition chain reduce the average CPU time by 23–29% and 38–58% respectively, and memory storage by 16–18% and 26–45% respectively for m-bit numbers with 14 ≤ m ≤ 22.     

When Can Limited Randomness Be Used in Repeated Games?

The central result of classical game theory states that every finite normal form game has a Nash equilibrium, provided that players are allowed to use randomized (mixed) strategies. However, in practice, humans are known to be bad at generating random-like sequences, and true random bits may be unavailable. Even if the players have access to enough random bits for a single instance of the game their randomness might be insufficient if the game is played many times. In this work, we ask whether randomness is necessary for equilibria to exist in finitely repeated games. We show that for a large class of games containing arbitrary two-player zero-sum games, approximate Nash equilibria of the n-stage repeated version of the game exist if and only if both players have Ω(n) random bits. In contrast, we show that there exists a class of games for which no equilibrium exists in pure strategies, yet the n-stage repeated version of the game has an exact Nash equilibrium in which each player uses only a constant number of random bits. When the players are assumed to be computationally bounded, if cryptographic pseudorandom generators (or, equivalently, one-way functions) exist, then the players can base their strategies on “random-like” sequences derived from only a small number of truly random bits. We show that, in contrast, in repeated two-player zero-sum games, if pseudorandom generators do not exist, then Ω(n) random bits remain necessary for equilibria to exist.     

Mean field games based on stable-like processes

We investigate the mean field games of N agents based on the nonlinear stable-like processes. The main result of the paper is that any solution of the limiting mean field consistency equation generates a 1/N-Nash equilibrium for the approximating game of N agents.     

Error bounds for complementarity problems with tridiagonal nonlinear functions

In this paper we consider the complementarity problem NCP(f) with f(x) = Mx + φ(x), where M ∈ R ^n×n is a real matrix and φ is a so-called tridiagonal (nonlinear) mapping. This problem occurs, for example, if certain classes of free boundary problems are discretized. We compute error bounds for approximations \({\hat x}\) to a solution x* of the discretized problems. The error bounds are improved by an iterative method and can be made arbitrarily small. The ideas are illustrated by numerical experiments.     

On the <Emphasis Type="Italic">k</Emphasis>-accessibility of cores of <Emphasis Type="Italic">TU</Emphasis>-cooperative games

This paper proposes a strengthening of the author’s core-accessibility theorem for balanced TU-cooperative games. The obtained strengthening relaxes the influence of the nontransitivity of classical domination αv on the quality of the sequential improvement of dominated imputations in a game v. More specifically, we establish the k-accessibility of the core C(α _v ) of any balanced TU-cooperative game v for all natural numbers k: for each dominated imputation x, there exists a converging sequence of imputations x₀, x₁,..., such that x₀ = x, lim x _r ∈ C(α _v ) and x_r?m is dominated by any successive imputation x _r with m ∈ [1, k] and r ≥ m. For showing that the TU-property is essential to provide the k-accessibility of the core, we give an example of an NTU-cooperative game G with a ”black hole” representing a nonempty closed subset B ? G(N) of dominated imputations that contains all the α _G -monotonic sequential improvement trajectories originating at any point x ∈ B.     

Endogenous games with goals: side-payments among goal-directed agents

Boolean games have been developed as a paradigm for modelling societies of goal-directed agents. In boolean games agents exercise control over propositional variables and strive to achieve a goal formula whose realization might require the opponents’ cooperation. The presence of agents that are goal-directed makes it difficult for an external authority to be able to remove undesirable properties that are inconsistent with agents’ goals, as shown by recent contributions in the multi-agent literature. What this paper does is to analyse the problem of regulation of goal-direct agents from within the system, i.e., what happens when agents themselves are given the chance to negotiate the strategies to be played with one another. Concretely, we introduce endogenous games with goals, obtained coupling a general model of goal-directed agents (strategic games with goals) with a general model of pre-play negotiations (endogenous games) coming from game theory. Strategic games with goals are shown to have a direct correspondence with strategic games (Proposition 1) but, when side-payments are allowed in the pre-play phase, display a striking imbalance (Proposition 4). The effect of side-payments can be fully simulated by taxation mechanisms studied in the literature (Proposition 7), yet we show sufficient conditions under which outcomes can be rationally sustained without external intervention (Proposition 5). Also, integrating taxation mechanisms and side-payments, we are able to transform our starting models in such a way that outcomes that are theoretically sustainable thanks to a pre-play phase can be actually sustained even with limited resources (Proposition 8). Finally, we show how an external authority incentivising a group of agents can be studied as a special agent of an appropriately extended endogenous game with goals (Proposition 11).     

Power and welfare in bargaining for coalition structure formation

We investigate a noncooperative bargaining game for partitioning n agents into non-overlapping coalitions. The game has n time periods during which the players are called according to an exogenous agenda to propose offers. With probability \(\delta \), the game ends during any time period \(t<n\). If it does, the first t players on the agenda get a chance to propose but the others do not. Thus, \(\delta \) is a measure of the degree of democracy within the game (ranging from democracy for \(\delta =0\), through increasing levels of authoritarianism as \(\delta \) approaches 1, to dictatorship for \(\delta =1\)). We determine the subgame perfect equilibrium (SPE) and study how a player’s position on the agenda affects his bargaining power. We analyze the relation between the distribution of power of individual players, the level of democracy, and the welfare efficiency of the game. We find that purely democratic games are welfare inefficient and that introducing a degree of authoritarianism into the game makes the distribution of power more equitable and also maximizes welfare. These results remain invariant under two types of player preferences: one where each player’s preference is a total order on the space of possible coalition structures and the other where each player either likes or dislikes a coalition structure. Finally, we show that the SPE partition may or may not be core stable.     

Guaranteed approach with the farthest of the runaways

Games of the family {Λ _N } _N?2 are formulated and studied with the application of generalized Isaacs’s approach. The game Λ _N is a simplest model of the counteraction of one persecutor P and coalition N of E ^N runaways for the case when the payoff is the distance up to the coalition of E ^N equal to the Euclidean distance between P and the farthest from the runaways; P is in command of the termination moment. Moreover, an approach within the limits of which in games with a smooth terminal payoff are generated strategies prescribing players’ motions in the directions of local gradients of the payoff is described. The approach is used for constructing pursuit strategies in games in which smooth approximations of the maximum of Euclidean distances up to the runaways are in place of payoffs. Pursuit strategies prescribing the motion in the direction of the farthest of the runaways are studied. A numerical simulation of the development of the games Λ₂ and Λ₃ is conducted in using different strategies by the players.     

Another Sub-exponential Algorithm for the Simple Stochastic Game

We study the problem of solving simple stochastic games, and give both an interesting new algorithm and a hardness result. We show a reduction from fine approximation of simple stochastic games to coarse approximation of a polynomial sized game, which can be viewed as an evidence showing the hardness to approximate the value of simple stochastic games. We also present a randomized algorithm that runs in \(\tilde{O}(\sqrt{|V_{\mathrm{R}}|!})\) time, where |V _R| is the number of RANDOM vertices and \(\tilde{O}\) ignores polynomial terms. This algorithm is the fastest known algorithm when |V _R|=ω(log?n) and \(|V_{\mathrm{R}}|=o(\sqrt{\min{|V_{\min}|,|V_{\max}|}})\) and it works for general (non-stopping) simple stochastic games.     

An orthogonal analysis method for decoupling the nozzle geometrical parameters of microthrusters

This paper proposes an orthogonal analysis method for decoupling the multiple nozzle geometrical parameters of microthrusters, thus an reconfigured design can be implemented to generate a proper thrust. In this method, the effects of various nozzle geometrical parameters, including throat width W _t , half convergence angle θ _in , half divergence angle θ _out , exit-to-throat section ratio W _e /W _t and throat radius of the curvature R _t /W _t , on the performance of microthrusters are sorted by range analysis. Analysis results show that throat width seriously affects thrust because range value of 67.53 mN is extremely larger than the range value of other geometry parameters. For average specific impulse (ASI), the range value of exit-to-throat section ratio W _e /W _t and half divergence angle θ _out are 4.82 s and 3.72 s, respectively. Half convergence angle with the range value of 0.39 s and throat radius with 0.32 s have less influence on ASI compared with exit-to-throat section ratio and half divergence angle. When increasing the half convergence angle from 10° to 40° and throat radius of the curvature from 3 to 9, average specific impulse initially decreases and then increases. A MEMS solid propellant thruster (MSPT) with the reconfigured geometrical parameters of nozzle is fabricated to verify the feasibility of the proposed method. The thrust of the microthruster can reach 25 mN. Power is estimated to be 0.84 W. This work provides design guideline to reasonably configure geometry parameters of microthruster.     

A cellular automaton for blocking queen games

We show that the winning positions of a certain type of two-player game form interesting patterns which often defy analysis, yet can be computed by a cellular automaton. The game, known as Blocking Wythoff Nim, consists of moving a queen as in chess, but always towards (0, 0), and it may not be moved to any of \(k-1\) temporarily “blocked” positions specified on the previous turn by the other player. The game ends when a player wins by blocking all possible moves of the other player. The value of k is a parameter that defines the game, and the pattern of winning positions can be very sensitive to k. As k becomes large, parts of the pattern of winning positions converge to recurring chaotic patterns that are independent of k. The patterns for large k display an unprecedented amount of self-organization at many scales, and here we attempt to describe the self-organized structure that appears. This paper extends a previous study (Cook et al. in Cellular automata and discrete complex systems, AUTOMATA 2015, Lecture Notes in Computer Science, vol 9099, pp 71–84, 2015), containing further analysis and new insights into the long term behaviour and structures generated by our blocking queen cellular automaton.     

Altruistic behavior in a nonantagonistic positional differential game

We consider a two-person nonantagonistic positional differential game (NPDG) whose dynamics is described by an ordinary nonlinear vector differential equation. Constraints on values of players’ controls are geometric. Final time of the game is fixed. Payoff functionals of both players are terminal. The formalization of positional strategies in an NPDG is based on the formalization and results of the general theory of antagonistic positional differential games (APDGs) (see monographs by N.N. Krasovskii and A.I. Subbotin [3, 4]). Additionally, in the present paper we assume that each player, together with the usual, normal (nor), type of behavior aimed at maximizing his own functional, can use other behavior types introduced in [2, 5]. In particular, these may be altruistic (alt), aggressive (agg), and paradoxical (par) types. It is assumed that in the course of the game players can switch their behavior from one type to another. Using the possibility of such switches in a repeated bimatrix 2 × 2 game in [5, 6] allowed to obtain new solutions of this game. In the present paper, extension of this approach to NPDGs leads to a new formulation of the problem. In particular, of interest is the question of how players’ outcomes at Nash solutions are transformed. An urgent problem is minimizing the time of “abnormal” behavior while achieving a good result. The paper proposes a formalization of an NPDG with behavior types (NPDGwBT). It is assumed that in an NPDGwBT each player, simultaneously with choosing a positional strategy, chooses also his own indicator function defined on the whole game horizon and taking values in the set {normal, altruistic, aggressive, paradoxical}. The indicator function of a player shows the dynamics of changes in the behavior type demonstrated by the player. Thus, in this NPDGwBT each player controls the choice of a pair {positional strategy, indicator function}. We define the notion of a BT-solution of such a game. It is expected that using behavior types in the NPDGwBT which differ from the normal one (so-called abnormal types) in some cases may lead to more favorable outcomes for the players than in the NPDG. We consider two examples of an NPDGwBT with simple dynamics in the plane in each of which one player keeps to altruistic behavior type over some time period. It is shown that in the first example payoffs of both players increase on a BT-solution as compared to the game with the normal behavior type, and in the second example, the sum of players’ payoffs is increased.     

Filtration of aerosol particles by cylindrical fibers within a parallel and staggered array

The World Health Organization (WHO) in 2013 reported that more than seven million unexpected losses every year are credited to air contamination. Because of incredible adaptability and expense viability of fibrous filters, they are broadly used for removing particulates from gasses. The influence of appropriate parameters, e.g., the fiber arrangement, solid volume fraction (SVF or α), fluid flow face velocity (mean inlet velocity), and filter thickness (I _x ), on pressure drop and deposition efficiency are researched. Furthermore, to study the effects of variation of the laminar flow regime and fiber’s cross-sectional shape on the deposition of particles, only a single square fiber has been placed in a channel. By means of finite volume method (FVM), the 2-D motion of 100–1000 nm particles was investigated numerically. The Lagrangian method has been employed and the Saffman’s lift, Drag, and Brownian forces have been considered to affect this motion. Contribution of increasing the Reynolds number to filtration performance increased with smaller fine aerosols to a level of 59.72 %. However, for over 500 nm, the Re = 100 has more efficient results up to 26.97 %. Remarkably, the single square fiber in Re = 200 regime performs similarly to the optimum choice of multi-fibrous filters. It was portrayed the parallel circular multi-fibrous filter with a ratio of horizontal-to-vertical distances between fibers, l/h = 1.143; α = 0.687, I _x  = 116.572, and h/d _f  = 1.0 is the most efficient filter’s structure. The increase in the ratio of vertical distances between fibers-to-fiber’s diameter (h/d _f ) and decrease in SVF or α, results in a drastically decrement of the filtration performance of both parallel and staggered structures. The obtained results have been validated with previous research findings.     

Threshold quantum secret sharing based on single qubit

Based on unitary phase shift operation on single qubit in association with Shamir’s (t, n) secret sharing, a (t, n) threshold quantum secret sharing scheme (or (t, n)-QSS) is proposed to share both classical information and quantum states. The scheme uses decoy photons to prevent eavesdropping and employs the secret in Shamir’s scheme as the private value to guarantee the correctness of secret reconstruction. Analyses show it is resistant to typical intercept-and-resend attack, entangle-and-measure attack and participant attacks such as entanglement swapping attack. Moreover, it is easier to realize in physic and more practical in applications when compared with related ones. By the method in our scheme, new (t, n)-QSS schemes can be easily constructed using other classical (t, n) secret sharing.     

Using neural networks to integrate structural analysis package and optimization package

To solve structural optimization problems, it is necessary to integrate a structural analysis package and an optimization package. Since most structural analysis packages suffer from closeness of system, it is very difficult to integrate it with an optimization package. To overcome the difficulty, we propose a possible alternative, DAMDO, which integrate Design, Analysis, Modeling, Definition, and Optimization phases into an integration environment as follows. (1) Design first generate many possible structural design alternatives. Each design alternative consists of many design variables X. (2) Analysis employ the structural analysis software to analyze all structural design alternatives to obtain their internal forces and displacements. They are the response variables Y. (3) Modeling employ artificial neural networks to build model Y = f(X) to obtain the relationship functions between the design variables X and the response variables Y. (4) Definition employ the design variables X and the response variables Y to define the objective function and constraint functions. (5) Optimization employ the optimization software to solve the optimization problem consisting of the objective function and the constraint functions to produce the optimum design variables X*. Optimization of truss structures was used to validate the DAMDO approach. The empirical results show that the truss optimization problems can be solved by the DAMDO approach, which employ neural networks to integrate the structural analysis package and optimization package without requiring direct integration of the two packages. This approach is promising in many engineering optimization domains which need to couple an analysis package and an optimization one to obtain the optimum solutions.     

On an approach to constructing a characteristic function in cooperative differential games

We propose a novel approach to constructing characteristic functions in cooperative differential games. A characteristic function of a coalition S is computed in two stages: first, optimal control strategies maximizing the total payoff of the players are found, and next, these strategies are used by the players from the coalition S, while the other players, those from N S, use strategies minimizing the total payoff of the players from S. The characteristic function obtained in this way is superadditive. In addition, it possesses a number of other useful properties. As an example, we compute values of a characteristic function for a specific differential game of pollution control.