| paper | Stable allocations in discrete exchange economies |
| authors | F. Echenique, Sumit Goel, Sang-Mok Lee |
| venue | JET 2024 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(\Theta\), rational masses \(\mu_\theta\), categories \(k\in\{1,\ldots,K\}\), finite goods \(O^k\), per-agent integral endowments \(e_{\theta,o}\), and acceptable sets \(G_\theta^k\), let \(v_\theta(B)=\sum_k \mathbf{1}[B\cap G_\theta^k\neq\emptyset]\) for integral bundles \(B\) containing at most one good per category, and let \(q_o=\sum_\theta\mu_\theta e_{\theta,o}\). Compute a mass allocation \(z_{\theta,B}\ge0\) with \(\sum_B z_{\theta,B}=\mu_\theta\) and \(\sum_{\theta,B:o\in B}z_{\theta,B}\le q_o\), such that no positive-mass selection \(0\le s_{\theta,B}\le z_{\theta,B}\) admits variables \(y_{\theta,B,B'}\ge0\) satisfying \(\sum_{B'}y_{\theta,B,B'}=s_{\theta,B}\), \(v_\theta(B')>v_\theta(B)\) whenever \(y_{\theta,B,B'}>0\), and \(\sum_{\theta,B,B':o\in B'}y_{\theta,B,B'}\le\sum_{\theta,B}s_{\theta,B}e_{\theta,o}\) for every good \(o\).
A nonatomic high-multiplicity categorical exchange economy with finite complete types \(\Theta\), masses \(\mu\), integral bundles, per-capita endowments, and decision variables \(z_{\theta,B}\); the task is feasibility or search for a mass allocation with no positive-mass blocking coalition, with block witnesses represented by \(s\) and \(y\).
Theorem 1's random-core step is existential rather than an end-to-end algorithm, and allowing one type to split across bundles changes the paper's pointwise target-utility argument.
fatal: False
The mirror directly covers Theorem 1's categorical dichotomous weak-core result; Lemma 2 motivates a separate housing/TTC extension. Proposition 1 is supporting context, while Proposition 2, Theorem 2, and the broader locally absorbing-set results remain uncovered.
Strictly speaking, the paper contains no numbered complexity result saying that a problem is in P, NP-hard, FPT, or similar. Its only explicit running-time statement is an unnumbered remark after Lemma 3, giving \(O(\log^{|A|}M)\) oracle time for finding a fixed point of \(T^2\). Thus the strongest positive case is a computational mirror of the paper’s constructive existence results, not a mirror of an explicit complexity theorem.
The strongest anchor is Theorem 1, proved in this paper:
“A categorical economy with additively separable and dichotomous preferences has nonempty weak core.”
In full, the theorem concerns finitely many categories, unit demand in each category, utilities additive across categories, and dichotomous values for individual goods. It says that there exists a deterministic allocation not strongly blocked by any coalition: no coalition can reallocate only its own endowments so that every member is strictly better off. The proof first obtains a random-core allocation using Proposition 1, then floors expected utilities and uses a rounding algorithm to produce an integral core allocation.
The corresponding mirror I would propose is the following.
Call it Continuum Categorical Weak-Core Search. An instance contains a finite type set \(\Theta\), rational masses \(\mu_\theta\) summing to \(1\), categories \(k\in\{1,\ldots,K\}\), finite good kinds \(O^k\), and, for every type \(\theta\):
The total mass of good kind \(o\in O^k\) is the mass inherited from the endowments, \(q_{k,o}=\sum_\theta \mu_\theta e_{\theta,o}\). A solution is an allocation of the unit interval of agents: every agent receives an integral bundle, but a type may be split across several bundles. Equivalently, the output is a mass table \(z_{\theta,B}\), where \(z_{\theta,B}\) is the mass of type \(\theta\) receiving bundle \(B\), satisfying the type-mass and good-supply constraints.
The allocation is in the continuum weak core if there is no positive-mass coalition that can improve every selected member strictly using only its members’ endowments. Formally, a potential coalition selects masses \(s_{\theta,B}\leq z_{\theta,B}\). A block would be a reassignment \(y_{\theta,B,B'}\) such that all selected mass currently receiving \(B\) is assigned to bundles \(B'\) with \(v_\theta(B')>v_\theta(B)\), while the total mass of every good used by the reassignment does not exceed the coalition’s inherited mass of that good. The task is to output any allocation for which no such \(s\) and \(y\) exist.
This is genuinely a population mirror, not merely divisible-goods exchange. Every individual still receives an integral bundle and owns an integral endowment. Only the set of indistinguishable agents is divisible: \(z_{\theta,B}\) records the mass of agents assigned each bundle. A rational instance with \(\mu_\theta=N_\theta/N\) expands directly into a finite economy with \(N_\theta\) identical clones of each type.
The natural regime is a large course-allocation or qualification market. There may be thousands of students but only a few dozen types, determined by programme, year, priority class, acceptable-course pattern, and initial entitlement. Course seats are good kinds, categories may represent time blocks or requirements, and each student consumes at most one seat per category. Students of the same type are indistinguishable for the problem. This is exactly the high-multiplicity regime rather than an artificial assumption about named individuals.
I expect this mirror to be Class A under Theorem 1’s restrictions. The paper’s random-core construction becomes a mass-allocation LP; the finite population no longer requires a separate rounding argument, because fractional entries can be implemented by measurable subsets of the population. The category constraints are transportation constraints, and the best bundle for a type is separable across categories. The real algorithmic question is separation over blocking coalitions, but the structure is sufficiently close to configuration LPs and flow problems that a polynomial algorithm is plausible. This is the paper’s underlying stable-allocation problem, not an artificially weakened welfare problem.
The paper’s Proposition 1 is useful support, though I would not count it as a separate mirror: it proves that categorical economies with additively separable utilities have a nonempty weak random core. In the continuum, the “random” allocation can be interpreted as assigning different integral bundles to different submasses of a type. The proposed mirror asks whether that population-level object can be computed and purified into an actual continuum weak-core allocation.
A second, narrower anchor is Lemma 2, also proved here. In the housing model, let \(\underline u\) be the utility vector from initial endowments, let \(A_r\) be the agents removed in round \(r\) of TTC, and let \(T\) be the paper’s trade-improvement operator. The lemma states that for every \(r\) and every \(i\in A_r\), \( (T^{2r-1}\underline u)_i=(T^{2r}\underline u)_i=(T^{2r+1}\underline u)_i=\cdots \). Thus the even iterates of \(T\) reproduce the rounds of TTC, and the utility profile generated by TTC is a fixed point of \(T\).
Its continuous mirror is Mass-TTC Core Search. The input is a finite set of housing types \(\Theta\), masses \(\mu_\theta\), one house type initially owned by each type, and a strict ranking of house types for each \(\theta\). The output is a mass assignment \(x_{\theta,h}\) with the correct type masses and house supplies, such that no positive-mass coalition can exchange only its initially owned houses and make every member strictly better off.
The algorithm is the type-level TTC procedure: each residual type points to its most preferred currently available house; house mass points back to its owner type; every positive-mass cycle is cleared in an amount equal to the minimum mass on that cycle, splitting a type whenever only part of its mass is cleared. The process terminates with a continuum housing-core allocation. This should be Class A: the number of type fragments and cycle-clearing operations is polynomial in the number of types, and it is a direct high-multiplicity analogue of the TTC construction that Lemma 2 identifies.
I would stop there. Theorem 1 gives the substantive mirror; Lemma 2 gives a clean algorithmic special case. I would not stretch the case to Proposition 2’s pairwise locally absorbing sets or Theorem 2’s gains-from-trade condition, because the paper gives no complexity guarantee for them and the continuum definitions would require additional choices about farsighted blocking.
The authors should recognize both mirrors. They preserve their categories, endowments, dichotomous or strict preferences, coalition-based blocking, and integral consumption. What changes is only that many agents of the same complete type are represented by mass. The continuous version is not already present in the paper: the paper studies finite agents and uses a nontrivial rounding argument. Existing large-economy and continuum exchange work supports the regime, but does not supply these computational questions.
The weakest point is unavoidable: the paper’s named results are existence and construction theorems, not complexity theorems. An opponent can therefore say that the proposed mirror upgrades the paper into a computational programme that the authors themselves did not formulate. That criticism is fair. The answer is that the upgrade is precisely meaningful here: Theorem 1 isolates rounding as the main discrete obstacle, while the continuum removes that obstacle without removing indivisible individual bundles or coalition stability. The resulting question—whether finite-type mass stability can be computed efficiently, and where that ceases to hold—is a legitimate continuous-computational problem even though this paper does not already state it.
The negative case is strongest at the level of eligibility: neither anchor is a computational result. The paper proves existence and gives constructive proof ideas, but it never formulates a finite-input search, decision, optimization, approximation, or complexity problem. The only runtime statement—the \(O(\log^{|A|} M)\) oracle remark after Lemma 3—is not an end-to-end algorithm: evaluating the oracle \(T\) is left entirely unspecified, and \(M\) may itself be exponential. Thus the proposed mirrors are new computational projects inspired by the paper, not continuizations of computational results proved in it.
Theorem 1 is the better anchor, but the proponent’s interpretation removes precisely the theorem’s distinctive content. The theorem says that, under dichotomous preferences, a deterministic allocation of indivisible objects exists in the weak core. Its proof first obtains a random-core allocation and then solves the genuinely discrete problem: rounding it so that every named agent receives an integral bundle meeting an individual target utility.
In the proposed continuum, a table \(z_{\theta,B}\) can split one type across several bundles. This makes the random allocation implementable as a measurable mass assignment, but it does not automatically preserve the theorem’s core guarantee. An expected utility for type \(\theta\) does not make every member of that type at least as well off: some positive submass may receive a low-utility bundle. That submass can itself participate in a blocking coalition. The claim that “no rounding is needed” therefore confuses implementation of a lottery with pointwise satisfaction of the deterministic core condition.
One can repair this by requiring every positive-mass subpopulation to receive an integral bundle meeting a pointwise target, or by formulating a separate measurable purification theorem. But that is a new theorem. If type-splitting is allowed freely, the paper’s rounding problem disappears; if it is disallowed in order to preserve that problem, one has retained indivisible cohorts rather than a genuinely continuous population. If one keeps named objects and idiosyncratic endowments, high multiplicity disappears instead. The proposed model is therefore sensible, but it does not preserve the computational content of Theorem 1.
The resulting mass-core search could certainly be worth studying in its own right. A course-allocation economy with repeated student types and per-capita supplies is a plausible high-multiplicity regime, and I am not treating existing high-multiplicity work as a novelty collision. But the paper supplies no computational claim about that problem, and its proof gives no polynomial bound, separation oracle, or encoding analysis. The proponent’s assertion that a polynomial algorithm is “plausible” cannot carry the anchor.
Lemma 2 is weaker still. It is an identity between finite-agent iterates of \(T\) and rounds of TTC in the housing model:
\[ (T^{2r-1}\underline u)_i=(T^{2r}\underline u)_i=(T^{2r+1}\underline u)_i=\cdots . \]
It does not state a complexity result. The proposed Mass-TTC procedure is a natural high-multiplicity version of the TTC mechanism, but it is not a computational mirror of this lemma. The paper’s \(T\) acts on a finite product \(U=\prod_i U_i\) of individual utility sets. With masses, a type can be partially cleared in one cycle and partially remain for later cycles; a single type-level utility coordinate no longer records the relevant state. One must augment the state by residual fragments or mass supplies. At that point one has defined a new mass-flow TTC process, not continued the finite \(T\)-iteration theorem.
The direct cycle-clearing algorithm may well be polynomial, but that makes the proposed question an elementary new mechanism-design exercise rather than a computational consequence of Lemma 2. To make it a genuine mirror, the authors would need to define the measure-valued analogue of \(T\), prove that its iterates reproduce the mass-TTC rounds, and establish stability against positive-mass coalitions. None of those claims appears in the paper.
The strongest rescue is therefore real but does not save this paper as an anchor: repeated-type housing or course-allocation markets are credible continuous-population subjects. What they support is a new ChoCo study of nonatomic exchange economies, not a continuization of a named computational result here. On the programme’s computational-anchor rule, neither Theorem 1 nor Lemma 2 survives.
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.