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 ∈ R~n|∑_(i=1)~n x_i = 1} be a subset of the n-dimensional Euclidean space R~n. For each i = 1, …, m, there is a class {M_i~j|j = 1, …, n} of subsets M_i~j of T~n. Assume that ∪_(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 ∈ T~n and its jth component x_j ≤ B(i,j) imply x is not an element of M_i~j. Then, theer exists a partition (Π(1), …, Π(m)) of {1, …, n} such that Π(i) ≠ 0 for all i and ∩_(i=1)~m ∩_(j∈Π(i)) M_i~j ≠ 0. 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.