35th Symposium on
Transformation groups
November 11–13, 2008

Okayama, Japan

Borsuk-Ulam type theorems andequilibria in a class of games
Stanislaw Spież
Institute of Mathematics
Polish Academy of Sciences
Warsaw, Poland

joint research withThomas Schick (Götingen),
Robert S. Simon (London) andHenryk Toruńczyk (Warsaw)

11. A brief description of
repeated games with incomplete information
We consider infinitely repeated two-person, nonzero-sum games of incomplete information on one
side on one side, which were introduced by Aumann,
Mashler and Stearns in late 1960’s. Further basic
results were obtained by S.Sorin in 1983.
There is a finite set K of states of nature andtwo players A and B.
Nature chooses a state k ∈ K according toa commonly known probability distribution on K.
The first player, but not the second player, is informed of nature’s choice. The chosen state remains
constant throughout the play.
The finite sets of moves for the players, I for A
and J for B, are the same for all states.
The chosen state k, along with the moves of theplayers, determines the stage payoffs, during the play
the second player learns nothing about his payoff, as
this could give him information about the state ofnature.
2Let m := |I| be the number of the first player’s
actions and n := |J| the number of the second
player’s actions.
For every state k ∈ K there are two m × n
matrices Ak and B k . The i, j entry of Ak is thepayoff that the first player receives if the state ofnature is k, the first player chooses the action i andthe second player chooses the actions j. Likewise thei, j entry of B k is the payoff that the second player
receives if the state of nature is k, the first playerchooses the action i and the second player chooses
the actions j.
An equilibrium of the game is a pair of strategies
such that• for every state k ∈ K there are limits ak andbk as the number n of stages go to infinity for theaverages summed over the stages up to the stagen of the expected payoffs of Players One and Two,
respectively, and• neither player can obtain a higher limit superior
as n goes to infinity for his average payoff summed
over the stages up to n (and determined by the initialprobability distribution on K) by choosing a different strategy.
3More detailed descriptions of equilibria for thegames under consideration can be found in [A–M],[So], [Si], [R] and [S–S–T 2].
We divide the problem of equilibrium existence
for these games into four levels of difficulty.
• The first level of difficulty concerns the conventional game (of standard information): after eachstage of play both players are informed of each others’ moves and this is the only information the players receive additional to what they knew when theplay began. Equilibrium existence for this level wasproven by S. Sorin (1983) in the case |K| ≤ 3, andin general case in [S–S–T 1], 1995.
• For the second level of difficulty both players do
not know exactly what the other player has done,
but at least the perception of the second player isindependent of the state. Equilibrium existence forthe second level was proven by J. Renault, [R], 2000.
• For the third level of difficulty the perception of
the second player could be dependent on the state,
however the first player has at least some channel
with which she can communicate messages that reveal nothing about the state. Equilibrium existence4for the third level was established in [S–S–T 2], 2002.
The methods used to prove equilibrium existence for the third level, were applied in [S–S–T 3],
2008, to economic situations broader than that of repeated games of incomplete information, in particular to principal-agent situations. A typical principalagent situation is that of the relationship between
the owner of a firm (the principal) and its manager(the agent). The owner employs the manager, bothare interested in the success of the firm, but their interests do not coincide and the agent has informationon the firm that the owner does not have.
• For the fourth level of difficulty there are no assumptions whatsoever concerning the perception of
the second player. The question of equilibrium existence for the fourth level remains open. A strategy of a proof of equilibrium existence is describedin [S], 2003. It requires a parametrized version of
Borsuk–Ulam theorem obtained in [S–S–S–T], 2007,
and further advances which still have to be workedout.

5

2. How do the topological results
enter into the play
For the Game with standard information, Aumann, Maschler and Stearns devised strategies (onefor each players) which lead to an equilibrium, provided such strategies pairs existed.
They proposed that both players agreed to playat each stage of the game in a certain prescribedmanner, known to both of them.
If any of the players violated this agreement,
the other one used a punishing strategy that kept
the payoff relatively low.
For all of this to work a complicated system ofinequalities and equalities needed to be solvable.

6

It turns out that a solution to this system would
exist if we were able to attack the following problem:
Let ∆ be an n-simplex in Rn , and let a pointp0 ∈ ∆ and real functions a and bv , v ∈ Rn , on
∆ be given, with the functions bv being convex andcontinuously depending on v. Let r : Rn → ∆ bethe nearest point retraction.
Establish conditions under which it is true that
• either bp0 can be separated from a by an affine
functional, or• there exits a finite set P0 ⊂ Rn and an affinefunctional Φ in Rn such that p0 ∈ conv (r(P0 )) anda ≤ Φ|∆ ≤ bp , for all p ∈ P0 .
This geometric problem leads to a setup concerning set–valued functions.

73. Some results on correspondences
By a correspondence F : X → Y we mean asubset of X × Y such that its projection to X is aproper mapping–that is, it is closed and has compact
point-inverses.
For x ∈ X, y ∈ Y we consider the sets
F (x) := {y 0 ∈ Y : (x, y 0 ) ∈ F } ,F −1 (y) := {x0 ∈ X : (x0 , y) ∈ F }In general, we do not assume that the set F (x)be non–empty for all x ∈ X.
The set dom F := {x ∈ X : F (x) 6= ∅} is called
the domain of F , and similarly we define F (U ) =Su∈U F (u), the image under F of a subset U of X.
By the restriction F |S of F to a set S ⊂ X wemean the correspondence F ∩ (S × Y ).
We say that F is acyclic–valued if, for each x ∈X, F (x) is non–empty and has trivial reduced Čechhomologies with coefficients in Z/2.

8

Let (W, ∂W ) be a relative k-manifold and F :W → Y a correspondence. We say F has property
S (spanning property) for (W, ∂W ) if the homomorphism
Hk (F, F|∂W ; Z/2) → Hk (W, ∂W ; Z/2)
of Čech homology groups induced by the projection
to W is an epimorphism. Note that in this casedom(F ) = W .
We say F : Rn → Y has property S for an open
set U ⊂ Rn if F|Ū has property S for (Ū , ∂U ).
In our setting, X is often going to be a subsetof an Euclidean space. Whenever this is the case wemay define the following correspondence:cF :=[conv (F −1 (y)) × {y}y∈YWe say that cF is a level–wise convexification of F .

9

Theorem 1. Let U be an open bounded subset ofRn , and let F be an acyclic-valued correspondence
defined on the closure of U . If dim F (U ) < n, thenc(F|∂U ) has property S for U and, consequently, U ⊂dom c(F|∂U ).
Thus each point p0 ∈ U is in the domain ofc(F|∂U ), i.e. there exists Ta finite set P0 ⊂ ∂U suchthat p0 ∈ conv (P0 ) and p∈P0 F (p) 6= ∅.
• Application to games. Theorem 1 allows to give arather satisfactory answer to the problem on separation of functions. We do not formulate the sufficient condition obtained, the essence of which is that
it forces the image of the arising correspondence tohave dimension smaller than n and thus makes Theorem 1 applicable. In this way the existence of an
equilibrium in the first level of difficulty is established (see [S–S–T 1]).
Applying Theorem 1 and some other properties of correspondences, we prove the following twotheorems, Theorem 2 and Theorem 3, needed in theproof of existence of an equilibrium in the third levelof difficulty (see [S–S–T 2] and [S–S–T 3]).

10

For applications to game theory, “saturated”
correspondences into cubes turn out to be special:
If F : ∆(L)→Y is a correspondence and Y ⊂RL , where L is a finite set, then by F + we denotethe correspondence ∆(L)→Y defined byF + (p) := {y ∈ Y : ∃x ∈ F (p) such that xl ≤ y l
for all l ∈ L and xl = y l if pl > 0}.
We call F + the Y -saturation of F and say that F issaturated if F = F + . Below, Y = I L is a cube, withI a non-trivial compact segment in R.
Theorem 2. Let C be a family
S of non-void subsets
of a finite set K such that
C = K. Suppose further there are given a point p ∈ ∆(K) and, for every
L ∈ C, a saturated correspondence FL : ∆(L)→I L
with property S for ∆(L) and a closed convex subset UL of I K containing Tthe point (b, b, . . . , b). Then
there exist a point y ∈ L∈C UL ⊂ I K and finitely
many sets L1 , . . . , Ls ∈ C and points pi ∈ ∆(Li ) ⊂∆(K), i = 1, . . . , s, such that the following conditions hold:p ∈ conv {p1 , . . . , ps } and y Li ∈ FLi (pi ) for each i .
11

To warrant property S of the correspondences
FL we depend on the following
Theorem 3. Let F : ∆ → I L be a convex-valued
correspondence and a : ∆ → I be a lower semicontinuous function such thata(q) ≤ sup{y · q : y ∈ F (p)} for all p, q ∈ ∆.
With F + denoting the I L –saturation of F , the correspondence Fe : ∆→RL defined by the formula below
has property S for ∆:Fe(p) := {y ∈ c(F + )(p) : y · q ≥ a(q) for all q ∈ ∆}.

Above, convex–valued means that each set F (p),p ∈ ∆, is non–empty and convex,

124. Relation to antipodal–type theorems.
From Theorem 1 applied to a single–valued
function it follows that when x0 is a point of a compact set C ⊂ Rn and f : C → Y is a mapping into aspace of dimension n − 1, then in the boundary of C
there exists a set C0 mapped by f into a singletonand containing x0 in its convex hull.
By Caratheodory’s theorem one can always replace C0 by its subset consisting of ≤ n + 1 points.
In general, this number cannot be lowered.
Example. Let f be the natural simplicial map of
the barycentric subdivision of an n-simplex ∆ onto
the join of the barycenter of ∆ and of the (n − 2)skeleton of ∆. Then the center of ∆ cannot be represented as a convex combination of n points thathave a common image.
However, in the special case where Y is an(n − 1)–manifold, a generalization of Borsuk-Ulamtheorem given by J. Olȩdzki implies that C0 may betaken to consist of 2 points. (Special cases of thiswere established by K. Sieklucki and K. D. Joshi.
The well–known Borsuk–Ulam theorem deals withthe case when C is a ball.)13

It would be interesting to know less restrictive
assumptions under which n + 1 above could be replaced by a smaller number.
This is related also to estimating the k–Urysohn
diameter of a compact set C, defined as the infimumof sup{diam(f −1 (y) : y ∈ f (C)} where f runs over
all mappings of C to k–dimensional spaces.
It follows easily from the above, that the (n−1)–
diameter of a ball in Rn equals to the “usual” diameter of a regular simplex inscribed into this ball’s
boundary (apparently this has already been known).
When k ∈ (n/2, n − 2] the k-Urysohn diameter of ann–ball remains unknown.

14

5. A parameterized Borsuk-Ulam theorem
Let W be an k-dimensional compact connected
manifold with boundary ∂W (possibly ∂W = ∅) andletF ⊂ W × S m × Rm
be compact.
We associate to F its Borsuk-Ulam correspondence G ⊂ W × Rm defined by
G := {(w, v) : ∃u ∈ S m : (w, u, v), (w, −u, v) ∈ F } .
Note that, if W = {pt} and F is the graph ofa continuous function S m → Rm , then the BorsukUlam theorem states that G is non-empty, whence
the chosen name.
Theorem 4. Suppose that the correspondence F :W × S m → Rm has property S for (W, ∂W ) × S m .
Then the correspondence G : W → Rm has property
S for (W, ∂W ). Consequently, G is mapped onto W
by the projection W × Rm → W .
Notation. Below, by H we denote the Čech homology functor with coefficients in Z/2.
15

An equivalent statement:
Suppose that the homomorphismp∗ : Hk+m (F, F|∂W ×S m ) → Hk+m ((W, ∂W ) × S m ) ,where p : (F, F|∂W ×S m ) → (W, ∂W )×S m is the map
induced by the projection W ×S m ×Rm → W ×S m ,is an epimorphism. Thenq∗ : Hk (G, G|∂W ) → Hk (W, ∂W ) ,where q : (G, G|∂W ) → (W, ∂W )) is the map inducedby the projection W × Rm → W , is an epimorphism
as well.
Remark. Theorem 4 is the parametrized BorsukUlam theorem. Loosely speaking, it asserts the following: if one has a family of Borsuk-Ulam problems
parametrized by a manifold W which depend “continuously” on the points in W , then the solutions tothe Borsuk-Ulam problem can be chosen to depend“continuously” on the points in W as well.
“Continuity” here is measured by the fact that
one can span a Čech-homology class through the set
which projects down to the fundamental class of W .
16

Sketch of the proof of Theorem 4
Let [(W, ∂W ) × S m ] and [W, ∂W ] be fundamental classes of the manifolds (W, ∂W ) × S m and(W, ∂W ), respectively.
Note that to prove the theorem it suffices todefine a map
Hk+m (F, F|∂W ×S m )) → Hk (G, G|∂W ), f 7→ gf
such that q∗ (gf ) = [(W, ∂W )] provided p∗ (f ) =[(W, ∂W ) × S m ].
To define this map, we need to establish a relative squaring construction in Čech homology.
Let (X, A) be a pair of compacta. On X ×X, wehave the involution τ with τ (x, y) = (y, x). Consider
the quotient pair
SP (X, A) := ((X × X)/τ, (X × A ∪ A × X ∪ D)/τ ) ,where D := {(x, x) | x ∈ X} is the diagonal.
Then there is a natural homomorphism, calledinvariant homology squaring
Sq : Hk (X, A) → H2k (SP (X, A)) ,with the following properties:
17(1) Let M be a manifold with the boundary∂M and let [M, ∂M ] ∈ Hdim M (M, ∂M ) be thefundamental class of (M, ∂M ). Then the fundamental class [SP (M, ∂M )] of the relative manifold
SP (M, ∂M ) is equal to Sq[M, ∂M ].
(2) Let (X, A) and (Y, B) be pairs of compacta
such that (X, A) ⊂ (Y, B). ThenSq(i∗ (x)) = j∗ (Sq(x))
for each x ∈ H∗ (X, A), where i : (X, A) ,→ (Y, B)
and j : SP (X, A) ,→ SP (Y, B) denote the inclusions.
(3) Let (X, A) and (Y, B) be arbitrary pairsof compact subsets of a manifold M , and let x ∈Hk (X, A) and y ∈ Hl (Y, B). ThenSq(x • y) = Sq(x) • Sq(y),where • denotes the intersection of homology classes.
(Let us recall, thatx • y ∈ Hk+l−dim M (X ∩ Y, X ∩ B ∪ A ∩ Y ) .)18

Using the invariant homology squaring, we describe for each f ∈ Hk+m (F, F|∂W ×S m ) the requiredelement gf ∈ Hk (G, G|∂W ) as follows.
We define the “antidiagonal”∆ := {[w, u, v, w, −u, v]} ⊂ SP (W × S m × Rm ) .
Observe that∆∼= W × RP m × Rm .
By [∆, ∂∆] ∈ H3k+2m (∆, ∂∆) we denote thefundamental class of the manifold (∆, ∂∆) (we use
locally finite homology).
Let (F 0 , ∂F 0 ) := SP (F, F|∂W ×S m ) ∩ (∆, ∂∆) .
We definegf := (πG )∗ (Sq(f ) • [∆, ∂∆]) ,where πG : (F 0 , ∂F 0 ) → (G, G|∂W ) is induced by theprojection ∆ ∼= W × RP m × Rm → W × Rm .

19One can observe thatq∗ (gf ) = (πW ◦ jF 0 )∗ (Sq(f ) • [∆, ∂∆]) ,where jF 0 : (F 0 , ∂F 0 ) → (∆, ∂∆) is the inclusion, andπW : (∆, ∂∆) ∼= (W, ∂W ) × RP m × Rm → (W, ∂W )denotes the projection.
Thus, to conclude the proof it suffice to showthat(a)(πW ◦ jF 0 )∗ (Sq(f ) • [∆, ∂∆]) = [W, ∂W ]provided p∗ (f ) = [(W, ∂W ) × S m ].
To prove (a), we first show that(b)d ),c , ∂W
Sq(f ) = [E, ∂E] in H2(k+m) (Wd ) := SP ((W, ∂W ) × S m × Rm ), E isc , ∂W
where (Wc consisting of all points
the subset of W[w, (u, um+1 ), u, w0 , (u0 , u0m+1 ), u0 ]d.
such that um+1 , u0m+1 ∈ S m , and ∂E := E ∩ ∂W

20

Notation. If (Xi , Ai ) ⊂ (Y, B), i = 1, 2, and xi ∈H∗ (Xi , Ai ), then we say that x1 and x2 are equal inH∗ (Y, B) if there images under the homeomorphismsof homology groups induced by the corresponding
inclusions are equal.
By (b), in Hk (∆, ∂∆) we haveSq(f ) • [∆, ∂∆] = [E, ∂E] • [∆, ∂∆] .
Since E and ∆ intersect transversally it follows that[E, ∂E] • [∆, ∂∆] = [E ∩ ∆, ∂E ∩ ∂∆] .
Next, because πW |(E ∩ ∆, ∂E ∩ ∂∆) is a homeomorphism onto (W, ∂W ), it follows that(πw ◦ jE∩∆ )∗ ([E ∩ ∆, ∂E ∩ ∂∆]) = [W, ∂W ] ,where jE∩∆ : (E ∩ ∆, ∂E ∩ ∂∆) ,→ (∆, ∂∆) is theinclusion.
Consequently,(πw ◦ jF 0 )∗ (Sq(f ) • [∆, ∂∆]) = [W, ∂W ]since in Hk (∆, ∂∆) we haveSq(f ) • [∆, ∂∆] = [E ∩ ∆, ∂E ∩ ∂∆] .
This completes the proof of Theorem 4.
21

References[A–M] R. Aumann, and M. Maschler, Repeated Games with Incomplete Information, with the collaboration of R. Stearns, M.I.T. Press, Cambridge, MA,1995.
[R] J. Renault, On Two-player Repeated Games
with Lack of Information on One Side and Stateindependent Signalling, Mathematics of Operations
Research, 25 (4), 552-572, 2000.
[S–S–S–T] T. Schick, R. S. Simon, S. Spież, H.
Toruńczyk, A parametrized version of Borsuk–Ulamtheorem, available on arXiv, 2007.
[Si] R. S. Simon, Habilitation thesis, Habilitation
thesis, Göttingen, 2003.
[S–S–T 1] R. S. Simon, S. Spież, H. Toruńczyk, The
Existence of Equilibria in Certain Games, Separation for Families of Convex Functions and a Theorem of Borsuk-Ulam Type, Israel Journal of Mathematics 92, 1–21, 1995.

22

[S–S–T 2] —— Equilibrium existence and topology insome repeated games with incomplete information,
Transactions of the American Mathematical Society
354, 5005–5026, 2002
[S–S–T 3] —— Equilibria in a class of games andtopological results implying their existence, Rev. R.
Acad. Cien. Serie A. Mat. 102, 161–179, 2008.
[So] S. Sorin, S, Some Results on the Existence ofNash Equilibria for Non-zero-sum Games with Incomplete Information, International Journal of Game
Theory 12, 193–205, 1983.

23