Optimal stopping problems by two or more decision makers: a survey

A review of the optimal stopping problem with more than a single decision maker (DM) is presented in this paper. We classify the existing literature according to the arrival of the offers, the utility of the DMs, the length of the sequence of offers, the nature of the game and the number of offers to be selected. We enumerate various definitions for this problem and describe some dynamic approaches. Fouad Ben Abdelaziz is on leave from the Institut Superieur de Gestion, University of Tunis, Tunisia e-mail: foued.benabdelaz@isg.run.tn.     

Reflection of Long Game Formulas

We study game formulas the truth of which is determined by a semantical game of uncountable length. The main theme is the study of principles stating reflection of these formulas in various admissible sets. This investigation leads to two weak forms of strict-II¹₁ reflection (or ∑₁-compactness). We show that admissible sets such as H(ω₂) and L_ω2 which fail to have strict-II¹₁ reflection, may or may not, depending on set-theoretic hypotheses satisfy one or both of these weaker forms. Mathematics Subject Classification : 03C70, 03C75.     

Location of terror response facilities: A game between state and terrorist

We study a leader follower game with two players: a terrorist and a state where the later one installs facilities that provide support in case of a terrorist attack. While the Terrorist attacks one of the metropolitan areas to maximize his utility, the State, which acts as a leader, installs the facilities such that the metropolitan area attacked is the one that minimizes her disutility (i.e., minimizes ‘loss’). We solve the problem efficiently for one facility and we formulate it as a mathematical programming problem for a general number of facilities. We demonstrate the problem via a case study of the 20 largest metropolitan areas in the United States.     

Game of two cars: Case of variable speed

A stochastic version of Isaacs's (Ref. 1) game of two cars is dealt with here. In this version, the pursuer, owing to thrust and drag forces, has a variable speed, whereas the evader's speed is constant. Also, the pursuer can maneuver as long as his speed is bounded by some lower and upper limits. The probability of interception, corresponding to optimal (saddle-point) feedback strategies, is computed and serves as a reference for evaluating the performance of four different versions of the proportional navigation pursuit law as well as two other strategies.     

The price of anarchy for non-atomic congestion games with symmetric cost maps and elastic demands

By showing that there is an upper bound for the price of anarchyρ(Γ) for a non-atomic congestion game Γ with only separable cost maps and fixed demands, Roughgarden and Tardos show that the cost of forgoing centralized control is mild. This letter shows that there is an upper bound for ρ(Γ) in Γ for fixed demands with symmetric cost maps. It also shows that there is a weaker bound for ρ(Γ) in Γ with elastic demands.     

Multicriteria Goal Games

In this paper, we deal with multicriteria matrix games. Different solution concepts have been proposed to cope with these games. Recently, the concept of Pareto-optimal security strategy which assures the property of security in the individual criteria against an opponent's deviation in strategy has been introduced. However, the idea of security behind this concept is based on expected values, so that this security might be violated by mixed strategies when replications are not allowed. To avoid this inconvenience, we propose in this paper a new concept of solution for these games: the G-goal security strategy, which includes as part of the solution the probability of obtaining prespecified values in the payoff functions. Thus, attitude toward risk together with payoff values are considered jointly in the solution analysis.     

SPAR: stochastic programming with adversarial recourse

We consider a general adversarial stochastic optimization model. Our model involves the design of a system that an adversary may subsequently attempt to destroy or degrade. We introduce SPAR, which utilizes mixed-integer programming for the design decision and a Markov decision process (MDP) for the modeling of our adversarial phase.     

A two-population game in observable double-ended queuing systems

In this study, the existing game theoretical framework is extended to strategic queuing in search of solutions for a two-population game in observable double-ended queuing systems with zero matching times. We show that multiple Nash equilibria and one unique subgame perfect Nash equilibrium exist in this game.     

Survivable network design under optimal and heuristic interdiction scenarios

We examine the problem of building or fortifying a network to defend against enemy attacks in various scenarios. In particular, we examine the case in which an enemy can destroy any portion of any arc that a designer constructs on the network, subject to some interdiction budget. This problem takes the form of a three-level, two-player game, in which the designer acts first to construct a network and transmit an initial set of flows through the network. The enemy acts next to destroy a set of constructed arcs in the designer’s network, and the designer acts last to transmit a final set of flows in the network. Most studies of this nature assume that the enemy will act optimally; however, in real-world scenarios one cannot necessarily assume rationality on the part of the enemy. Hence, we prescribe optimal network design algorithms for three different profiles of enemy action: an enemy destroying arcs based on capacities, based on initial flows, or acting optimally to minimize our maximum profits obtained from transmitting flows.     

Constrained cost-coupled stochastic games with independent state processes

We study non-cooperative constrained stochastic games in which each player controls its own Markov chain based on its own state and actions. Interactions between players occur through their costs and constraints which depend on the state and actions of all players. We provide an example from wireless communications.