Game’s Degeneracy Running Proportional to Polytope’s Redundancy.

For a given set of vertices V ⊆ R^K a Polytope P can be defined as the following set of points:

P = {∑_i=1^|V|λ_iv_i ∈ R^K | ∑_i=1^|V|λ_i = 1; λ_i ≥ 0; v_i ∈ V}

Polytope is an intersection of boundaries that separate the space into two distinct areas. If a polytope is to be defined as an intersection of half spaces, then for a matrix M ∈ R^mxn, and a vector b ∈ R^m, polytope P is defined as a set of points

P = {x ∈ Rⁿ | M_x ≤ b}

Switching over to a two-player game, (A, B) ∈ R^mxn2_>0, the row/column best response polytope P/Q is defined by:

P = {x ∈ R^m | x ≥ 0; xB ≤ 1}

Q = {y ∈ Rⁿ | Ay ≤ 1; y ≥ 0}

The polytope P, corresponds to the set of points with an upper bound on the utility of those points when considered as row strategies against which the column player plays.

An affine combination of points z₁,….z_k in some Euclidean space is of the form ∑_i=1^kλ_iz_i, where λ₁, …, λ_k are reals with ∑_i=1^kλ_i= 1. It is called a convex combination, if λ_i ≥ 0 ∀ i. A set of points is convex if it is closed under forming convex combinations. Given points are affinely independent if none of these points are an affine combination of the others. A convex set has dimension d iff it has d + 1, but no more, affinely independent points.

A polyhedron P in R^d is a set {z ∈ R^d | C_z ≤ q} for some matrix C and vector q. It is called full-dimensional if it has dimension d. It is called a polytope if it is bounded. A face of P is a set {z ∈ P | c^⊤z = q₀} for some c ∈ R^d, q₀ ∈ R, such that the inequality c^⊤z ≤ q₀ holds for all z in P. A vertex of P is the unique element of a zero-dimensional face of P. An edge of P is a one-dimensional face of P. A facet of a d-dimensional polyhedron P is a face of dimension d − 1. It can be shown that any nonempty face F of P can be obtained by turning some of the inequalities defining P into equalities, which are then called binding inequalities. That is, F = {z ∈ P | c_iz = q_i, i ∈ I}, where c_iz ≤ q_i for i ∈ I are some of the rows in C_z ≤ q. A facet is characterized by a single binding inequality which is irredundant; i.e., the inequality cannot be omitted without changing the polyhedron. A d-dimensional polyhedron P is called simple if no point belongs to more than d facets of P, which is true if there are no special dependencies between the facet-defining inequalities. The “best response polyhedron” of a player is the set of that player’s mixed strategies together with the “upper envelope” of expected payoffs (and any larger payoffs) to the other player.

Nondegeneracy of a bimatrix game (A, B) can be stated in terms of the polytopes P and Q as no point in P has more than m labels, and no point in Q has more than n labels. (If x ∈ P and x has support of size k and L is the set of labels of x, then |L ∩ M| = m − k, so |L| > m implies x has more than k best responses in L ∩ N. Then P and Q are simple polytopes, because a point of P, say, that is on more than m facets would have more than m labels. Even if P and Q are simple polytopes, the game can be degenerate if the description of a polytope is redundant in the sense that some inequality can be omitted, but nevertheless is sometimes binding. This occurs if a player has a pure strategy that is weakly dominated by or payoff equivalent to some other mixed strategy. Non-simple polytopes or redundant inequalities of this kind do not occur for “generic” payoffs; this illustrates the assumption of nondegeneracy from a geometric viewpoint. (A strictly dominated strategy may occur generically, but it defines a redundant inequality that is never binding, so this does not lead to a degenerate game.) Because the game is nondegenerate, only vertices of P can have m labels, and only vertices of Q can have n labels. Otherwise, a point of P with m labels that is not a vertex would be on a higher dimensional face, and a vertex of that face, which is a vertex of P, would have additional labels. Consequently, only vertices of P and Q have to be inspected as possible equilibrium strategies. Algorithmically, if the input is a nondegenerate bimatrix game, and output is an Nash equilibria of the game, then the method employed for each vertex x of P − {0}, and each vertex y of Q − {0}, if (x, y) is completely labeled, the output then is the Nash equilibrium (x · 1/1^⊤x, y · 1/1^⊤y).

Advertisement

Banach Spaces

Some things in linear algebra are easier to see in infinite dimensions, i.e. in Banach spaces. Distinctions that seem pedantic in finite dimensions clearly matter in infinite dimensions.

The category of Banach spaces considers linear spaces and continuous linear transformations between them. In a finite dimensional Euclidean space, all linear transformations are continuous, but in infinite dimensions a linear transformation is not necessarily continuous.

The dual of a Banach space V is the space of continuous linear functions on V. Now we can see examples of where not only is V* not naturally isomorphic to V, it’s not isomorphic at all.

For any real p > 1, let q be the number such that 1/p  + 1/q = 1. The Banach space L^p is defined to be the set of (equivalence classes of) Lebesgue integrable functions f such that the integral of ||f||^p is finite. The dual space of L^p is L^q. If p does not equal 2, then these two spaces are different. (If p does equal 2, then so does q; L² is a Hilbert space and its dual is indeed the same space.)

In the finite dimensional case, a vector space V is isomorphic to its second dual V**. In general, V can be embedded into V**, but V** might be a larger space. The embedding of V in V** is natural, both in the intuitive sense and in the formal sense of natural transformations. We can turn an element of V into a linear functional on linear functions on V as follows.

Let v be an element of V and let f be an element of V*. The action of v on f is simply fv. That is, v acts on linear functions by letting them act on it.

This shows that some elements of V** come from evaluation at elements of V, but there could be more. Returning to the example of Lebesgue spaces above, the dual of L¹ is L^∞, the space of essentially bounded functions. But the dual of L^∞ is larger than L¹. That is, one way to construct a continuous linear functional on bounded functions is to multiply them by an absolutely integrable function and integrate. But there are other ways to construct linear functionals on L^∞.

A Banach space V is reflexive if the natural embedding of V in V** is an isomorphism. For p > 1, the spaces L^p are reflexive.

Suppose that X is a Banach space. For simplicity, we assume that X is a real Banach space, though the results can be adapted to the complex case in the straightforward manner. In the following, B(x₀,ε) stands for the closed ball of radius ε centered at x₀ while B◦(x₀,ε) stands for the open ball, and S(x₀,ε) stands for the corresponding sphere.

Let Q be a bounded operator on X. Since we will be interested in the hyperinvariant subspaces of Q, we can assume without loss of generality that Q is one-to-one and has dense range, as otherwise ker Q or Range Q would be hyperinvariant for Q. By {Q}′ we denote the commutant of Q.

Fix a point x₀ ≠ 0 in X and a positive real ε<∥x0∥. Let K= Q⁻¹B(x₀,ε). Clearly, K is a convex closed set. Note that 0 ∉ K and K≠ ∅ because Q has dense range. Let d = inf_K||z||, then d > 0. If X is reflexive, then there exists z ∈ K with ||z|| = d, such a vector is called a minimal vector for x₀, ε and Q. Even without reflexivity condition, however, one can always find y ∈ K with ||y|| ≤ 2d, such a y will be referred to as a 2-minimal vector for x₀, ε and Q.

The set K ∩ B(0, d) is the set of all minimal vectors, in general this set may be empty. If z is a minimal vector, since z ∈ K = Q⁻¹B(x₀, ε) then Qz ∈ B(x₀, ε). As z is an element of minimal norm in K then, in fact, Qz ∈ S(x₀, ε). Since Q is one-to-one, we have

QB(0, d) ∩ B(x₀, ε) = Q B(0, d) ∩ K) ⊆ S(x₀, ε).

It follows that QB(0,d) and B◦(x₀,ε) are two disjoint convex sets. Since one of them has non-empty interior, they can be separated by a continuous linear functional. That is, there exists a functional f with ||f|| = 1 and a positive real c such that f_|QB(0,d)  ≤ c and f_|B◦(x0,ε) ≥ c. By continuity, f_|B(x0,ε) ≥ c. We say that f is a minimal functional for x₀, ε, and Q.

We claim that f(x₀) ≥ ε. Indeed, for every x with ||x|| ≤ 1 we have x₀ − εx ∈ B(x₀,ε). It follows that f(x₀ − εx) ≥ c, so that f(x₀) ≥ c + εf(x). Taking sup over all x with ||x|| ≤ 1 we get f(x0) ≥ c + ε||f|| ≥ ε.

Observe that the hyperplane Q^∗f = c separates K and B(0, d). Indeed, if z ∈ B(0,d), then (Q^∗f)(z) = f(Qz) ≤ c, and if z ∈ K then Qz ∈ B(x₀,ε) so that (Q∗f)(z) = f(Qz) ≥ c. For every z with ||z|| ≤ 1

we have dz ∈ B(0,d), so that (Q^∗f)(dz) ≤ c, it follows that Q^∗f ≤ c/d

On the other hand, for every δ > 0 there exists z ∈ K with ||z|| ≤ d+δ, then (Q^∗f)(z) ≥ c ≥ c/(d+δ) ||z||, whence ||Q^∗f|| ≥ c/(d+δ) . It follows that

||Q∗f|| = c/d.

For every z ∈ K we have (Q^∗f)(z) ≥ c = d ||Q^∗f||. In particular, if y is a 2-minimal vector then

(Q^∗f)(y) ≥ 1/2 Q^∗f ||y||….

Galois Connections. Part 3.

Let (P,≤P) and (Q,≤Q) be posets, and consider two set functions ∗ ∶ P ⇄ Q ∶ ∗. We will denote these by p ↦ p ∗ and q ↦ q ∗ for all p ∈ P and q ∈ Q. This pair of functions is called a Galois connection if, for all p ∈ P and q ∈ Q, we have

p ≤ P q ∗ ⇐⇒ q ≤ Q p  ∗

Let ∗ ∶ P ⇄ Q ∶ ∗ be a Galois connection. For all elements x of P or Q we will use the notations x ∗ ∗ ∶= (x ∗)∗ and x ∗ ∗ ∗ ∶= (x ∗ ∗)∗.

(1) For all p ∈ P and q ∈ Q we have

p ≤ P p ∗ ∗ and q ≤ Q q ∗ ∗.

(2) For all elements p1, p2 ∈ P and q1, q2 ∈ Q we have

p1 ≤ P p2 ⇒ p ∗ 2 ≤ Q p ∗ 1 and q1 ≤ Q q2 ⇒ q2 ∗ ≤ P q1 ∗.

(3) For all elements p ∈ P and q ∈ Q we have

p ∗ ∗ ∗ = p ∗ and q ∗ ∗ ∗ = q ∗

Proof:

Since the definition of a Galois connection is symmetric in P and Q, we will simplify the proof by using the notation

x ≤ y ∗ ⇐⇒ y ≤ x ∗

for all elements x,y such that the inequalities make sense. To prove (1) note that for any element x we have x ∗ ≤ x ∗ by the reflexivity of partial order. Then from the definition of Galois connection we obtain,

(x ∗) ≤ (x) ∗ ⇒ (x) ≤ (x ∗) ∗ ⇒ x ≤ x ∗ ∗

To prove (2) consider elements x, y such that x ≤ y. From (1) and the transitivity of partial x ≤ y ≤ y ∗ ∗ ⇒ x ≤ y ∗ ∗. Then from the definition of Galois connection we obtain

(x) ≤ (y ∗) ∗ ⇒ (y ∗) ≤ (x) ∗ ⇒ y ∗ ≤ x ∗.

To prove (3) consider any element x. On the one hand, part (1) tells us that

(x ∗) ≤ (x ∗) ∗ ∗ ⇒ x ∗ ≤ x ∗ ∗ ∗.

On the other hand, part (1) tells us that x ≤ x ∗ ∗ and then part (2) says that

(x) ≤ (x ∗ ∗) ⇒ (x ∗ ∗) ∗ ≤ (x) ∗ ⇒ x ∗ ∗ ∗ ≤ x ∗

Finally, the antisymmetry of partial order says that x∗∗∗ = x∗, which we interpret as isomorphism of objects in the poset category. The following definition captures the essence of these three basic properties.

Definition of Closure in a Poset. Given a poset (P,≤), we say that a function cl ∶ P → P is a closure operator if it satisfies the following three properties:

(i) Extensive: ∀p ∈ P, p ≤ cl(p)

(ii) Monotone: ∀ p,q ∈ P, p ≤ q ⇒ cl(p) ≤ cl(q)

(iii) Idempotent: ∀ p ∈ P, cl(cl(p)) = p.

[Remark: If P = 2^U is a Boolean lattice, and if the closure cl ∶ 2^U → 2^U also preserves finite unions, then we call it a Kuratowski closure. Kuratowski proved that such a closure is equivalent to a topology on the set U.]

If ∗ ∶ P → Q ∶ ∗ is a Galois connection, then the basic properties above immediately imply that the compositions ∗ ∗ ∶ P → P and ∗ ∗ ∶ Q → Q are closure operators.

Proof: Property (ii) follows from applying property (2) twice and property (iii) follows from applying ∗ to property (3).

Fundamental Theorem of Galois Connections: Any Galois connection ∗ ∶ P ⇄ Q ∶ ∗ determines two closure operators ∗ ∗ ∶ P → P and ∗ ∗ ∶ Q → Q. We will say that the element p ∈  P (resp. q ∈  Q) is ∗ ∗-closed if p∗ ∗ = p (resp. q∗ ∗ = q). Then the Galois connection restricts to an order-reversing bijection between the subposets of ∗ ∗-closed elements.

Proof: Let Q ∗ ⊆ P and P ∗ ⊆ Q denote the images of the functions ∗ ∶ Q → P and ∗ ∶ P  → Q, respectively. The restriction of the connection to these subsets defines an order-reversing bijection:

Indeed, consider any p ∈ Q ∗, so that p = q ∗ for some q ∈ Q. Then by properties (1) and (3) of Galois connections we have

(p) ∗ ∗ = (q ∗) ∗ ∗ ⇒ p ∗ ∗ = q ∗ ∗ ∗ ⇒ p ∗ ∗ = q ∗ ⇒ p ∗ ∗ = p

Similarly, for all q ∈ P ∗ we have q ∗ ∗ = q. The bijections reverse order because of property (2).

Finally, note that Q ∗ and P ∗ are exactly the subsets of ∗ ∗-closed elements in P and Q, respectively. Indeed, we have seen above that every element of Q ∗ is ∗ ∗-closed. Conversely, if p ∈ P is ∗ ∗-closed then we have

p = p ∗ ∗ ⇒ p = (p ∗) ∗,

and it follows that p ∈ Q ∗. Similarly, every element of P ∗ is ∗ ∗-closed.

Thus, a Galois connection is something like a “loose bijection”. It’s not necessarily a bijection but it becomes one after we “tighten it up”. Sort of like tightening your shoelaces.

The shaded subposets here consist of the ∗ ∗-closed elements. They are supposed to look (anti-) isomorphic. The unshaded parts of the posets get “tightened up” into the shaded subposets. Note that the top elements are ∗ ∗-closed. Indeed, property (2) tells us that 1_P ≤ P ≤ 1_p^∗∗ and then from the universal property of the top element we have 1_P^** = 1_P. Since the left hand side is always true, so is the right hand side. But then from the universal property of the top element in Q we conclude that 0^∗_P = 1_Q. As a consequence of this, the arbitrary meet of ∗ ∗-closed elements (if it exists) is still ∗ ∗-closed. We will see, however, that the join of ∗ ∗-closed elements is not necessarily ∗ ∗-closed. And hence not all Galois connections induce topologies.

Galois connections between Boolean lattices have a particularly nice form, which is closely related to the universal quantifier “∀“. Galois Connections of Boolean Lattices. Let U,V be sets and let ∼ ⊆ U × V be any subset (called a relation) between U and V . As usual, we will write “u ∼ v” in place of the statement “(u,v) ∈ ∼“, and we read this as “u is related to v“. Then for all S ∈ 2^U and T ∈ 2^V we define,

S^∼ ∶= {v ∈ V ∶ ∀ s ∈ S, s ∼ v} ∈ 2^V,

T^∼ ∶= {u ∈ U ∶ ∀ t ∈ T , u ∼ t} ∈ 2^U

The pair of functions S ↦ S^∼ and T ↦ T^∼ is a Galois connection, ∼ ∶ 2^U ⇄ 2^V ∶ ∼.

To see this, note that ∀ subsets S ∈ 2^U and T ∈ 2^V we have

S ⊆ T^∼ ⇐⇒ ∀ s ∈ S, s ∈ T^∼

⇐⇒ ∀ s ∈ S,∀ t ∈ T, s ∼ t

⇐⇒ ∀ t ∈ T, ∀ s ∈ S, s ∼ t

⇐⇒ ∀ t ∈ T, t ∈ S^∼

⇐⇒ T ⊆ S^∼.

Moreover, one can prove that any Galois connection between 2^U and 2^V arises in this way from a unique relation.

Orthogonal Complement: Let V be a vector space over field K and let V ∗ be the dual space, consisting of linear functions α ∶ V → K. We define the relation ⊥ ⊆ V ∗ × V by

α ⊥ v ⇐⇒ α(v) = 0.

The resulting ⊥⊥-closed subsets are precisely the linear subspaces on both sides. Thus the Fundamental Theorem of Galois Connections gives us an order-reversing bijection between the subspaces of V ∗ and the subspaces of V.

Convex Complement: Let V be a Euclidean space, i.e., a real vector space with an inner product ⟨-,-⟩ ∶ V ×V → ℜ. We define the relation ∼ ⊆ V ×V by

u ∼ v ⇐⇒ ⟨u,v⟩ ≤ 0.

∀ S ⊆ V the operation S ↦ S ∼ ∼ gives the cone genrated by S, thus the ∼ ∼-closed sets are precisely the cones. Here is a picture:

Original Galois Connection: Let L be a field and let G be a finite group of automorphisms of L, i.e., each g ∈ G is a function g ∶ L → L preserving addition and multiplication. We define a relation ∼ ⊆ G × L by

g ∼ l ⇐⇒ g(l) = l.

Define K ∶= L ∼ to be the “subfield fixed by G“. The original Fundamental Theorem of Galois Theory says that the ∼ ∼-closed subsets of G are precisely the subgroups and the ∼ ∼-closed subsets of L are precisely the subfields containing K.

Hilbert’s Nullstellensatz: Let K be a field and consider the ring of polynomials K[x] ∶= K[x₁,…,x_n] in n commuting variables. For each polynomial f(x) ∶= f(x₁,…,x_n) ∈ K[x] and for each n-tuple of field elements α ∶= (α₁,…,α_n) ∈ Kn, we denote the evaluation by f(α) ∶= f(α₁,…,α_n) ∈ K. Now we define a relation ∼ ⊆ K[x] × Kn by

f(x) ∼ α ⇐⇒ f(α) = 0

By definition, the closure operator ∼ ∼ on subsets of Kn is called the Zariski closure. It is not difficult to prove that it satisfies the additional property of a Kuratowski closure (i.e., finite unions of closed sets are closed) and hence it defines a topology on Kn, called the Zariski topology. Hilbert’s Nullstellensatz says that if K is algebraically closed, then the ∼ ∼-closed subsets of K[x] are precisely the radical ideals (i.e., ideals closed under taking arbitrary roots).