{"id":"745b2c4e-1b72-4c8f-bdea-647771ceaab2","arxiv_id":"2505.06005","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper gives exact polynomial-time algorithms for Second Price Matching on (d,2)-regular graphs when d≥4, a 9/10 approximation for d=3, and settles the approximability of a new perfect-matching variant at (1-1/e).","lead":"This paper studies an auction matching problem where a good earns profit only when a second, unmatched bidder also wants it. It gives exact polynomial-time algorithms for regular graphs where each bidder bids on exactly two goods, and a tight approximation for a new variant requiring all goods to be matched.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's asserted cycle/forest decomposition of H is unproved; a theta-shaped 2-core would invalidate the path cover and the resulting 9/10 guarantee.","rationale":"I read the central claim as: degree-constrained second-price matching is tractable on (d,2)-regular graphs. The d>=4 half is convincing: the Hall arguments in Section 2.1.2 are degree-counting arguments that work (the right-side bound deg(b)<=2 gives |N(X)|>=|X| for every X subset of A). The d=3 half, however, is only as strong as Theorem 4, and Theorem 4 depends on an asserted decomposition of H into cycles plus forest. I was unable to find in Claims 1–4 a derivation of that decomposition; the claims begin after it is assumed. Because a (3,2)-regular bipartite graph can have a theta-shaped 2-core that is compatible with all listed degrees, and the only stated use of maximality of M' is to prohibit adjacent unmatched A-vertices, the decomposition is not justified. This is the same weakness the reader identified, so I agree. A separate, secondary issue: in the proof of Theorem 2 the inequality '3OPT_VC >= m, i.e., n/OPT_VC <= 1/2' reverses the bound; the correct implication is n/OPT_VC <= 2, which changes the hardness constant from 293/297 to at most 593/594, though APX-hardness itself is not affected. I would keep the CONDITIONAL verdict: the contribution is substantial and likely correct, but the d=3 structural lemma must be proved (or a counterexample found) before the stated claims are accepted.","tokens_in":16884,"tokens_out":32420,"duration_ms":408635,"concrete_test":"Exhaustively generate all (3,2)-regular bipartite instances with |A|=n<=12 (equivalently all 3-regular multigraphs G' on n vertices), run the blossom algorithm to get a maximum matching M', build H = G[B\\B'], repeatedly delete degree-1 vertices, and test whether the remaining 2-core is a disjoint union of even cycles. If any instance yields a theta or other non-cycle 2-core, Theorem 4's construction as written fails and Theorem 3(1) needs a new d=3 argument. If no small counterexample appears, independently prove the missing lemma: show from maximality of M' that no two degree-3 vertices of L = G' minus M' can lie in the same 2-core component, or identify the extra condition required.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 4 (Section 2.1.1) is built on the assertion that, after deleting B', H can be partitioned into vertex-disjoint even cycles and a forest F. This is exactly the statement that the 2-core of H (equivalently of L = G' minus M') is a disjoint union of cycles. The degree bounds alone do not imply it: in H, vertices in A\\N(B') have degree 3 while vertices in B\\B' have degree 2, so a 2-core component may be a theta graph—two degree-3 A-vertices joined by three internally disjoint paths. The maximality of M' forbids only an edge of G' connecting two vertices of A\\N(B'); it does not, as argued, rule out a longer theta. Claims 1–4 prove properties of the leaf-peeling process assuming the cycle/forest decomposition already exists, and Claim 3 ('every a in A belongs either to exactly one cycle or exactly one path') is precisely what would fail if a theta component is present. In that case the constructed matching M need not be A-perfect, so the claimed value n/2 + nu(G') is not established. Since the 9/10-approximation in Theorem 3(1) is obtained entirely from Theorem 4, this unproved structural lemma is the load-bearing step of the d=3 result. The lemma may be true, but the text supplies no proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the Second Price Matching problem (2PM) and its perfect-matching variant (2PPM) on degree-constrained bipartite inputs. The main algorithmic claims are: for inputs in which every bidder has degree 2 and every good has degree d, there is an exact polynomial-time algorithm for both 2PM and 2PPM when d≥4; and for d=3, there is an algorithm that solves 2PPM exactly with optimal value n/2+ν(G′), where G′ is an auxiliary graph on the goods, which in turn yields a 9/10 approximation to 2PM. For general 2PPM, the paper gives a (1−1/e)-approximation via submodular maximization over a matroid and proves that this ratio is best possible unless a corresponding Max k-Cover hardness assumption holds. It also proves an APX-hardness result for degree-constrained 2PPM with a stated inapproximability factor of 293/297, and an exact polynomial-time algorithm for the case deg(a)=2 for all a∈A. The proofs combine maximum matching in non-bipartite graphs via the blossom algorithm, the Tutte-Berge formula, Hall's theorem, and a gap-preserving reduction from Max k-Cover.","tokens_in":17092,"tokens_out":43136,"duration_ms":463651,"significance":"If all results were fully established, they would constitute a significant advance: the d≥4 exact algorithm for 2PM and 2PPM is a clean and convincing result, and the (1−1/e) tight characterization of general 2PPM via matroid duality is elegant and valuable. The 9/10 approximation for (3,2)-regular inputs would markedly improve the known 1/2 upper bound for 2PM on these inputs. Strengths of the paper include the explicit auxiliary graph construction, the parameter-free use of the Tutte-Berge formula in the lower bound, the submodularity reformulation, and the explicit gap-preserving reduction for the general 2PPM hardness. However, the d=3 exactness proof rests on a structural decomposition that is asserted without proof and appears inconsistent with the paper's own tight example, and the proof of Theorem 2 contains an arithmetically incorrect inequality. These are load-bearing issues for two of the paper's headline claims, so the paper is not acceptable in its present form.","major_comments":[{"comment":"The proof begins by asserting that H can be partitioned into vertex-disjoint even cycles and a forest F, and the rest of the construction—the leaf-removal process, Claims 1–4, the path decomposition P_j, and the construction of the A-perfect matching M—depends on this decomposition. The only justification offered is that the maximum degree in H is 3, which is not sufficient: a theta graph has maximum degree 3 and is not a disjoint union of vertex-disjoint cycles plus a forest. More seriously, the asserted decomposition is inconsistent with the authors' own tight example for Claim 6. If G′ is the 10-vertex 3-regular multigraph with ν(G′)=4 and M′ is a maximum matching, then H has exactly two vertices in A of degree 3, all remaining vertices in A of degree 2, and all vertices in B\\B′ of degree 2. Thus H has no leaves and its 2-core is the whole graph; it contains a component that is not a cycle and cannot be a forest. For such an input the path/cycle construction is not defined. Since Theorem 4 is used to prove Proposition 5 and then the 9/10 guarantee in Theorem 6, the d=3 part of Theorem 3 is not proved as written. The authors need either a proof of a correct structural statement about the 2-core of H under the maximality of M′, or a different argument for the formula n/2+ν(G′).","section":"§2.1.1, proof of Theorem 4"},{"comment":"Independently of the decomposition issue, the proof of Claim 2 asserts that an internal vertex a of a path P removed from F′ has degree 3 in H because its degree in P is 2. This is not justified: if a∈N(B′), then a has degree 2 in H and it can still have degree 2 in P. The subsequent conclusion that a lies in A\\N(B′) is used to show that each leaf b of the remaining forest has one neighbor in N(B′) and one in A\\N(B′), and this is exactly what the counting argument in Claim 5 needs. The proof requires an additional reason why such an internal vertex cannot belong to N(B′); none is supplied.","section":"§2.1.1, Claim 2"},{"comment":"The derivation of the inapproximability ratio 293/297 contains an arithmetic error. The text states: 'Since G is 3-regular, we have 3n = 2m and 3OPT_VC ≥ m, i.e., n/OPT_VC ≤ 1/2.' From 3n=2m and 3OPT_VC≥m one obtains OPT_VC≥n/2, hence n/OPT_VC≤2, not ≤1/2. Consequently the upper bound in inequality (9), namely |U|/OPT_VC ≤ 7/4(1−α)+α, does not follow from the stated hypotheses, and the conclusion α≤293/297 is not established by the displayed argument. The reduction may be salvageable, but the proof of Theorem 2 must be reworked with a correct bound before the stated constant can be accepted.","section":"§3.2, proof of Theorem 2"}],"minor_comments":[{"comment":"The sentence 'a leaf x of F must belong to exactly one of the cycles C_i' is confusing under the claimed vertex-disjoint partition of H into cycles plus a forest; a leaf of the forest cannot also belong to a cycle. This sentence appears to be a typo or a sign that the intended structure is different and should be clarified.","section":"§2.1.1, paragraph after defining F"},{"comment":"The hardness proof for general 2PPM should state precisely which hardness variant of Max k-Cover is being cited from [10]. If Feige's (1−1/e+ε) inapproximability is stated under a quasi-polynomial-time assumption, then the phrase 'unless P=NP' in Theorem 1 needs a justification or a more careful qualification.","section":"§2.2 and §3.1"},{"comment":"The Hall argument for the multigraph G′′ is terse. Since G′′ may have parallel edges, the text should explicitly say that degrees are counted with multiplicity and that M′′ is a matching in the multigraph, so that each vertex in N(B′) is incident to at most one edge of M′′. The current proof is correct but would benefit from this clarification.","section":"§2.1.2, proof of Theorem 7"},{"comment":"There are several typos and formatting glitches: 'lto' in the proof of Claim 2, '˝' in Section 2.3, 'B{a∈A' in Definition 1, and inconsistent spacing in 'OPTV C'. These should be corrected in a revision.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The d=3 result and the 9/10 ratio are the paper's headline, and the current proof of that part has a load-bearing gap that appears to be more than a missing detail. The d≥4 exact algorithm and the general 2PPM submodular/hardness results are substantially cleaner and would be publishable on their own if the paper were restructured around them. I found no circular reasoning and no problematic citation pattern; the issue is purely the correctness of two proofs. I would encourage a thorough revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the 2PPM variant and the d≥4 algorithms are real contributions, but the d=3 results rest on a structural claim that is not proven and is probably false as stated, so the paper is not ready as is.\n\nWhat is good. The general 2PPM story is clean: the Max k-Cover reduction with private and dummy nodes gives the (1−1/e) hardness, and the transversal matroid/submodular reformulation gives the matching upper bound. That part checks out. The exact algorithm for (d,2)-regular graphs with d≥4 is also sound—the Hall arguments work by degree counting, including with parallel edges, and the perfect matching step after removing S is correct. The lower bound on maximum matchings in 3-regular multigraphs (Claim 6) is correct and gives the 9n/10 bound once the exact d=3 formula is established.\n\nThe problem is Theorem 4. The proof asserts that H can be partitioned into vertex-disjoint even cycles plus a forest F. But H has no leaves, and the vertices in A\\N(B′) have degree 3. If the 2-core of H is a theta graph—two degree-3 A-vertices joined by three internally disjoint paths—no such vertex-disjoint cycle decomposition exists. Maximality of M′ only forbids a B-vertex adjacent to two vertices in A\\N(B′); it does not forbid longer theta structures. The text gives no argument excluding them. Since the matching construction and the count N(S)=n/2+ν(G′) both depend on this decomposition, the exact d=3 result and the 9/10 approximation are unsupported. This is a load-bearing gap, not a missing minor detail.\n\nThere is also a numerical error in Theorem 2's proof: for 3-regular vertex cover, OPT_VC ≥ n/2, so n/OPT_VC ≤ 2, not 1/2. Correcting it yields the stronger constant 593/594, so the theorem may be recoverable, but the stated derivation of 293/297 is wrong.\n\nWho this is for: people working on matching algorithms, auction revenue, and submodular maximization will find the general 2PPM results and the d≥4 algorithms valuable. I would not cite the d=3 claims until the structural issue is resolved. I would send this to a serious referee, with the message that the d=3 section needs a real proof, not a patch.","headline":"Solid general 2PPM results and d≥4 exact algorithms, but the d=3 proof rests on an unproved (and likely false) cycle/forest decomposition, plus a numerical error in the APX-hardness constant.","tokens_in":17710,"tokens_out":33471,"would_cite":true,"duration_ms":350760,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C70","68Q17","68W25","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"When every bidder bids on exactly two goods, second-price matching is 9/10-approximable for degree 3 and exact for higher degree.","keywords":["second-price matching","perfect matching variant","(d,2)-regular graphs","approximation algorithms","Tutte-Berge formula","submodular maximization","matroid constraint","APX-hardness"],"falsifier":"Take any (3,2)-regular instance and compute $\\nu(G')$; if the optimal 2PPM value ever differs from $|A|/2+\\nu(G')$, Theorem 4 fails. More directly, search for a (3,2)-regular input whose leftover graph $H$ contains a 2-core with a vertex of degree 3, since the paper's decomposition requires the 2-core to be a disjoint union of even cycles; the leaf-removal argument would break on that instance.","tokens_in":16628,"feed_emoji":"🎯","tokens_out":12401,"duration_ms":99823,"temperature":0.7,"pith_summary":"Second-price matching asks for a set of goods $W$ and a set of bidders $S$ such that the bidders not in $S$ can be matched to all goods in $W$, and profit is the number of goods that also have a neighbor in $S$. In general the problem is APX-hard and the best known guarantee is $1/2$. This paper claims that when every bidder bids on exactly two goods and every good is bid on by exactly $d$ bidders, the structure changes completely: for $d\\ge 4$ both second-price matching and its perfect-matching variant are solvable exactly in polynomial time, and for $d=3$ the perfect variant is exact while the original admits a $9/10$ approximation. It also proves that the perfect variant is, in general, hard to approximate beyond $1-1/e$ and that the matching $1-1/e$ upper bound is achieved by submodular maximization over a matroid. If the claims hold, degree regularity is a dividing line between computational intractability and polynomial-time solvability for this auction mechanism.","feed_headline":"With two bids per bidder, second-price matching is tractable","feed_subtitle":"When every good has degree at least 4, both variants solve exactly; degree 3 gives a 9/10 approximation.","key_machinery":"The load-bearing construction is the auxiliary graph $G'$: since every bidder $b$ has degree 2, it connects exactly two goods, so each bidder becomes the edge between those two goods in $G'$. A matching in $G'$ selects a set $B'$ of bidders whose two neighbors are both profitable; because the matching bidders are disjoint, those goods can still be matched by the remaining bidders. The algorithm finds a maximum matching $M'$ in $G'$ with the blossom algorithm, removes the corresponding bidders, and decomposes what remains into even cycles and a forest; paths between leaves are then harvested, and the leaf-removal claims guarantee every good is covered exactly once. For the $9/10$ bound on $d=3$, the Tutte-Berge formula is applied to the 3-regular auxiliary graph to prove $\\nu(G')\\ge 2|A|/5$, which yields the target ratio.","core_discovery":"The central discovery is that the hardness of second-price matching disappears when the bidder side is 2-regular. The paper's main theorem states that for input graphs with $\\deg(a)=d$ for every good $a$ and $\\deg(b)=2$ for every bidder $b$: if $d=3$, a polynomial-time algorithm yields a $9/10$-approximation for 2PM and solves 2PPM exactly; if $d\\ge 4$, the algorithm solves both 2PM and 2PPM exactly, with optimal value $n=|A|$. The argument builds an auxiliary graph whose vertices are goods and whose edges are bidders, takes a maximum matching in it, and then augments the chosen bidder set through a cycle-and-path decomposition of the remaining graph. For the perfect variant in the $d=3$ case, the optimal value is characterized by the formula $n/2+\\nu(G')$, where $\\nu(G')$ is the maximum matching size in the auxiliary graph.","pith_inferences":["The auxiliary-graph reduction may extend to bidders with a fixed number $t>2$ of bids by replacing each bidder with a small gadget in a non-bipartite graph; if so, the tractability boundary would be a function of the bidder's bid count rather than its exact value.","Since the $d=3$ optimum is pinned by the maximum matching number of a 3-regular multigraph, any improvement beyond $9/10$ would have to come from a sharper matching lower bound, not from auction-specific reasoning.","Because the general $1-1/e$ hardness is coverage-based, the regular-degree cases identified here are a rare natural class where the generic submodular hardness does not apply; similar one-sided regularity assumptions may tame other allocation problems.","A direct numerical check on random $(3,2)$-regular instances should show the greedy submodular maximizer trailing the new algorithm on the 10-good tight multigraph; that example is the test case that pins the $9/10$ ratio."],"forward_implications":["For $(d,2)$-regular inputs with $d\\ge 4$, both 2PM and 2PPM are solved exactly in polynomial time, so the optimal value is always $|A|$; every good can be made profitable even when the matching must be perfect.","For $(3,2)$-regular inputs, 2PPM is solved exactly and 2PM is approximated within $9/10$ in polynomial time, improving the previous $1/2$ guarantee on this class.","In general, 2PPM cannot be approximated within $1-1/e+\\varepsilon$ unless P=NP, and the submodular-maximization algorithm reaches the matching $1-1/e$ guarantee, so the perfect variant is no easier than max $k$-cover.","2PPM remains APX-hard even with goods of degree 2 or 3 and bidders of degree at most 4, showing that bounded degree alone is not enough; one side must be 2-regular.","When all goods have degree at least $d_A$ and all bidders at most $d_B$, every feasible perfect allocation is a $(1-d_B/d_A)$-approximation, which beats the generic bounds when the gap is large."],"supporting_citations":[{"why":"introduces 2PM, proves APX-hardness of the general problem, and supplies the $1/2$-approximation baseline that this paper improves.","marker":"[4]"},{"why":"gives the blossom algorithm for maximum non-bipartite matching and the Tutte-Berge formula used to analyze the $(3,2)$-regular case.","marker":"[19]"},{"why":"provides the $1-1/e$ inapproximability of max $k$-cover used in the gap-preserving reduction of Theorem 1.","marker":"[10]"},{"why":"provides the hardness of approximating vertex cover on 3-regular graphs from which the degree-constrained APX-hardness of 2PPM is derived.","marker":"[8]"},{"why":"supplies the $1-1/e$-approximation for monotone submodular maximization over a matroid, matching the upper bound for general 2PPM.","marker":"[6]"},{"why":"gives the lower bound of $2|V|/5$ on the maximum matching size in 3-regular multigraphs that Claim 6 adapts for the $9/10$ ratio.","marker":"[16]"}],"fun_headline_variants":["Second-price matching: bidder degree 2 yields exact or 9/10","Bidder degree 2 makes second-price matching tractable","Exact second-price matching when goods have degree ≥4","9/10 approximation for degree-constrained second-price matching"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For $d=3$, the proof relies on the assertion that after removing the bidders selected by a maximum matching of the auxiliary graph, the leftover graph splits into vertex-disjoint even cycles and paths that cover every good exactly once; if some leftover graph resisted that decomposition, the construction would not be guaranteed to cover all goods.","fun_headline_variants_meta":{"raw":{"variants":["Second-price matching: bidder degree 2 yields exact or 9/10","Bidder degree 2 makes second-price matching tractable","Exact second-price matching when goods have degree ≥4","9/10 approximation for degree-constrained second-price matching"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001048,"raw_usage":{"total_tokens":4441,"prompt_tokens":1022,"completion_tokens":3419,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":638,"completion_tokens_details":{"reasoning_tokens":3346}},"tokens_in":638,"tokens_out":3419,"duration_ms":22765,"temperature":1.0,"reasoning_tokens":3346,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:57:14.013949+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take any (3,2)-regular instance and compute $\\nu(G')$; if the optimal 2PPM value ever differs from $|A|/2+\\nu(G')$, Theorem 4 fails. More directly, search for a (3,2)-regular input whose leftover graph $H$ contains a 2-core with a vertex of degree 3, since the paper's decomposition requires the 2-core to be a disjoint union of even cycles; the leaf-removal argument would break on that instance.","supporting_citations":[{"cited_title":"Karlin, and C","cited_arxiv_id":null,"evidence_quote":"introduces 2PM, proves APX-hardness of the general problem, and supplies the $1/2$-approximation baseline that this paper improves."},{"cited_title":"Combinatorial Optimization: Polyhedra and Efficiency","cited_arxiv_id":null,"evidence_quote":"gives the blossom algorithm for maximum non-bipartite matching and the Tutte-Berge formula used to analyze the $(3,2)$-regular case."},{"cited_title":"A threshold of ln n for approximating set cover","cited_arxiv_id":null,"evidence_quote":"provides the $1-1/e$ inapproximability of max $k$-cover used in the gap-preserving reduction of Theorem 1."},{"cited_title":"Complexity of approximating bounded variants of opti- mization problems","cited_arxiv_id":null,"evidence_quote":"provides the hardness of approximating vertex cover on 3-regular graphs from which the degree-constrained APX-hardness of 2PPM is derived."},{"cited_title":"Maximizing a submodular set function subject to a matroid constraint","cited_arxiv_id":null,"evidence_quote":"supplies the $1-1/e$-approximation for monotone submodular maximization over a matroid, matching the upper bound for general 2PPM."},{"cited_title":"3-regular graph maximum matching.https://math.stackexchange","cited_arxiv_id":null,"evidence_quote":"gives the lower bound of $2|V|/5$ on the maximum matching size in 3-regular multigraphs that Claim 6 adapts for the $9/10$ ratio."}],"review_version":1}