An Intersection Theorem on an Unbounded Set and Its Application to the Fair Allocation Problem

摘要

We prove the following theorem. Let m and n be any positive integers with m≤n, and let $T^n = { x in mathbb{R}^n |Sigma _{i = 1}^n x_i = 1}$ be a subset of the n-dimensional Euclidean space ℝ n . For each i=1, . . . , m, there is a class ${ M_i^j {text{| }}j = 1,...,n}$ of subsets M i j of Tn . Assume that $cup _{j = 1}^n M_i^j = T^n ,$ for each i=1, . . . , m, that M i j is nonempty and closed for all i, j, and that there exists a real number B(i, j) such that $x in T^n$ and its jth component xj≤B(i, j) imply $xnot in M_i^j$ . Then, there exists a partition $(Pi (1),...,Pi (m))$ of {1, . . . , n} such that $Pi (i) ne emptyset$ for all i and $cap _{i = 1}^m cap _{j in Pi (i)} M_i^j ne emptyset .$ We prove this theorem based upon a generalization of a well-known theorem of Birkhoff and von Neumann. Moreover, we apply this theorem to the fair allocation problem of indivisible objects with money and obtain an existence theorem.