Limites de modelos

MARCELO TSUJI, NEWTON C. A. DA COSTA and FRANCISCO A. DORIA
THE INCOMPLETENESS OF THEORIES OF GAMES?
ABSTRACT. We first state a few previously obtained results that lead to general undecidability
and incompleteness theorems in axiomatized theories that range from the theory
of finite sets to classical elementary analysis. Out of those results we prove several incompleteness
theorems for axiomatic versions of the theory of noncooperative games with Nash
equilibria; in particular, we show the existence of finite games whose equilibria cannot be
proven to be computable.
KEYWORDS: Chaitin, incompleteness, noncooperative games, Richardson’s functor, undecidability
1. INTRODUCTION
The Santa Fe Institute has recently started a multidisciplinary program
headed by J. Casti and J. Traub whose aim is to investigate the limits
of scientific knowledge [2, 3]. Rather reasonably, concepts such as those
that deal with the complexity and intractability of computations and with
noncomputable functions [20] were taken as starting points for that investigation
which is still under course, as our scientific endeavor is mainly
concerned with the development of mathematical models for reality and
their application. Since economics and other areas in the social sciences are
now heavily dependent on sophisticated mathematical tools, the limitations
intrinsically inherent in those tools have to be investigated and pondered in
their applications. Examples of deep mathematical questions that arise in
the biological and social sciences may be seen in the widely used nonlinear
reaction–diffusion equations in ecology. Their computational intractability
was already well-known; there are related systems whose chaotic behavior
can be proved; and now the Gödel incompleteness phenomenon has been
shown to be of import in those models [8].
More precisely, we may say that economists and social scientists have
until now been concerned with positive (or negative) existential theorems
that prove (or disprove) facts about particular mathematical models in their
domains of activity. Archetypal examples are the Arrow–Debreu model
? Partially supported by Fapesp and CNPq, Brazil, and by the PREVI-UFJF Program,
96–97.
Journal of Philosophical Logic 27: 553–568, 1998.
© 1998 Kluwer Academic Publishers. Printed in the Netherlands.
554 MARCELO TSUJI ET AL.
and Arrow’s Impossibility Theorem. Yet, more recently that concern with
existential results has been extended to metamathematical aspects of economic
models, and specifically with their computational aspects, such as
the algorithmic resources required by the economic agents to carry out the
effective implementation of those models. The existence of a journal solely
dedicated to those questions, Computational Economics, bears witness to
this growing concern.
Mais