A model is presented of learning automata playing stochastic games at two levels. The high level represents the choice of the game environment and corresponds to a group decision. The low level represents the choice of action within the selected game environment. Both of these decision processes are affected by delays in the information state due to inherent latencies or to the delayed broadcast of state changes. Analysis of the intrinsic properties of this Markov process is presented along with simulated iterative behavior and expected iterative behavior. The results show that simulation agrees with expected behavior for small step lengths in the iterative map. A Feigenbaum diagram and numerical computation of the Lyapunov exponents show that, for very small penalty parameters, the system exhibits chaotic behavior.

Multilevel games are abstractions of situations where decision makers are distributed in a network environment. In Part I of this paper, the authors present several of the challenging problems that arise in the analysis of multilevel games. In this paper a specific set up is considered where the two games being played are zero-sum games and where the decision makers use the linear reward-inaction algorithm of stochastic learning automata. It is shown that the effective game matrix is decided by the willingness and the ability to cooperate and is a convex combination of two zero-sum game matrices. Analysis of the properties of this effective game matrix and the convergence of the decision process shows that players tend toward noncooperation in these specific environments. Simulation results illustrate this noncooperative behavior.

Farber and Keil [Algorithmica, 4 (1989), pp. 221–236] presented an $O(n^3 )$-time algorithm for finding a minimum-weight dominating set in permutation graphs. This result was improved to $O(n^2 \log ^2 n)$ by Tsai and Hsu [SIGAL ’90 Algorithms, Lecture Notes in Computer Science, Springer-Verlag, New York, 1990, pp. 109–117] and to $O(n(n + m)$ by the authors of this paper [Inform. Process. Lett., 37 (1991), pp. 219–224], respectively. In this paper, we introduce a new faster algorithm that takes only $O(n + m)$ time to solve the same problem, where m is the number of edges in a graph of n vertices.

This paper describes a class of interconnection networks based on Cayley graph of (S_n, \Omega_CT)> where S_n is the symmetric group of degree n and order n! and \Omega_CT is the generator set consisting of all the n (n -1)/2 transpositions, called the complete transposition graph (CTG). A complete enumeration of a set of node disjoint paths for CTG is given which in turn implies that CTG has maximum fault-tolerance.

Abstract This paper introduces a new class of interconnection scheme based on the Cayley graph of the alternating group. It is shown that this class of graphs are edge symmetric and 2‐transitive. We then describe an algorithm for (a) packet routing based on the shortest path analysis, (b) finding a Hamiltonian cycle, (c) ranking and unranking along the chosen Hamiltonian cycle, (d) unit expansion and dilation three embedding of a class of two‐dimensional grids, (e) unit dilation embedding of a variety of cycles, and (f) algorithm for broadcasting messages. The paper concludes with a short analysis of contention resulting from a typical communication scheme. Although this class of graphs does not possess many of the symmetry properties of the binary hypercube, with respect to the one source broadcasting, these graphs perform better than does a hypercube, and with respect to the contention problem, these graphs perform better than do the star graphs and are close to the hypercube. © 1993 by John Wiley & Sons, Inc.

Orthogonal graphs are natural extensions of the classical binary and b-ary hypercubes b=2/sup l/ and are abstractions of interconnection schemes used for conflict-free orthogonal memory access in multiprocessor design. Based on the type of connection mode, these graphs are classified into two categories: those with disjoint and those with nondisjoint sets of modes. The former class coincides with the class of b-ary b=2/sup l/ hypercubes, and the latter denotes a new class of interconnection. It is shown that orthogonal graphs are Cayley graphs, a certain subgroup of the symmetric (permutation) group. Consequently these graphs are vertex symmetric, but it turns out that they are not edge symmetric. For an interesting subclass of orthogonal graphs with minimally nondisjoint set of modes, the shortest path routing algorithm and an enumeration of node disjoint (parallel) paths are provided. It is shown that while the number of node disjoint paths is equal to the degree, the distribution is not uniform with respect to Hamming distance as in the binary hypercube.>

A class of nonlinear learning algorithms for the Q-and S-model stochastic automaton-random environment setup are described. Necessary and sufficient conditions for absolute expediency of these algorithms are derived. Various algorithms that are so far reported in literature can be obtained as special cases of the general algorithm given in this correspondence.

A nonparametric training procedure capable of processing an arbitrary sequence of patterns based on stochastic approximation techniques is considered. An acceleration scheme based on the adaptive Robbins-Monro procedure to increase the rate of convergence and to make the estimation asymptotically efficient is proposed. This scheme has been applied to the problem of recognition of handwritten characters.