Reasoning About Others: Representing and Processing Infinite Belief HierarchiesSviatoslav Brainov and Tuomas SandholmDepartment of Computer ScienceWashington UniversitySt. Louis, MO 63130{brainov, sandholm}@cs.wustl.eduAbstractIn this paper we focus on the problem of how infinitebelief hierarchies can be represented and reasonedwith in a computationally tractable way. Whenmodeling nested beliefs one usually deals with twotypes of infinity: infinity of beliefs on every level ofreflection and infinity of levels. In this work weassume that beliefs are finite at every level, while thenumber of levels may still be infinite. We propose amethod for reducing the infinite regress of beliefs to afinite structure. We identify the class of infinite belieftrees that allow finite representation. We propose amethod for deciding on an action based on thispresentation. We apply the method to the analysis ofauctions. We prove that if the agents’ prior beliefsare not common knowledge, the revenue equivalencetheorem ceases to hold. That is, different auctionsyield different expected revenue. Our method can beused to design better auction protocols, given theparticipants’ belief structures.1. IntroductionReasoning about others and interactive knowledgehave been the subject of continuous interest inmultiagent systems [11,12,13,20], artificialintelligence [6,7,8] and game theory [1,3,15]. Inmultiagent interaction, where an agent’s actioninterferes with other agents’ actions, hierarchies ofbeliefs arise in an essential way. Usually an agent’soptimal decision depends on what he believes theother agents will do, which in turn depends on whathe believes the other agents believe about him, and soon. An infinite regress of this kind gives rise toseveral important issues. The first issue concerns themethods for representing infinitely nested beliefs. Inorder to maintain and update such beliefs, agentsneed some finite and computationally tractable wayto represent them. The second issue that deservesconsideration is the feasibility of decision makingbased on infinitely nested beliefs.Finite hierarchies of beliefs have been studied byGmytrasiewicz, Durfee and Vidal [11,12,13, 20]. Themain advantage of their recursive modeling method isthat a solution can always be derived. The recursivemodeling method is based on the assumption thatonce an agent has run out of information his beliefhierarchy can be cut at the point where there is nosufficient information. At the point of cutting,absence of information is represented by a uniformdistribution over the space of all possible states of theworld. The absence of information with which tomodel other agents implies that belief hierarchies arepotentially finite. In our work we take a differentapproach. We suppose that every belief hierarchy ispotentially infinite and we consider the problem ofhow such a hierarchy can be represented using a finitestructure and manipulated in a computationallytractable way. We show that some infinite belief treesallow finite representation in the form of pointedaccessible graphs.The most typical and the most studied example ofinfinite belief hierarchies is common knowledge[4,7,10]. Common knowledge means that everyoneknows that everyone knows that… Commonknowledge, however, is a very special case of a beliefhierarchy, namely, a hierarchy that consists of infiniterepetition of some event. Such a hierarchy can bereduced to a finite representation if we treat all therepetitions in the hierarchy as identical. In this paperwe extend this idea to infinite belief hierarchies withmore complex structure.The research presented in this paper is closelyrelated to the work in game theory devoted to gameswith incomplete information [9]. In our work, theepistemic state of each agent is modeled as an infinitehierarchy of beliefs. Harsanyi suggested that eachhierarchy of beliefs could be summarized by thenotion of agent’s type [9]. Later Mertens and Zamirproved that the space of all possible types is closed inthe sense that it is large enough to include evenhigher-order beliefs about itself [15]. Brandenburgerhas shown that if agents’ beliefs are coherent thespace of all possible types is closed [4].The paper is organized as follows. In Section 2 wepropose the notion of balanced strategy labeling. InSection 3 we show how regular belief trees can berepresented with finite trees. In section 4 we proposea graph representation for infinite belief trees. Weapply our approach to the analysis of auctions inSection 5. Finally, the paper concludes bysummarizing the results and providing directions forfuture research.2. Infinite belief hierarchiesIn every multiagent interaction, an agent faces twotypes of uncertainty: basic and belief uncertainty.Basic uncertainty relates to the elements of thephysical environment, which are uncertain to agents.We model basic uncertainty by a finite set T,T={t1,t2,…,tn}, including all uncertain elements of thephysical environment. We represent agents’ basicbeliefs as a subjective probability distributions on T.While basic uncertainty deals with the elements ofthe physical environment, belief uncertainty relates toother agents’ beliefs. That is, belief uncertaintyincludes an agent’s beliefs about other agents’beliefs, his beliefs about other agents’ beliefs aboutother agents’ beliefs, and so on.Figure 1. A first-order belief treeSuppose that the agents under consideration areagent i and agent j. First order beliefs of agent i canbe represented by a discrete probability distributionσ, σ=(p1,p2,…,pn). That is, agent i believes that thetrue state of the environment is t1 with probability p1,t2 with probability p2, and so on. First order beliefs ofagent i can be represented by a belief tree. The nodesof the tree are labeled with the elements of T and arcsare labeled with probabilities. For every node, thesum of the probabilities on outgoing arcs is 1. Figure1 shows a belief tree that represents first-order beliefsof agent i.Second order beliefs of agent i include his beliefsabout the true state of the environment and his beliefsabout agent j’s beliefs about the true state of theenvironment. A second-order belief tree for agent i isrepresented in Figure 2.Figure 2. A second-order belief treeLet σ1 denote the first-order beliefs of agent j thatthe true state of the environment is t1 with probabilityq1 and t2 with probability q2, and so on. Similarly, letσn denote agent j’s beliefs that the true