Pseudo-Randomness of Certain Sequences of <Emphasis Type="Italic">k</Emphasis> Symbols with Length <Emphasis Type="Italic">pq</Emphasis>

The theory of finite pseudo-random binary sequences was built by C. Mauduit and A. Sárközy and later extended to sequences of k symbols (or k-ary sequences). Certain constructions of pseudo-random sequences of k symbols were presented over finite fields in the literature. In this paper, two families of sequences of k symbols are constructed by using the integers modulo pq for distinct odd primes p and q. The upper bounds on the well-distribution measure and the correlation measure of the families sequences are presented in terms of certain character sums over modulo pq residue class rings. And low bounds on the linear complexity profile are also estimated.     

A model of best choice under incomplete information

This paper suggests two approaches to the construction of a two-player game of best choice under incomplete information with the choice priority of one player and the equal weights of both players. We consider a sequence of independent identically distributed random variables (x _i , y _i ), i = 1..., n, which represent the quality of incoming objects. The first component is announced to the players and the second component is hidden. Each player chooses an object based on the information available. The winner is the player whose object has a greater sum of the quality components than the opponent’s object. We derive the optimal threshold strategies and compare them for both approaches.     

Simple and efficient local codes for distributed stable network construction

In this work, we study protocols so that populations of distributed processes can construct networks. In order to highlight the basic principles of distributed network construction, we keep the model minimal in all respects. In particular, we assume finite-state processes that all begin from the same initial state and all execute the same protocol. Moreover, we assume pairwise interactions between the processes that are scheduled by a fair adversary. In order to allow processes to construct networks, we let them activate and deactivate their pairwise connections. When two processes interact, the protocol takes as input the states of the processes and the state of their connection and updates all of them. Initially all connections are inactive and the goal is for the processes, after interacting and activating/deactivating connections for a while, to end up with a desired stable network. We give protocols (optimal in some cases) and lower bounds for several basic network construction problems such as spanning line, spanning ring, spanning star, and regular network. The expected time to convergence of our protocols is analyzed under a uniform random scheduler. Finally, we prove several universality results by presenting generic protocols that are capable of simulating a Turing Machine (TM) and exploiting it in order to construct a large class of networks. We additionally show how to partition the population into k supernodes, each being a line of \(\log k\) nodes, for the largest such k. This amount of local memory is sufficient for the supernodes to obtain unique names and exploit their names and their memory to realize nontrivial constructions.     

Quantum secure two-party computation for set intersection with rational players

Recently, Shi et al. (Phys Rev A 92:022309, 2015) proposed quantum oblivious set member decision protocol where two legitimate parties, namely Alice and Bob, play a game. Alice has a secret k, and Bob has a set \(\{k_1,k_2,\ldots k_n\}\). The game is designed towards testing if the secret k is a member of the set possessed by Bob without revealing the identity of k. The output of the game will be either “Yes” (bit 1) or “No” (bit 0) and is generated at Bob’s place. Bob does not know the identity of k, and Alice does not know any element of the set. In a subsequent work (Shi et al in Quant Inf Process 15:363–371, 2016), the authors proposed a quantum scheme for private set intersection (PSI) where the client (Alice) gets the intersected elements with the help of a server (Bob) and the server knows nothing. In the present draft, we extended the game to compute the intersection of two computationally indistinguishable sets X and Y possessed by Alice and Bob, respectively. We consider Alice and Bob as rational players, i.e. they are neither “good” nor “bad”. They participate in the game towards maximizing their utilities. We prove that in this rational setting, the strategy profile ((cooperate, abort), (cooperate, abort)) is a strict Nash equilibrium. If ((cooperate, abort), (cooperate, abort)) is strict Nash, then fairness and correctness of the protocol are guaranteed.     

Energy Efficient Sleep Schedule with Service Coverage Guarantee in Wireless Sensor Networks

Service oriented architecture has been proposed to support collaborations among distributed wireless sensor network (WSN) applications in an open dynamic environment. However, WSNs are resource constraint, and have limited computation abilities, limited communication bandwidth and especially limited energy. Fortunately, sensor nodes in WSNs are usually deployed redundantly, which brings the opportunity to adopt a sleep schedule for balanced energy consumption to extend the network lifetime. Due to miniaturization and energy efficiency, one sensor node can integrate several sense units and support a variety of services. Traditional sleep schedule considers only the constraints from the sensor nodes, can be categorized to a one-layer (i.e., node layer) issue. The service oriented WSNs should resolve the energy optimization issue considering the two-layer constraints, i.e., the sensor nodes layer and service layer. Then, the one-layer energy optimization scheme in previous work is not applicable for service oriented WSNs. Hence, in this paper we propose a sleep schedule with a service coverage guarantee in WSNs. Firstly, by considering the redundancy degree on both the service level and the node level, we can get an accurate redundancy degree of one sensor node. Then, we can adopt fuzzy logic to integrate the redundancy degree, reliability and energy to get a sleep factor. Based on the sleep factor, we furthermore propose the sleep mechanism. The case study and simulation evaluations illustrate the capability of our proposed approach.     

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.     

An efficient protocol for secure multicast key distribution in the presence of adaptive adversaries

In this paper, an efficient construction of multicast key distribution schemes based on semantically secure symmetric-key encryption schemes and cryptographically strong pseudo-random number generators is presented and analyzed. The proposed scheme is provably secure against adaptive adversaries leveraging the security amplification technique defined over the logical key hierarchy structures. Our protocol tolerates any coalition of revoked users; in particular, we do not assume any limit on the size or structure of the coalition. The proposed scheme is efficient as a performance of Join or Leave procedure requires 2 log(N) multicast activities defined over a sibling ancestor node set, 2 log(N) internal state updates of the underlying pseudo-random number generator and 2 log(N) symmetric-key encryption activities for N users in a session.     

Stochastic coalitional better-response dynamics and stable equilibrium

We consider coalition formation among players in an n-player finite strategic game over infinite horizon. At each time a randomly formed coalition makes a joint deviation from a current action profile such that at new action profile all the players from the coalition are strictly benefited. Such deviations define a coalitional better-response (CBR) dynamics that is in general stochastic. The CBR dynamics either converges to a K-stable equilibrium or becomes stuck in a closed cycle. We also assume that at each time a selected coalition makes mistake in deviation with small probability that add mutations (perturbations) into CBR dynamics. We prove that all K-stable equilibria and all action profiles from closed cycles, that have minimum stochastic potential, are stochastically stable. Similar statement holds for strict K-stable equilibrium. We apply the CBR dynamics to study the dynamic formation of the networks in the presence of mutations. Under the CBR dynamics all strongly stable networks and closed cycles of networks are stochastically stable.     

Majority bargaining for resource division

We address the problem of how a set of agents can decide to share a resource, represented as a unit-sized pie. The pie can be generated by the entire set but also by some of its subsets. We investigate a finite horizon non-cooperative bargaining game, in which the players take it in turns to make proposals on how the resource should for this purpose be allocated, and the other players vote on whether or not to accept the allocation. Voting is modelled as a Bayesian weighted voting game with uncertainty about the players’ weights. The agenda, (i.e., the order in which the players are called to make offers), is defined exogenously. We focus on impatient players with heterogeneous discount factors. In the case of a conflict, (i.e., no agreement by the deadline), no player receives anything. We provide a Bayesian subgame perfect equilibrium for the bargaining game and conduct an ex-ante analysis of the resulting outcome. We show that the equilibrium is unique, computable in polynomial time, results in an instant Pareto optimal outcome, and, under certain conditions provides a foundation for the core and also the nucleolus of the Bayesian voting game. In addition, our analysis leads to insights on how an individual’s bargained share is influenced by his position on the agenda. Finally, we show that, if the conflict point of the bargaining game changes, then the problem of determining the non-cooperative equilibrium becomes NP-hard even under the perfect information assumption. Our research also reveals how this change in conflict point impacts on the above mentioned results.     

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 strategies for escaping encirclement

This paper considers a conflict situation on the plane as follows. A fast evader E has to break out the encirclement of slow pursuers P _{j1,...,j n} = {P _j1,..., P _jn }, n ≥ 3, with a miss distance not smaller than r ≥ 0. First, we estimate the minimum guaranteed miss distance from E to a pursuer P _a , a ∈ {j ₁,..., j _n }, when the former moves along a given straight line. Then the obtained results are used to calculate the guaranteed estimates to a group of two pursuers P _b,c = {P _b , P _c }, b, c ∈ {j ₁,..., j _n }, b ≠ c, when E maneuvers by crossing the rectilinear segment P _b P _c , and the state passes to the domain of the game space where E applies a strategy under which the miss distance to any of the pursuers is not decreased. In addition, we describe an approach to the games with a group of pursuers P _{j1,... jn} , n ≥ 3, in which E seeks to break out the encirclement by passing between two pursuers P _b and P _c , entering the domain of the game space where E can increase the miss distance to all pursuers by straight motion. By comparing the guaranteed miss distances with r for all alternatives b, c ∈ {j ₁,..., j _n }, b ≠ c, and a ? {b, c}, it is possible to choose the best alternative and also to extract the histories of the game in which the designed evasion strategies guarantee a safe break out from the encirclement.     

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.     

Object detection in video sequences by a temporal modular self-adaptive SOM

A video segmentation algorithm that takes advantage of using a background subtraction (BS) model with low learning rate (LLR) or a BS model with high learning rate (HLR) depending on the video scene dynamics is presented in this paper. These BS models are based on a neural network architecture, the self-organized map (SOM), and the algorithm is termed temporal modular self-adaptive SOM, TMSA_SOM. Depending on the type of scenario, the TMSA_SOM automatically classifies and processes each video into one of four different specialized modules based on an initial sequence analysis. This approach is convenient because unlike state-of-the-art (SoA) models, our proposed model solves different situations that may occur in the video scene (severe dynamic background, initial frames with dynamic objects, static background, stationary objects, etc.) with a specialized module. Furthermore, TMSA_SOM automatically identifies whether the scene has drastically changed (e.g., stationary objects of interest become dynamic or drastic illumination changes have occurred) and automatically detects when the scene has become stable again and uses this information to update the background model in a fast way. The proposed model was validated with three different video databases: Change Detection, BMC, and Wallflower. Findings showed a very competitive performance considering metrics commonly used in the literature to compare SoA models. TMSA_SOM also achieved the best results on two perceptual metrics, Ssim and D-Score, and obtained the best performance on the global quality measure, FSD (based on F-Measure, Ssim, and D-Score), demonstrating its robustness with different and complicated non-controlled scenarios. TMSA_SOM was also compared against SoA neural network approaches obtaining the best average performance on Re, Pr, and F-Measure.     

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.     

Interactive Restless Multi-armed Bandit Game and Swarm Intelligence Effect

We obtain the conditions for the emergence of the swarm intelligence effect in an interactive game of restless multi-armed bandit (rMAB). A player competes with multiple agents. Each bandit has a payoff that changes with a probability p _c per round. The agents and player choose one of three options: (1) Exploit (a good bandit), (2) Innovate (asocial learning for a good bandit among n _I randomly chosen bandits), and (3) Observe (social learning for a good bandit). Each agent has two parameters (c, p _obs ) to specify the decision: (i) c, the threshold value for Exploit, and (ii) p _obs , the probability for Observe in learning. The parameters (c, p _obs ) are uniformly distributed. We determine the optimal strategies for the player using complete knowledge about the rMAB. We show whether or not social or asocial learning is more optimal in the (p _c , n _I ) space and define the swarm intelligence effect. We conduct a laboratory experiment (67 subjects) and observe the swarm intelligence effect only if (p _c , n _I ) are chosen so that social learning is far more optimal than asocial learning.     

Resource allocation in cooperative cognitive radio networks towards secure communications for maritime big data systems

In this paper, an innovative framework labeled as cooperative cognitive maritime big data systems (CCMBDSs) on the sea is developed to provide opportunistic channel access and secure communication. A two-phase frame structure is applied to let Secondary users (SUs) entirely utilize the transmission opportunities for a portion of time as the reward by cooperation with Primary users (PUs). Amplify-and-forward (AF) relaying mode is exploited in SU nodes, and Backward induction method based Stackelberg game is employed to achieve optimal determination of SU, power consumption and time portion of cooperation both for non-secure communication scenario and secure communication. Specifically, a jammer-based secure communications scheme is developed to maximize the secure utility of PU, to confront of the situation that the eavesdropper could overheard the signals from SU _i and the jammer. Close-form solutions for the best access time portion as well as the power for SU _i and jammer are derived to realize the Nash Equilibrium. Simulation results validate the effectiveness of our proposed strategy.     

Partial and complete local diagnosis in computer systems with circulant structure

System diagnosis at multiple faults of multiplicity not greater than t is considered. The conditions when the state of each system module is only determined by the testing rusults of the physically connected modules (self-determination conditions) are analysed. The diagnosability conditions are established for the case when the self-determination conditions are not satisfied for any module. A new class of locally (t _r /t)-diagnosable systems is introduced, where t is the fault multiplicity and t _r is the multiplicity of faults at which the states of all system modules can be determined correctly and completely. The values of t _r are estimated. It is shown that the local t-diagnosability can be achieved by the system test redundancy.     

The pursuit-evasion game on the 1-skeleton graph of a regular polyhedron. I

We consider a game between a group of n pursuers and one evader moving with the same maximum velocity along the 1-skeleton graph of a regular polyhedron. The goal of the paper is finding, for each regular polyhedron M, a number N(M) with the following properties: if n ≥ N(M), the group of pursuers wins, while if n < N(M), the evader wins. Part I of the paper is devoted to the case of polyhedra in ?³; Part II will be devoted to the case of ? ^d , d ≥ 5; and Part III, to the case of ?⁴.     

Virtual reality software package for implementing motor learning and rehabilitation experiments

Virtual reality games for rehabilitation are attracting increasing growth. In particular, there is a demand for games that allow therapists to identify an individual’s difficulties and customize the control of variables, such as speed, size, distance, as well as visual and auditory feedback. This study presents and describes a virtual reality software package (Bridge Games) to promote rehabilitation of individuals living with disabilities and highlights preliminary researches of its use for implementing motor learning and rehabilitation. First, the study presents seven games in the software package that can be chosen by the rehabilitation team, considering the patient’s needs. All game characteristics are described including name, function presentation, objective and valuable measurements for rehabilitation. Second, preliminary results illustrate some applications of two games, considering 343 people with various disabilities and health status. Based on the results, in the Coincident Timing game, there was a main effect of movement sensor type (in this instance the most functional device was the keyboard when compared with Kinect and touch screen) on average time reached by sample analyzed, F(2, 225) = 4.42, p < 0.05. Similarly, in the Challenge! game, a main effect was found for movement sensor type. However, in this case, touch screen provided better performance than Kinect and Leap Motion, F(2, 709) = 5.90, p < 0.01. Thus, Bridge Games is a possible software game to quantify motor learning. Moreover, the findings suggest that motor skills might be practiced differently depending on the environmental interface in which the game may be used.     

A formal algorithmic language FALGOL. Thirty years after

FALGOL (Formal ALGOrithmic Language) is a fundamental theoretical model of high-level operational languages with unrestricted program object hierarchy. This model formalizes binding, assignment, substitution, and recursion; moreover, the principle of dynamic binding is implemented in the model in contrast to other formal systems of this sort, which makes FALGOL appropriate to specify the most difficultly formalized concepts in modern object programming languages.