| paper | d4-journals-geb-2022-0038 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: The exact resulting circulation is computable in time polynomial in \(m,\tau,Q,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Corollary 10
statement extracted from the paper’s text layer
Given a finite set of types \(T\), rational masses \(\mu_t>0\) summing to \(1\), integer capacities \(q_t\), rankings \(\succ_t\) of good types, and a schedule containing each type \(t\) exactly \(q_t\) times, compute the resulting type-level circulation. At each scheduled phase for type \(t\), assign mass \(\mu_t\) one unit of acceptable goods per unit of agent mass, choosing the lexicographically best assignment in \(\succ_t\) among those that leave an individually rational completion for all remaining mass. Each good type \(u\) supplies \(q_u\mu_u\); the final allocation must use all supplies and leave every type with an acceptable bundle.
A distribution over exchange-agent types, each defined by a common capacity, ranking, and priority class. Type \(t\) has mass \(\mu_t\) and supplies \(q_t\mu_t\) units of its type-good. The decision at each scheduled phase is a mass allocation vector; its feasible set consists of assignments that preserve a balanced, individually rational completion. Rational-capacity flow computations and lexicographic optimization provide a route to an exact algorithm, with running time to be stated in \(|T|\), \(Q=\sum_t q_t\), and the input bit length.
The case does not show that the lexicographically chosen cohort batches always equal the aggregation of the paper’s individual greedy turns under a corresponding block order.
fatal: False
The mirror covers the efficient implementation of Single-Serial-IR evaluation in Corollary 10. It does not address the paper’s other efficiency or incentive results.
The strongest positive case is the paper’s implementation problem. Its best named anchor is Corollary 10, proved in this paper: every Single-Serial-IR rule can be implemented using the paper’s alternative definition, in time \(O(n^6Q)\), where \(n\) is the number of agents and \(Q=\sum_i q_i\). The paper’s flow characterization of IR-extendability is the engine behind that algorithm. I do not see a comparable named hardness result in the paper; the NP-hardness mentioned in Remark 2 is cited from Aziz et al. and concerns checking Pareto-efficiency, a different problem.
Here is a continuous version that keeps the rule’s central choices. Call it Mass Single-Serial-IR Evaluation. The instance has a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), per-agent capacities \(q_t\in\mathbb N\), and a strict ranking \(\succ_t\) of good types for each type \(t\). The type’s own good type \(t\) is its reservation benchmark; goods \(u\) with \(u\succeq_t t\) are acceptable. Members of a type have the same capacity and ranking, and goods supplied by members of the same type are interchangeable. Thus type \(u\) supplies mass \(q_u\mu_u\) of its good.
The instance also includes a turn schedule \(\sigma=(t_1,\ldots,t_Q)\), with each type \(t\) appearing \(q_t\) times, where \(Q=\sum_t q_t\). This is a cohort-synchronous version of the paper’s \(q\)-priority order: each time \(t\) appears, every member of that cohort receives one pick. At phase \(r\), if \(t=t_r\), choose a vector \(y^r\) where \(y^r_u\) is the mass of type-\(t\) agents receiving one unit of good \(u\). It must satisfy \(\sum_u y^r_u=\mu_t\). Among choices that leave an individually rational completion for all remaining mass, select the lexicographically best vector in the order of \(\succ_t\): assign as much mass as possible its top acceptable good, then its next-best good, and so on. Completion is tested by a flow network on types and good types, with acceptable type-good pairs as edges and the remaining rational masses as capacities.
The question is to compute the full sequence of phase choices, or equivalently the resulting type-level circulation. Each agent still receives an integral bundle of \(q_t\) goods; only the cohort’s average allocation is fractional. The aggregate transfers must use exactly \(q_u\mu_u\) units of every good type \(u\), and every assigned good must be acceptable. The rule has a lexicographic choice objective at each phase, rather than a cardinal welfare objective, just as the paper’s serial rule does.
I would expect this problem to be Class A, tractable. Each residual completion is a max-flow feasibility problem on a network with \(O(\tau)\) type and good nodes, where \(\tau=|T|\). Each phase’s lexicographic choice can be found by optimizing at most \(\tau\) mass coordinates over flow-feasible completions. That suggests an exact algorithm polynomial in \(\tau\), \(Q\), and the binary input length \(L\) of the rational masses. A useful next question is whether this bound can avoid dependence linear in \(Q\) when capacities are binary-encoded. Another is to prove a finite-to-continuous rounding guarantee for markets with \(N_t\) agents of type \(t\), where \(\mu_t=N_t/n\).
A plausible regime is a large regional shift-exchange system: thousands of workers, grouped by role, location, shift pattern, capacity, acceptable-shift ranking, and any priority tier used by the rule. The number of workers can be far larger than the number of such types. A cohort-based priority schedule is credible if the clearinghouse processes priority classes or cohorts, and workers care about shift categories rather than the identity of the particular worker who supplied a shift. That is a high-multiplicity exchange market: the society is the distribution over types, and each type supplies its per-capita capacity times its mass.
The weakness is real: the paper’s goods are individually owned, and its priority orders can distinguish named agents. The mirror pools goods within a type and uses a restricted, cohort-synchronous schedule. If source identity or individual priority materially affects choices, the support may grow with the population and this compression may no longer represent the authors’ problem. The case survives only in the regime where those identities truly do not matter. In that regime, the mirror preserves the paper’s central task—serially making ordinal picks while maintaining an IR-completable circulation—and replaces a large finite population with rational type masses. It covers the efficient implementation result, not the paper’s full set of efficiency and incentive claims.
Corollary 10 is a genuine computational anchor: it gives an explicit implementation bound, \(O(n^6Q)\), and a max-flow characterization of individual-rationality extendability.
The strongest objection is that the paper’s rule acts through \(Q\) ordered turns by named agents. Each turn consumes one indivisible good and changes what remains feasible. A continuum cohort has no first individual whose pick can start that process. The proposed phase rule supplies a reasonable replacement: an entire cohort chooses at once, using a lexicographic mass objective. But that adds a batch-choice rule. A schedule over types does not encode every possible individual priority order, especially when turns interleave members of different cohorts. One could add priority class to the type and retain a small support when there are repeated classes; unique ranks, however, can make the support grow with the population.
The stronger version of the mirror is also plausible. In a large exchange system with repeated priority tiers and interchangeable goods within type, process each tier as a cohort. That can correspond to a finite serial order arranged in blocks, and rational masses fit naturally into the paper’s flow model. The type-level choice rule would need to be shown equivalent to aggregating those finite turns, but the paper’s results give proponents a promising route. This is not an objection to grouping agents who share prices, costs, capacities, and preferences.
The computational novelty may be modest: the paper already reduces extendability to max flow, and rational capacities look like a direct extension of that machinery. Modest novelty alone cannot rule out a worthwhile mirror. In a repeated-priority regime, the continuous problem is coherent and Corollary 10 may survive as its computational anchor. My negative case therefore does not establish the universal claim. Its real force is that the proposed batch evaluator needs an equivalence argument before it can be called a mirror of the paper’s serial rule; without that, it is a new cohort policy. If that equivalence holds, I cannot honestly defeat this anchor.
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.