{"id":"1513fc02-e32b-4000-b652-02de6bf11821","arxiv_id":"2502.09265","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Choice correspondences that stay path-independent under every tie-breaking are rationalizable, produce generalized matroids, and allow a cycle-based characterization of constrained efficient stable matchings.","lead":"This paper defines path-independence for choice rules that can return several tied outcomes, and proves that such rules always maximize some utility function and have a matroid structure. It then shows that under these rules plus a monotonicity condition, efficient stable matchings can be characterized by cycles and found in polynomial time.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 9 asserts an unproved aggregation step: edge-by-edge PSIC inclusions are used to conclude that the entire cycle matching is chosen from A\\X. This step is load-bearing for Theorem 6, yet no proof or formal shortcut definition is supplied.","rationale":"The reader's verdict is CONDITIONAL and identifies LAD as the weakest assumption. I agree that LAD is essential, but the more specific load-bearing concern I find is an unproved aggregation step inside Lemma 9. The theorem's central claim is that a maximal stable matching with a shortcut-free PSIC can be improved to a stable matching; the proof of Lemma 9 needs to show that after applying the cycle, each school's new assignment is still chosen from the reduced available set. The step from individual PSIC inclusions to the joint inclusion ν(s) ⊆ C^{w_s}_s(A\\X) is asserted with only the phrase 'since C^{w_s}_s satisfies PI.' For a choice function, PI is equivalent to SUB and IRC, but neither axiom makes this aggregation immediate, because the elements removed from A are removed simultaneously, while each PSIC edge only removes one student. If this inclusion fails, the constructed matching ν need not be stable, and the sufficiency half of Theorem 6 collapses. The paper also never defines 'shortcut,' and the proof assumes without proof that deleting a shortcut produces another PSIC. I do not claim the theorem is false; the structural results in Sections 3 and the construction of the exchange graph are plausible, and the proof may be repairable with an additional lemma. But as written, the most load-bearing step of the main matching theorem is not fully justified. This supports keeping the CONDITIONAL verdict rather than accepting or rejecting outright, and my read does not move the verdict, hence UNCHANGED.","tokens_in":40572,"tokens_out":33236,"duration_ms":299947,"concrete_test":"Formalize the aggregation step as a lemma for PI choice functions: if C(A) = X, |C(A−x)| = |X|, and C(A−x) = X−x+y_x for all x ∈ X, then {y_x : x ∈ X} ⊆ C(A\\X). Use a SAT/CP solver to search over all choice functions on a 5-element ground set that satisfy SUB+IRC (i.e., PI) and LAD. If a violation exists, embed it in the two-school market of Lemma 9 to produce a maximal stable μ with a shortcut-free PSIC whose cycle matching is unstable, disproving Theorem 6. If no violation is found up to |I| = 6, attempt a proof of the aggregation step from SUB+IRC; a successful proof would patch the gap and leave the overall verdict unchanged.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The doubt is in Lemma 9, not primarily in the LAD assumption. Fix a school s and let X = μ(s) ∩ (cycle students) and Y = ν(s) ∩ (cycle students). For each i_ℓ ∈ Y, the PSIC condition gives μ(s) − i_{ℓ+1} + i_ℓ ∈ C_s({i : s ≽_i μ(i)} − i_{ℓ+1}), and the preceding weight argument shows equality with C^{w_s}_s of that set. The proof then says: 'Hence, since C^{w_s}_s satisfies PI, we obtain ν(s) = Y ∪ (μ(s)\\X) ⊆ C^{w_s}_s({i : s ≽_i μ(i)} \\ X).' This is not a consequence of PI without an additional argument. PI for choice functions is SUB+IRC, and those axioms do not obviously allow aggregating one-element removals into a simultaneous removal of all students in X: the choice from A\\X can drop one of the cycle entrants even though each entrant survives its own single removal. This inclusion is exactly what converts a PSIC into a stable Pareto-improving matching; LAD is then used only for the cardinality equality. If the inclusion fails, the cycle matching ν may be unstable, so Theorem 6's sufficiency direction and the polynomial algorithm lose their support. The missing formal definition of 'shortcut' is related: the proof assumes without stating or proving it that shortening a PSIC preserves the PSIC property. The gap is addressable, but it is the most load-bearing unproved step in the paper.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces path-independence (PI) for choice correspondences by requiring that every consistent tie-breaking choice function is PI, and it studies the consequences for rationalizability, combinatorial structure, and stable matching. The main theoretical results are: (i) every PI choice correspondence is rationalizable (Theorem 2); (ii) for every available set X, the family C(X) of chosen sets forms a generalized matroid, yielding polynomial-time membership and computation results (Theorem 3, Theorem 4, Proposition 3); and (iii) choice correspondences rationalized by ordinally concave functions are PI, with size-restricted concavity additionally giving LAD (Theorem 5). The matching application defines an LAD extension for correspondences and proves that, under PI and LAD, a stable matching is constrained efficient if and only if it is maximal and admits no potentially-stable improvement cycle (PSIC), thereby restoring the Erdil-Ergin cycle characterization and providing a polynomial-time algorithm to compute a constrained efficient stable matching that Pareto dominates a given stable matching. The paper closes with applications to responsive choice, controlled school choice, evenly distributed and constrained responsive choice, and overlapping reserves.","tokens_in":40860,"tokens_out":15557,"duration_ms":139956,"significance":"This is a substantive theoretical contribution. The paper extends the well-developed PI/ordinal-concavity toolkit from choice functions to the more realistic setting of choice correspondences, where indifferences and ties are inherent. The rationalizability theorem and the g-matroid theorem are nontrivial and the connection to discrete convex analysis is convincing. The matching result, Theorem 6, is a genuine generalization of the Erdil-Ergin theorem: it replaces responsiveness with PI plus LAD and still obtains a cycle characterization, and the polynomial-time algorithm is an added strength. The paper is largely self-contained, with detailed proofs, consistent examples, and a clear statement of reliance on Yokote et al. (2024). There are no fitted parameters or circular reductions; the central claims are falsifiable mathematical statements. The main weaknesses are a load-bearing but undefined notion of 'shortcut' in the proof of Lemma 9 and several compressed or typo-laden passages in the proof of Theorem 5. These are fixable without changing the main results.","major_comments":[{"comment":"The term 'shortcut' is used repeatedly but never formally defined. Lemma 9 begins with 'Let (i0,...,i_{m-1}) be any PSIC for mu that does not contain a shortcut,' and the proof uses this property both to construct the weight function and to claim a contradiction when a shorter PSIC is produced. To make the sufficiency direction of Theorem 6 complete, the authors must give a formal definition of a shortcut (for example, a chord in the directed exchange graph that itself forms a PSIC) and prove that whenever a PSIC exists, a shortcut-free PSIC also exists (for example, by taking a shortest directed cycle in the graph G defined later in the proof). As written, the proof of Lemma 9 depends on an undefined property, and this is load-bearing for Theorem 6.","section":"Section 4.3.1, Lemma 9 and Definition 3"},{"comment":"The proof contains a clear typo in the ordinal concavity case analysis: in case (iii), the sentence 'either uw(X)<uw(X−i+j) or uw(X)<uw(X−i+j)' should read 'either uw(X)<uw(X−i+j) or uw(X′)<uw(X′+i−j).' In the size-restricted concavity paragraph, the sentence 'uw(X)>uw(X−i) if w(i)>0 and uw(X′)>uw(X′+i) if w(i)<0' is also not the correct way to state the verification; the correct observation is that condition (i) of size-restricted concavity holds for every sign of w(i). These are local errors, but they should be corrected because the theorem is central to the paper's applications.","section":"Section 3.3, proof of Theorem 5"},{"comment":"The step from the individual PSIC inclusions to the simultaneous inclusion 'nu(s) = Y ∪ (mu(s)\\X) ⊆ C^{w_s}_s({i:s≽_i mu(i)} \\ X)' is compressed to the point of being hard to verify. The step is in fact valid: since PI implies substitutability, for each i_ℓ in Y we have i_ℓ ∈ C^{w_s}_s(A−i_{ℓ+1}) and i_ℓ ∉ X, so repeated application of substitutability gives i_ℓ ∈ C^{w_s}_s(A\\X); moreover, mu(s)\\X ⊆ C^{w_s}_s(A\\X) follows from mu(s)=C^{w_s}_s(A). I recommend that the authors spell out this argument explicitly, because this inclusion is the crucial bridge that turns a PSIC into a stable Pareto-improving matching.","section":"Section 4.3.1, Lemma 9, aggregation step"}],"minor_comments":[{"comment":"The proof of Theorem 3 is extremely dense, especially the two case analyses with the auxiliary weight functions w and w′. Adding a short high-level explanation or moving some of the routine verifications to an appendix would significantly improve readability.","section":"Section 3.2, proof of Theorem 3"},{"comment":"The preference list for student i5 is written as '(s1 s4 ∅ s3 s4)', which appears to contain a typo and to list s4 twice. It should presumably be '(s1 s4 ∅ s2 s3)' or another complete strict preference order.","section":"Appendix D.2, Example 6"},{"comment":"The sentence 'In practice, each student can have multiple types. In practice, each student can have multiple types.' contains a duplicated phrase; one copy should be deleted.","section":"Section 5, Overlapping Reserves"},{"comment":"The PSIC definition would be clearer if the indexing conventions were stated more explicitly, in particular the treatment of im = i0 and sm = s0 in the third bullet. The current notation is understandable but easy to misread.","section":"Section 4.2, Definition 3"}],"recommendation":"major_revision","confidential_remarks":"The paper is well within the scope of the journal and the main results appear correct. The referee's concern about the aggregation step in Lemma 9 does not land, since substitutability justifies the inclusion, but the undefined 'shortcut' notion is a genuine gap in the written proof of Theorem 6. This is fixable with a formal definition and a short existence argument, so I recommend major revision rather than rejection. The authors should also correct the typos in Theorem 5 and expand the compressed steps in Lemma 9."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one. It is a real theory paper, not a repackaging. The central move—defining path independence for a choice correspondence by requiring every consistent tie-breaking to yield a PI choice function—is natural and productive. It gives rationalizability (Theorem 2), the g-matroid structure (Theorem 3), and restores the Erdil-Ergin cycle characterization for constrained efficient stable matchings under PI+LAD (Theorem 6). That last result covers responsive rules with ties, quotas, reserves, and overlapping reserves, which is where the practical payoff sits. The polynomial algorithms are a nice bonus.\n\nThe proofs are mostly careful. I checked the one step the stress-test flagged in Lemma 9, where edge-by-edge PSIC inclusions are aggregated to ν(s) ⊆ C(U\\X). The worry was that PI does not allow aggregating single removals. It does, immediately: substitutability (part of PI) applied to the subset U\\X ⊆ U − i_{ℓ+1} gives each entrant y ∈ C(U\\X), and the unchanged students from μ(s) are already chosen by SUB from C(U). The step is valid; the concern does not land.\n\nWhat is actually soft is minor. 'Shortcut' in Lemma 9 is used without a formal definition; Example 4 explains the idea but the proof relies on it. Define it or replace it with an explicit minimal-cycle argument. The proof of Theorem 5 has a typo in the ordinal concavity case—the same inequality appears twice—and Theorem 3's proof is dense enough that I would want a careful read before trusting every exchange. None of this undermines the main results. The citations, including the authors' own prior work, look appropriate.\n\nWho is this for: anyone working on matching with ties, affirmative action, or distributional constraints, and people who care about choice-theoretic foundations of matroidal structures. The paper deserves a serious referee. I would send it out; the referee should verify Theorem 3 and the shortcut-free construction in Lemma 9, but there is a coherent and novel contribution here.","headline":"New definition of PI for choice correspondences delivers a clean theory and restores the Erdil-Ergin cycle characterization; the flagged Lemma 9 gap dissolves under substitutability.","tokens_in":41429,"tokens_out":5083,"would_cite":true,"duration_ms":44681,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B68","05B35","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that under path-independent choice correspondences satisfying the law of aggregate demand, a stable matching is constrained efficient if and only if it is maximal and admits no potentially-stable improvement cycle, and a…","keywords":["path-independent choice correspondence","generalized matroid","stable matching","constrained efficiency","ordinal concavity","law of aggregate demand","potentially-stable improvement cycle","school choice"],"falsifier":"Exhaustively search all markets with at most five students and three schools in which every school's correspondence is path-independent but at least one violates the law of aggregate demand, using a PI-but-not-LAD rule such as the paper's C2 table example. If any market contains a stable matching that is maximal, admits no potentially-stable improvement cycle, and is nevertheless Pareto dominated by another stable matching, then Theorem 6 genuinely needs the LAD hypothesis.","tokens_in":40318,"feed_emoji":"🎓","tokens_out":12561,"duration_ms":105254,"temperature":0.7,"pith_summary":"This paper defines path independence for choice correspondences: a set-valued choice rule is path-independent if every consistent tie-breaking between tied options yields a path-independent choice function in the classical sense. The paper proves that such correspondences are rationalizable, that their chosen families are generalized matroids, and that correspondences arising from ordinally concave utility functions satisfy the condition. These structural facts are applied to matching markets in which schools have weak priorities or diversity constraints. The central market result is that when every school's choice correspondence is path-independent and satisfies the law of aggregate demand—the chosen set cannot grow when the pool shrinks—a stable matching is constrained efficient exactly when it is maximal and admits no potentially-stable improvement cycle, and a constrained efficient Pareto improvement of any given stable matching can be computed in polynomial time. This restores a cycle-based characterization that was known only for restrictive responsive choices and that fails under weaker substitutability assumptions.","feed_headline":"Cycle characterization of efficient stable matchings is restored","feed_subtitle":"Path-independent school choice plus a demand law makes efficient stable matchings exactly the maximal, cycle-free ones.","key_machinery":"The central object is a choice correspondence $C:2^I\\Rightarrow 2^I$ such that every consistent tie-breaking—choosing, for each available set, the subset in $C(X)$ of maximum weight under a unique-maximizing weight function—yields a path-independent choice function, where path-independence (PI) is the classical property that choices are unchanged by partitioning the available set. The proof machinery also uses the closure operator $\\tau(X)=\\bigcup\\{Y\\subseteq I : C(X)\\cap C(Y)\\neq\\emptyset\\}$, which is extensive, idempotent, and monotone; it supplies the rationalizing utility $u(X)=|\\tau(X)|$ when $X\\in C(X)$ and $|\\tau(X)|-1$ otherwise, together with the interval lemma $S\\in C(T)$ if and only if $S\\subseteq T\\subseteq \\tau(S)$. A generalized matroid, also used here, is a family of subsets with an exchange property that makes all inclusion-maximal sets of the family have the same size. For the matching theorem, the named object is a potentially-stable improvement cycle (PSIC), a cycle of students in which each student moves to a preferred school and each receiving school still finds the resulting set acceptable; the proof shows that under PI plus the law of aggregate demand (LAD) a shortcut-free PSIC preserves stability and that any Pareto-improving stable matching generates one.","core_discovery":"The paper introduces a path-independent choice correspondence: for every unique-maximizing weight function, the tie-broken choice function $C_w(X)=\\arg\\max_{Y\\in C(X)} w(Y)$ is path-independent. It establishes four results. First, every such correspondence is rationalizable by an explicit utility built from a closure operator, extending a known property of path-independent choice functions. Second, for every available set $X$, the family $C(X)$ of chosen subsets is a generalized matroid, so tie-broken choices can be computed polynomially from a membership oracle. Third, any choice correspondence rationalized by an ordinally concave function is path-independent, and if the function also satisfies size-restricted concavity, the correspondence satisfies the law of aggregate demand. Fourth, in a matching market where each school's correspondence is path-independent and obeys the law of aggregate demand, a stable matching is constrained efficient if and only if it is maximal and admits no potentially-stable improvement cycle; moreover, a constrained efficient matching that Pareto dominates any given stable matching can be found in polynomial time.","pith_inferences":["The paper explicitly leaves open whether every PI choice correspondence is rationalizable by an ordinally concave function; a positive answer would make path independence exactly the correspondence-level counterpart of ordinal concavity, mirroring the known choice-function theorem.","The proof uses LAD at two cardinality equalities; the paper's C2 example shows PI alone does not control selected-set sizes, so the cycle characterization is likely to need LAD or an extra cardinality assumption in applications, though the paper does not exhibit such a market.","A concrete testable consequence for policy is that DA with arbitrary tie-breaking can be Pareto-dominated (the paper gives such a market); measuring this efficiency loss on real school-choice data would quantify the value of the polynomial-time improvement algorithm."],"forward_implications":["Stable matchings exist whenever every school's choice correspondence is path-independent, and deferred acceptance with any fixed tie-breaking produces one such matching.","Under PI plus LAD, the set of constrained efficient stable matchings is exactly the set of maximal stable matchings with no PSIC, giving a polynomial-time certificate for constrained efficiency.","For any given stable matching, a constrained efficient stable matching that Pareto dominates it can be computed in polynomial time by repeatedly restoring maximality and then applying shortcut-free PSICs.","Realistic school-choice correspondences—responsive with ties, type-specific quotas, reserves, overlapping reserves, evenly distributed and constrained responsive rules, and meritorious horizontal rules—all satisfy PI and LAD because they are rationalized by $M^\\natural$-concave (in particular laminar concave) functions.","For PI plus LAD correspondences, a tie-broken choice $C_w(X)$ can be computed in $O(|X|^2)$ time, making the improvement algorithm practical."],"supporting_citations":[{"why":"Gives the equivalence between PI and substitutability plus IRC for choice functions, the classical benchmark the paper extends to correspondences.","marker":"[Aizerman and Malishevski, 1981]"},{"why":"Supplies the extended substitutability and IRC conditions for choice correspondences that the new PI condition strengthens.","marker":"Sotomayor [1999]"},{"why":"Proved the cycle characterization for responsive choice correspondences that Theorem 6 generalizes to PI and LAD correspondences.","marker":"Erdil and Ergin [2008]"},{"why":"Introduced PSIC and showed the cycle-based characterization fails under acceptant and substitutable correspondences, defining the gap the paper fills.","marker":"Erdil and Kumano [2019]"},{"why":"Proved PI choice functions are exactly those rationalizable by ordinally concave functions; Theorem 5 and the LAD characterization build on this.","marker":"Yokote et al. [2024]"},{"why":"Relates PI choice functions to closure operators, the technique adapted to prove rationalizability of PI correspondences.","marker":"Johnson and Dean [1996]"},{"why":"Also establishes the closure-operator and convex-geometry connection for PI choice functions used in the rationalizability proof.","marker":"Koshevoy [1999]"},{"why":"Shows M♮-concave utility functions induce PI and LAD choice functions, used to verify the applications satisfy the hypotheses.","marker":"Fujishige and Tamura [2006]"}],"fun_headline_variants":["Path-independence revives cycle rule for efficient matchings","PI choice correspondences give matroids and cycles","Matroid structure from path-independent ties","Efficient stable matchings via path-independent schools","A new path to constrained efficiency in matchings"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every school's choice correspondence satisfies the law of aggregate demand—for every consistent tie-breaking, shrinking the available set cannot increase the size of the chosen set—because the cycle argument uses this cardinality monotonicity to force shortcut-free cycles and to equate school sizes across Pareto-improving matchings.","fun_headline_variants_meta":{"raw":{"variants":["Path-independence revives cycle rule for efficient matchings","PI choice correspondences give matroids and cycles","Matroid structure from path-independent ties","Efficient stable matchings via path-independent schools","A new path to constrained efficiency in matchings"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000285,"raw_usage":{"total_tokens":1739,"prompt_tokens":1065,"completion_tokens":674,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":681,"completion_tokens_details":{"reasoning_tokens":603}},"tokens_in":681,"tokens_out":674,"duration_ms":6808,"temperature":1.0,"reasoning_tokens":603,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T22:06:47.893948+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhaustively search all markets with at most five students and three schools in which every school's correspondence is path-independent but at least one violates the law of aggregate demand, using a PI-but-not-LAD rule such as the paper's C2 table example. If any market contains a stable matching that is maximal, admits no potentially-stable improvement cycle, and is nevertheless Pareto dominated by another stable matching, then Theorem 6 genuinely needs the LAD hypothesis.","supporting_citations":[],"review_version":1}