An elementary proof of the Knaster-Kuratowski-Mazurkiewicz-Shapley theorem (Q1341506): Difference between revisions

The Knaster-Kuratowski-Mazurkiewicz-Shapley (K-K-M-S) theorem is formulated as follows: For every integer \(n \geq 1\), let \(N\) denote \(\{1,2,\dots,n\}\). If \(S \subseteq N\), then \(\Delta^ S\) means the simplex formed by all points \((x_ 1,\dots, x_ n)\) for which \(x_ i \geq 0\), \(\sum x_ i = 1\), and \(x_ i = 0\) for \(i \notin S\). The central point of the simplex \(\Delta^ S\) (with \(x_ i = 1/| S|\) for \(i \in S\)) is denoted by \(m^ S\). Let \(C_ S\), \(S \subseteq N\), be a family of closed subsets of \(\Delta^ N\) such that for every \(T \subseteq N\), and for every \(x \in \Delta^ T\), there exists a subset \(S \subseteq T\) for which \(x \in C_ S\). The theorem states that there exists a family \(\mathcal B\) of subsets of \(N\) for which all sets \(C_ S\), \(S \in {\mathcal B}\), have a common point, and for which \(m^ N\) is a convex combination of \(m^ S\) for \(S \in {\mathcal B}\). One possible direct game-theoretic interpretation of this result is as follows: Suppose that we have a situation in which \(n\) persons have different possible strategies. The largest total utility that they can gain is \(U\). The problem is: how to divide that utility between them, i.e., how to assign fractions \(x_ i \geq 0\), \(1 \leq i \leq n\), \(\sum x_ i = 1\) so that \(i\)-th person gets \(x_ i \cdot U\). For every coalition \(S\), let \(C_ S\) denote the set of all allocation vectors that members of this coalition considers fair to them. If \(x \in \Delta^ T\) (i.e., if money goes only to members of \(T\)), then either this \(x\) is fair to all persons from \(T\), or some members of \(T\) believe that they do not get their fair share, in which case this distribution \(x\) is fair only to some members of \(T\) (i.e., \(x \in C_ S\) for some \(S \subset T\)). In this setting, the theorem says that there exist a family \(\mathcal B\) of coalitions such that, first, there exists an allocation vector \(\tilde x\) that is acceptable by all these coalitions, and second, \(m^ N = \sum p(S)m^ S\) for some probabilities \(p(S) \geq 0\), \(\sum p(S) = 1\). This means that with probability \(p(S)\), we can form a coalition \(S\). As a result, each person has an equal chance of belonging to a deciding coalition, and all these coalitions agree that \(\widetilde {x}\) is a fair allocation. So, this \(\widetilde {x}\) can be produced as an allocation that is (in a reasonable sense) fair for everyone. On a formal level, the K-K-M-S theorem is used to prove that every balanced game with non-transferable utility (NTU) has a core. All previously known proofs of this theorem were difficult to understand for a non-mathematician who is only interested in game-theoretic applications. The paper under review provides an elementary proof of the K-K-M-S theorem, that is based on Brouwer's fixed point theorem. There are a few typos: p. 468, Section 2.2., second line, \(\}\}\) should be \(\}\); in References, Komiya's paper's pages should be 463-466, and Scarf's reference should be 38, 50-69 (1967).