Exact original maximin shares using at most one duplicated good: A Hall-deficiency certificate and an obstruction to fixed MMS partitions
The question permits at most one extra used copy of one original good, with copies assigned to different agents. The benchmark is each agent's maximin share in the original market: \[
\mu_i=\max_{(P_1,\ldots,P_n)}\min_j v_i(P_j).
\] This note analyzes the natural strategy of selecting a partition first and repairing its assignment by one copied good. It gives an exact criterion for that strategy and a small family showing why choosing one agent's MMS partition does not suffice by itself.
Definition: Fix a partition $P_1,\ldots,P_n$ of $M$ and additive nonnegative values $a_{ig}$. The acceptance graph has agents on its left, bundle indices on its right, and edge $i j$ when $v_i(P_j)\geq\mu_i$. A repair edge $i j$ can be supplied by good $g$ if \[
g\notin P_j,\qquad v_i(P_j)<\mu_i\leq v_i(P_j)+a_{ig}.
\] A partition-preserving allocation assigns each original bundle intact to a distinct agent and may add one copied good to one of the assigned bundles.
Theorem (Exact criterion for one-copy repair): A fixed partition admits a partition-preserving MMS allocation with at most one copy if and only if its acceptance graph already has a perfect matching, or there is a repair edge $i j$ such that adding that edge produces a perfect matching. In the second case, the original good and its copy are assigned to distinct agents, and no agent receives the same good twice. Given the partition, values, and exact benchmarks, this criterion is decidable in polynomial time by testing at most $n^2m$ candidate repairs.
Proof: If a perfect matching exists, use it without augmentation. Otherwise take a perfect matching after adding repair edge $i j$ supplied by $g$. This matching must use the new edge. Assign all original bundles by the matching and give agent $i$ an extra copy of $g$. All other matched agents meet their benchmarks via original edges, and agent $i$ meets its benchmark by the repair inequality. Since $g\notin P_j$, its original instance lies in another bundle, assigned by the matching to a different agent. Thus all copy conventions hold.
Conversely, in a partition-preserving allocation with at most one copy, every recipient except possibly the copy's recipient must already be matched along an acceptance edge. If the copy's recipient lacked an original acceptance edge, its successful augmented bundle provides precisely a repair edge. The underlying bijection is then a perfect matching after that one edge is added. Testing the displayed repair inequalities and recomputing a bipartite maximum matching for each candidate is polynomial in the given data. The assertion does not include computation of MMS benchmarks from arbitrary binary-encoded values. ∎
Proposition (Hall form of the certificate): Suppose the acceptance graph has maximum matching size $n-1$. Let $\mathcal D$ be the nonempty family of deficient agent sets \[
\mathcal D=\{S\subseteq[n]:|N(S)|=|S|-1\}.
\] Adding a missing edge $i j$ produces a perfect matching if and only if \[
i\in\bigcap_{S\in\mathcal D}S,
\qquad j\notin\bigcup_{S\in\mathcal D}N(S).
\] If the maximum matching size is at most $n-2$, no single added edge can produce a perfect matching.
Proof: A matching of size $n-1$ matches all but one agent, so for every $S$ it matches at least $|S|-1$ of its members into distinct neighbors. Thus every Hall failure has deficiency exactly one and belongs to $\mathcal D$. Adding $i j$ increases the neighbor set of $S$ precisely when $i\in S$ and $j\notin N(S)$, in which case it increases its size by one. Every originally deficient set must gain this neighbor; originally nondeficient sets stay nondeficient. Hall's theorem now gives exactly the two displayed conditions. Finally, adding one edge can increase maximum matching size by at most one, because removing that edge from any new matching leaves an old matching. ∎
Example (One agent's MMS partition can have deficiency two): Take four agents and sixteen goods, partitioned into four blocks $P_1,P_2,P_3,P_4$ of size four. Agent 1 values every good at one, so $\mu_1=4$ and these blocks form an MMS partition for agent 1. Each of agents 2, 3, and 4 values exactly the four goods of $P_1$ at one and every other good at zero. Their original MMS is one, obtained by putting one valued good in each of four bundles.
In the acceptance graph, agent 1 is adjacent to all four blocks, and the other three agents are adjacent only to $P_1$. Its maximum matching size is two. A single repair edge therefore cannot create a perfect matching. Nevertheless the original instance has an MMS allocation with no copies: give one distinct good of $P_1$ to each of agents 2, 3, and 4, and give every remaining good to agent 1. The latter receives thirteen units, exceeding its benchmark four.
Hence failure of a fixed-partition repair certificate is not evidence against the one-copy conjecture. Even starting from a valid MMS partition of one agent can require substantial rebundling.
Source relationship and remaining gap.
Akrami et al. [source], Section 1.2, ask the one-copy question and prove the three-agent case in Corollary 3.9. Matching methods also appear in their positive results. The certificate and obstruction here analyze a narrower fixed-partition method; they do not claim a new resolution for three agents. For general $n$, one still needs either a method producing a partition with an available repair edge, allowing rebundling, or a genuine instance ruling out every one-copy allocation.
References
- [source] H. Akrami, S. Barman, A. Eden, M. Feldman, A. Fiat, Y. Gal-Tzur, S. Rammohan, and A. Sethia. Maximin-Share Fairness via Resource Augmentation, version 3, 2026. https://arxiv.org/html/2502.09377v3.
Completion Estimate
5%