{"id":"f4798b9b-d588-4ae9-a900-a78dcd085db8","arxiv_id":"2412.00301","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper gives epoch explore-then-commit algorithms with regret bounds for utilitarian-optimal and maximin stable matching in two-sided bandit markets, but the maximin algorithm appears to solve a different objective.","lead":"This paper proposes two bandit learning algorithms, one targeting utilitarian-optimal stable matching and one targeting Rawlsian (maximin) stable matching, when both sides of a matching market have unknown preferences. It reports regret bounds and simulations, but a load-bearing gap in the maximin algorithm makes the Rawlsian claim unsupported.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5's Γ bound does not apply to minima across the two sides; a 2x2 example with errors below Γ/2 flips the maximin matching, so Theorem 2's Rawlsian regret proof is invalid.","rationale":"The most load-bearing flaw is not the side-restriction of Algorithm 3 (though that is also a real gap); it is the incorrect use of the cross-side gap Γ in Lemma 5. The proof needs the minimum rewards of any two stable matchings to differ by at least Γ, but Γ only separates utilities within the same side. Since the Rawlsian value R(m) is a minimum over the union of agent and arm utilities, the gap between an agent-side minimizer and an arm-side minimizer can be arbitrarily small even when Γ is large. The 2x2 counterexample demonstrates this: with true utilities as above, Γ=49 but the two stable matchings have Rawlsian values 1 and 10, and a perturbation of 10 (< 24.5) reverses their order under the estimated profile, so any algorithm returning the estimated-profile maximin would output M1 with true value 1 instead of the optimal 10. This directly contradicts Lemma 5, and therefore invalidates Theorem 2's regret bound and Theorem 4's sample complexity. The reader's Algorithm 3 concern is real but secondary: even if Algorithm 3 were replaced by a correct global maximin subroutine, the analysis would still fail. The verdict should remain REJECT.","tokens_in":16113,"tokens_out":15933,"duration_ms":131560,"concrete_test":"Use exhaustive search to compute the global maximin stable matching for the perturbed 2x2 instance: true utilities as above, agent estimates U_{a1,b2}=0, U_{a2,b1}=0, and all other estimates equal to true values. If the global maximin with respect to the estimates is M1 (min value 1) while the true maximin is M2 (min value 10), then Lemma 5's condition |error| < Γ/2 is satisfied but the conclusion fails, disproving the lemma.","verdict_should_be":"REJECT","load_bearing_attack":"Lemma 5 (and hence Theorem 2 and Theorem 4) relies on the claim that if all estimates deviate from true utilities by less than Γ/2, then the estimated-profile maximin matching has the true optimal Rawlsian value. The proof asserts that whenever R(m̂) < R(m*), the gap is at least Γ: 'by construction of Γ, R(m̂)+Γ ≤ R(m*)'. But Γ = min{Γ_a, Γ_b} only lower-bounds differences between two utilities on the same side (agent-side values or arm-side values); R(m) is the minimum over the union of both sides. The distance between an agent's utility and an arm's utility is not controlled by Γ. Concretely, with utilities U_{a1,b1}=100, U_{a1,b2}=10, U_{a2,b1}=10, U_{a2,b2}=100, U_{b1,a1}=1, U_{b1,a2}=50, U_{b2,a1}=50, U_{b2,a2}=1, the two stable matchings are M1={(a1,b1),(a2,b2)} with min=1 and M2={(a1,b2),(a2,b1)} with min=10. Here Γ = min(90,49)=49, yet R(M2)-R(M1)=9 < Γ. Perturb U_{a1,b2} and U_{a2,b1} from 10 to 0 (errors 10 < Γ/2=24.5); the estimated-profile maximin is M1 (min=1 vs 0), so the algorithm outputs M1 whose true value is 1, while the true maximin is M2 with value 10. Lemma 5 is false. This invalidates Theorem 2's regret bound and Theorem 4's sample complexity, independently of whether Algorithm 3 computes the global maximin.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper considers a two-sided matching market with N agents and N arms in which the cardinal utilities of both sides are unknown and are learned from stochastic rewards. The authors study two welfarist objectives among stable matchings: maximizing total utilitarian welfare and maximizing the minimum (Rawlsian) utility over all participants. They propose two epoch-based Explore-Then-Commit algorithms (Algorithm 2 for utilitarian, Algorithm 4 for maximin), relying on known-preference subroutines (Algorithm 1 for utilitarian-optimal and Algorithm 3 for maximin stable matchings). They claim regret bounds of O(N^2 log T log log T + N^3 log T + 2^{l1}N) and O(N log T log log T + 4N^2 log T + 2^{l1}), respectively, and PAC sample complexity bounds O(N^2/β^2 log(N^2/α)) and O(N^2/Γ^2 log(N^2/α)), supported by simulations on random preference profiles.","tokens_in":16448,"tokens_out":9779,"duration_ms":82053,"significance":"The welfarist framing is timely and, if the results were correct, the bounds would be the first regret guarantees for utilitarian and Rawlsian objectives in two-sided unknown-preference matching markets; the distinction between within-side and cross-side preference gaps is a reasonable analytical idea. The paper's utilitarian arm contains a credible epoch-ETC structure and a provable error-probability argument conditional on Algorithm 1. However, the Rawlsian half is not established: Lemma 5 is false as stated, Algorithm 3 is not shown to compute the global maximin stable matching, and the error-event analysis in Lemma 6 does not account for non-unique maximizers. Because Theorems 2 and 4 rely on these components, the advertised Rawlsian results cannot be accepted. The paper provides no machine-checked proofs or code release; the experiments are illustrative and lack baselines.","major_comments":[{"comment":"Lemma 5 in Section 4.3 is false. The proof's key step is the assertion that if R(\\hat m) < R(m*), then R(\\hat m) + Γ ≤ R(m*) 'by construction of Γ'. But Γ = min{Γ_a, Γ_b} lower-bounds the distance between two utilities on the same side of the market, whereas R(m) is the minimum over the union of both sides; the gap between an agent-side utility and an arm-side utility is not controlled by Γ. A concrete instance with N = 2 shows the failure: set (μ_{a1,b1}, μ_{a1,b2}) = (100, 10), (μ_{a2,b1}, μ_{a2,b2}) = (10, 100), (μ_{b1,a1}, μ_{b1,a2}) = (1, 50), and (μ_{b2,a1}, μ_{b2,a2}) = (50, 1). The two stable matchings are M1 = {(a1,b1), (a2,b2)} with R(M1) = 1 and M2 = {(a1,b2), (a2,b1)} with R(M2) = 10, so Γ = min(90, 49) = 49 but R(M2) - R(M1) = 9 < Γ. If the estimates of μ_{a1,b2} and μ_{a2,b1} are both changed from 10 to 0, all estimate errors are below Γ/2, yet the estimated-profile maximin matching becomes M1, whose true Rawlsian value is 1 rather than 10. Thus the hypotheses of Lemma 5 can hold while its conclusion fails. Lemma 5 is used to prove Lemma 6, Theorem 2, and Theorem 4, so the Rawlsian regret and sample-complexity claims are not supported.","section":"Section 4.3, Lemma 5"},{"comment":"Algorithm 3 is introduced as computing the arm-side maximin stable matching, but Definition 4.1 defines the maximin stable matching as maximizing the minimum over all agents and arms. No theorem or proof establishes that the arm-side maximizer has the global maximin value, or that combining arm-side and agent-side variants yields the global maximizer. Theorem 2 asserts that Algorithm 4 computes the maximin stable matching, and the analysis in Lemma 5 simply assumes that the matching output by Algorithm 3 maximizes \\hat R over the stable set. This is a load-bearing gap: without such a proof, even a correct perturbation bound would not connect the algorithm's output to the stated Rawlsian objective.","section":"Section 4.1, Algorithm 3"},{"comment":"Lemma 6 defines E_l as the event that the matching returned in epoch l differs from m*. Lemma 5, even if repaired to guarantee value optimality, does not imply uniqueness of the maximin stable matching. If several stable matchings attain the maximin value, the estimated-profile maximizer can differ from a fixed m* while still having optimal true value; the claimed probability bound P(E_l) ≤ 4N^2 exp(-c1 l log(l) Γ^2 / 8) then does not follow. For the regret analysis only the probability that the returned matching's true Rawlsian value is suboptimal is needed, and the lemma should be restated accordingly.","section":"Section 4.3, Lemma 6"}],"minor_comments":[{"comment":"There are numerous typos, including 'application' for 'applications' in Section 1, 'mimimum' in Section 4.1, 'optiaml' in Section 6, and 'decompostion' in the proof of Lemma 3 in Appendix A.1.","section":"Throughout"},{"comment":"The definition of the cross-side minimum preference gap is hard to parse: the displayed formula for Γ_a should explicitly state that the minimization is over ordered quadruples with non-zero utility difference and should show the absolute value unambiguously; the current notation does not make the index ranges and the absolute value clear.","section":"Section 4.3"},{"comment":"In Theorem 3, the quantity β is used in the sample complexity bound but is not defined in the statement; it should be β = min{δ/(4N), Δ_a/2, Δ_b/2} as introduced in Lemma 4.","section":"Section 3.3, Theorem 3"},{"comment":"The proof of Theorem 4 twice refers to the target as 'the utilitarian-optimal stable matching'; it should refer to the maximin stable matching.","section":"Appendix C, proof of Theorem 4"},{"comment":"The pseudocode of Algorithm 3 is incomplete: the break-matching operation is not specified, ties among multiple minimum-reward arms are not addressed, and the stopping condition in line 3 ('no arm with reward R(m_{i+1})') is unclear.","section":"Algorithm 3"}],"recommendation":"reject","confidential_remarks":"The stress-test concern lands: Lemma 5 is false under the paper's own assumptions, and the gap is central to Theorems 2 and 4. I also see no proof that the arm-side maximin subroutine computes the global maximin object required by Definition 4.1. The utilitarian half may be salvageable as a separate contribution, but the Rawlsian contribution as written cannot be repaired by a local fix. I do not see any concern about prior-work disclosure or fit with the journal's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a worthwhile problem — two-sided unknown preferences plus welfarist objectives — and the utilitarian epoch-ETC analysis is mostly credible. The Rawlsian contribution, which the title promises, is not. Lemma 5 is false as stated, so Theorem 2 and Theorem 4 do not go through.\n\nWhat is new: prior bandit-matching work mostly optimizes for one side of the market (agent-optimal or arm-optimal). Studying utilitarian and maximin stable matchings on both sides with unknown preferences is a real gap, and the paper correctly notes that DA's one-sided optimality is unfair. The utilitarian algorithm via rotations and min-cut is classical, and the regret decomposition using within-side gaps is standard but competently executed. The sample-complexity appendix is a useful addition.\n\nSoft spots, in order of severity:\n\n1. Lemma 5. The proof argues that if R(hat m) < R(m*), then R(hat m) + Gamma <= R(m*) \"by construction of Gamma\". But Gamma only lower-bounds differences between two agent-side utilities or two arm-side utilities. R(m) is the minimum over the union of both sides, so the gap between a candidate's worst arm value and the optimum's worst agent value is not controlled by Gamma. The stress-test 2x2 example is correct: Gamma = 49, yet the two stable matchings have R values 1 and 10 with gap 9 < Gamma; perturbing two agent utilities by 10 (< Gamma/2) flips the estimated maximin from the true optimum to the worse matching. Lemma 5 is genuinely false, and Theorem 2's regret bound and Theorem 4's sample complexity fall with it.\n\n2. Algorithm 3. It is explicitly the arm-side maximin procedure. The paper asserts without proof that this gives the global maximin of Definition 4.1. A symmetric agent-side variant plus an argument that one of them achieves the global optimum might fix this, but that argument is absent.\n\n3. Algorithm 1's correctness is asserted from Irving et al. with no proof of the cardinal-utility adaptation. This matters less if Lemma 2 is accepted, but the whole utilitarian half depends on the min-cut subroutine being correct.\n\nThe experiments are small but honest; they do not rescue the theory.\n\nWho this is for: people working on bandit learning in matching markets. The utilitarian half might be salvageable and citeable after a real proof pass. The Rawlsian half needs a new algorithm or a corrected analysis. I would send this to a serious referee — the question is new and the flaws are identifiable — but I would expect a reject-and-resubmit, not acceptance.","headline":"Fresh welfarist framing for bandit matching, but the Rawlsian half rests on a false lemma; the utilitarian half is plausible but under-proved.","tokens_in":17016,"tokens_out":3747,"would_cite":false,"duration_ms":35757,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B68","68W27","62L05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that both the utilitarian-optimal and the maximin stable matching can be learned when neither side knows its preferences, with regret that is nearly logarithmic in time.","keywords":["two-sided matching markets","multi-armed bandits","utilitarian welfare","Rawlsian welfare","maximin stable matching","explore-then-commit","regret bounds","preference learning"],"falsifier":"Enumerate all stable matchings of a small market (e.g., $N=3$) with randomly drawn utilities, compute the true maximin stable matching, and compare it to the output of Algorithm 3 run with the true utilities. If the algorithm's output has a lower minimum utility than some other stable matching, the side-restricted maximin routine is not computing the global maximin, and Lemma 5 and Theorem 2 would not target the stated objective.","tokens_in":15845,"feed_emoji":"⚖️","tokens_out":8665,"duration_ms":76114,"temperature":0.7,"pith_summary":"Two-sided matching markets — school choice, medical residency, ride-hailing — are usually analyzed as if preferences were known, and the standard deferred acceptance algorithm protects only the proposing side. This paper asks what can still be guaranteed when both sides must learn their preferences from noisy samples, and it answers with an explore-then-commit scheme. It claims that one version of the scheme converges to the stable matching maximizing total (utilitarian) welfare with regret $\\tilde O(N^2 \\log T)$, and another converges to the stable matching maximizing the utility of the worst-off participant (Rawlsian or maximin welfare) with regret $\\tilde O(N \\log T)$. Both guarantees require a minimum preference gap, meaning utilities that are almost tied make the problem harder; if the bounds are right, a planner can tolerate unknown preferences and still lose only polylogarithmic welfare over time.","feed_headline":"Bandit learners find stable matches that serve both sides","feed_subtitle":"New regret bounds cover utilitarian and worst-off-first objectives when neither side knows its tastes.","key_machinery":"The load-bearing objects are the minimum preference gaps. The within-side gap $\\Delta_a$ ($\\Delta_b$) is the smallest utility difference between any two arms for one agent (any two agents for one arm); it controls whether sample averages preserve ordinal preferences. The cross-side gap $\\Gamma$ is the smallest difference between any two utilities anywhere in the market; it controls whether the maximin objective survives estimation. Between them sits the rotation structure: starting from the agent-optimal stable matching obtained by deferred acceptance, repeatedly eliminating rotations traces all stable matchings to the arm-optimal one, and the utilitarian optimum is the minimum-weight closed set of rotations, computable by an $s$--$t$ min-cut. The algorithms are epoch explore-then-commit routines: in each epoch agents do round-robin exploration, form sample-average utilities, compute the estimated optimal matching, and commit to it for $2^l$ steps.","core_discovery":"The paper's central claim is that the classical discrete structure of stable matchings — the lattice of rotations between agent-optimal and arm-optimal matchings — survives in the bandit setting and can be exploited without knowing either side's preferences. For the utilitarian objective, it recovers a cardinal-utility version of the rotation-based algorithm: starting from the two deferred-acceptance extremes, every stable matching is produced by eliminating a closed set of rotations, and the utilitarian optimum is the minimum-weight closed set. It proves that if every estimated mean is within $\\min\\{\\delta/(4N), \\Delta_a/2, \\Delta_b/2\\}$ of the truth, where $\\delta$ is the welfare gap to the second-best stable matching, the recovered matching is exactly the utilitarian optimum; this yields regret $O(N^2 \\log T \\log\\log T + N^3 \\log T + 2^{l_1}N)$. For the Rawlsian objective, it adapts the side-restricted maximin procedure and shows that estimation error below $\\Gamma/2$, where $\\Gamma$ is the cross-side minimum preference gap, suffices to recover the maximin stable matching, with regret $O(N \\log T \\log\\log T + 4N^2 \\log T + 2^{l_1})$.","pith_inferences":["The Rawlsian proof treats the arm-side maximin routine (and its agent-side mirror) as a way to compute the global two-sided maximin of Definition 4.1; this equivalence is assumed rather than shown, so a reader should check it before relying on Theorem 2's benchmark.","The additive $2^{l_1}$ term with $l_1$ exponential in $1/\\Gamma^2$ indicates that near-tied utilities anywhere in the market force a burn-in exponential in the inverse gap; replacing the hard-gap analysis with gap-free or adaptive estimation is a natural extension.","The same rotation-lattice template should apply to other objectives defined on stable matchings, with the optimization oracle determining the learning rate rather than the exploration scheme."],"forward_implications":["If the bounds are correct, a planner facing two-sided unknown preferences can guarantee that after an initial burn-in the market nearly always plays the targeted stable matching, with regret growing only polylogarithmically in the horizon.","The two gap notions give an instance-dependent measure of hardness: a small $\\delta$ (two stable matchings with nearly equal utilitarian welfare) or a small $\\Gamma$ (two utilities anywhere nearly tied) forces longer exploration.","The utilitarian bound scales as $N^2$ in the number of agents while the maximin bound scales as $N$ (ignoring gap and exponential terms), so the worst-off-focused objective is not harder in market size; the cross-side gap dominates instead.","For unequal numbers of agents and arms, the rural hospital theorem restricts attention to the fixed set of stable partners, so the same algorithms apply to the $\\min\\{N, K\\}$ matched pairs."],"supporting_citations":[{"why":"Establishes that every market has at least one stable matching and defines the deferred-acceptance extremes from which the algorithms start.","marker":"[Gale and Shapley, 1962]"},{"why":"Shows the agent-optimal stable matching is arm-pessimal and supplies the rotation and break-matching operations used to move through the stable set.","marker":"[McVitie and Wilson, 1971]"},{"why":"Provides the rotation-lattice and min-cut method for utilitarian-optimal stable matching that Algorithm 1 adapts to cardinal utilities.","marker":"[Irving et al., 1987]"},{"why":"Defines the maximin stable-matching algorithm that Algorithm 3 adapts to cardinal utilities.","marker":"[Gusfield, 1987]"},{"why":"The rural hospital theorem, used to handle markets with unequal numbers of agents and arms.","marker":"[Roth, 1986]"},{"why":"Supplies the subgaussian concentration lemma used in the error-probability proofs of both regret bounds.","marker":"[Lattimore and Szepesvári, 2020]"},{"why":"Previous one-sided-unknown bandit matching model whose regret framework this paper extends to two-sided unknown preferences.","marker":"[Liu et al., 2020]"}],"fun_headline_variants":["Bandit matching learns fair stable outcomes","Both sides win in bandit-learned matches","No tastes needed: bandit finds stable match","Utilitarian and Rawlsian bandit matchmaking","Stable market matches from bandit learning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The Rawlsian proof assumes that the procedure that maximizes the worst-off arm (and, symmetrically, the worst-off agent) produces the stable matching that maximizes the minimum utility across both sides; the paper does not demonstrate that equivalence.","fun_headline_variants_meta":{"raw":{"variants":["Bandit matching learns fair stable outcomes","Both sides win in bandit-learned matches","No tastes needed: bandit finds stable match","Utilitarian and Rawlsian bandit matchmaking","Stable market matches from bandit learning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000301,"raw_usage":{"total_tokens":1755,"prompt_tokens":987,"completion_tokens":768,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":603,"completion_tokens_details":{"reasoning_tokens":698}},"tokens_in":603,"tokens_out":768,"duration_ms":6718,"temperature":1.0,"reasoning_tokens":698,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:32:26.629326+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all stable matchings of a small market (e.g., $N=3$) with randomly drawn utilities, compute the true maximin stable matching, and compare it to the output of Algorithm 3 run with the true utilities. If the algorithm's output has a lower minimum utility than some other stable matching, the side-restricted maximin routine is not computing the global maximin, and Lemma 5 and Theorem 2 would not target the stated objective.","supporting_citations":[{"cited_title":"The stable marriage problem","cited_arxiv_id":null,"evidence_quote":"Shows the agent-optimal stable matching is arm-pessimal and supplies the rotation and break-matching operations used to move through the stable set."},{"cited_title":"On the allocation of residents to rural hospitals: a general property of two-sided matching markets","cited_arxiv_id":null,"evidence_quote":"The rural hospital theorem, used to handle markets with unequal numbers of agents and arms."}],"review_version":1}