Game Development Reference
economists want to design a spectrum auction so that the equilibrium
has certain features. As I pointed out in an earlier overview [Halpern,
2003], game theory has typically focused on 'small' games: games that
are easy to describe, such as the prisoner's dilemma. The focus has been
on subtleties regarding basic issues such as rationality and coordination.
To the extent that game theory is used to tackle larger, more practical
problems, and especially to the extent that it is computers, or software
agents, playing games, rather than people, it will be important to specify
carefully exactly what a solution to the game must accomplish. For
example, in the context of a spectrum auction, a specification will have
to address what should happen if a computer crashes while an agent is
in the middle of transmitting a bid, how to deal with agents bidding on
slow lines, dealing with agents who win but then go bankrupt, and so
Finding logics to reason about solutions, especially doing so in a way
that takes into account robustness and asynchrony, seems to me a di cult
and worthwhile challenge. Indeed, one desideratum for a good solution
concept is that it should be easy to reason about. Pursuing this theme,
computer scientists have learned that one good way of designing correct
programs is to do so in a modular way. Can a similar idea be applied in
game theory? That is, can games designed for solving smaller problems be
combined in a seamless way to solve a larger problem? If so, results about
composability of solutions will be needed; we might want solution concepts
that allow for such composability.
Acknowledgements: Work supported in part by NSF under under grants ITR-
0325453 and IIS-0534064, and by AFOSR under grant FA9550-05-1-0055.
Thanks to Krzysztof Apt for useful comments.
I. Abraham, D. Dolev, R. Gonen, and J. Y. Halpern. Distributed computing meets
game theory: robust mechanisms for rational secret sharing and multiparty
computation. In Proc. 25th ACM Symposium on Principles of Distributed
Computing , pages 53-62, 2006.
I. Abraham, D. Dolev, and J. Y. Halpern. Lower bounds on implementing robust
and resilient mediators. In Fifth Theory of Cryptography Conference , pages
E. Adar and B. Huberman. Free riding on Gnutella. First Monday , 5(10), 2000.
R. J. Aumann. Acceptable points in general cooperative n -person games. In A. W.
Tucker and R. D. Luce, editors, Contributions to the Theory of Games IV,