{"id":"abb5314b-5637-4c4e-a769-d84c6a5b1585","arxiv_id":"2506.01509","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The two-stage stochastic assignment game is polynomial-time solvable for explicit distributions, and its LP relaxation has an integral polyhedron.","lead":"This paper analyzes a game where groups of players split value from matching, and the player set may change after a random event. The authors show that finding stable payoff plans that change as little as possible is computationally easy when the random event's chances are known, and they use this to solve a related graph problem.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The integrality proof hinges on an unproven WLOG normalization of dual γ variables in Lemma 2/Claim 2 (and Lemma 7/Claim 4); the written adjustment is ill-defined when γ_v > 1, so the dual-to-primal mapping is not established.","rationale":"The paper's central claim is that the feasible regions of (2SAG-LP) and (6) are integral polyhedra, leading to polynomial-time solvability and the multistage vertex cover consequence. The proof strategy is to formulate a dual flow LP, invoke total unimodularity, and then map an optimal dual solution back to the original LP. The mapping is the delicate part: it requires modifying the free γ variables so that certain inequalities become tight. The reader identified this normalization as the weakest assumption, and my reading agrees. The specific flaw I found is in the operation 'lower y_v by min{y_v, 1 − γ_v}' in Claim 2: when γ_v > 1, the proposed decrement is negative, so the instruction is not a valid operation in a feasible-region argument, and the subsequent dichotomy ('if not done, then y_v=0 and γ_v>1') is unsupported. A feasible example with γ_v=10, y_v=1 shows that without normalization, dropping γ variables can produce a point violating the constraints of (3). This directly threatens Lemma 2 and, by the identical structure, Lemma 7. The issue is not that the theorem is false; it is that the proof as written does not justify the transfer of integrality from the dual to the original LP. This is a repair needed for the central claim, supporting a conditional verdict. The multistage vertex cover convention is a real but smaller issue: the definition in Section 4 must explicitly require a minimum-cardinality vertex cover at each stage, otherwise the problem is trivial and the claimed polynomial-time result is vacuous. I do not see an independent reason to reject the paper; the construction of the auxiliary graph and the overall architecture are plausible, and the flaw is localized to the normalization argument. Therefore the reader's CONDITIONAL verdict should stand unchanged.","tokens_in":19814,"tokens_out":21685,"duration_ms":232485,"concrete_test":"Exhaustively enumerate all two-stage instances with up to 4 vertices per stage and up to 2 scenarios (all bipartite graphs, and objective coefficients α, β, b chosen from a small grid such as {-2,-1,0,1,2}), solve (2) and (3) as exact LPs, and compare optimal values; any instance with opt(2) < opt(3) disproves Lemma 2, and any instance where adding the normalization equalities γ_v + y_v = 1 / −γ_v + y_v = 0 changes the optimum isolates where the WLOG step fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is Claim 2 of Lemma 2 (and its k-stage analogue Claim 4 of Lemma 7): to map an optimal solution of the dual flow LP (2) to an optimal solution of (3), the proof must normalize γ so that γ_v + y_v = 1 on V1-side vertices and −γ_v + y_v = 0 on V2-side vertices. This normalization is what allows the coupling constraints γ_v − γ_S^v + δ_S^v ≥ 0 and γ_S^v − γ_v + d_S^v ≥ 0 to be converted into the inequalities y_v − y_S^v ≤ δ_S^v and y_S^v − y_v ≤ d_S^v of (3). As written, the proof is defective: for v ∈ V0 ∩ V1 with γ_v + y_v > 1, it instructs lowering y_v by min{y_v, 1 − γ_v}; when γ_v > 1 this decrement is negative, so the operation is undefined and the conclusion 'it must be that y_v = 0' does not follow. The same defect appears in the range argument of Claim 4. Absent a correct normalization argument, restriction of a feasible point of (2) to (3) can fail (e.g., a single V1 vertex with γ_v=10, y_v=1, γ_S^v=1, y_S^v=0, δ=0, d=9 satisfies (2) but violates y_v − y_S^v ≤ δ). The claim may be salvageable for optimal solutions, but the proof does not supply the needed argument, so Theorem 1 and Theorem 4 are not fully established. A secondary modeling gap: Theorem 5 never states that each stage must choose a minimum vertex cover, without which the problem is trivial.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a two-stage stochastic version of the assignment game, where the first-stage graph is known and the second-stage graph is drawn from a distribution. The main formal claim is that the feasible region of the natural LP formulation (2SAG-LP) is an integral polyhedron (Theorem 1), and that the analogous k-stage LP (6) is also integral (Theorem 4). The proof proceeds by formulating an auxiliary maximum-flow LP, passing to its dual, exploiting total unimodularity to obtain an integral dual optimum, and then mapping that optimum back to the original LP through two intermediate LPs, (3) and (9). The integrality results are then used to obtain a sample-average-approximation bound in the implicit-distribution setting (Theorem 3) and to show polynomial solvability of a variant of multistage vertex cover when all stages are bipartite with the same bipartition (Theorem 5).","tokens_in":20211,"tokens_out":20912,"duration_ms":228376,"significance":"If the integrality theorems are correct, the paper makes a solid contribution: it gives a polynomial-time LP formulation for the explicit-distribution case with integral optimal core vectors, extends the two-stage stochastic framework of [4] to assignment games, and identifies a nontrivial tractable case of multistage vertex cover. The SAA analysis is honest about following [4], and the hardness reduction from counting vertex covers is a nice self-contained argument. However, the central proof has a load-bearing gap in the dual-to-primal mapping, so the significance is conditional on repairing that argument.","major_comments":[{"comment":"The proof of the \"without loss of generality\" normalization of the dual variables is defective at a load-bearing point. For v in V0 ∩ V1 with γ_v + y_v > 1, the proof instructs lowering y_v by min{y_v, 1 − γ_v}; when γ_v > 1, this quantity is negative, so the operation is not a lowering and the subsequent conclusion \"it must be that y_v = 0\" does not follow from the stated case analysis. The same issue affects the V2-side normalization, which is dismissed with \"by similar arguments\" even though the required operation is not symmetric: for V2 vertices one may need to increase γ_v, and this interacts with the coupling constraints γ^S_v − γ_v + δ^S_v ≥ 0 and γ_v − γ^S_v + d^S_v ≥ 0. The restriction of a feasible point of (2) to (3) is exactly what converts the coupling constraints of (2) into the inequalities y_v − y^S_v ≤ δ^S_v and y^S_v − y_v ≤ d^S_v of (3); without a correct normalization argument, Theorems 1 and 4 are not fully established. The gap may be repairable (for example, by first reducing y_v to max{0, 1−γ_v} and then decreasing γ_v to 1 with a suitable cascade on γ^S_v, and by a separate argument for V2 vertices), but the current manuscript does not supply that argument.","section":"Section 2, Lemma 2, Claim 2"},{"comment":"The statement of the multistage vertex cover problem in Section 4 omits any requirement that each stage choose a minimum-cardinality vertex cover. With the definition as written, taking all vertices in every stage is a feasible solution with total difference 0, so the problem is trivial. The proof via LP (6) implicitly imposes the constraint 1^T y_i = ν(G_i), i.e., a minimum vertex cover at each stage, and this is the only reason the argument works. The theorem needs to state this minimum-cover convention explicitly and align its definition with the one used in [5]; otherwise Theorem 5 is not a meaningful statement about the problem as defined in the paper.","section":"Section 4, Theorem 5"},{"comment":"The proof asserts \"We will have ẽ ≤ 1 and ŷ^S ≤ 1\" (and its analogue in Lemma 8) without justification. Feasibility of (3) alone does not bound y^S_v by 1; the bound must come from optimality together with the specific definition of ε, and this is not shown. In addition, the displayed inequality after the replacement writes Σ α_v ẽ_v ≤ Σ α_v, which is not valid when some α_v are negative; the correct termwise bound is α_v ẽ_v ≤ |α_v| for ẽ_v ∈ [0,1]. These issues are fixable, but as written the proof of the optimality transfer from (3) to (2SAG-LP) is incomplete.","section":"Section 2, Lemma 3"}],"minor_comments":[{"comment":"In the displayed formula after equation (4a), the notation G0[S] should be Π(S) (or G0[Π(S)]) to match the definition of the second-stage vertex set.","section":"Section 3, equation (4a)"},{"comment":"The definition of ε in the multistage setting is missing the outer summation over stages: it should be ε = 1 / (1 + Σ_{i=1}^k Σ_{v∈Vi} |α^i_v| + Σ_{i=1}^{k-1} Σ_{v∈Vi∩Vi+1} (β^i_v + b^i_v)).","section":"Section 4, definition of ε"},{"comment":"In the proof of Lemma 8, several sums are written as \"Σ_{k=1}^k\" where the index should be i=1; this is a typographical error that should be corrected.","section":"Section 4, proof of Lemma 8"},{"comment":"The phrase \"the bipartition of G0 merged with all GS\" should be made a standing assumption that every second-stage graph GS has the same bipartition as G0 on the common vertex set, since the auxiliary graph construction relies on a consistent bipartition of all vertices.","section":"Section 2, paragraph before Lemma 2"}],"recommendation":"major_revision","confidential_remarks":"The main gap is localized to the normalization argument in Lemma 2/Claim 2 and Lemma 7/Claim 4, plus the triviality issue in the statement of Theorem 5. The overall approach is promising and the rest of the paper appears sound, so this is a repairable major revision rather than a rejection. I would ask the authors to supply a complete proof of the dual normalization or to restructure the proof so that the map from (2) to (3) is fully justified."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The two-stage stochastic assignment game is a natural object, and the paper gets the easy parts right: the explicit-distribution LP is polynomial-size, the hardness reduction via counting vertex covers is clean, and the SAA analysis correctly adapts Faenza et al. The potential payoff is real: an integral polyhedron for this game, plus a new polynomial-time case of multistage vertex cover when the bipartition is fixed across stages. If the integrality theorem holds, this is worth having.\n\nThe problem is that the proof of the integrality theorem has a load-bearing gap. In Lemma 2, Claim 2, the proof wants to normalize any feasible dual solution so that γ_v + y_v = 1 on V1-side vertices and −γ_v + y_v = 0 on V2-side vertices. The written argument tells you to lower y_v by min{y_v, 1−γ_v} when γ_v + y_v > 1. If γ_v > 1, that decrement is negative, so the operation is undefined and the later conclusion that y_v must be 0 does not follow. This is not a purely cosmetic issue: take a single V1 vertex with γ_v = 10, y_v = 1, γ_S^v = 1, y_S^v = 0, δ = 0, d = 9. This satisfies (2) but, after the proposed restriction, violates y_v − y_S^v ≤ δ. The claim that any feasible dual solution maps to a feasible point of (3) is false as stated. The duality step in Lemma 7 for the k-stage case has the same defect. The theorem may still be salvageable for optimal solutions, but the paper does not provide the argument.\n\nThe secondary issue is in Theorem 5. The paper defines multistage vertex cover without requiring a minimum-cardinality cover at each stage; as stated, the problem is trivial (take all vertices at every stage). The LP in (6) implicitly enforces minimum covers via 1^T y_i = ν(G_i), so the result is about minimum vertex covers—that convention needs to be stated in the theorem. Lemma 3 also asserts bounds on y^S without a complete proof; that looks like a minor omission, but it should be filled in.\n\nThe paper is clearly written and the ideas are sensible. The central claim is plausible; the proof is just not there yet. This deserves a serious referee, but the referee should push hard on the normalization step and on the formal definition of the multistage problem. I would not cite it in its current form.","headline":"New two-stage stochastic assignment game with a flow-based integrality proof that has a genuine gap at the WLOG normalization step; the same-bipartition multistage vertex cover result is nice but needs a minimum-cover assumption to be non-trivial.","tokens_in":20709,"tokens_out":4423,"would_cite":false,"duration_ms":45103,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A12","90C27","90C05","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"The two-stage stochastic assignment game is polynomial-time solvable via an integral LP, and the same integrality makes multistage vertex cover polynomial when all stages share one bipartition.","keywords":["assignment game","two-stage stochastic optimization","core","integral polyhedron","total unimodularity","sample average approximation","multistage vertex cover","bipartite graph"],"falsifier":"Compute, by exact enumeration over all small two-stage bipartite instances with the same bipartition, whether every extreme point of the multistage LP is integral; a single fractional extreme point would refute Theorem 4, as would a feasible dual solution for which the claimed gamma-normalization strictly worsens the objective.","tokens_in":19636,"feed_emoji":"🎲","tokens_out":9208,"duration_ms":85962,"temperature":0.7,"pith_summary":"The paper studies the assignment game, a cooperative game on a bipartite graph where stable allocations form the core, and asks how to keep an allocation stable when players and edges change in a second stage drawn from a distribution. Its central claim is that the natural linear program for the two-stage problem has an integral polyhedron: every extreme point of the feasible region is an all-integer vector. If true, this makes the explicit-distribution version polynomial-time solvable with integer optimal core vectors, and it supplies the combinatorial control needed to approximate the hard implicit-distribution version by sampling. The same integrality result, extended to k stages, implies that the multistage vertex cover problem is polynomial-time solvable whenever every stage graph is bipartite and all stages share the same bipartition, even though the general two-stage bipartite case is NP-hard.","feed_headline":"A single integral LP solves two-stage assignment games","feed_subtitle":"The same integrality makes multistage vertex cover polynomial when every stage shares one bipartition.","key_machinery":"The carrying object is the auxiliary flow network G' and the dual LP obtained from it. The graph has a source and sink, one copy of each vertex per stage or scenario, arcs whose capacities encode the objective coefficients through a small parameter epsilon, and unbounded arcs for the edges of the bipartite graphs. Because the maximum-flow LP has a totally unimodular constraint matrix, meaning every square submatrix has determinant 0 or +/-1, its dual has an integral feasible region. The central technical step is a two-way feasibility-preserving map between that dual and the original LP, including a 'without loss of generality' normalization of the dual variables gamma; this transfers integrality from the flow polytope to the assignment-game polyhedron.","core_discovery":"On the paper's own terms, the discovery is Theorem 1 and its k-stage analogue Theorem 4: the feasible regions of the two-stage and multistage assignment-game LPs are integral polyhedra. Because these LPs solve the explicit-distribution and multistage problems, the paper obtains polynomial-time algorithms and, importantly, guarantees that optimal solutions can be chosen integral, i.e., as 0-1 vertex covers of the bipartite stage graphs. Integrality is proved by building an auxiliary maximum-flow network whose dual LP is equivalent to the original LP up to a small perturbation of the objective; since flow LPs have totally unimodular constraint matrices, the dual polyhedron is integral, and a two-way mapping between the two feasible regions transfers an integral optimum back. The authors leverage Theorem 1 to show that when the distribution is given only by a sampling oracle the problem is hard, since its objective would count vertex covers, but a sample average approximation finds a first-stage allocation within additive error with high probability. Finally, the k-stage version yields a polynomial-time algorithm for multistage vertex cover when all graphs are bipartite with the same bipartition.","pith_inferences":["An unstated testable consequence is that the complexity of multistage vertex cover should degrade gradually as the bipartitions of consecutive stages diverge; if the same-bipartition condition is the only source of tractability, instances whose bipartitions differ on few vertices may admit fixed-parameter algorithms, while unrestricted two-stage instances remain NP-hard.","Because integral core vectors are exactly 0-1 vertex covers, the two-stage assignment game can be read as a stochastic vertex-cover selection problem with switching penalties, which suggests direct approximation algorithms for stochastic vertex cover via rounding without going through the game-theoretic core.","The SAA guarantee counts all 2^|V0| integral core vectors in the union bound; replacing that count by the number of minimal vertex covers or by a structural parameter could yield sharper sample-size bounds in sparse graphs.","The hardness reduction equates the objective with the number of vertex covers, so even determining the objective value is #P-hard; this suggests that any multiplicative approximation of the implicit-distribution problem would require structurally different assumptions, since the additive SAA guarantee does not rule out large relative error."],"forward_implications":["With an explicit list of scenarios and probabilities, the two-stage stochastic assignment game can be solved in polynomial time, and the optimal core vectors can be chosen integral, i.e., as 0-1 vertex covers of the stage graphs.","When the distribution is hidden behind a sampling oracle, no polynomial-time exact algorithm exists unless P = NP, but the sample average approximation delivers, with probability at least 1 - alpha, a first-stage core allocation whose expected loss exceeds the optimum by at most sqrt(2) * sum_v lambda_v * sqrt(ln(2|V0|/alpha)/N), using polynomially many samples.","For any fixed number of stages k, the multistage assignment-game LP has an integral polyhedron, so the multistage problem of minimizing total absolute change between core allocations is polynomial-time solvable.","The multistage vertex cover problem becomes polynomial-time solvable for any number of stages when every graph is bipartite and all bipartitions are identical, contrasting with the known NP-hardness of the two-stage bipartite case with different bipartitions.","By choosing which auxiliary loss variables enter the objective, the same LP formulation covers absolute loss, positive loss, or one-sided loss of the remaining players."],"supporting_citations":[{"why":"Defines the assignment game and characterizes its core as the minimum fractional vertex covers of the bipartite graph, the object the paper extends to two stages.","marker":"[13]"},{"why":"Supplies the total unimodularity properties that make the dual flow LP's polyhedron integral.","marker":"[12]"},{"why":"Provides the two-stage stochastic stable matching framework, including the hardness reduction strategy and the sample average approximation analysis the paper adapts.","marker":"[4]"},{"why":"Establishes the NP-hardness of multistage vertex cover for two bipartite stages, the baseline that Theorem 5 contrasts with.","marker":"[5]"},{"why":"Introduces the sample average approximation method used for the implicit-distribution setting.","marker":"[8]"},{"why":"Gives the #P-hardness of counting vertex covers used in the hardness reduction for the implicit-distribution problem.","marker":"[10]"},{"why":"Supplies the concentration inequality used to bound the probability that the sampled solution is far from optimal in the SAA proof.","marker":"[7]"}],"fun_headline_variants":["Integral LP polyhedron solves two-stage assignment games","Same bipartition in each stage makes vertex cover polynomial","Flow duality proves integrality of assignment game polyhedra","Integrality of assignment games unlocks polynomial solutions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof relies on the assumption that every feasible dual solution can be normalized so that on the first side of the fixed bipartition gamma_v + y_v = 1 and on the second side -gamma_v + y_v = 0 without changing feasibility or the objective, and the vertex-cover application further assumes each stage demands a minimum-cardinality cover.","fun_headline_variants_meta":{"raw":{"variants":["Integral LP polyhedron solves two-stage assignment games","Same bipartition in each stage makes vertex cover polynomial","Flow duality proves integrality of assignment game polyhedra","Integrality of assignment games unlocks polynomial solutions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000375,"raw_usage":{"total_tokens":2005,"prompt_tokens":952,"completion_tokens":1053,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":568,"completion_tokens_details":{"reasoning_tokens":990}},"tokens_in":568,"tokens_out":1053,"duration_ms":10200,"temperature":1.0,"reasoning_tokens":990,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:43:36.769316+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, by exact enumeration over all small two-stage bipartite instances with the same bipartition, whether every extreme point of the multistage LP is integral; a single fractional extreme point would refute Theorem 4, as would a feasible dual solution for which the claimed gamma-normalization strictly worsens the objective.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the assignment game and characterizes its core as the minimum fractional vertex covers of the bipartite graph, the object the paper extends to two stages."},{"cited_title":"Combinatorial Optimization","cited_arxiv_id":null,"evidence_quote":"Supplies the total unimodularity properties that make the dual flow LP's polyhedron integral."},{"cited_title":"Two-stage stochastic stable matching","cited_arxiv_id":null,"evidence_quote":"Provides the two-stage stochastic stable matching framework, including the hardness reduction strategy and the sample average approximation analysis the paper adapts."},{"cited_title":"Multistage vertex cover","cited_arxiv_id":null,"evidence_quote":"Establishes the NP-hardness of multistage vertex cover for two bipartite stages, the baseline that Theorem 5 contrasts with."},{"cited_title":"Kleywegt, Alexander Shapiro, and Tito Homem-de Mello","cited_arxiv_id":null,"evidence_quote":"Introduces the sample average approximation method used for the implicit-distribution setting."},{"cited_title":"Scott Provan and Michael O","cited_arxiv_id":null,"evidence_quote":"Gives the #P-hardness of counting vertex covers used in the hardness reduction for the implicit-distribution problem."},{"cited_title":"Probability Inequalities for sums of Bounded Random Variables , pages 409–426","cited_arxiv_id":null,"evidence_quote":"Supplies the concentration inequality used to bound the probability that the sampled solution is far from optimal in the SAA proof."}],"review_version":1}