Inspection games in arms control

An inspection game is a mathematical model of a situation in which an inspector verifies the adherence of an inspectee to some legal obligation, such as an arms control treaty, where the inspectee may have an interest in violating that obligation. The mathematical analysis seeks to determine an optimal inspection scheme, ideally one which will induce legal behavior, under the assumption that the potential illegal action is carried out strategically; thus a non-cooperative game with two players, inspector and inspectee, is defined. Three phases of development in the application of such models to arms control and disarmament may be identified. In the first of these, roughly from 1961 through 1968, studies that focused on inspecting a nuclear test ban treaty emphasized game theory, with less consideration given to statistical aspects associated with data acquisition and measurement uncertainty. The second phase, from 1968 to about 1985, involves work stimulated by the Treaty on the Non-Proliferation of Nuclear Weapons (NPT). Here, the verification principle of material accountancy came to the fore, along with the need to include the formalism of statistical decision theory within the inspection models. The third phase, 1985 to the present, has been dominated by challenges posed by such far-reaching verification agreements as the Intermediate Range Nuclear Forces Agreement (INF), the Treaty on Conventional Forces in Europe (CFE) and the Chemical Weapons Convention (CWC), as well as perceived failures of the NPT system in Iraq and North Korea. In this connection, the interface between the political and technical aspects of verification is being examined from the game-theoretic viewpoint.     

Equilibrium analysis in batch-arrival queues with complementary services

This paper studies a batch-arrival queue with two complementary services. The two services are complementary and any customer has no benefit from obtaining just one of them. To the best of the authors’ knowledge, there are no works contributed to the batch-arrival queues on analysis of the equilibrium behaviors in queueing systems by now. The properties of batch-arrival queues, which is more practical and universal in reality, induce different Nash equilibria under competition or monopoly compared with the single-arrival queues. We observe the joint effect of batch joining rate and cost structure on the behavior of customers and graphically interpret the equilibrium solutions under competition. Moreover, we discuss the model under three types of price structures and give comparisons from customer and server points.     

Opportunistic timing and manipulation in Australian Federal Elections

In many parliamentary systems, election timing is an important decision made by governments in order to maximize their expected remaining life in power. Governments can also introduce policy or economic actions to enhance their popular standing and thus their chance of being re-elected. On the other hand, an oppositions’ natural objective is to gain power, and they will also apply controls through their own policies to reduce the governments’ chance of being re-elected. In this paper we employ a dynamic programming approach to determine the optimal timing for governments and oppositions to best utilize their limited resources. At each decision branch, the optimal control is interpreted as a Nash–Cournot equilibrium of a zero-sum political game which, in certain states, admits mixed strategy solutions. We perform a case study on the Australian Federal Election for House of Representatives.     

Promoting cooperation in selfish computational grids

In distributed computing, the recent paradigm shift from centrally-owned clusters to organizationally distributed computational grids introduces a number of new challenges in resource management and scheduling. In this work, we study the problem of Selfish Load Balancing which extends the well-known load balancing (LB) problem to scenarios in which each processor is concerned only with the performance of its local jobs. We propose a simple mathematical model for such systems and a novel function for computing the cost of the execution of foreign jobs. Then, we use the game-theoretic framework to analyze the model in order to compute the expected result of LB performed in a grid formed by two clusters. We show that, firstly, LB is a socially-optimal strategy, and secondly, for similarly loaded clusters, it is sufficient to collaborate during longer time periods in order to make LB the dominant strategy for each cluster. However, we show that if we allow clusters to make decisions depending on their current queue length, LB will never be performed. Then, we propose a LB algorithm which balances the load more equitably, even in the presence of overloaded clusters. Our algorithms do not use any external forms of compensation (such as money). The load is balanced only by considering the parameters of execution of jobs. This analysis is assessed experimentally by simulation, involving scenarios with multiple clusters and heterogeneous load.     

Equilibria of two-sided matching games with common preferences

Problems of matching have long been studied in the operations research literature (assignment problem, secretary problem, stable marriage problem). All of these consider a centralized mechanism whereby a single decision maker chooses a complete matching which optimizes some criterion. This paper analyzes a more realistic scenario in which members of the two groups (buyers–sellers, employers–workers, males–females) randomly meet each other in pairs (interviews, dates) over time and form couples if there is mutual agreement to do so. We assume members of each group have common preferences over members of the other group. Generalizing an earlier model of Alpern and Reyniers [Alpern, S., Reyniers, D.J., 2005. Strategic mating with common preferences. J. Theor. Biol. 237, 337–354], we assume that one group (called males) is r   times larger than the other, r?1$r?1$. Thus all females, but only 1/r$1/r$ of the males, end up matched. Unmatched males have negative utility -c$-c$. We analyze equilibria of this matching game, depending on the parameters r   and c$c$. In a region of (r,c)$(r\text{,}c)$ space with multiple equilibria, we compare these, and analyze their ‘efficiency’ in several respects. This analysis should prove useful for designers of matching mechanisms who have some control over the sex ratio (e.g. by capping numbers of males at a ‘singles event’or by having ‘ladies free’ nights) or the nonmating cost c (e.g. tax benefits to married couples).     

Pure subgame-perfect equilibria in free transition games

We consider a class of stochastic games, where each state is identified with a player. At any moment during play, one of the players is called active. The active player can terminate the game, or he can announce any player, who then becomes the active player. There is a non-negative payoff for each player upon termination of the game, which depends only on the player who decided to terminate. We give a combinatorial proof of the existence of subgame-perfect equilibria in pure strategies for the games in our class.     

Nash equilibria in all-optical networks

We consider the problem of routing a number of communication requests in WDM (wavelength division multiplexing) all-optical networks from the standpoint of game theory. If we view each routing request (pair of source-target nodes) as a player, then a strategy consists of a path from the source to the target and a frequency (color). To reflect the restriction that two requests must not use the same frequency on the same edge, conflicting strategies are assigned a prohibitively high cost.Under this formulation, we consider several natural cost functions, each one reflecting a different aspect of restriction in the available bandwidth. For each cost function we examine the problem of the existence of pure Nash equilibria, the complexity of recognizing and computing them and finally, the problem in which we are given a Nash equilibrium and we are asked to find a better one in the sense that the total bandwidth used is less. As it turns out some of these problems are tractable and others are NP-hard.     

Game-perfect graphs

A graph coloring game introduced by Bodlaender (Int J Found Comput Sci 2:133–147, 1991) as coloring construction game is the following. Two players, Alice and Bob, alternately color vertices of a given graph G with a color from a given color set C, so that adjacent vertices receive distinct colors. Alice has the first move. The game ends if no move is possible any more. Alice wins if every vertex of G is colored at the end, otherwise Bob wins. We consider two variants of Bodlaender’s graph coloring game: one (A) in which Alice has the right to have the first move and to miss a turn, the other (B) in which Bob has these rights. These games define the A-game chromatic number resp. the B-game chromatic number of a graph. For such a variant g, a graph G is g-perfect if, for every induced subgraph H of G, the clique number of H equals the g-game chromatic number of H. We determine those graphs for which the game chromatic numbers are 2 and prove that the triangle-free B-perfect graphs are exactly the forests of stars, and the triangle-free A-perfect graphs are exactly the graphs each component of which is a complete bipartite graph or a complete bipartite graph minus one edge or a singleton. From these results we may easily derive the set of triangle-free game-perfect graphs with respect to Bodlaender’s original game. We also determine the B-perfect graphs with clique number 3. As a general result we prove that complements of bipartite graphs are A-perfect.      

Transmit power and bits/channel use adaption in competitive cognitive radio networks

In this paper, we propose an optimization framework to determine the distribution of power and bits/channel use to secondary users in a competitive cognitive radio networks. The objectives of the optimization framework are to minimize total transmission power, maximize total bits/channel use and also to maintain quality of service. An upper bound on probability of bit error and lower bound on bits/channel use requirement of secondary users are considered as quality of service. The optimization problem is also constrained by total power budget across channels for a user. Simulating the framework in a centralized manner shows that more transmit power is required to allocate in a channel with higher noise power. However, allocation of bits/channel use is directly proportional to signal to interference plus noise power ratio. The proposed framework is more capable of supporting high bits/channel use requirement than existing resource allocation framework. We also develop the game theoretic user based distributed approach of the proposed framework. We see that user based distributed solution also follows centralized solution.     

RAT selection for IoT devices in HetNets: Reinforcement learning with hybrid SMDP algorithm

Due to the increasing deployment of heterogeneous networks (HetNets), the selection of which radio access technologies (RATs) for Internet of Things (IoT) devices such as user equipments (UEs) has recently received extensive attention in mobility management research. Most of existing RAT selection methods only optimize the selection strategies from the UE side or network side, which results in heavy network congestion, poor user experience and system utility degradation. In this paper the UE side and the network side are considered comprehensively, based on the game theory (GT) model we propose a reinforcement learning with assisted network information algorithm to overcome the crucial points. The assisted information is formulated as a semi-Markov decision process (SMDP) provided for UEs to make accurate decisions, and we adopt the iteration approach to reach the optimal policy. Moreover, we investigate the impacts of different parameters on the system utility and handover performance. Numerical results validate that our proposed algorithm can mitigate unnecessary handovers and improve system throughputs.