{"id":"010248c0-dab0-4ea5-8982-a43ffc7027d0","arxiv_id":"2506.02655","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"In Bayesian valid and basic utility games, the strategy representability gap is 1-1/e for independent priors and Θ(1/√n) for correlated priors, yielding price of anarchy and stability bounds that differ across mediated equilibrium concepts.","lead":"This paper proves bounds on social welfare when a mediator coordinates players in Bayesian games with submodular payoffs. It shows the welfare guarantee depends on which mediated equilibrium concept is used, and introduces a new measure called the strategy representability gap.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: SR-gap/PoA proofs are sound within the stated model; the consistent-f scope restriction is acknowledged and shown necessary.","rationale":"I read the paper as making conditional mathematical claims about the class of Bayesian valid/basic utility games it defines. The reader's weakest assumption—the need for a single consistent monotone submodular f—is exactly the place where the generality of the results is limited, and the paper acknowledges this in Appendix B.1, even proving that the assumption is necessary via Example B.3. I verified the main proofs in detail: the independent SR gap follows cleanly from the correlation gap and Lemma 2.7; the correlated SR gap proof's heavy/light action split, the use of the multilinear extension, and the final OPT vs STR inequality are all valid; the PoA smoothness arguments for SFCBSs, SFCCEs, and communication equilibria correctly handle the Bayesian deviations; and the 0.441 example is a legitimate Bayesian valid utility game with a genuine Bayesian solution. The only concrete issue I found is in the secondary PoS result, where the proof shows a family of games with PoS approaching 4/5 from above rather than a single game with PoS at most 4/5. This is a wording/imprecision issue that does not affect the central SR-gap and PoA theorems, so the reader's ACCEPT verdict remains appropriate.","tokens_in":27385,"tokens_out":47560,"duration_ms":447441,"concrete_test":"Recompute the exact ratio in Proposition 5.7 for any ε>0: (2+ε)/((5+ε)/2) = 2(2+ε)/(5+ε), which is strictly greater than 4/5 but tends to 4/5 as ε→0. This confirms the PoS claim needs an asymptotic qualifier while leaving the central SR-gap/PoA results unaffected.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the strategy representability gap and the resulting PoA bounds, and I find no internal flaw in that chain. Proposition 3.2 correctly combines the correlation gap with Lemma 2.7; the correlated lower bound in Theorem 3.4 uses a valid heavy/light decomposition and the multilinear-extension inequalities check out; the smoothness arguments for SFCBSs, SFCCEs, and communication equilibria are valid; and the 0.441 Bayesian-solution example satisfies the valid-utility conditions. The only substantive caveat is the model's scope: the definition requires one monotone submodular f on the union of all type-action pairs, which is stronger than requiring each fixed-type game to be a valid utility game. Appendix B.1 states this explicitly, and Example B.3 shows that without consistency the SR gap can degrade to Θ(1/n). Since the paper flags this restriction and demonstrates its necessity, it limits breadth but does not undermine the conditional theorems. A minor, non-load-bearing imprecision is that Proposition 5.7's 'at most 4/5' is really an asymptotic statement: the constructed unique communication equilibrium has ratio 2(2+ε)/(5+ε) > 4/5 for every ε>0, approaching 4/5 as ε→0.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Bayesian extensions of valid and basic utility games, in which a single monotone submodular set function f on the union of all type–action pairs defines social welfare for every type profile. The central new object is the strategy representability gap (SR gap): the best welfare achievable by strategies depending only on a player's own type divided by the full-information optimum. The paper proves that the SR gap is at least 1−1/e for product priors and Θ(1/√n) for correlated priors, with matching constructions. It then derives price-of-anarchy lower bounds of (1−1/e)/2 and Ω(1/√n) for strategic-form coarse Bayesian solutions, improves the independent-prior PoA to 1/2 for SFCCEs and communication equilibria, and exhibits a Bayesian valid utility game where the PoA for Bayesian solutions is at most about 0.441. For basic utility games it proves PoS=1 for Bayesian solutions, identifies the PoS for Bayes–Nash equilibria with the SR gap, and gives a communication-equilibrium example with PoS approaching 4/5.","tokens_in":27586,"tokens_out":33924,"duration_ms":343719,"significance":"The results are technically substantial and, if correct, give the first systematic welfare analysis of mediator-assisted equilibrium concepts in Bayesian submodular games and the first separation of PoA/PoS among natural Bayes correlated equilibrium concepts. The proofs are careful: the independent case uses the correlation gap correctly, the correlated case uses a valid heavy/light decomposition with the multilinear extension, and the smoothness arguments respect the different deviation classes. The paper is also honest about its main scope restriction: all results are conditional on the existence of a single consistent submodular f across type profiles, and Appendix B.1 and Example B.3 show that this restriction is necessary. This limits breadth but does not undermine the conditional theorems.","major_comments":[],"minor_comments":[{"comment":"As written, Proposition 5.7 does not establish the stated 'at most 4/5' for the displayed game with ε>0: the unique communication equilibrium has welfare ratio 2(2+ε)/(5+ε), which is strictly larger than 4/5 for every ε>0. This is easily repaired by taking ε=0, where the ratio is exactly 4/5, or by restating the result as a limit as ε→0.","section":"Section 5.3, Proposition 5.7"},{"comment":"The step 'from Lemma 2.7' is applied to distributions whose per-partition probabilities sum to at most 1, while Lemma 2.7 is stated for sums exactly equal to 1. The intended inequality still follows from Proposition 2.6 or by adding dummy elements, but the text should make this extension explicit.","section":"Section 3.2, proof of Theorem 3.4"},{"comment":"The sentence 'PoAΠ and PoAΠ' should read 'PoAΠ and PoSΠ'.","section":"Section 2.2, after Definition 2.4"},{"comment":"In the definition of π, the set is written as X={a^θ_i,...,a^θ_n}; this should be X={a^θ_1,...,a^θ_n}.","section":"Section 3.1, proof of Proposition 3.2"},{"comment":"Typo: 'out study' should be 'our study'.","section":"Section 1.2"}],"recommendation":"minor_revision","confidential_remarks":"I found no circularity, no missing proofs in the central chain, and no inappropriate use of prior work; the self-citation to Fujii (2023) is used only for definitions and prior smoothness results. The main caveat is scope: the abstract and title could overstate the generality relative to the consistent-f assumption, so the authors should make that restriction prominent in the abstract."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a solid theory paper worth your time. The new idea is the strategy representability gap, which cleanly captures the welfare loss from players knowing only their own types. The independent-prior bound 1 − 1/e follows from Vondrák's correlation gap, but the correlated-prior Θ(1/√n) bound is genuinely new and technically non-trivial, using a heavy/light action decomposition together with the multilinear extension. I checked the delicate step in Theorem 3.4 where disjointness of type-action sets is used to equate the union distribution with the multilinear extension; it holds. The derived PoA/PoS bounds are then honest consequences of the SR gap plus smoothness arguments, not fitted constants, and the separation between equilibrium concepts (PoA 1/2 for SFCCEs and communication equilibria versus 0.441 for Bayesian solutions; PoS 1 versus 4/5) is a real contribution that had been missed in prior work.\n\nThe main soft spot is the modelling assumption that a single monotone submodular f on the union of all type-action pairs works for every type profile. That is stronger than requiring each fixed-type game to be a valid utility game, and Appendix B.1 openly says the reduction can fail; Example B.3 shows the SR gap can degrade to Θ(1/n) without consistency. This restricts the scope, but the paper does not hide it, and the conditional theorems remain correct. A minor, non-load-bearing imprecision: Proposition 5.7 states the PoS for communication equilibria is 'at most 4/5', but the constructed example actually gives ratio 2(2+ε)/(5+ε), which is strictly above 4/5 for every ε > 0, converging to 4/5 as ε → 0. That is an asymptotic statement and should be phrased as such, but it does not affect the conclusion that the PoS is strictly below 1.\n\nSelf-citations to Fujii (2023) provide background and prior smoothness results, not the target bounds, so I see no circularity. The proof of Proposition 4.6, using untruthful-type deviations to bypass strategy representability, is especially neat and correct under the product-prior assumption.\n\nThis paper deserves a serious referee and, after minor revision, acceptance. Whoever reviews it should focus on the consistent-f assumption and on tightening the wording of Proposition 5.7, not on hunting for structural flaws, because the mathematical core is sound. I would cite the SR gap results in my own work on Bayesian welfare analysis.","headline":"Fresh and careful: a new strategy representability gap drives the first PoA/PoS bounds for Bayesian valid/basic utility games, with a genuine separation between equilibrium concepts; the main caveat is the consistent-submodular-f restriction, which the authors acknowledge and show can fail.","tokens_in":28129,"tokens_out":1213,"would_cite":true,"duration_ms":12706,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"In Bayesian games with monotone submodular social welfare, the strategy representability gap is 1-1/e for independent priors and Θ(1/√n) for correlated priors, and these values drive the price of anarchy and stability for every class of…","keywords":["strategy representability gap","Bayesian games","price of anarchy","price of stability","Bayes correlated equilibria","submodular social welfare","valid utility games","correlation gap"],"falsifier":"The central claim would be refuted by exhibiting a Bayesian valid utility game with independent priors whose strategy representability gap is strictly below $1-1/\\mathrm{e}$, or by finding a communication equilibrium or strategic-form coarse correlated equilibrium in such a game with welfare below half the optimum. A concrete check is to compute the SR gap of the coverage-function example in Proposition 3.3 and the correlated example in Proposition 3.6; any deviation from the predicted $1-1/\\mathrm{e}$ and $2/\\sqrt{n}$ values would signal a flaw. More generally, a brute-force search over small type-action instances satisfying the consistency condition can test whether the worst-case SR gap ever drops below the stated constants.","tokens_in":27162,"feed_emoji":"⚖️","tokens_out":15217,"duration_ms":139969,"temperature":0.7,"pith_summary":"The paper asks how much of the optimal social welfare a mediator can preserve in a Bayesian game, where each player knows only their own type and the mediator can coordinate them through communication protocols. The class of games considered has monotone submodular social welfare, a setting that generalizes valid and basic utility games used to model facility location, influence maximization, and congestion. The central quantity is the strategy representability gap: the fraction of full-information optimal welfare that remains achievable when each player's action may depend only on their own type. The paper proves this gap is exactly $1-1/\\mathrm{e}$ under independent type priors and is $\\Theta(1/\\sqrt{n})$ under correlated priors, and it then shows these bounds determine the worst- and best-case welfare guarantees of Bayes (coarse) correlated equilibria. It also establishes a separation among equilibrium concepts: communication equilibria and strategic-form coarse correlated equilibria keep a 1/2 guarantee, while Bayesian solutions can fall below 0.441.","feed_headline":"Correlated player types cut mediated welfare to 1/√n","feed_subtitle":"Independent priors hold the guarantee at 1-1/e; the strategy representability gap sets every price-of-anarchy bound.","key_machinery":"The load-bearing object is the strategy representability gap, the ratio of the best expected welfare over strategy profiles to the expected full-information optimal welfare. The proof machinery around it has three parts: the correlation-gap inequality for monotone submodular functions (Proposition 2.5), which bounds the loss when a distribution over optimal action sets is replaced by its independent counterpart; Lemma 2.7, derived from weak negative regression, which lets one replace a one-from-each-player product distribution by a componentwise independent distribution; and, in the correlated case, a heavy/light decomposition that separates, for each player and type, the at most $\\sqrt{n}$ actions with mass above $1/\\sqrt{n}$, analyzed via the multilinear extension. Smoothness arguments then transfer these welfare bounds to equilibrium concepts, with the untruthful-reporting incentive constraints of communication equilibria used to obtain the 1/2 price-of-anarchy bound without strategy representability.","core_discovery":"The central discovery is a tight characterization of the strategy representability gap, together with the equilibrium bounds it implies. In any Bayesian valid or basic utility game, the best welfare achievable by a strategy profile that uses only each player's own type is at least a $1-1/\\mathrm{e}$ fraction of the full-information optimum when the type prior is independent, and this is tight (Proposition 3.3). Under correlated priors the gap drops to $\\Theta(1/\\sqrt{n})$, tight up to constants (Theorem 3.4, Proposition 3.6). Combining the gap with smoothness arguments yields price-of-anarchy lower bounds of $(1-1/\\mathrm{e})/2$ and $\\Omega(1/\\sqrt{n})$ for strategic-form coarse Bayesian solutions, an improved 1/2 bound for strategic-form coarse correlated equilibria and communication equilibria under independent priors, and an upper bound of 0.441 for Bayesian solutions. On the price of stability side, Bayesian basic utility games have price of stability 1 for Bayesian solutions, $1-1/\\mathrm{e}$ for Bayes–Nash equilibria under independent priors, $\\Theta(1/\\sqrt{n})$ under correlated priors, and at most 4/5 for communication equilibria.","pith_inferences":["Editorial extension: the SR gap isolates a two-stage design rule for other Bayesian resource-allocation games: if the consistent-submodular-welfare condition holds, one can quote these bounds directly; if it fails, Example B.3 suggests the guarantees can collapse to order $1/n$, so checking consistency should be the first step in practical applications.","Editorial extension: the paper's consistency condition is likely a stricter requirement than the standard Bayesian-game formulation; a testable research direction is to find natural classes where the type only changes feasible actions, as in the routing and task-assignment examples, and to prove that a single $f$ always exists, thereby expanding the scope of the $1-1/\\mathrm{e}$ and $\\Theta(1/\\sqr","Editorial extension: the 0.441 upper bound and the 4/5 communication-equilibrium example suggest that whether the mediator can verify reported types is a genuine design lever; one could search empirically for other valid utility games where verification changes the guarantee by more than the constants reported here.","Editorial extension: because the correlated-case bound is proved with the multilinear extension and a heavy/light split, the same technique may transfer to other Bayesian objectives satisfying the consistency condition, giving analogous $\\Theta(1/\\sqrt{n})$ behavior for non-submodular welfare functions."],"forward_implications":["Under independent priors, no strategic-form coarse Bayesian solution can produce welfare below $(1-1/\\mathrm{e})/2 \\approx 0.316$ of the optimum, and strategic-form coarse correlated equilibria and communication equilibria are guaranteed at least 1/2 of the optimum.","Under correlated priors, the worst-case welfare for these mediated equilibria degrades like $\\Omega(1/\\sqrt{n})$ of the optimum, and the SR gap shows this is tight up to a constant.","Bayesian solutions are strictly worse than communication equilibria: there is a valid utility game with independent priors where the best Bayesian solution achieves only about 0.44 of optimal welfare.","In Bayesian basic utility games, Bayesian solutions achieve full optimal welfare (price of stability 1), while Bayes–Nash equilibria under independent priors may only reach $1-1/\\mathrm{e}$, and communication equilibria can be stuck at 4/5.","Because every Bayes–Nash equilibrium is a strategy profile, no equilibrium concept that refines Bayes–Nash can beat the SR gap as an upper bound on price of anarchy."],"supporting_citations":[{"why":"It defines valid and basic utility games and proves the 1/2 price-of-anarchy bound and the price-of-stability-1 property that the Bayesian results extend.","marker":"Vetta (2002)"},{"why":"It supplies the correlation-gap inequality (Proposition 2.5) that yields the $1-1/\\mathrm{e}$ lower bound on the strategy representability gap.","marker":"Vondrák (2007)"},{"why":"It supplies the weak-negative-regression dominance result used to prove Lemma 2.7, which underpins the correlated-prior bound.","marker":"Qiu and Singla (2022)"},{"why":"It provides the correlation-gap theorem for monotone submodular functions invoked in the independent-prior analysis.","marker":"Agrawal et al. (2012)"},{"why":"It establishes the strategic-form equivalence for Bayes–Nash equilibria used to transfer the price-of-stability argument in Section 5.2.","marker":"Harsanyi (1967)"},{"why":"It provides the smoothness framework for Bayesian games that the paper extends to the equilibrium-concept bounds.","marker":"Roughgarden (2015a)"},{"why":"It establishes the communication-equilibrium and Bayes correlated equilibrium definitions that the paper uses to separate the concepts.","marker":"Forges (1993)"},{"why":"It introduces the strategy-representability notion and the relations among Bayes correlated equilibria that motivate the SR gap.","marker":"Fujii (2023)"},{"why":"It gives the Erdős–Rényi perfect-matching threshold used to prove tightness of the independent-prior $1-1/\\mathrm{e}$ example.","marker":"Frieze and Karoński (2015)"}],"fun_headline_variants":["Mediated Bayesian welfare: 1-1/e independent, 1/√n correlated","Bayesian mediation gap: 1-1/e for independent types, 1/√n for correlated","Price of anarchy in Bayesian games: 1-1/e independent, 1/√n correlated","Strategy representability gap sets Bayesian price of anarchy bounds","Bayesian mediators: 1-1/e for independent priors, 1/√n for correlated"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole analysis assumes that one monotone submodular function $f$ on the union of all type-action pairs satisfies the valid/basic utility conditions for every type profile at once; the paper itself notes in Appendix B.1 that such a consistent $f$ need not exist, and Example B.3 shows the guarantees can degrade to $\\Theta(1/n)$ when it is absent.","fun_headline_variants_meta":{"raw":{"variants":["Mediated Bayesian welfare: 1-1/e independent, 1/√n correlated","Bayesian mediation gap: 1-1/e for independent types, 1/√n for correlated","Price of anarchy in Bayesian games: 1-1/e independent, 1/√n correlated","Strategy representability gap sets Bayesian price of anarchy bounds","Bayesian mediators: 1-1/e for independent priors, 1/√n for correlated"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001122,"raw_usage":{"total_tokens":4751,"prompt_tokens":1113,"completion_tokens":3638,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":729,"completion_tokens_details":{"reasoning_tokens":3530}},"tokens_in":729,"tokens_out":3638,"duration_ms":27106,"temperature":1.0,"reasoning_tokens":3530,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:21:50.080287+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The central claim would be refuted by exhibiting a Bayesian valid utility game with independent priors whose strategy representability gap is strictly below $1-1/\\mathrm{e}$, or by finding a communication equilibrium or strategic-form coarse correlated equilibrium in such a game with welfare below half the optimum. A concrete check is to compute the SR gap of the coverage-function example in Proposition 3.3 and the correlated example in Proposition 3.6; any deviation from the predicted $1-1/\\mathrm{e}$ and $2/\\sqrt{n}$ values would signal a flaw. More generally, a brute-force search over small type-action instances satisfying the consistency condition can test whether the worst-case SR gap ever drops below the stated constants.","supporting_citations":[],"review_version":1}