Computational aspects of multiagent systems: Modeling efficiency and computing sequential equilibrium
by Azhar, Salman, Ph.D., Duke University, 1993, 246 pages; AAT 9420402
Abstract (Summary)
Scheduling decisions are vital to the operation of distributed systems, and pose interesting combinatorial optimization problems. This is a treatise on computational aspects of efficiency in a formal systems and computation of sequential equilibrium in economic systems.
We analyze the time series data of flow in a network as pseudorandom sequences with respect to cryptographic complexities, and apply cryptocomplexity techniques to model and furnish proofs for fundamental properties of our model. This is perhaps one of the first applications of cryptocomplexity theory in this context.
This thesis presents a formal treatment of determining efficiency, or lack thereof. The result is the formulation of a family of robust models to emulate timedependent flow of streams of sequences in a network. These new models provide simple and precise paradigms which bear essential characteristics of a wide range of systems, yet lend themselves to rigorous analysis. The major contribution of this work is its ability to provide rigorous proofs for relating efficiency to predictability in the aforementioned models (see S 3.4 (page 96) for further details).
This thesis discusses computation of equilibria as a selfcontained subject. This research yields algorithms for finding equilibria of mixed strategy in multistage noncooperative games of incomplete information (like probabilistic blindfold chess), where at every opportunity a player can perform a variety of simultaneous moves with their associated probability distribution. The main result of this work is an algorithm for computing Sequential Equilibrium, which is the most widely accepted class of equilibrium (for mixed strategies of noncooperative probabilistic games) in mainstream economic game theory. Previously, there were no known algorithms for computing sequential equilibria strategies (except for the special case of single stage games).
Given a recursively represented game, with a position space bound S(n) and a logspacecomputable next move relation, these algorithms can compute an example mixed strategy satisfying the sequential equilibria condition, all in space bound O(S(n)). Furthermore, the connected components of mixed strategies satisfying sequential equilibria can be computed in space O(EXP(S(n))).
Indexing (document details)
Advisor: 

School: 
Duke University 
School Location: 
United States  North Carolina 
Source: 
DAIB 55/03, p. 994, Sep 1994 
Source type: 
Dissertation 
Subjects: 

Publication Number: 
AAT 9420402 



