Title: Competitive Equilibrium For almost All Incomes,
Abstract: Competitive equilibrium from equal incomes (CEEI) is a well-known rule for
fair allocation of resources among agents with different preferences. It has
many advantages, among them is the fact that a CEEI allocation is both Pareto
efficient and envy-free. However, when the resources are indivisible, a CEEI
allocation might not exist even when there are two agents and a single item.
In contrast to this discouraging non-existence result, Babaioff, Nisan and
Talgam-Cohen (2017) recently suggested a new and more encouraging approach to
allocation of indivisible items: instead of insisting that the incomes be
equal, they suggest to look at the entire space of possible incomes, and check
whether there exists a competitive equilibrium for almost all income-vectors
(CEFAI) --- all income-space except a subset of measure zero. They show that a
CEFAI exists when there are at most 3 items, or when there are 4 items and two
agents. They also show that when there are 5 items and two agents there might
not exist a CEFAI. They leave open the cases of 4 items with three or four
agents.
This paper presents a new way to implement a CEFAI, as a subgame-perfect
equilibrium of a sequential game. This new implementation allows us both to
offer much simpler solutions to the known cases (at most 3 items, and 4 items
with two agents), and to prove that a CEFAI exists even in the much more
difficult case of 4 items and three agents. Moreover, we prove that a CEFAI
might not exist with 4 items and four agents. When the items to be divided are
bads (chores), CEFAI exists for two agents with at most 4 chores, but does not
exist for two agents with 5 chores or with three agents with 3 or more chores.
Thus, this paper completes the characterization of CEFAI existence for monotone
preferences.