{"id":"80567d74-446c-4cdc-b502-f558eaf40719","arxiv_id":"2502.08412","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"With adaptive costly audits and a flagging rule, a repeated non-monetary allocation mechanism achieves O(K^2) social-welfare regret and O(K^3 log T) expected audits for heterogeneous strategic agents, despite the planner having no prior distributional information.","lead":"An allocation designer with no knowledge of users' preferences can still get near-optimal total value over many rounds by occasionally auditing the winner and banning liars. The cost is small: the number of audits grows only logarithmically with time.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The main theorem assumes a PBE exists in the auxiliary game (Def. 8) without proof; if that existence fails for some allowed distributions, the 'there exists π*' claim is unsubstantiated.","rationale":"I identify the unproven existence of a PBE in the auxiliary game (Definition 8) as the single most load-bearing concern. The reader's formal weakest_assumption is the informational asymmetry (agents know all distributions while the planner knows none); that is an explicit modeling assumption and is necessary for the Bayesian equilibrium formalism, so I do not see it as a correctness gap. The reader does, however, mention the auxiliary-game existence assumption in the rationale and uses it to justify the CONDITIONAL verdict. Because the central theorem's claim is existential ('there exists a PBE π*'), a missing proof that the auxiliary game has a PBE is a direct gap in the argument: if the auxiliary game has no PBE for some allowed distributions, the construction in Theorem 10 has no foundation. I consider this gap likely fixable via standard distributional-strategy arguments, consistent with the reader's CONDITIONAL verdict, so I do not move the verdict. The disagreement field is set to 'disagree' because the reader's stated weakest_assumption is not the same as my chosen load-bearing concern, even though the reader identified my concern in the rationale.","tokens_in":38561,"tokens_out":18574,"duration_ms":173310,"concrete_test":"Provide a rigorous existence proof for a PBE of the auxiliary game (Definition 8) for all distributions satisfying Assumption 1, for example by verifying the hypotheses of a fixed-point theorem for Bayesian games with continuous types and compact actions while handling discontinuities at ties. As a minimal computational/analytical check, solve the auxiliary game for K=2, U1=δ_{2/3}, U2=δ_{1/3}, T=2 by backward induction on the two rounds; if a PBE exists, then test a distribution with atoms (e.g., a two-point distribution) to see whether discontinuities break existence. If no PBE exists for some admissible distribution, the proof of Theorem 5 is invalid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 5 asserts that for every collection {U_i} satisfying Assumption 1, there exists a PBE π* of AdaAudit with the stated regret and audit guarantees. The proof builds π* from 'a PBE π*^r in the auxiliary game' (Definition 8) and then proves Theorem 10, which transfers this equilibrium to the original game. However, the paper never proves that the auxiliary game actually has a PBE. The auxiliary game is a finite-horizon Bayesian game with continuous private types (utilities in [0,1]), compact but type-dependent action sets ([0,u_t,i] when p_t,i <= 1, otherwise [0,1]), and payoffs that are discontinuous at report ties and at elimination events. Assumption 1 allows distributions with atoms, so standard continuity-based existence theorems for Bayesian games do not directly apply. Without an existence proof or a citation establishing the required fixed-point conditions, the premise 'let π*^r be a PBE' is unjustified. If there exists some admissible distribution for which the auxiliary game has no PBE, then the constructed π* does not exist and the central existence claim of Theorem 5 collapses. The reader's rationale flags this same gap as a reason for CONDITIONAL, and I agree that it is the most load-bearing obstruction to the theorem as stated.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies repeated single-resource allocation among K strategic agents when monetary transfers are disallowed and the planner has no prior knowledge of the agents' utility distributions. The planner can audit the winner after each allocation and observe the winner's true utility, but cannot revoke the allocation. The main result, Theorem 5, claims that for every collection of distributions satisfying Assumption 1 there is a Perfect Bayesian Equilibrium of the proposed mechanism AdaAudit under which the social-welfare regret is at most K^2 and the expected number of audits is O(K^3 log T / c). The mechanism adapts audit probabilities to online estimates of agents' fair winning probabilities, and it allows agents to flag biased estimates. The equilibrium analysis proceeds by reducing the original game to a more restrictive auxiliary game, proving a correspondence between equilibria of the two games, and then bounding regret and audit counts in the auxiliary equilibrium. The paper also provides lower bounds showing Omega(K) regret is necessary and that constant expected audits force polynomial regret.","tokens_in":38831,"tokens_out":7195,"duration_ms":83809,"significance":"If the main theorem is correct, this is a substantive contribution: it gives the first general sub-linear social-welfare guarantee for repeated non-monetary allocation when the planner has no distributional information, and it introduces two transferable ideas, namely adaptive future punishments calibrated by audited fair shares and an incentive-aligned flagging component. The auxiliary-game reduction is also interesting as a way to circumvent the failure of the revelation principle in a setting where the planner must work for all distributions at once. The paper is unusually explicit about the structure of its proofs and the constants involved. The main reservation is that the central equilibrium-existence claim is taken as an input rather than proved, and the audit-count proof contains a stopping-time concentration step that is not fully justified as written.","major_comments":[{"comment":"The proof of the main theorem assumes, rather than establishes, that the auxiliary game has a Perfect Bayesian Equilibrium. Theorem 10 begins with 'Let π*^r be a PBE in the auxiliary game from Definition 8', and Theorem 5 then asserts existence of a PBE of AdaAudit for every collection of distributions satisfying Assumption 1. However, no existence theorem for the auxiliary game is stated, proved, or cited. The auxiliary game has continuous private types in [0,1], action sets that depend on the realized type (Restriction 2 gives action set [0,u_t,i] when p_t,i <= 1), payoffs that are discontinuous at report ties and at elimination events, and Assumption 1 explicitly permits distributions with atoms. Standard continuity-based Bayesian equilibrium existence theorems do not apply directly. This is load-bearing: if for some admissible distributions the auxiliary game has no PBE, the constructed π* need not exist and the existence claim of Theorem 5 collapses. The authors should either prove existence of a PBE in the auxiliary game under Assumption 1, cite a theorem that applies to this class of discontinuous type-dependent-action Bayesian games, or restrict the main theorem to the class of distributions for which existence is established.","section":"Section 5.1, Definition 8, Theorem 10"},{"comment":"The bound on the expected number of audits in the estimation phase relies on the random time t_{ℓ,i} defined in Eq. (21) as the first round in which the empirical frequency of the independent fair-winning indicators F_{t,i} lies in [q_{ℓ,i}/3, 3q_{ℓ,i}], while the agent has won sufficiently many times. The proof of Claim 25 dismisses the case t_{ℓ,i} = t_{ℓ+1} - 1 as 'immediate', but in that case Eq. (21) is not satisfied, and the subsequent inequalities in Claim 26 use Eq. (21) to convert empirical frequencies into bounds on the estimate. Claim 26 then applies Chernoff-type concentration to sums over deterministic dyadic horizons to control 2^{k_{ℓ,i}}. The step connecting the stopping time t_{ℓ,i} (or its non-existence) to the dyadic-horizon concentration bounds is not written out, and as it stands the proof does not establish the claimed O(K^3 log T) audit bound for epochs in which no round satisfies Eq. (21). The authors should either prove the required concentration statement at the stopping time directly, or rework the definition of t_{ℓ,i} and the proof of Claim 26 so that the no-such-t case is covered by the displayed inequalities.","section":"Appendix B.2, Claim 25 and Claim 26"},{"comment":"The lower-bound proof says 'By the revelation principle, we assume without loss of generality that under this specific utility distributions setup {U_i} and mechanism M truthful reporting truth is the considered PBE.' This is true only after a direct-revelation transformation of M that depends on the fixed prior, and it is potentially confusing given the paper's own discussion that the revelation principle cannot be applied globally across all distributions. The argument should state explicitly that the transformation is performed for the fixed distributions of the lower bound and that it preserves the allocation, audit, and utility processes. As written, the unqualified 'WLOG' invites a circularity objection even though the step can be made valid in this fixed-prior context.","section":"Appendix D, Theorem 28"}],"minor_comments":[{"comment":"When the empirical winning probability \\hat q_{t,i_t} is zero, which occurs in the first rounds of an epoch, the audit probability \\hat p_{t,i_t} = min(8K^2/((T-t)\\hat q_{t,i_t} c), 1) is undefined as written. The intended convention, stated in Section 4.2, is that the agent is audited with probability 1 during the estimation phase. Please add an explicit convention such as \\hat p_{t,i_t}=1 when \\hat q_{t,i_t}=0.","section":"Algorithm 1, Line 6"},{"comment":"Definitions 8 and 9 are referred to in the main text as 'Theorem 8' and 'Theorem 9' (e.g., Theorem 10 and several places in Appendix A). This makes the logical status of the statements confusing; the labels should be unified so that definitions are cited as definitions and theorems as theorems.","section":"Section 5.1 and Appendix A"},{"comment":"These are labeled informal theorems in the main text and then proved in the appendix under different numbers (Theorems 18–20). It would improve readability to use a single numbering scheme, or at least to add explicit forward references when the informal statements are introduced.","section":"Lemmas 11, 12, 13"},{"comment":"The abstract states the audit bound as O(K^3 log T) without the factor 1/c that appears in Theorem 5. Since c is a parameter of Assumption 1 and appears in the proof, the abstract should either include the factor or state that c is a fixed constant of the problem.","section":"Abstract and Theorem 5"},{"comment":"The statement that all agents know the utility distributions while the planner knows none is a very strong information asymmetry. The paper justifies it as necessary for the Bayesian equilibrium definition, but it would be helpful to state explicitly in the introduction or the model section that the results do not cover the case where agents also have distributional uncertainty, since the flagging strategy in Definition 9 requires agents to compare the planner's estimate with the true fair winning probability.","section":"Section 3"}],"recommendation":"major_revision","confidential_remarks":"The central ideas are strong and the paper is clearly written, but the missing existence proof for the auxiliary-game PBE is a genuine gap in the proof of the main theorem. I believe it is fixable: the authors may need to add a separate existence argument or cite a suitable existence theorem for discontinuous Bayesian games with type-dependent action sets. The audit-count concentration step also needs a rigorous stopping-time treatment. If those two points are resolved, the paper would make a solid contribution. The lower-bound section is interesting but the revelation-principle step should be clarified to avoid the appearance of circularity."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth your attention. It gives the first mechanism for repeated non-monetary allocation that achieves T-independent regret and O(K^3 log T) audits without distributional information, and it handles heterogeneous agents, which prior work (Yin et al.) could not. The adaptive audit scheme, with audit probability inversely tied to the winner's future winning probability, is elegant; the flagging component is a genuinely new way to keep online estimates unbiased when agents are strategic; and the auxiliary-game reduction is a clever workaround to the absence of the revelation principle. The lower bounds are also nontrivial and put the upper bounds in context. The appendix is detailed and mostly transparent, and I saw no circularity or fitted constants.\n\nThe soft spot is real and load-bearing. Theorem 5 asserts that for every distribution family satisfying Assumption 1, there exists a PBE of AdaAudit with the stated guarantees. The proof constructs that PBE from a PBE of the auxiliary game (Def. 8), but the existence of a PBE in that auxiliary game is never proved or cited. The auxiliary game is a finite-horizon Bayesian game with continuous types, type-dependent action sets, discontinuities at ties and elimination events, and Assumption 1 allows atoms. Standard continuity-based existence theorems do not directly apply. If there is any admissible distribution family for which the auxiliary game has no PBE, the construction collapses and the main theorem as stated is unsupported. This is the first thing I would ask the authors to fix. I suspect it can be fixed with a fixed-point / approximation argument or a careful citation to a suitable existence theorem for discontinuous Bayesian games, but it needs to be done explicitly.\n\nA second weakness, more a limitation than a flaw, is the informational asymmetry: agents know all utility distributions, the planner knows none. This is essential for their Bayesian equilibrium concept, but it is strong and should be flagged clearly; it makes the word 'prior-free' sound better than it is in practice.\n\nThe audit-count proof also leans on a concentration argument for fair-winning events that is stated a little loosely, but I did not find a concrete error there.\n\nOverall: this is a solid paper with one serious gap. It deserves a referee's time and a conditional accept, with the existence proof as the condition. I would bring it to reading group and cite it if the gap gets patched.","headline":"A genuine first result in prior-free non-monetary repeated allocation, but the main theorem leans on an unproved PBE existence claim in the auxiliary game; fixable, but must be fixed before it stands.","tokens_in":39368,"tokens_out":1548,"would_cite":true,"duration_ms":20498,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B03","91A20","91A27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Without knowing utility distributions and without any money, a planner can achieve $\\mathcal{O}(K^2)$ regret using adaptive audits with $\\mathcal{O}(K^3 \\log T)$ expected checks.","keywords":["mechanism design without money","costly state verification","adaptive auditing","no prior distributional information","social welfare regret","Perfect Bayesian Equilibrium","repeated resource allocation","incentive compatibility"],"falsifier":"Simulate AdaAudit on a distribution satisfying Assumption 1, with agents playing the well-behaved flagging equilibrium, and record total regret and audit count over long horizons; the proof asserts regret never exceeds $K^2$ and audits stay within $\\mathcal{O}(K^3 \\log T / c)$, so any instance violating those bounds would falsify Theorem 5.","tokens_in":38317,"feed_emoji":"🔍","tokens_out":15002,"duration_ms":131139,"temperature":0.7,"pith_summary":"This paper asks whether a planner who knows nothing about agents' utility distributions and cannot use monetary transfers can still allocate a single resource efficiently when agents are strategic. It answers yes, provided the planner can occasionally audit the winning agent after the allocation to observe that agent's true utility. The proposed mechanism, AdaAudit, chooses audit probabilities adaptively from online estimates of each agent's fair winning probability and lets agents flag biased estimates; under a constructed Perfect Bayesian Equilibrium, the expected social-welfare regret is at most $K^2$ while the expected number of audits is $\\mathcal{O}(K^3 \\log T / c)$. The result matters because it gives the first general sub-linear regret guarantee for non-monetary mechanisms with no prior distributional information, showing that costly verification can substitute for both money and prior knowledge.","feed_headline":"Adaptive audits give constant regret with no priors, no money","feed_subtitle":"A planner who can audit winners occasionally keeps strategic agents near-optimal using only logarithmically many checks.","key_machinery":"The central object is the adaptive audit probability $\\hat p_{t,i} = \\min(8K^2 / ((T-t) \\hat q_{t,i} c), 1)$, where $\\hat q_{t,i}$ is the planner's current estimate of $q_{t,i}$, the probability that agent $i$ would win a round under truthful reports from the current set of alive agents. This formula makes the expected future loss from being eliminated, roughly $\\hat p_{t,i} (T-t) \\mu_{t,i}$, dominate the at-most-one unit of current gain from lying, while the sum over $t$ of $q_{t,i}/((T-t) \\mu_{t,i})$ is $\\mathcal{O}((\\log T)/c)$. Because $q_{t,i}$ is unknown, AdaAudit estimates it in epochs and allows any agent to flag an estimate outside a factor-4 window around the true value; the well-behaved flagging strategy is shown to be individually rational. The equilibrium proof works through an auxiliary game that forbids mark-ups unless the audit probability is 1 and restricts reports to depend only on $(t, \\text{alive set})$; a PBE of that restricted game is lifted to the full game via a V-function correspondence.","core_discovery":"The central claim is Theorem 5: for any utility distributions satisfying Assumption 1 (at least one agent's utility is at least $c > 0$ almost surely), there exists a Perfect Bayesian Equilibrium $\\pi^*$ of AdaAudit with $R_T(\\pi^*, \\mathrm{AdaAudit}) \\le K^2$ and $B_T(\\pi^*, \\mathrm{AdaAudit}) = \\mathcal{O}(K^3 \\log T / c)$. The paper also proves an $\\Omega(K)$ lower bound on regret and an $\\Omega(1)$ lower bound on audits for low regret, so the qualitative guarantees cannot be obtained without cost. The mechanism's insight is that an audit probability inversely proportional to the winner's expected future gain makes lying unprofitable: the threat of elimination, scaled by the audit probability, outweighs the one-shot gain from misreporting, and summing those probabilities over time yields a harmonic series and hence only logarithmically many audits.","pith_inferences":["Beyond the paper, the flagging rule suggests a reusable design pattern: when a planner's estimate is coupled to agents' reports, let agents who expect to be harmed by a biased estimate veto it, because their private information can police estimation errors.","A direct extension would drop the agents-know-distributions assumption and replace the exact $q$-comparison in the flagging rule with a statistical test; making that work would extend the result to settings where agents and planner share no common prior.","The proof technique of reducing equilibrium analysis to an auxiliary game with restricted strategies appears transferable to other mechanism design problems, but only where the planner can commit to immediate elimination on detected lies.","The gap between the $K^2$ regret upper bound and the $\\Omega(K)$ lower bound suggests a plausible next target of closing the factor $K$ with sharper estimates or different audit schedules; this is not claimed in the paper."],"forward_implications":["If Theorem 5 is correct, an organization that can audit outcomes occasionally can run a near-efficient allocation with zero prior preference data and zero budget for transfers.","The logarithmic audit count means the cost of verification, not the number of rounds, is the bottleneck: over a $T$-round horizon the planner spends only $\\mathcal{O}(K^3 \\log T / c)$ audits in expectation.","The lower bounds imply no mechanism can remove the polynomial dependence on $K$ or avoid some constant number of audits, so AdaAudit's qualitative trade-off is essentially unavoidable.","The paper's extension to imperfect audit models means the audit signal does not need to be perfectly reliable for the regret and audit guarantees to survive."],"supporting_citations":[{"why":"Supplies the closest previous mechanism for non-monetary allocation without distributional information, under the restriction of identical utility distributions; AdaAudit adapts its elimination threat to distinct distributions.","marker":"[Yin et al., 2022]"},{"why":"Establishes the promised-utility and Perfect Bayesian Equilibrium framework for non-monetary mechanisms with known distributions that AdaAudit seeks to match without priors.","marker":"[Balseiro et al., 2019]"},{"why":"Provides the artificial-currencies benchmark whose initial budgets depend on utility distributions, motivating the need for a distribution-free alternative.","marker":"[Gorokh et al., 2021b]"},{"why":"Grounds the claim that without feedback the planner cannot simultaneously achieve efficiency and incentive compatibility, hence audits are needed as the information-acquisition channel.","marker":"[Arrow, 1950; Gibbard, 1973; Satterthwaite, 1975]"},{"why":"Supplies the performance-difference lemma used to reduce a unilateral deviation over the whole horizon to per-round Q-function comparisons in the PBE proof.","marker":"[Kakade and Langford, 2002]"},{"why":"Provides the binary KL-divergence bound used in the lower-bound proof on the audit/regret trade-off.","marker":"[Blanchard and Voracek, 2024]"}],"fun_headline_variants":["Adaptive audits: no money, no priors, near-optimal welfare","Costly audits beat no-prior allocation without cash","Log audits, constant regret: mechanism without priors or money","Audit winners, not wallets: new mechanism achieves efficiency","Priors? Cash? Neither: adaptive audits keep agents honest"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every agent knows all utility distributions exactly while the planner knows none, because the flagging strategy requires agents to compare the planner's estimate with the true fair winning probability.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive audits: no money, no priors, near-optimal welfare","Costly audits beat no-prior allocation without cash","Log audits, constant regret: mechanism without priors or money","Audit winners, not wallets: new mechanism achieves efficiency","Priors? Cash? Neither: adaptive audits keep agents honest"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000182,"raw_usage":{"total_tokens":1339,"prompt_tokens":1004,"completion_tokens":335,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":620,"completion_tokens_details":{"reasoning_tokens":249}},"tokens_in":620,"tokens_out":335,"duration_ms":4050,"temperature":1.0,"reasoning_tokens":249,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T05:11:58.566071+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate AdaAudit on a distribution satisfying Assumption 1, with agents playing the well-behaved flagging equilibrium, and record total regret and audit count over long horizons; the proof asserts regret never exceeds $K^2$ and audits stay within $\\mathcal{O}(K^3 \\log T / c)$, so any instance violating those bounds would falsify Theorem 5.","supporting_citations":[],"review_version":1}