Bayesianism in Game Theory. Thought of the Day 24.0

Bayesianism in game theory can be characterised as the view that it is always possible to define probabilities for anything that is relevant for the players’ decision-making. In addition, it is usually taken to imply that the players use Bayes’ rule for updating their beliefs. If the probabilities are to be always definable, one also has to specify what players’ beliefs are before the play is supposed to begin. The standard assumption is that such prior beliefs are the same for all players. This common prior assumption (CPA) means that the players have the same prior probabilities for all those aspects of the game for which the description of the game itself does not specify different probabilities. Common priors are usually justified with the so called Harsanyi doctrine, according to which all differences in probabilities are to be attributed solely to differences in the experiences that the players have had. Different priors for different players would imply that there are some factors that affect the players’ beliefs even though they have not been explicitly modelled. The CPA is sometimes considered to be equivalent to the Harsanyi doctrine, but there seems to be a difference between them: the Harsanyi doctrine is best viewed as a metaphysical doctrine about the determination of beliefs, and it is hard to see why anybody would be willing to argue against it: if everything that might affect the determination of beliefs is included in the notion of ‘experience’, then it alone does determine the beliefs. The Harsanyi doctrine has some affinity to some convergence theorems in Bayesian statistics: if individuals are fed with similar information indefinitely, their probabilities will ultimately be the same, irrespective of the original priors.

The CPA however is a methodological injunction to include everything that may affect the players’ behaviour in the game: not just everything that motivates the players, but also everything that affects the players’ beliefs should be explicitly modelled by the game: if players had different priors, this would mean that the game structure would not be completely specified because there would be differences in players’ behaviour that are not explained by the model. In a dispute over the status of the CPA, Faruk Gul essentially argues that the CPA does not follow from the Harsanyi doctrine. He does this by distinguishing between two different interpretations of the common prior, the ‘prior view’ and the ‘infinite hierarchy view’. The former is a genuinely dynamic story in which it is assumed that there really is a prior stage in time. The latter framework refers to Mertens and Zamir’s construction in which prior beliefs can be consistently formulated. This framework however, is static in the sense that the players do not have any information on a prior stage, indeed, the ‘priors’ in this framework do not even pin down a player’s priors for his own types. Thus, the existence of a common prior in the latter framework does not have anything to do with the view that differences in beliefs reflect differences in information only.

It is agreed by everyone that for most (real-world) problems there is no prior stage in which the players know each other’s beliefs, let alone that they would be the same. The CPA, if understood as a modelling assumption, is clearly false. Robert Aumann, however, defends the CPA by arguing that whenever there are differences in beliefs, there must have been a prior stage in which the priors were the same, and from which the current beliefs can be derived by conditioning on the differentiating events. If players differ in their present beliefs, they must have received different information at some previous point in time, and they must have processed this information correctly. Based on this assumption, he further argues that players cannot ‘agree to disagree’: if a player knows that his opponents’ beliefs are different from his own, he should revise his beliefs to take the opponents’ information into account. The only case where the CPA would be violated, then, is when players have different beliefs, and have common knowledge about each others’ different beliefs and about each others’ epistemic rationality. Aumann’s argument seems perfectly legitimate if it is taken as a metaphysical one, but we do not see how it could be used as a justification for using the CPA as a modelling assumption in this or that application of game theory and Aumann does not argue that it should.

Advertisement

Weil Conjectures. Note Quote.

Solving Diophantine equations, that is giving integer solutions to polynomials, is often unapproachably difficult. Weil describes one strategy in a letter to his sister, the philosopher Simone Weil: Look for solutions in richer fields than the rationals, perhaps fields of rational functions over the complex numbers. But these are quite different from the integers:

We would be badly blocked if there were no bridge between the two. And voilà god carries the day against the devil: this bridge exists; it is the theory of algebraic function fields over a finite field of constants.

A solution modulo 5 to a polynomial P(X,Y,..Z) is a list of integers X,Y,..Z making the value P(X,Y,..Z) divisible by 5, or in other words equal to 0 modulo 5. For example, X² + Y² − 3 has no integer solutions. That is clear since X and Y would both have to be 0 or ±1, to keep their squares below 3, and no combination of those works. But it has solutions modulo 5 since, among others, 3² + 3² − 3 = 15 is divisible by 5. Solutions modulo a given prime p are easier to find than integer solutions and they amount to the same thing as solutions in the finite field of integers modulo p.

To see if a list of polynomial equations P_i(X, Y, ..Z) = 0 have a solution modulo p we need only check p different values for each variable. Even if p is impractically large, equations are more manageable modulo p. Going farther, we might look at equations modulo p, but allow some irrationals, and ask how the number of solutions grows as we allow irrationals of higher and higher degree—roots of quadratic polynomials, roots of cubic polynomials, and so on. This is looking for solutions in all finite fields, as in Weil’s letter.

The key technical points about finite fields are: For each prime number p, the field of integers modulo p form a field, written F_p. For each natural number r > 0 there is (up to isomorphism) just one field with p^r elements, written as F_p^r or as F_q with q = p^r. This comes from F_p by adjoining the roots of a degree r polynomial. These are all the finite fields. Trivially, then, for any natural number s > 0 there is just one field with q^s elements, namely F_p^(r+s) which we may write F_q^s. The union for all r of the F_p^r is the algebraic closure F^–_p. By Galois theory, roots for polynomials in F_p^r, are fixed points for the r-th iterate of the Frobenius morphism, that is for the map taking each x ∈ F^–_p to x^pr.

Take any good n-dimensional algebraic space (any smooth projective variety of dimension n) defined by integer polynomials on a finite field F_q. For each s ∈ N, let N_s be the number of points defined on the extension field F_(q^s). Define the zeta function Z(t) as an exponential using a formal variable t:

Z(t) = exp(∑_s=1^∞N_st_s/s)

The first Weil conjecture says Z(t) is a rational function:

Z(t) = P(t)/Q(t)

for integer polynomials P(t) and Q(t). This is a strong constraint on the numbers of solutions N_s. It means there are complex algebraic numbers a₁ . . . a_i and b₁ . . . b_j such that

N_s =(a^s₁ +…+ a^s_i) − (b^s₁ +…+ b^s_j)

And each algebraic conjugate of an a (resp. b) also an a (resp. b).

The second conjecture is a functional equation:

Z(1/qⁿt) = ± q^nE/2t^EZ(t)

This says the operation x → qⁿ/x permutes the a’s (resp. the b’s).The third is a Riemann Hypothesis

Z(t) = (P₁(t)P₃(t) · · · P_2n−1(t))/(P₀(t)P₂(t) · · · P_2n(t))

where each P_k is an integer polynomial with all roots of absolute value q^−k/2. That means each a has absolute value q^k for some 0 ≤ k ≤ n. Each b has absolute value q^(2k−1)/2 for some 0 ≤ k ≤ n.

Over it all is the conjectured link to topology. Let B₀, B₁, . . . B_2n be the Betti numbers of the complex manifold defined by the same polynomials. That is, each B_k gives the number of k-dimensional holes or handles on the continuous space of complex number solutions to the equations. And recall an algebraically n-dimensional complex manifold is topologically 2n-dimensional. Then each P_k has degree B_k. And E is the Euler number of the manifold, the alternating sum

∑_k=0²ⁿ (−1)^kB_k

On its face the topology of a continuous manifold is worlds apart from arithmetic over finite fields. But the topology of this manifold tells how many a’s and b’s there are with each absolute value. This implies useful numerical approximations to the numbers of roots N_s. Special cases of these conjectures, with aspects of the topology, were proved before Weil, and he proved more. All dealt with curves (1-dimensional) or hypersurfaces (defined by a single polynomial).

Weil presented the topology as motivating the conjectures for higher dimensional varieties. He especially pointed out how the whole series of conjectures would follow quickly if we could treat the spaces of finite field solutions as topological manifolds. The topological strategy was powerfully seductive but seriously remote from existing tools. Weil’s arithmetic spaces were not even precisely defined. To all appearances they would be finite or (over the algebraic closures of the finite fields) countable and so everywhere discontinuous. Topological manifold methods could hardly apply.

Abelian Categories, or Injective Resolutions are Diagrammatic. Note Quote.

Jean-Pierre Serre gave a more thoroughly cohomological turn to the conjectures than Weil had. Grothendieck says

Anyway Serre explained the Weil conjectures to me in cohomological terms around 1955 – and it was only in these terms that they could possibly ‘hook’ me …I am not sure anyone but Serre and I, not even Weil if that is possible, was deeply convinced such [a cohomology] must exist.

Specifically Serre approached the problem through sheaves, a new method in topology that he and others were exploring. Grothendieck would later describe each sheaf on a space T as a “meter stick” measuring T. The cohomology of a given sheaf gives a very coarse summary of the information in it – and in the best case it highlights just the information you want. Certain sheaves on T produced the Betti numbers. If you could put such “meter sticks” on Weil’s arithmetic spaces, and prove standard topological theorems in this form, the conjectures would follow.

By the nuts and bolts definition, a sheaf F on a topological space T is an assignment of Abelian groups to open subsets of T, plus group homomorphisms among them, all meeting a certain covering condition. Precisely these nuts and bolts were unavailable for the Weil conjectures because the arithmetic spaces had no useful topology in the then-existing sense.

At the École Normale Supérieure, Henri Cartan’s seminar spent 1948-49 and 1950-51 focussing on sheaf cohomology. As one motive, there was already de Rham cohomology on differentiable manifolds, which not only described their topology but also described differential analysis on manifolds. And during the time of the seminar Cartan saw how to modify sheaf cohomology as a tool in complex analysis. Given a complex analytic variety V Cartan could define sheaves that reflected not only the topology of V but also complex analysis on V.

These were promising for the Weil conjectures since Weil cohomology would need sheaves reflecting algebra on those spaces. But understand, this differential analysis and complex analysis used sheaves and cohomology in the usual topological sense. Their innovation was to find particular new sheaves which capture analytic or algebraic information that a pure topologist might not focus on.

The greater challenge to the Séminaire Cartan was, that along with the cohomology of topological spaces, the seminar looked at the cohomology of groups. Here sheaves are replaced by G-modules. This was formally quite different from topology yet it had grown from topology and was tightly tied to it. Indeed Eilenberg and Mac Lane created category theory in large part to explain both kinds of cohomology by clarifying the links between them. The seminar aimed to find what was common to the two kinds of cohomology and they found it in a pattern of functors.

The cohomology of a topological space X assigns to each sheaf F on X a series of Abelian groups HⁿF and to each sheaf map f : F → F′ a series of group homomorphisms Hⁿf : HⁿF → HⁿF′. The definition requires that each Hⁿ is a functor, from sheaves on X to Abelian groups. A crucial property of these functors is:

HⁿF = 0 for n > 0

for any fine sheaf F where a sheaf is fine if it meets a certain condition borrowed from differential geometry by way of Cartan’s complex analytic geometry.

The cohomology of a group G assigns to each G-module M a series of Abelian groups HⁿM and to each homomorphism f : M →M′ a series of homomorphisms HⁿF : HⁿM → HⁿM′. Each Hⁿ is a functor, from G-modules to Abelian groups. These functors have the same properties as topological cohomology except that:

HⁿM = 0 for n > 0

for any injective module M. A G-module I is injective if: For every G-module inclusion N M and homomorphism f : N → I there is at least one g : M → I making this commute

Cartan could treat the cohomology of several different algebraic structures: groups, Lie groups, associative algebras. These all rest on injective resolutions. But, he could not include topological spaces, the source of the whole, and still one of the main motives for pursuing the other cohomologies. Topological cohomology rested on the completely different apparatus of fine resolutions. As to the search for a Weil cohomology, this left two questions: What would Weil cohomology use in place of topological sheaves or G-modules? And what resolutions would give their cohomology? Specifically, Cartan & Eilenberg defines group cohomology (like several other constructions) as a derived functor, which in turn is defined using injective resolutions. So the cohomology of a topological space was not a derived functor in their technical sense. But a looser sense was apparently current.

Grothendieck wrote to Serre:

I have realized that by formulating the theory of derived functors for categories more general than modules, one gets the cohomology of spaces at the same time at small cost. The existence follows from a general criterion, and fine sheaves will play the role of injective modules. One gets the fundamental spectral sequences as special cases of delectable and useful general spectral sequences. But I am not yet sure if it all works as well for non-separated spaces and I recall your doubts on the existence of an exact sequence in cohomology for dimensions ≥ 2. Besides this is probably all more or less explicit in Cartan-Eilenberg’s book which I have not yet had the pleasure to see.

Here he lays out the whole paper, commonly cited as Tôhoku for the journal that published it. There are several issues. For one thing, fine resolutions do not work for all topological spaces but only for the paracompact – that is, Hausdorff spaces where every open cover has a locally finite refinement. The Séminaire Cartan called these separated spaces. The limitation was no problem for differential geometry. All differential manifolds are paracompact. Nor was it a problem for most of analysis. But it was discouraging from the viewpoint of the Weil conjectures since non-trivial algebraic varieties are never Hausdorff.

Serre replied using the same loose sense of derived functor:

The fact that sheaf cohomology is a special case of derived func- tors (at least for the paracompact case) is not in Cartan-Sammy. Cartan was aware of it and told [David] Buchsbaum to work on it, but he seems not to have done it. The interest of it would be to show just which properties of fine sheaves we need to use; and so one might be able to figure out whether or not there are enough fine sheaves in the non-separated case (I think the answer is no but I am not at all sure!).

So Grothendieck began rewriting Cartan-Eilenberg before he had seen it. Among other things he preempted the question of resolutions for Weil cohomology. Before anyone knew what “sheaves” it would use, Grothendieck knew it would use injective resolutions. He did this by asking not what sheaves “are” but how they relate to one another. As he later put it, he set out to:

consider the set13 of all sheaves on a given topological space or, if you like, the prodigious arsenal of all the “meter sticks” that measure it. We consider this “set” or “arsenal” as equipped with its most evident structure, the way it appears so to speak “right in front of your nose”; that is what we call the structure of a “category”…From here on, this kind of “measuring superstructure” called the “category of sheaves” will be taken as “incarnating” what is most essential to that space.

The Séminaire Cartan had shown this structure in front of your nose suffices for much of cohomology. Definitions and proofs can be given in terms of commutative diagrams and exact sequences without asking, most of the time, what these are diagrams of.  Grothendieck went farther than any other, insisting that the “formal analogy” between sheaf cohomology and group cohomology should become “a common framework including these theories and others”. To start with, injectives have a nice categorical sense: An object I in any category is injective if, for every monic N → M and arrow f : N → I there is at least one g : M → I such that

Fine sheaves are not so diagrammatic.

Grothendieck saw that Reinhold Baer’s original proof that modules have injective resolutions was largely diagrammatic itself. So Grothendieck gave diagrammatic axioms for the basic properties used in cohomology, and called any category that satisfies them an Abelian category. He gave further diagrammatic axioms tailored to Baer’s proof: Every category satisfying these axioms has injective resolutions. Such a category is called an AB5 category, and sometimes around the 1960s a Grothendieck category though that term has been used in several senses.

So sheaves on any topological space have injective resolutions and thus have derived functor cohomology in the strict sense. For paracompact spaces this agrees with cohomology from fine, flabby, or soft resolutions. So you can still use those, if you want them, and you will. But Grothendieck treats paracompactness as a “restrictive condition”, well removed from the basic theory, and he specifically mentions the Weil conjectures.

Beyond that, Grothendieck’s approach works for topology the same way it does for all cohomology. And, much further, the axioms apply to many categories other than categories of sheaves on topological spaces or categories of modules. They go far beyond topological and group cohomology, in principle, though in fact there were few if any known examples outside that framework when they were given.