| paper | EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture |
| authors | — |
| venue | AAMAS 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.9
statement extracted from the paper’s text layer
Given a finite catalogue of local bipartite multigraph types \(G_\theta=(V_\theta,E_\theta)\), rational copy masses \(\alpha_\theta\), and rational additive valuations \(v^\theta_u(e)\), where each copy contains one agent of every role \(u\in V_\theta\) and one indivisible item for every edge \(e\in E_\theta\), output nonnegative masses \(z_{\theta,X}\) over complete integral allocation patterns \(X\) such that \(\sum_X z_{\theta,X}=\alpha_\theta\) and every pattern with \(z_{\theta,X}>0\) is EFX for its local market.
A high-multiplicity disjoint union of repeated local bipartite multigraph markets: types are complete local roles \( (\theta,u) \), population mass is \( \alpha_\theta \), each market copy contains indivisible edge-items, and the decision variable \(z_{\theta,X}\) is a mass of copies using integral EFX pattern \(X\).
The population masses are computationally inert because feasibility factors by local market type, making the mirror a census of independently solved finite allocation problems rather than a coupled society-level problem.
fatal: False
The mirror directly covers the existence and polynomial-time computation result in Theorem 4.9 for repeated bipartite multigraph markets. It leaves the EFX-orientation landscape, Theorem 3.6's NP-completeness result, Theorem 4.10's orientation guarantee, and Theorem 5.1's multi-cycle result outside the main mirror.
The strongest honest mirror is a repeated-market version of the paper’s main positive result, Theorem 4.9, proved in this paper:
For every fair-division instance on a bipartite multigraph with additive valuations, an EFX allocation exists and can be computed in polynomial time.
I would call the continuous problem Typed-Repeated Bipartite EFX\(_\infty\).
A finite type \((\theta,u)\) consists of a local market type \(\theta\) and a role \(u\) in a bipartite multigraph \(G_\theta=(V_\theta,E_\theta)\). The type records the agent’s complete local graph position, its incident item slots, and all additive values \(v^\theta_u(e)\). Thus two agents have the same type only when they are indistinguishable for the entire allocation problem.
The regime is a large federation of repeated local markets: many regions, campuses, branches, or logistical units have the same small bipartite multigraph of agents and pairwise-valued projects. Each copy contains one agent of every role \(u\in V_\theta\) and one indivisible item for every edge \(e\in E_\theta\). An edge-item is valued positively only by its two endpoint agents, exactly as in the paper. The number of copies may be enormous, while the number of local types and graph descriptions remains small.
Formally, the input gives finitely many local-market types \(\theta\), rational masses \(\alpha_\theta\) of their repeated copies, and the rational additive valuations in each \(G_\theta\). The induced population mass of agent type \((\theta,u)\) is
\[ \mu_{\theta,u} = \frac{\alpha_\theta} {\sum_{\eta}\alpha_\eta |V_\eta|}. \]
The items also repeat with the market: every copy of \(G_\theta\) contains one indivisible copy of each \(e\in E_\theta\). This scaling is essential. Keeping only finitely many items while the population grows would make almost everyone receive the empty bundle, trivialising EFX.
An allocation pattern \(X\) for \(G_\theta\) assigns every edge-item \(e\in E_\theta\) to one agent in \(V_\theta\); it may be wasteful, since Theorem 4.9 does not require an item to go to an endpoint. Writing \(X_u\) for the bundle assigned to \(u\), the pattern is EFX when
\[ v^\theta_u(X_u) \ge v^\theta_u(X_w\setminus\{e\}) \]
for every pair \(u,w\in V_\theta\) and every \(e\in X_w\).
The continuous decision variable is an allocation census
\[ z_{\theta,X}\ge 0, \]
where \(z_{\theta,X}\) is the mass of copies of market type \(\theta\) receiving the whole integral allocation pattern \(X\). A feasible solution must satisfy
\[ \sum_X z_{\theta,X}=\alpha_\theta \]
for every \(\theta\), and \(z_{\theta,X}>0\) only for EFX patterns \(X\). The objective is feasibility: output a complete EFX allocation law. This is not fractional allocation of items. Every positive-mass pattern assigns every item integrally; only the population of repeated copies is represented by mass.
This has an exact high-multiplicity bridge. If all masses are rational, choose a denominator \(D\), create \(D\alpha_\theta\) finite copies of every market type, and realise \(Dz_{\theta,X}\) copies with pattern \(X\). Conversely, any allocation of this finite clone instance can be aggregated into the \(z_{\theta,X}\). Agents in different local markets value one another’s items at zero, so EFX holds globally exactly when it holds in every supported local pattern.
The expected classification is Class A for this explicit repeated-market model. Apply Theorem 4.9 separately to each \(G_\theta\), obtaining an EFX pattern \(X_\theta\), and set
\[ z_{\theta,X_\theta}=\alpha_\theta. \]
This runs in time polynomial in the explicit type catalogue, the local graph sizes, and the valuation encoding length, independently of the possibly astronomical number of repeated agents. The result preserves the paper’s actual fairness notion, additive graph valuations, complete allocation requirement, and allowance for wasteful assignments. It is therefore recognisably the same problem in a high-multiplicity regime, rather than a divisible-goods reformulation.
I would not use Theorem 3.6 as a second anchor. Its NP-completeness result has only a constant number of agents and encodes Partition in the values of individual edge-items. Its hardness is therefore not population-multiplicity hardness. Aggregating or splitting the population would likely destroy the reduction, while retaining every edge-item as indivisible leaves essentially the original finite gadget. Likewise, the orientation results are interesting follow-up questions but are not needed for the strongest positive case.
The natural next questions are whether the disjoint repeated-market assumption can be removed; whether agents of the same type can share one connected aggregate graph with only edge-copy densities specified; whether EFX allocation laws can be optimized for welfare or waste; and whether the orientation boundary from Theorems 3.2–3.6 survives in a genuinely shared-population model.
The weakest point is clear: this is a repeated-indivisible-market extension, not an atomless allocation in which individual agents receive infinitesimal bundles. It also scales item supply with the population and uses local market copies, so an opponent can call it a new configuration model rather than the literal continuum limit of one connected graph. The defence is that this is precisely the honest high-multiplicity interpretation: agent types are complete local roles, items remain indivisible, rational mass has an exact finite-clone realisation, and the mirror covers Theorem 4.9 without weakening EFX or confusing population continuity with outcome-space divisibility.
Theorem 4.9 is a genuine computational anchor, so the negative case cannot honestly rely on the paper lacking one. The stronger objection is that the proposed mirror does not make the population a computationally relevant continuous object.
In the repeated-market construction, let \(\mathcal E_\theta\) be the finite set of EFX allocation patterns for market type \(\theta\). Its feasible census is simply
\[ \left\{z:\ \sum_{X\in\mathcal E_\theta} z_{\theta,X}=\alpha_\theta \text{ for every }\theta\right\}. \]
There is no constraint coupling two market copies, two local types, or two masses. The population vector \(\alpha\) only says how many independent copies of already-solved finite instances exist. The exact finite-clone correspondence confirms this: it establishes a valid high-multiplicity encoding, but also shows that the continuous problem is a product of the original finite problems. The EFX predicate itself contains no population mass.
That is not the objection that the answer happens to be polynomial. A dull Class A problem would still be worthwhile if the continuum changed the computational object. Here the proposed continuum does not: it is a census of independent local allocations. Calling the copies regions or campuses supplies an application story, but no society-level fairness trade-off. The theorem is applied once per local graph, and the mass variables disappear from feasibility.
The natural repair—keep one common graph or item pool while increasing the population—runs into the structure that makes this paper special. An item is not merely an item type: it is an edge incident to two particular agents. A distribution of agent types does not specify which agents share which items, nor the resulting cycles, paths, diameter, or global adjacency. Those are not cosmetic details; the paper’s orientation landscape is explicitly parameterized by them.
If the item set stays fixed while the population grows, the limit degenerates. Once \(n\ge m\), assign every item to a different agent. Every bundle is then a singleton or empty, and removing any item from another bundle leaves the empty bundle, so the allocation is automatically EFX. Thus the interesting problem vanishes.
If item supply scales with the population, one must also scale the incidence structure. Repeating whole components gives exactly the proponent’s decomposed model. Connecting the copies requires an additional graph sequence, matching rule, or spatial incidence measure. That extra object is not recoverable from the type distribution. If types are expanded to include the complete connected structure, then growing connected instances generally have essentially no repeated types; if only local neighbourhoods are retained, the model has forgotten correlations on which EFX orientations depend.
A graphon-like repair does not solve this. With linearly many edge-items, each individual item has vanishing normalized mass in the limit. Removing one item then has no effect, so EFX approaches ordinary envy-freeness. If atomic items are retained instead, the model needs a measurable field of local bundles and a consistency structure for which agents share each atom. That is a new graph-limit or spatial allocation problem, not a population continuization of Theorem 4.9. Making the goods divisible would be still further outside the programme’s scope.
The same issue defeats a stronger orientation-based mirror. In the repeated-market setting, an EFX orientation law exists exactly when each positive-mass local market type has an EFX orientation. Theorem 3.6’s Partition hardness remains inside each constant-size gadget; mass does not participate in the decision. A shared-population orientation problem would require the missing global incidence information. Theorem 4.10’s guarantee that half the agents are EFX likewise becomes a weighted average of independent local patterns unless one adds a common graph or welfare objective, at which point one has formulated a new problem rather than mirrored the paper’s theorem.
This is not an objection to high multiplicity in general. High-multiplicity fair division could be sensible when item multiplicities and agent multiplicities are jointly modelled. It is also not an objection that the continuous version is tractable. The narrower point is that, for this paper, preserving indivisible edge-items and EFX forces either independent repeated markets, where the population mass is mathematically inert, or a graph-valued limit, where type masses alone do not describe the instance and atomlessness threatens to erase the “up to any item” notion.
The negative case is therefore not airtight. If the programme is willing to count a federation of independent repeated markets as a worthwhile continuous mirror, the proponent has a valid Class A construction. But if “continuization” is required to make the society—not merely the number of copies—continuous and computationally consequential, Theorem 4.9 does not provide it.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.