| paper | d4-journals-mss-2023-0027 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: Polynomial-time solvable. Every original optimal assignment is preserved, and all stated extremum laws extend to cohorts; the changing seller's midpoint formula requires the correction proved above. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given finite seller and buyer type sets \(S,B\), rational masses \(r_s,q_b\), seller reservation values \(s_s\), and buyer valuations \(t_{sb}\), set \(a_{sb}=(t_{sb}-s_s)^+\). Use the mass assignment LP \(\max \sum_{s,b}a_{sb}x_{sb}\), subject to \(\sum_b x_{sb}\le r_s\), \(\sum_s x_{sb}\le q_b\), and \(x_{sb}\ge0\), and its weighted dual \(\min \sum_s r_su_s+\sum_bq_bv_b\), subject to \(u_s+v_b\ge a_{sb}\) and \(u_s,v_b\ge0\). For a seller type \(k\), let \(\underline u_k,\bar u_k\) be the minimum and maximum \(u_k\) over the dual optimal face. When \(0\le c\le\bar u_k\), raise \(s_k\) to \(s_k+c\) for the whole cohort and determine the exact changes in each type’s minimum and maximum stable payoff and their midpoint, including sharp bounds; establish whether Theorem 4’s response laws extend or give the correct replacements.
A two-sided population with finite seller and buyer type supports and rational masses, matched by a fractional flow between types under per-type capacities. Each unit of mass receives an integral object allocation, while type-level flows and weighted dual payoffs can be fractional. The sensitivity operation raises the reported reservation value of an entire positive-mass seller type.
The mirror shifts the reports of all sellers in type \(k\), so it does not measure how much one seller can gain in an atomless market; the proponent acknowledges this difference but does not establish that the cohort shift has the same individual-incentive interpretation.
fatal: False
The mirror covers the seller-side sensitivity result in Theorem 4 and its price translation in Corollary 2; Lemma 1 supports computation of extreme payoffs. It leaves the buyer-side results, other mechanism-design claims, and the nucleolus discussion outside the anchored question.
The strongest case is that assignment markets are a natural high multiplicity regime: many units and households can share a small catalogue of complete valuation types. Think of a large rental market with many similar apartments and households whose values for each apartment category are the same within a type. The masses record each type’s share of the market. A matching is a flow \(x_{sb}\) between seller type \(s\) and buyer type \(b\), with each unit of mass matched to at most one partner. A type-level flow can be fractional even though each infinitesimal household receives an integral bundle. This keeps the paper’s assignment question intact while letting the population and capacities scale.
My lead anchor is Theorem 4, proved in this paper. It studies a seller \(k\) who raises their reservation value by \(c\), with \(0\le c\le\bar u_k\), while all other valuations stay fixed. The optimal assignment remains optimal. The minimum core payoff of \(k\) becomes \(\underline u'_k=(\underline u_k-c)^+\), while each other seller’s minimum payoff satisfies \(\underline u_i\le\underline u'_i\le\underline u_i+c\). The maximum payoff of \(k\) falls by \(c\), so \(\bar u'_k=\bar u_k-c\); other sellers’ maximum payoffs do not change. Since fair payoff is the average of the minimum and maximum, \(\tilde u'_k=\tilde u_k-c+\tfrac12(c-\underline u_k)^+\), and \(\tilde u_i\le\tilde u'_i\le\tilde u_i+\tfrac c2\) for \(i\ne k\). The bounds in the minimum and fair payoff claims are sharp. The paper also gives the corresponding price result in Corollary 2.
The continuous question I would put to a prover is Type-Cohort Fair-Price Sensitivity. The input is a finite catalogue of seller and buyer types, rational masses \(r_s,q_b\), rational reservation values \(s_s\), and buyer valuations \(t_{sb}\). For the reported market, let \(a_{sb}=(t_{sb}-s_s)^+\). A stable per-type payoff is an optimal solution of the dual assignment LP: \(u_s,v_b\ge0\), \(u_s+v_b\ge a_{sb}\), minimizing \(\sum_s r_su_s+\sum_b q_bv_b\). Given a seller type \(k\) and a shift \(c\), change that cohort’s reported reservation value to \(s_k+c\), recompute the minimum, maximum, and fair competitive prices, and return their exact changes. The question is whether the response law of Theorem 4 extends to this positive-mass cohort setting, and, if it does not, what sharp type-level bounds replace it. A solution is the exact price and payoff changes, with a proof of the universal law or a counterexample and corrected bounds.
I expect the computation for this mirror to be tractable: with \(\tau\) types there are \(O(\tau^2)\) matching variables and a rational linear program of polynomial size. The genuinely interesting part is whether the paper’s sharp response formulas survive when an entire type cohort changes its report. That also opens questions about nonuniform changes within a type, buyer cohorts, and the breakpoints in the price response as \(c\) varies.
A second useful anchor is Lemma 1, proved in this paper. In the paper’s reference graph, for each seller \(k\), the maximum path length \(\alpha_k\) from the fictitious node \(0\) to \(k\) equals \(k\)’s minimum core payoff, and the negative of the maximum path length \(\beta_k\) from \(k\) to \(0\) equals their maximum core payoff. The lemma also says some seller has minimum payoff zero and some seller has maximum payoff equal to their matched pair’s full profit. The paper notes that these longest-path values can be computed in polynomial time.
Its continuous mirror, Type-Assignment Price Computation, takes the finite type catalog, rational masses, and valuations, and asks for the minimum and maximum stable payoff vectors and their fair average, hence the corresponding competitive prices. A solution is the exact rational vectors and a certificate of stability and optimality. I expect this to be tractable by the weighted assignment LP; the paper’s path characterization is evidence for the tractability of the individual-agent version, while the type-mass formulation makes the relevant support size explicit.
The main limitation is that Theorem 4 concerns one seller’s unilateral report, whereas a positive-mass type changing its report is a cohort action. In an atomless model a single agent has zero mass and cannot move aggregate prices. I would not present the cohort result as a literal preservation of individual manipulability: it is a plausible, useful continuous extension of the paper’s price-sensitivity question. The mirror covers the assignment and fair-price sensitivity results, not every mechanism-design result in the paper. The paper offers no named hardness result or complexity classification; the algorithmic anchors here are its longest-path characterization and exact sensitivity theorem.
The strongest case against is that this paper has no named complexity theorem to continuize. Theorem 4 is a sensitivity formula, and Lemma 1 characterizes extreme payoffs by longest paths; the paper notes that those paths can be computed in polynomial time. So neither anchor poses an unknown complexity question of the kind ChoCo most needs.
Theorem 4’s central object is one seller’s unilateral report. In an atomless population, one seller has zero mass and cannot move market prices. The proposed repair—shift the report of an entire seller type—gives a meaningful question, but it changes the strategic actor from one agent to a cohort acting together. A closer population analogue would perturb the mass of sellers making that report and study the resulting price response. That is coherent comparative statics, but it no longer measures the individual manipulation gain proved in the paper.
Lemma 1 has a more direct type-level translation, but it appears to offer little computational gap: with \(\tau\) seller and buyer types, price computation is a rational transportation LP with \(O(\tau^2)\) variables. One can optimize over its optimal face to obtain the extreme prices and their average. The paper’s path identity may not survive unequal type masses, but replacing it with that LP gives a routine exact computation, while the original finite market already has a polynomial path algorithm. That makes this a weak priority for a programme aimed at mapping where continuization changes computational tractability.
I would not claim that continuum assignment markets are already a collision: existing assignment-market work on continuum agents and core structure is evidence that the regime is sensible, not that this paper’s computational question has been answered. [A paper surveying that continuum-agent core literature](https://ykanoria.github.io/kss-or-final.pdf) treats core convergence, rather than this paper’s price-sensitivity computation.
So the negative case is limited: it can argue that the individual-manipulation result atomizes and that the price-computation mirror is low-yield. It cannot honestly establish that no worthwhile mirror exists. A type-mass price-response problem remains plausible, especially if the authors recognize cohort sensitivity as their question.
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.