About the problem
The classic problem in fair division involves dividing a set of goods among a set of people in a fair way. A key question is what it means for an allocation of goods to be fair. One such notion is that of envy-freeness.
Suppose we have a set \(N = \{1, \ldots, n\}\) of \(n\) agents and a set \(M = \{g_1, \ldots, g_m\}\) of \(m\) goods. Every agent \(i\) has a preference function \(v_i\), where \(v_i(g_j)\) represents how much agent \(i\) values good \(g_j\). An allocation is a partition of \(M\) into \(n\) sets \((X_1, \ldots, X_n)\), where \(X_i \subseteq M\) is the set of goods given to agent \(i\). The allocation \((X_1, \ldots, X_n)\) is envy-free if, for every \(i\) and \(j\),
\[\sum_{g \in X_i} v_i(g) \geq \sum_{g \in X_j} v_i(g).\]That is, for every \(i\), agent \(i\) values their set of goods \(X_i\) at least as much as any other agent’s set of goods \(X_j\), so no one is envious of anyone else.
It is known that envy-free allocations do not always exist. For instance, if there are two agents and one object, and both agents want the object, there is no way to specify an envy-free allocation.
A modification of the notion of envy-freeness is called envy-freeness up to any good (EFX). Here, the guarantee is that for every \(i\) and \(j\), and for every \(g^* \in X_j\),
\[\sum_{g \in X_i} v_i(g) \geq \sum_{g \in X_j \setminus g^*} v_i(g).\]That is, for every \(i\), agent \(i\) does not envy anyone else if we remove any one of their goods.
Read more about EFX allocations here, where Ariel Procaccia says that, in his view, EFX “is the successor of envy-free cake cutting as fair division’s biggest problem.”
Chaudhury, Garg, and Mehlhorn proved that EFX allocations always exist for three agents with additive valuations (which means that the value of a set of goods is equal to the sum of the values of each good, as we implicitly assume above). This problem asks whether EFX allocations always exist.
In particular, this problem asks for a counterexample: an instance of at least four agents, goods, and preferences for which there is no EFX allocation.
A recent paper from June 2026 showed that, in the additive case, there is an example with \(n\) agents for every \(n \geq 4\) such that no EFX allocation exists when allocating chores instead of goods. (The difference is that agents want to value their allocation of chores less than others’.) This gives some evidence that such counterexamples might exist for EFX allocations of goods, too.
The main risk with this problem is that no such counterexample exists: maybe there is always an EFX allocation. Another risk is that the instance is too large to be computationally verified.
Prompt
# An example with no EFX allocation
## Setup
We divide m indivisible goods among n agents. Agent i has an **additive**
valuation: a nonnegative integer value V[i][g] for each good g, and values a
bundle S of goods by the sum of its parts,
v_i(S) = sum over g in S of V[i][g].
An **allocation** (A_1, ..., A_n) partitions the goods: every good is given to
exactly one agent (bundles may be empty). There are exactly n^m allocations.
## EFX (envy-free up to any good)
An allocation is **EFX** if no agent strongly envies another after the removal of
any single positively-valued good from the envied bundle. Formally, for every
ordered pair of distinct agents i, j and every good g in A_j with V[i][g] > 0:
v_i(A_i) >= v_i(A_j) - V[i][g].
The phrase "up to *any* good" is the crux: the inequality must hold even for the
good whose removal helps i the least (the smallest good in A_j that i values
positively). Equivalently, for every ordered pair (i, j) such that A_j contains
at least one good i values positively:
v_i(A_i) >= v_i(A_j) - min{ V[i][g] : g in A_j and V[i][g] > 0 }.
## Your task
Exhibit an example where an EFX allocation does not exist: choose n and m and
an n-by-m valuation matrix such that **no** allocation of the m goods to the n
agents is EFX. Since EFX allocations always exist for n <= 3, choose n >= 4.
## Submission format
Write your answer to a JSON file: an array of n rows, where row i is a list of m
nonnegative integers giving agent i's values for goods 0, 1, ..., m-1. All rows
must have the same length. Submit that file's path with the submit tool.
Example:
[[3, 0, 1],
[1, 2, 2]]
Here agent 0 values the three goods at 3, 0, 1 and agent 1 at 1, 2, 2. (This
example is only to show the format; it is not a counterexample -- an EFX
allocation exists for it.)
Keep n^m small enough that all allocations can be checked within the time
limit.