Complexity of games and bounded rationality

An attempt is made to propose a concept of limited rationality for choice junctions based on computability theory in computer science.

Starting with the observation that it is possible to construct a machine simulating strategies of each individual in society, one machine for each individual's preference structure, we identify internal states of this machine with strategies or strategic preferences. Inputs are possible actions of other agents in society thus society is effectively operating as a game generated by machines. The main result states that effective realization of game strategies bound by the “complexity of computing machines'.     

Some properties of the bilevel programming problem

The purpose of this paper is to elaborate on the difficulties accompanying the development of efficient algorithms for solving the bilevel programming problem (BLPP). We begin with a pair of examples showing that, even under the best of circumstances, solutions may not exist. This is followed by a proof that the BLPP is NP-hard.This work was partially supported by a grant from the Advanced Research Program of the Texas Higher Education Coordinating Board.     

Static search games played over graphs and general metric spaces

We define a general game which forms a basis for modelling situations of static search and concealment over regions with spatial structure. The game involves two players, the searching player and the concealing player, and is played over a metric space. Each player simultaneously chooses to deploy at a point in the space; the searching player receiving a payoff of 1 if his opponent lies within a predetermined radius r of his position, the concealing player receiving a payoff of 1 otherwise. The concepts of dominance and equivalence of strategies are examined in the context of this game, before focusing on the more specific case of the game played over a graph. Methods are presented to simplify the analysis of such games, both by means of the iterated elimination of dominated strategies and through consideration of automorphisms of the graph. Lower and upper bounds on the value of the game are presented and optimal mixed strategies are calculated for games played over a particular family of graphs.     

3D differential game guidance

Three-dimensional guidance in the neighborhood of collision course, based on a terminal differential game, renders ellipsoidal control sets. As a result, a saddle-point contains singularities. This paper (a) generalizes previous results on linear dynamics with terminal cost and ellipsoidal control sets and (b) applies the results to the above guidance problem to include general missile and target transfer functions. We further demonstrate the construction of the isocost surfaces (tubes).     

Cooperative game analysis of retail space-exchange problems

We analyze retail space-exchange problems where two or more retailers exchange their excess retail spaces to improve the utilization of their space resource. We first investigate the two-retailer space exchange problem. In order to entice both retailers with different bargaining powers to exchange their spaces, we use the generalized Nash bargaining scheme to allocate the total profit surplus between the two retailers. Next, we consider the space-exchange problem involving three or more retailers, and construct a cooperative game in characteristic function form. We show that the game is essential and superadditive, and also prove that the core is non-empty. Moreover, in order to find a unique allocation scheme that ensures the stability of the grand coalition, we propose a new approach to compute a weighted Shapley value that satisfies the core conditions and also reflects retailers’ bargaining powers. Our analysis indicates that the space exchange by more retailers can result in a higher system-wide profit surplus and thus a higher allocation to each retailer under a fair scheme.     

The uniqueness property for networks with several origin–destination pairs

We consider congestion games on networks with nonatomic users and user-specific costs. We are interested in the uniqueness property defined by Milchtaich (2005) as the uniqueness of equilibrium flows for all assignments of strictly increasing cost functions. He settled the case with two-terminal networks. As a corollary of his result, it is possible to prove that some other networks have the uniqueness property as well by adding common fictitious origin and destination. In the present work, we find a necessary condition for networks with several origin–destination pairs to have the uniqueness property in terms of excluded minors or subgraphs. As a key result, we characterize completely bidirectional rings for which the uniqueness property holds: it holds precisely for nine networks and those obtained from them by elementary operations. For other bidirectional rings, we exhibit affine cost functions yielding to two distinct equilibrium flows. Related results are also proven. For instance, we characterize networks having the uniqueness property for any choice of origin–destination pairs.     

Self-conjugate partitions with the same disparity

We give a bijection between the set of ordinary partitions and that of self-conjugate partitions with some restrictions. Also, we show the relationship between hook lengths of a self-conjugate partition and its corresponding partition via the bijection. As a corollary, we give new combinatorial interpretations for the Catalan number and the Motzkin number in terms of self-conjugate simultaneous core partitions.     

Optimal control of systems with multiple criteria when disturbances are present

Optimal control problems with a vector performance index and uncertainty in the state equations are investigated. Nature chooses the uncertainty, subject to magnitude bounds. For these problems, a definition of optimality is presented. This definition reduces to that of a minimax control in the case of a scalar cost and to Pareto optimality when there is no uncertainty or disturbance present. Sufficient conditions for a control to satisfy this definition of optimality are derived. These conditions are in terms of a related two-player zero-sum differential game and suggest a technique for determining the optimal control. The results are illustrated with an example.This research was supported by AFOSR under Grant No. 76-2923.     

Optimal control problem for an automatic transmission

Attention is given to the control-theoretic aspects of the operation of an automatic transmission for a road vehicle. A differential game model for vehicle control is presented and analyzed; furthermore, the approach leads to a synthesis of the optimal feedback strategy for the selection of the transmission ratio of the automatic gearbox.This work was partially supported by a grant from Control Data.