AN ESSAY ON DECISION THEORY WITH IMPERFECT RECALL LÓRÁND AMBRUS-LAKATOS Budapest September 1999 KTK/IE Discussion Papers 1999/5. Institute of Economics Hungarian Academy of Sciences KTK/IE Discussion papers

Please download to get full document.

View again

of 68
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Home & Garden

Publish on:

Views: 70 | Pages: 68

Extension: PDF | Download: 0

AN ESSAY ON DECISION THEORY WITH IMPERFECT RECALL LÓRÁND AMBRUS-LAKATOS Budapest September 1999 KTK/IE Discussion Papers 1999/5. Institute of Economics Hungarian Academy of Sciences KTK/IE Discussion papers are circulated to promote discussion and provoque comments. Any references to discussion papers should clearly state that the paper is preliminary. Materials published in this series may be subject to further publication. An Essay on Decision Theory with Imperfect Recall Author: Lóránd AMBRUS-LAKATOS, research fellow Institute of Economics, Hungarian Academy of Sciences, Budapest; assistant professor at the Department of Political Science and the Economics Department, Central European University, Budapest; research fellow at the William Davidson Institute, University of Michigan; and a research affiliate in CEPR s Transition Economics research programme. Postal address: Budaörsi út 45. Budapest, H 1112 Hungary. Phone: (36-1) Fax: (36-1) Keywords: decision theory, bounded rationality, imperfect recall, strategy Published by the Institute of Economics Hungarian Academy of Sciences. Budapest, With financial support the Hungarian Economic Foundation LÓRÁND AMBRUS-LAKATOS AN ESSAY ON DECISION THEORY WITH IMPERFECT RECALL Abstract In this paper, I seek to establish a framework in which solutions to imperfect recall decision problems can be suitably examined. I introduce a strategy concept which is an extension of the standard concept employed since von Neumann and Morgenstern, and show how it may provide optimal solutions to problems which feature forgetting. For a technical analysis, I provide a characterization of imperfect recall extensive forms, a crucial input into future studies on the properties of optimal extended strategies. Also, I discuss further issues in decision theory with imperfect recall, including the prospects of induced forgetting when preferences change during the problem. Összefoglaló A tanulmányban a döntéselmélet olyan átfogó vizsgálatára teszek kísérletet, amely figyelembe veszi a döntéshozó esetleges felejtéséből adódó problémákat is. Áttekintem, milyen új elméleti keretben vizsgálható a döntéselmélet ezen ága és javaslatot teszek egy kibővített stratégia fogalom bevezetésére. I. 1. Economic Situations with Imperfect Recall 1. It may be not difficult to argue that there are situations, purely economic or merely having economic relevance, where the forgetting previously held crucial information plays a salient role. One could refer to the following story. It is natural that governments facing elections are interested in convincing voters that things went generally well during their tenure. But since most of the time there are some things which did not go very well, a government seeking reelection may adopt the strategy of blaming other agents for the failures. These other agents could well be agencies or institutions over which the government has some control, but only a limited control. So the government could undertake to insinuate that it was not able to improve on a certain policy outcome just because of the independence of those institutions. Now, since governments are after all responsible for the overall good management of the life of the political community, the emphasis on independence is then concomitant to a silence about at least some aspects of their true relationship to these agencies. It even could have been the case that at the beginning of the electoral term the government had enthusiastically supported the independence of the agency in question for some other reason. We should also acknowledge that it is notoriously difficult to offer a clear-cut and acute description of what the independence of a given government agency or public authority really amounts to. One can even go as far as asserting that such relationships are fairly elusive, even inherently ambiguous. Thus we can also say: quite often governments engage in deliberate switching between radically different interpretations of what their relationship to certain agencies is or was, and offer before the elections the interpretation which is the most expedient for them. For a more concrete example, consider the scenario when the government, in concordance with its overall efforts to manage the economy, makes the central bank of the country independent in some legislative sense, or adopts and advertises policies which facilitate the independent policy-making of the central bank. This could be induced by an intention to lower the inflationary expectations of the public; reasons for adopting such measures are well-known. So if the government later, during the election campaign, undertakes to blame the stubborn selfinterest of the central bank for a bad outcome, it must count on the likely forgetting (or lack of thorough understanding) on the part of the voters of what the original reasons for having the given relationship with the central bank were. Much ingenuity and care have been devoted recently to the formulation of this and kindred situations in terms of a strategic game between the government and the electorate, the latter pictured as a judiciously composed aggregate of opinions and interests. Now, if one accepts that the electorate, while making a choice at the election, exhibits not only imperfect knowledge but also imperfect recall about the political events in the preceding term, and that governments under some circumstances are interested in taking advantage of the fact that voters have imperfect recall, then there arises the need to model properly this situation as a game which contains forgetful players in its specification. 1 1 More generally, one can claim that the formal modelling of any situation featuring blaming or scapegoat creation (which can be seen as specific instances of the problem 2. The situation presented above involves undoubtedly one of the largest game conceivable. It suffices to mention that in such a gametheoretical model the whole electorate of a country should be treated as a player in a strategic setting, that the duration of the game is very long, and that the web of actions is fantastically intricate. I would like then next to point to a situation which could be termed as very small and which involves bargaining between two agents. Here the rules are precise, and the boundaries of the situation are crisp. Suppose 2 that two agents, an employer and an employee, find themselves in a dispute over wages to be paid to the employee. One way to settle such a dispute is to submit their claims to a court of arbitration. Suppose also that the prevalent rules for arbitering over wage disputes prescribe that there are two subsequent stages available for the parties for reaching an agreement. A first arbitrator studies the case and offers terms for a settlement. Next, the parties make a decision about whether to accept the settlement or not. If they do not, they turn to a second arbitrator whose decision they have to accept as binding. Now if we take the view, or rather assume, that arbitrators have an interest in making an impartial decision (possibly because of their strive to maintain a reputation of always making neutral, unbiased, and wise of responsibility allocation), ought to involve the stipulation of forgetful players. Focal scenarios include those in which an agent seeks to manipulate the forgetfulness of others and those in which a group of agents tries to overcome forgetting by establishing rules for the allocation of responsibility; and there are many more. I discuss problems in modelling responsibility allocation at somewhat more length in Part III of my (1996): Institutions for Monetary Management, Delegation and Accountability. Mimeo, Princeton University. There I do not discuss forgetting in any depth, but suggest that any adequate model of responsibility allocation has to transcend the so-called Harsányi doctrine. See John Harsányi ( ): Games with Incomplete Information Played by `Bayesian' Players. Management Science 14; , , See Orley Ashenfelter, James Dow and Daniel Gallagher (1986): Arbitration and Negotiation Behavior under an Appellate System , mimeo., Princeton University judgements), and that the second arbitrator has an access only to the offer the first one made but not the information on which the reasons for the offer were grounded this situation of dispute settlement can be seen as one featuring imperfect recall. Both of the arbitrators want to make the same right decision, but the second one does not know what was known by the first one, who acted upon information strictly relevant to the case and also relied on the knowledge of the rules for the whole arbitration procedure. So one can suitably represent the team of the two arbitrators as one agent in a strategic game that loses information in the course of that game. 3. For those who cannot be content with drawing up just some model of the economic situations outlined above, but also feel that the challenge of incorporating forgetting players in those models should be met because of the crucial role forgetting plays in the scenarios, there seems to be no readily available paradigm to turn to. Indeed, the literature on decision theory with imperfect recall is very small, and the literature on game theory with imperfect recall is even smaller. 3 And I think it is fair to add that few 3 Recent papers include Steve Alpern (1988): Games with Repeated Decisions SIAM Journal of Control and Optimization 26, 2: ; and his (1991): Cycles in Extensive Form Perfect Information Games Journal of Mathematical Analysis and Applications 159, 1: 1-17; J. L. Ferreira, Itzhak Gilboa, and Michael Maschler (1992): Credible Equilibria in Games with Utilities Changing during the Play, mimeo., Northwestern University (later sections); Kenneth Binmore (1992): Fun and Games. Heath: Lexington; pp It has been recognized that the literature on repeated games played by automata is also relevant here, see Ariel Rubinstein (1986): Finite Automata Play the Repeated Prisoner's Dilemma. Journal of Economic Theory 39, 1: Ariel Rubinstein and Dilip Abreu (1988): The Structure of Nash Equilibrium in Repeated Games with Finite Automata. Econometrica 56, 6: ; Ehud Lehrer (1988): Repeated Games with Stationary Bounded Recall Strategies. Journal of Economic Theory 46, 1: On automata, see the remarks in 28 below. Consider also Robert Aumann and Sylvain Sorin (1989): Cooperation and Bounded Recall. Games and Economic Behavior 1, 1: 5 39; and James Dow (1991): Search Decisions with Limited Memory. Review of Economic Studies 58, 1: 1 14. of the contributions to this small literature could be straightforwardly put into work in an economic context. I will not embark on the task of identifying and modelling economic situations in which forgetting plays a pivotal part in this essay, which is on decision theory with imperfect recall in general. The reason for giving a draft of some situations viewed as relevant, real, and robust which ought to admit forgetting agents was to emphasize that efforts spent on decision or game theory with imperfect recall do not seek their sole ultimate rewards in checking yet an other perturbation of the core framework of formal decision theory, but in the prospect of providing tools for a satisfactory treatment of some important economic phenomena, including the two mentioned in the previous point among numerous others. That is, just like while motivating a preoccupation with models of bounded rationality, one has to stress that the ultimate rationale for developing and hopefully applying models which go beyond the core model lies not predominantly in the demand of presenting a total picture of human decision making. This is not necessary for the analysis of economic situations. What we need is a satisfactory model of human decision making, just good enough to capture aspects which ought to enter into the examination of a particular scenario, if that examination wishes to meet reasonable standards of adequacy. We are interested in modelling forgetting not because we are in the predicament of providing a perfect model of human decision making with imperfect recall, but because we cannot miss the modelling of situations where forgetting is central. In the examples of the two previous points, one cannot satisfice oneself with an attempt to formulate the most parsimonious model which gives some explanation of what is going on. Forgetting is in the essence of these examples. Is it not the same aim of saving the phenomena which is expressed below by the founders of game theory: (Economic models) must be similar to reality in those respects which are essential in the investigation at hand... Similarity is needed to make the operation significant ? 4 2. Decision Theory with Imperfect Recall 4. A significant number of works on decision theory which address the phenomenon of forgetting were written in the early fifties, the era of the first wave of the systematization and clarification of the ideas in the book of von Neumann and Morgenstern. Indeed, it was a landmark of this period, the famous article of Kuhn 5 which both settled the definition of games with perfect recall and at the same time, unintentionally perhaps, endowed games featuring forgetting with the status of awkward exceptions. At the same time, his paper offered a new set of mathematical objects to serve as the canonical model of games and therewith achieved a certain regimentation of the thought of von Neumann and Morgenstern. Other worked which analyzed imperfect recall, like those of Thompson, Dalkey, Isbell, and somewhat later Aumann 6 remained in relative obscurity despite their worthy contents. 4 John von Neumann and Oskar Morgenstern (1944), (1947): Theory of Games and Economic Behavior Princeton: Princeton University Press, p Harold W. Kuhn (1953): Extensive Games and the Problem of Information. Contributions to the Theory of Games Vol. II, edited by H. Kuhn and W. Tucker. Princeton: Princeton University Press, pp For papers related to the issue of imperfect recall from this period see G. L. Thompson (1953): Signalling Strategies in n-person Games. Contributions to the Theory of Games Vol. II, edited by H. Kuhn and W. Tucker, Princeton: Princeton University Press, pp ; Norman Dalkey (1953): Equivalence of Information Patterns and One problem with modelling forgetting is that it begs the question about the identity of players in a game. Indeed, von Neumann and Morgenstern mention imperfect recall not in the context of the issue of what one individual player can know during a game, 7 but in connection with the challenge of modelling the card game Bridge. Teammates in Bridge have identical interests, but they are compelled to make choices alternatingly, not seeing each others' deals. An individual player, when it is his turn to move, is imperfectly informed about some of the past events which were observed by his partner. Now, von Neumann and Morgenstern insist that Bridge is a two-player game. Kuhn also raises the issue of the identity of players in imperfect recall situations. He proposes to decompose a player into a collection of agents identified by occasions to make a choice. This is, in fact, motivated by making sense of Bridge 8 and by the need for clarifying his conception of information sets. He sees this decomposition as natural for perfect recall games, and adds that it is Essentially Determinate Games. Contributions to the Theory of Games Vol. II, edited by H. Kuhn and W. Tucker, Princeton: Princeton University Press, pp ; J. R. Isbell (1957): Finitary Games. Contributions to the Theory of Games Vol. III, edited by M. Drescher, W. Tucker, and P. Wolfe, Princeton: Princeton University Press, pp ; and Robert Aumann (1964): Mixed and Behavior Strategies in Infinite Extensive Games. Advances in Game Theory, edited by M. Drescher, L. Shapley, and W. Tucker, Princeton: Princeton University Press, pp See also R. Duncan Luce and Howard Raiffa (1957): Games and Decisions 2nd ed., Dover; pp See Von Neumann Morgenstern: Theory of Games and Economic Behavior, p. 53, 79. Cf. Luce-Raiffa Games and Decisions, pp Cf. Kuhn Extensive Games and the Problem of Information : (The) seeming plethora of agents is occasioned by the possibly complicated state of information of our players who may be forced by the rules to forget facts which they knew earlier in a play. (It has been asserted by von Neumann that Bridge is a two-person game in exactly this manner) , p. 195. exactly in imperfect recall situations when it is somewhat not clear how these agents make up a player. In these cases they make up a team. 9 One wonders whether such a hesitation even in the identification of the concept of players in an imperfect recall context could not only have aggravated the difficulties and could not have discouraged prematurely the engagement with the issue head on. 5. The subsequent development of game theory saw virtually all papers and textbooks routinely sidestepping, or if not swiftly abandoning, the case of imperfect recall. Thus when Piccione and Rubinstein 10 took up the issue again, they almost had to start the discourse from the state it was left in the fifties. They set out to catalog the difficulties which may have prevented others to write on this topic. Their paper is conceptual, the emphasis is more on the explication of these difficulties than on a comprehensive formal analysis of imperfect recall problems, based on some stance on what the right treatment of then would be. But as already a first reading of their work reveals, there was more behind the intermittent silence than neglect and preoccupation with the 9 See Kuhn, Extensive Games and the Problem of Information , pp , And also ...each player is allowed by the rules of the game to remember everything he knew at previous moves and all of his choices at those moves. This obviates the use of agents; indeed, the only games that do not have perfect recall are those, such as Bridge, which include the description of the agents in their verbal rules. , p Michele Piccione and Ariel Rubinstein (1994): On the Interpretation of Decision Problems with Imperfect Recall, mimeo, University of British Columbia and Tel-Aviv University. There is by now a series of papers for which the work of Piccione and Rubinstein serves as a starting point: these include Pierpaolo Battigalli (1995): Time Consistency, Sequential Rationality, and Rational Inferences in Decision Problems with Imperfect Recall, his (1996): Dynamic Consistency and Imperfect Recall. Both mimeo, Princeton University; Joseph Y. Halpern (1995), (1996): On Ambiguities in the Interpretation of Game Trees. Both versions mimeo., IBM Research Division; and Robert Aumann, Sergiu Hart, and Motty Perry (1995): The Absent-Minded Driver. In: Theoretical Aspects of Rationality and Knowledge Vol. VI, edited by Y. Shoham, San fashionable ideas of the day. They make it evident that the difficulties in the analysis of imperfect recall are not simply due to technical complexities or the vagueness surrounding the concept of players. Many concepts, techniques and approaches which serve as cornerstones for decision and game theory as they stand do not work very well in the presence of imperfect recall. As a natural first step, their attention was limited to decision theory. It could be asserted that they made five main observations about the interpretation of decision theory with imperfect recall. The first registers the need of employing behavioral strategies to solve some imperfect recall problems. This result has been already pointed out by Isbell 11 but Piccione and Rubinstein identify additional ambiguities in interpreting behavioral strategies in imperfect recall contexts. Second, they point out that imperfect recall could generate instances of time inconsistency, the nature of which is totally different from instances when time inconsist
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!