{"id":"e4fcb68a-9307-437d-89e7-3b996b6ee34c","arxiv_id":"2505.13824","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A uniform randomized bidding strategy guarantees each agent a 2 minus sqrt(2), about 0.59, fraction of ideal utility robustly in repeated first-price auctions with artificial currencies, breaking the previous 1/2 barrier.","lead":"This paper shows that a simple randomized bidding strategy lets each agent in a repeated first-price auction with artificial currency guarantee about 59 percent of her ideal utility, no matter what other agents do, beating the previous 50 percent guarantee. The result nearly matches a known 63 percent upper bound, so it clarifies how much fairness and efficiency online resource sharing can robustly achieve.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's stated O(sqrt(logT/T)) rate is not supported by the Appendix A proof: the Azuma tail bound and the algebra in Eqs. (10)-(15) leave additive losses of order T^{-1/4}(log T)^{1/4} or T^{-1/(2bbar)}, not O(sqrt(logT/T)).","rationale":"I read the paper as a serious attempt to improve robust guarantees in repeated first-price auctions, and the high-level idea is plausible: randomization in bidding breaks the adversary's ability to predict the exact bid, and the uniform distribution is the natural extremal choice. Lemma 1's reduction is conceptually sound, though the printed equality chain contains a step that needs the convention that the simulated policy does not win on Vhat=0; this is fixable. The main issue I find is in the proof of Theorem 1 itself. The martingale concentration and the subsequent algebra in Appendix A contain multiple concrete errors: the Azuma denominator is wrong, Eq. (10) drops a factor of bbar, and the budget-shortfall term in Eq. (15) is undercounted by a factor of about sqrt(tau). Together these errors mean the proof does not establish the stated O(sqrt(logT/T)) approximation rate. The asymptotic constant 2 - sqrt(2) may still be correct, since the leading term in the minimization is unchanged and the extra losses are o(1), so I do not think this warrants a reject; it warrants a conditional acceptance contingent on a corrected proof. The reader's weakest assumption was the agent's knowledge of her value distribution, which is a real but different concern; the reader also noted the Eq. (9)-(10) algebra, which is a symptom of the same proof issues. My recommendation is to keep the CONDITIONAL verdict but require a repaired Appendix A before final acceptance.","tokens_in":20176,"tokens_out":28530,"duration_ms":265156,"concrete_test":"Re-derive the proof of Theorem 1 symbolically with corrected constants: (1) apply Azuma-Hoeffding to M1, M2, and M3 using their true increment bounds (bbar, 1, and bbar respectively); (2) recompute Eq. (10) from Eq. (9) without dropping factors of bbar; (3) track the term sqrt(tau*(2bbar^2 + 2bbar^2*epsilon)/alpha)/(bbar*T) through Eqs. (13)-(15). Substitute epsilon = sqrt(T ln T) and compute the asymptotic order of the total additive loss. If the loss is Theta(T^{-1/4}(log T)^{1/4}) or Theta(T^{-1/(2bbar)}), then the stated O(sqrt(logT/T)) rate is false. Then test whether choosing epsilon = C sqrt(T ln T) with a large constant C, together with the corrected Eq. (10), yields an error O(sqrt(logT/T)); if not, the rate claim is not salvageable by this proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 1, and its proof in Appendix A does not establish the stated convergence rate. First, Eq. (4) applies Azuma-Hoeffding with denominator 2bbar*T, but for martingales M1 and M3 whose increments are bounded by bbar over T steps the correct denominator is 2bbar^2*T. With epsilon = sqrt(T ln T), the failure probability is at least about T^{-1/(2bbar^2)} (or T^{-1/(2bbar)} using the printed bound), which is not small enough to be absorbed into an O(sqrt(logT/T)) guarantee. Second, the algebra from Eq. (9) to Eq. (10) drops a factor of bbar: the correct inequality is sum b'^2 <= bbar^2*tau - 2bbar*T + (2bbar^2 + 2bbar^2*epsilon)/alpha, not ... + (2bbar + 2bbar*epsilon)/alpha. Third, in the tau >= 2T/bbar case, the term originating from the budget shortfall is bounded in Eqs. (13)-(15) as (1/(bbar*T)) * sqrt((2bbar + 2bbar*epsilon)/alpha), but the correct term is sqrt(tau*(2bbar^2 + 2bbar^2*epsilon)/alpha)/(bbar*T), which is of order T^{-1/4}(log T)^{1/4} when epsilon = sqrt(T ln T). These errors mean the proof as written gives a rate like 2 - sqrt(2) - O(T^{-c}) with c < 1/2, not the claimed O(sqrt(logT/T)). The asymptotic 0.59 constant may well survive after repair, but the main theorem as stated is not proven.","agreement_with_reader":"partial"},"referee_report":null,"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper has a genuinely new idea: a randomized bidding strategy that provably (modulo appendix repair) beats the 1/2 robustness barrier in the repeated first-price auction, plus a Bernoulli worst-case reduction that should apply broadly. Second, the main theorem as stated is not proven: the Appendix A analysis appears to have real algebra errors in the Azuma denominator, the Eq. (9)-(10) step, and the tau >= 2T/bbar case, which would degrade the claimed O(sqrt(logT/T)) rate to something like T^{-1/4}. That doesn't kill the 2 - sqrt(2) constant necessarily, but it means the theorem's current form overclaims.\n\nWhat's actually new and good: the RRB strategy is simple and elegant; the reduction to Bernoulli valuations in Lemma 1 is a clean general tool; the static-policy 3/5 upper bound and the constructive adversary for 1 - 1/e are solid contributions. The paper is well-written and honest about the adversarial model.\n\nSoft spots: (1) The appendix rate issue is load-bearing because the theorem statement uses a specific rate. The authors need to either fix the algebra or restate the theorem with the slower rate. This is not a minor typo; the stress-test identifies a factor of bbar lost in two places and a sqrt(tau) term that changes the rate. A referee should demand the appendix be reworked. (2) The experimental section overstates: the 1 - (1 - 1/n)^n claim about RRB in symmetric play is presented as if it were a proven bound (\"we show\") but actually it's just a simulation observation. That needs to be flagged. (3) The strategy requires knowing F and the optimal rho-star; that's a standard assumption in this line, but it's worth noting as a limitation.\n\nIf the appendix gets fixed, this is a meaningful within-subfield advance. Even with the flaws, it deserves peer review and a careful referee; the ideas are too useful to desk-reject. I'd recommend sending it out, with instructions that the referee should verify Appendix A equation by equation. I would not cite the current version's rate claim.","headline":"A genuinely promising idea with a flawed main-proof appendix; send to a careful referee, but don't cite the rate claim until fixed.","tokens_in":21156,"tokens_out":1815,"would_cite":false,"duration_ms":17361,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B26","91B32"],"pacs":[],"model":"deepseek-v4-flash","headline":"Repeated first-price auctions with artificial currency can guarantee each agent at least $2-\\sqrt{2}\\approx 0.59$ of her ideal utility against arbitrary other-agent behavior, breaking the $1/2$ barrier and approaching the $1-1/e$ ceiling.","keywords":["robust guarantees","online resource allocation","artificial currency","randomized bidding","repeated first-price auction","ideal utility","fair division","price of anarchy"],"falsifier":"Run the model with $\\mathrm{Bernoulli}(\\alpha)$ values and the Randomized Robust Bidding strategy against an adversary that bids a fixed $b'\\in[1,1+\\sqrt{2}]$ each round until its budget runs out; the theorem says the agent's per-round utility is at least $2-\\sqrt{2}-O(\\sqrt{\\log T/T})$ times ideal utility. If a simulation with large $T$ (say $10^6$) reliably falls below that curve for some $\\alpha$, the bound is wrong. Alternatively, in the $\\alpha\\to 0$ limit, any fixed bidding distribution that achieves more than $3/5$ of ideal utility in the same simulation would refute Theorem 2.","tokens_in":19926,"feed_emoji":"🎲","tokens_out":7821,"duration_ms":73239,"temperature":0.7,"pith_summary":"Fair repeated allocation of a single resource without money has a known ceiling visible from several mechanisms: each agent can robustly guarantee only about half of the utility she would get from her fair share. This paper breaks that $1/2$ barrier in the repeated first-price auction with artificial currency, claiming every agent can guarantee $2-\\sqrt{2}\\approx 0.59$ of her ideal utility no matter how the others bid. The strategy, Randomized Robust Bidding, is to bid uniformly on $[0,1+\\sqrt{2}]$ whenever the realized value lies in the agent's top fair-share quantile. A reduction shows the worst-case value distribution is Bernoulli, and an upper bound shows no fixed bid distribution can guarantee more than $0.6$, so the randomized uniform strategy is almost optimal.","feed_headline":"Randomized bidding lifts guaranteed fair share from 50% to 59%","feed_subtitle":"Uniform random bids in artificial-currency auctions beat any fixed strategy and nearly hit the known ceiling.","key_machinery":"The load-bearing object is the bid CDF chosen by the agent: $F(x)=x/\\bar b$ on $[0,\\bar b]$, i.e. a uniform bid, with $\\bar b=1+\\sqrt{2}$. Against an adversary who spends a constant bid $b'\\ge 1$ until budget runs out, the agent's win share among her bidding rounds is $1-F(b')/b'$; maximizing the minimum over $b'$ forces $F$ linear and sets $\\bar b$ at the point where the agent neither overspends nor underspends. This cost-geometry identity, together with Lemma 1's Bernoulli reduction and the three-martingale concentration argument in Appendix A, carries the $2-\\sqrt{2}$ lower bound.","core_discovery":"The central claim is Theorem 1: the Randomized Robust Bidding strategy with bid support $[0,1+\\sqrt{2}]$ is $\\beta$-robust for $\\beta=2-\\sqrt{2}-O(\\sqrt{\\log T/T})$ for every nonnegative value distribution $F$ that the agent may have. Robustness means that against arbitrary, even collusive, behavior of the other agents, her long-run expected utility is at least $\\beta$ times her ideal utility. The proof rests on Lemma 1, which reduces any value distribution to the worst case $\\mathrm{Bernoulli}(\\alpha)$ by simulating the optimal ideal-utility allocation rule $\\rho^\\star$, and on a martingale bound synchronizing the agent's spending, her utility, and the adversary's spending. The paper also proves Theorem 2, that any strategy bidding from a fixed distribution whenever value is $1$ cannot be more than $3/5$-robust as $\\alpha\\to 0$, and Theorem 3, an explicit stationary adversary bid distribution that caps any agent strategy at $1-1/e+\\alpha/e+O(\\sqrt{\\log T/T})$ of ideal utility.","pith_inferences":["Beyond the paper, the same uniform-bid cost-geometry argument could be tested in other payment formats such as all-pay or second-price auctions, since the proof only uses the trade-off between win probability and expected payment per round.","Beyond the paper, the Bernoulli reduction hints that the essence of robust sharing is a binary high-value signal; if true for this mechanism, similar reductions may hold for correlated or non-stationary value processes under an appropriately redefined benchmark.","Beyond the paper, the small gap between $2-\\sqrt{2}\\approx 0.59$ and the $0.6$ static-policy ceiling suggests time-varying or history-dependent randomized strategies, not considered in the static analysis, deserve simulation to ask whether the constant can be pushed closer to $1-1/e$."],"forward_implications":["Under any equilibrium of the repeated first-price auction, every agent now gets at least about $0.59$ of her ideal utility, not just half.","With equal fair shares, the price of anarchy for social welfare is at most $1/(2-\\sqrt{2})\\approx 1.69$ in this mechanism.","The $3/5$ upper bound shows randomization is essential: any static bidding-distribution policy leaves a gap to the $2-\\sqrt{2}$ lower bound.","When all $n$ agents follow Randomized Robust Bidding, their realized utility approaches $1-(1-1/n)^n$, tending to $1-1/e$ as $n\\to\\infty$, which is the best any allocation rule could guarantee for symmetric Bernoulli agents.","The explicit adversary bid distribution of Theorem 3 turns the previously existential $1-1/e$ impossibility into a concrete stationary strategy that attains it up to small corrections."],"supporting_citations":[{"why":"Introduces the repeated Fisher-market first-price auction with artificial currency and defines ideal utility; supplies the baseline $1/2$-robust guarantee and the mechanism studied here.","marker":"[12]"},{"why":"Gives the $1-1/e$ upper bound on robust guarantees and derives the $1/2$ barrier under dynamic max-min fairness; it is the benchmark the new strategy approaches.","marker":"[10]"},{"why":"Extends the $1/2$-robust guarantee to reusable resources using reserve prices and fixed-bid reasoning; shows why fixed bidding seemed to cap guarantees.","marker":"[5]"},{"why":"Provides the deterministic fixed-bid robust strategy used as the experimental comparison baseline.","marker":"[11]"},{"why":"First models single-item repeated allocation with random valuations without money; anchors the model family.","marker":"[13]"}],"fun_headline_variants":["Randomized bids guarantee 59% fair share in online sharing","Better than 50: randomized strategy boosts online fairness","Randomized bidding beats static in fair resource sharing","Nearly optimal robust sharing via random bids","Randomized strategy lifts robust fair share to 59%"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The bound assumes the agent knows her own value distribution $F$ and can compute the optimal allocation rule $\\rho^\\star$ solving the ideal-utility program; with only finite samples or an estimated distribution, the stated guarantee is not directly implementable.","fun_headline_variants_meta":{"raw":{"variants":["Randomized bids guarantee 59% fair share in online sharing","Better than 50: randomized strategy boosts online fairness","Randomized bidding beats static in fair resource sharing","Nearly optimal robust sharing via random bids","Randomized strategy lifts robust fair share to 59%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000283,"raw_usage":{"total_tokens":1718,"prompt_tokens":1038,"completion_tokens":680,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":654,"completion_tokens_details":{"reasoning_tokens":605}},"tokens_in":654,"tokens_out":680,"duration_ms":6267,"temperature":1.0,"reasoning_tokens":605,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:11:05.145879+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the model with $\\mathrm{Bernoulli}(\\alpha)$ values and the Randomized Robust Bidding strategy against an adversary that bids a fixed $b'\\in[1,1+\\sqrt{2}]$ each round until its budget runs out; the theorem says the agent's per-round utility is at least $2-\\sqrt{2}-O(\\sqrt{\\log T/T})$ times ideal utility. If a simulation with large $T$ (say $10^6$) reliably falls below that curve for some $\\alpha$, the bound is wrong. Alternatively, in the $\\alpha\\to 0$ limit, any fixed bidding distribution that achieves more than $3/5$ of ideal utility in the same simulation would refute Theorem 2.","supporting_citations":[{"cited_title":"The remarkable robustness of the re- peated fisher market","cited_arxiv_id":null,"evidence_quote":"Introduces the repeated Fisher-market first-price auction with artificial currency and defines ideal utility; supplies the baseline $1/2$-robust guarantee and the mechanism studied here."},{"cited_title":"Robust pseudo-markets for reusable public resources","cited_arxiv_id":null,"evidence_quote":"Extends the $1/2$-robust guarantee to reusable resources using reserve prices and fixed-bid reasoning; shows why fixed bidding seemed to cap guarantees."},{"cited_title":"From monetary to non-monetary mech- anism design via artificial currencies","cited_arxiv_id":null,"evidence_quote":"Provides the deterministic fixed-bid robust strategy used as the experimental comparison baseline."},{"cited_title":"Strategy-proof allocation of multiple items between two agents without payments or priors","cited_arxiv_id":null,"evidence_quote":"First models single-item repeated allocation with random valuations without money; anchors the model family."}],"review_version":1}