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 pseudo-random sequences with respect to cryptographic complexities, and apply crypto-complexity techniques to model and furnish proofs for fundamental properties of our model. This is perhaps one of the first applications of crypto-complexity 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 time-dependent 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 self-contained 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 log-space-computable 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)


Reif, John H.


Duke University

School Location:

United States -- North Carolina


DAI-B 55/03, p. 994, Sep 1994

Source type:



Computer scienceEconomicsFinance

Publication Number:

AAT 9420402