Department of Computer Science

State University of New York at Albany

Albany, NY 12222

Ph.D. Thesis

*
*

In Part I, we study bounded rationality in repeated two-person zero-sum games. First we investigate infinitely repeated games in which both players are restricted to pure strategies that can be executed on a finite automaton. In particular, we provide an upper bound on the number of states that Player 2 needs to defeat Player 1 when Player 1 is restricted to simple cycles of length m. Next we argue that the finite automaton approach to bounded rationality is not satisfactory. As an alternative, we propose limiting the number of strategies available to the players. We provide a thorough study of finitely repeatedly zero sum games in which Player 1 is restricted to mixing over a fixed number of pure strategies while Player 2 is unrestricted. We describe an optimal set of pure strategies for Player 1 and a method for describing these strategies such that any strategy from this set can be efficiently executed given its description. We develop upper and lower bounds on the value of these games and discuss how the value is related to the strategic entropy function defined by Neyman and Okada (1999). Finally, we show that an approximately optimal set can be produced in time which is linear in the size of the set. This set achieves a total expected payoff that is within an additive constant of the optimal.

In Part II, we investigate the problem of designing mechanisms to control collective decisions made by self-interested autonomous agents. In particular, we examine how results in the economics literature on mechanism design apply to collective decisions involving NP-hard optimization problems. We formalize the idea of polynomial time mechanism design and investigate both dominant strategy and Nash implementation for a multiagent version of \maxsatf. In particular, we show that there exists a polynomial time mechanism for multiagent \maxsat that guarantees the outcome to be within a factor of 1/2 of the optimal outcome. We also show that, in general, a 1/2 approximation is the best approximation possible for dominant strategy, Nash, undominated Nash and subgame perfect implementation. Our analysis highlights some of the difficulties that arise in applying results from mechanism design to computational problems.

For shorter and more up to date expositions of much of this work see:

- O'Connell, T. C. and Stearns, R. E. (2005).
"Mechanism Design for Software Agents with Complete Information,",
*Decision Support Systems, Volume 39, Issue 2, April 2005, Pages 197-217.*

- O'Connell, T. C. and Stearns, R. E. (2002).
"Polynomial Time Mechanisms for Collective Decision Making,"
in Game theory and decision theory in agent-based systems,
Parsons, S., Gmytrasiewicz, P. and Wooldridge, M. J. (eds.),
Kluwer Academic Publishers.

abstract/ full paper (postscript). - O'Connell, T.C. and Stearns, R.E. (2003).
"On Finite Strategy Sets for Finitely Repeated Zero-Sum Games,"
*Games and Economic Behavior, Volume 43, Issue 1, April 2003, Pages 107-136.*

Download paper ( ps.gz , pdf ).

June 2000