Two-stage Stochastic Assignment Games

Laura Sanit\`a; Lucy Verberk

REVIEW 3 major objections 4 minor 15 references

Two-stage Stochastic Assignment Games

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2506.01509 v1 pith:ENAOT2TX submitted 2025-06-02 cs.DM

Laura Sanità , Lucy Verberk This is my paper

classification cs.DM MSC 91A1290C2790C0505C70

keywords assignmentgametwo-stagestochasticoptimizationcoreintegralpolyhedrontotalunimodularitysampleaverageapproximationmultistagevertexcoverbipartitegraph

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

The 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.

The 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.

Referee Report

3 major / 4 minor

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).

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 (3)

[Section 2, Lemma 2, Claim 2] 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 4, Theorem 5] 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 2, Lemma 3] 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.

minor comments (4)

[Section 3, equation (4a)] 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 4, definition of ε] 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 4, proof of Lemma 8] 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 2, paragraph before Lemma 2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the integrality proof is self-contained and the cited external results are independent.

full rationale

The paper's derivation chain is self-contained and no load-bearing step reduces to its own inputs. The explicit-distribution result is a direct LP formulation; integrality is established by dualizing a maximum-flow LP whose constraint matrices are totally unimodular, citing only standard external facts (Kőnig's theorem, Schrijver on TU matrices, Hoeffding's inequality, and #P-hardness of counting vertex covers from Provan and Ball). The SAA analysis in Section 3 explicitly follows the independent prior work of Faenza, Foussoul, and He [4], replacing their bounded-number-of-stable-matchings argument with the paper's own integrality result; no parameter is fitted and no conclusion is imported from the authors' own prior work. The WLOG normalization of the dual γ variables in Lemma 2/Claim 2 and Lemma 7/Claim 4, while flagged by the skeptic as potentially defective when γ_v > 1, is a proof-completeness gap rather than circularity: the paper does not define the target quantity in terms of that normalization, and the normalization is not equivalent to the statement being proved. Likewise, the missing minimum-vertex-cover convention in Theorem 5 is a modeling assumption, not circular reasoning. No self-citation chain appears: references [4], [5], [10], and [13] are external, and the paper's own theorems are never cited to justify themselves. The central claims therefore have independent mathematical content, and any concerns about the normalization argument belong to correctness, not circularity.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper relies on standard results from LP duality, total unimodularity, network flow, bipartite matching, and probability. It introduces no new constants, no fitted parameters, and no new physical or mathematical entities. The only hidden assumption is the minimum-cover convention carried over from the multistage vertex cover literature.

assumptions (6)

standard math The core of an assignment game equals the set of minimum fractional vertex covers (Shapley-Shubik), restated in Section 1.1.
Used to formulate both stages as y_u+y_v≥1, 1^T y=ν(G).
standard math Kőnig's theorem: maximum matching equals minimum vertex cover in bipartite graphs.
Gives ν(G)=τ(G)=τ_f(G), used throughout Sections 2 and 4.
standard math The constraint matrix of a maximum flow LP is totally unimodular, and this property is inherited by its transpose.
Basis for Lemmas 1 and 6.
standard math Hoeffding's inequality for sums of independent bounded random variables.
Used in Lemma 5 to prove the SAA bound.
standard math Counting vertex covers is #P-hard (Provan-Ball), cited from [10].
Used in Theorem 2 hardness reduction.
domain assumption In the multistage vertex cover problem, each stage is required to have a minimum-cardinality vertex cover.
Not stated in Section 4, but necessary for Theorem 5; otherwise the problem is trivial.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Two-stage Stochastic Assignment Games." pith.science (2026). https://pith.science/paper/ENAOT2TX

@misc{pith2026250601509,
  author       = {Pith},
  title        = {Pith review of: Two-stage Stochastic Assignment Games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ENAOT2TX}},
  note         = {Machine review of arXiv:2506.01509}
}

read the original abstract

In this paper, we study a two-stage stochastic version of the assignment game, which is a fundamental cooperative game. Given an initial setting, the set of players may change in the second stage according to some probability distribution, and the goal is to find core solutions that are minimally modified. When the probability distribution is given explicitly, we observe that the problem is polynomial time solvable, as it can be modeled as an LP. More interestingly, we prove that the underlying polyhedron is integral, and exploit this in two ways. First, integrality of the polyhedron allows us to show that the problem can be well approximated when the distribution is unknown, which is a hard setting. Second, we can establish an intimate connection to the well-studied multistage vertex cover problem. Here, it is known that the problem is NP-hard even when there are only 2 stages and the graph in each stage is bipartite. As a byproduct of our result, we can prove that the problem is polynomial-time solvable if the bipartition is the same in each stage.

Figures

Figures reproduced from arXiv: 2506.01509 by the authors.

**Figure 2.** Example of the auxiliary graph for the instance given by [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[4]

Two-stage stochastic stable matching

Yuri Faenza, Ayoub Foussoul, and Chengyue He. Two-stage stochastic stable matching. In Jens Vygen and Jaros law Byrka, editors, Integer Programming and Combinatorial Optimization , pages 154–167, Cham, 2024. Springer Nature Switzerland. 18

work page 2024
[5]

Multistage vertex cover

Till Fluschnik, Rolf Niedermeier, Valentin Rohm, and Philipp Zschoche. Multistage vertex cover. Theory of Computing Systems , 66(2):454–483, Apr 2022

work page 2022
[1]

Online multistage subset maximization problems

Evripidis Bampis, Bruno Escoffier, Kevin Schewior, and Alexandre Teiller. Online multistage subset maximization problems. Algorithmica, 83(8):2374–2399, Aug 2021

work page 2021
[2]

Online 2-stage stable matching

Evripidis Bampis, Bruno Escoffier, and Paul Youssef. Online 2-stage stable matching. Discrete Applied Mathematics, 341:394–405, 2023

work page 2023
[3]

Sampling bounds for stochastic optimization

Moses Charikar, Chandra Chekuri, and Martin P´ al. Sampling bounds for stochastic optimization. In Chandra Chekuri, Klaus Jansen, Jos´ e D. P. Rolim, and Luca Trevisan, editors, Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 257–269, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg

work page 2005
[6]

Changing bases: Multistage optimization for ma- troids and matchings

Anupam Gupta, Kunal Talwar, and Udi Wieder. Changing bases: Multistage optimization for ma- troids and matchings. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming, pages 563–575, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg

work page 2014
[7]

Probability Inequalities for sums of Bounded Random Variables , pages 409–426

Wassily Hoeffding. Probability Inequalities for sums of Bounded Random Variables , pages 409–426. Springer New York, New York, NY, 1994

work page 1994
[8]

Kleywegt, Alexander Shapiro, and Tito Homem-de Mello

Anton J. Kleywegt, Alexander Shapiro, and Tito Homem-de Mello. The sample average approxi- mation method for stochastic discrete optimization. SIAM Journal on Optimization , 12(2):479–502, 2002

work page 2002

Show all 15 references

[9]

Maximum matching in the online batch-arrival model

Euiwoong Lee and Sahil Singla. Maximum matching in the online batch-arrival model. ACM Trans. Algorithms, 16(4), July 2020

2020
[10]

Scott Provan and Michael O

J. Scott Provan and Michael O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal on Computing , 12(4):777–788, 1983

1983
[11]

Ravi and Amitabh Sinha

R. Ravi and Amitabh Sinha. Hedging uncertainty: Approximation algorithms for stochastic opti- mization problems. Mathematical Programming, 108(1):97–114, Aug 2006

2006
[12]

Combinatorial Optimization

Alexander Schrijver. Combinatorial Optimization . Springer Berlin, Heidelberg, 2003

2003
[13]

L. S. Shapley and M. Shubik. The assignment game i: The core. International Journal of Game Theory, 1(1):111–130, 12 1971

1971
[14]

Chaitanya Swamy and David B. Shmoys. The sample average approximation method for 2-stage stochastic optimization. Unpublished manuscript
[15]

Chaitanya Swamy and David B. Shmoys. Sampling-based approximation algorithms for multistage stochastic optimization. SIAM Journal on Computing , 41(4):975–1004, 2012. 19

2012

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [4]

Two-stage stochastic stable matching

Yuri Faenza, Ayoub Foussoul, and Chengyue He. Two-stage stochastic stable matching. In Jens Vygen and Jaros law Byrka, editors, Integer Programming and Combinatorial Optimization , pages 154–167, Cham, 2024. Springer Nature Switzerland. 18

work page 2024

[2] [5]

Multistage vertex cover

Till Fluschnik, Rolf Niedermeier, Valentin Rohm, and Philipp Zschoche. Multistage vertex cover. Theory of Computing Systems , 66(2):454–483, Apr 2022

work page 2022

[3] [1]

Online multistage subset maximization problems

Evripidis Bampis, Bruno Escoffier, Kevin Schewior, and Alexandre Teiller. Online multistage subset maximization problems. Algorithmica, 83(8):2374–2399, Aug 2021

work page 2021

[4] [2]

Online 2-stage stable matching

Evripidis Bampis, Bruno Escoffier, and Paul Youssef. Online 2-stage stable matching. Discrete Applied Mathematics, 341:394–405, 2023

work page 2023

[5] [3]

Sampling bounds for stochastic optimization

Moses Charikar, Chandra Chekuri, and Martin P´ al. Sampling bounds for stochastic optimization. In Chandra Chekuri, Klaus Jansen, Jos´ e D. P. Rolim, and Luca Trevisan, editors, Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 257–269, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg

work page 2005

[6] [6]

Changing bases: Multistage optimization for ma- troids and matchings

Anupam Gupta, Kunal Talwar, and Udi Wieder. Changing bases: Multistage optimization for ma- troids and matchings. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming, pages 563–575, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg

work page 2014

[7] [7]

Probability Inequalities for sums of Bounded Random Variables , pages 409–426

Wassily Hoeffding. Probability Inequalities for sums of Bounded Random Variables , pages 409–426. Springer New York, New York, NY, 1994

work page 1994

[8] [8]

Kleywegt, Alexander Shapiro, and Tito Homem-de Mello

Anton J. Kleywegt, Alexander Shapiro, and Tito Homem-de Mello. The sample average approxi- mation method for stochastic discrete optimization. SIAM Journal on Optimization , 12(2):479–502, 2002

work page 2002