CS Paper Radar

Who Moved the Frontier? Paying Open Frontier Challenges with Free Identities

Luca Zanolini, Duc V. Le

cs.GT cs.AIcs.LG ·submitted 2026-11-11 03:34 UTC · v1
theory

Abstract

In an open frontier challenge, anyone, person or AI agent, submits changes to a shared problem, and a change that beats the best measured score becomes the public baseline. How should it pay when identities are free? Rank prizes can be gamed: on a replay of one track of a recent challenge, one solver's steps under two identities would have taken first and second prize. We consider a prediction-market rule, proposed for machine-learning contests, that pays each accepted step for the progress it adds; with exact scores, among rules that see only a step's start and end, only these resist splitting and merging, and extra identities gain nothing. With noisy scores and independent normal runs, we prove that any payment that never takes money back and pays real improvements also pays something, on average, to a change that does nothing. We propose a fee per submission, at least what luck pays per attempt, that removes each attempt's expected profit if verifiers are honest and no submission is noisier than planned; nothing enforces that bound, and under noise the rule does not cap the total paid. If crediting another and faking credit to one's second account look the same, a rule that neither rewards fakes nor punishes honesty pays for credit at most what lying costs. We introduce a royalty on how much a later gain falls without the earlier change, which needs no claims but needs removable changes. For five public challenges, we name the rule our results would support.

Closest papers

Nearest neighbours by meaning across the whole index.

Pathwise Individual Rationality in Federated Learning: A Mechanism-Architecture Co-Design

cs.LG cs.GT ·2026-09-13 ·Amin Meghrazi, Srinivasan Parthasarathy, Andrew Perrault
theory similarity 0.60
Abstract · 27 pages, 9 figures, 8 tables

Participation in federated learning (FL) comes at a cost. Clients trade off privacy, communication, and compute costs for potentially greater gains in model efficacy. This paper explores this tradeoff under the aegis of individual rationality (IR) versus autarky, the basic game-theoretic requirement that the federation provide utility no worse than local training. Using the above as the design target, we examine pathwise performance of FL, as a per-round bound on cumulative surplus rather than only an asymptotic equilibrium guarantee under different degrees of client data heterogeneity. Along the learning path, clients can remain below their local-training baseline for hundreds of rounds. The natural remedy is to cap each client's per-round contribution so that this shortfall stays bounded. We prove that such a cap drives all contributions to zero, with high probability, when its tolerance is small relative to the warm-up deficit, and we observe learning collapse under it even at low heterogeneity. We then propose a design that combines a short-term participation guarantee, enforced after an announced grace window, with personalized model evaluation, while preserving the incentive properties of the underlying mechanism. We provide a theoretical basis for this approach and empirically demonstrate that, after the grace window, clients meet IR on nearly all rounds without harming overall performance under low to moderate heterogeneity; under severe heterogeneity, the design shows promising outcomes for clients compared to their local baseline at some cost in accuracy.

0.18

Tight Efficiency Guarantees for Strategyproof Linear Regression

cs.GT cs.DS ·2026-09-27 ·Yichen Huang, Yuqi Pan, Michael Mitzenmacher, Milind Tambe, Yiling Chen
similarity 0.58
Abstract

We study the trade-off between squared-error accuracy and incentive compatibility in linear regression. Agents report private labels associated with publicly known features and prefer predictions close to their true labels. Ordinary least squares (OLS) need not elicit truthful reports. For regression with $d$ parameters, we design a deterministic group-strategyproof mechanism achieving a $(d+1)$-approximation to the least-squares optimum and prove optimality even among universally strategyproof randomized mechanisms, answering an open question of Chen et al. (EC 2018). Relaxing universal strategyproofness to strategyproofness in expectation reveals a sharp separation: squared individual loss retains the factor $d+1$, while absolute individual loss admits the tight ratio $2-1/(\lceil d/2\rceil+1)$.

0.28

NFT-Based Reward Mechanisms: Sybil Farming, Vesting, and Stochastic Verification

cs.CE cs.DCcs.GT ·2026-09-11 ·Marco Alberto Javarone, Stefanos Leonardos, Carmine Ventre
similarity 0.57
Abstract

We study NFT-based reward mechanisms in which a user can create multiple identities and submit fraudulent claims that mature a reward subject to vesting. We assume that the issuer stochastically verifies claims during the vesting period and that identities can be linked into clusters so that the detection of one identity submitting a fraudulent claim causes the whole cluster to be forfeited through a penalty. A farmer's payoff is then non-linear in the number of identities: rewards increase linearly, while the probability of avoiding detection decreases geometrically. We characterise the optimal farming scale in the continuous relaxation of the problem. This allows us to derive a sufficient condition for deterrence and then consider the issuer's choice of reward vesting and claim verification. Vesting reduces the probability that a fraudulent claim is paid but also affects genuine participants, while verification is costly for the issuer. We characterise the sufficient deterrence frontier for the issuer in terms of auditing cost, vesting schedule, and penalty value. When small amounts of audit capacity can be added at negligible marginal cost, vesting alone is not optimal. We also distinguish the role of penalties from that of cluster-level auditing. Finally, we discuss the implications for NFT reward programmes on high-throughput ledgers, such as Hedera.

0.17

Guiding Worker Self-Selection in Crowdsourcing Contests: An LLM-Augmented Algorithmic Approach

cs.LG cs.GT ·2026-09-07 ·Nguyen Thach, Hau Chan, David Parkes, Karim Lakhani
published similarity 0.57
Abstract · Accepted to HCOMP 2026

Crowdsourcing platforms coordinate large pools of online workers who strategically choose which contests to enter and how much effort to invest. This self-selection can leave important contests with too few participants or too little effort, while workers may regret entering contests that leave them worse off than available alternatives. We study how platforms can recommend contests to workers using self-selection in Tullock contests (SSTC), a two-stage model in which workers first choose contests and then compete within them. We introduce GRAF, a greedy polynomial-time framework that constructs self-selection outcomes by ordering workers according to a score vector, with guarantees of zero worker regret and platform optimality in special cases of SSTC. Because effective orderings are difficult to design under worker heterogeneity, we propose LLMScore, an LLM-driven evolutionary framework that automatically designs GRAF's scoring algorithm. LLMScore addresses two challenges: jointly optimizing platform utility and worker satisfaction, and evaluating worker regret when exact computation is intractable. Trained only on small instances of one setting, it transfers to larger and structurally different settings; moreover, its output is human-readable code that platform operators can inspect and modify. Across 1,000 synthetic instances spanning four settings, GRAF with LLMScore consistently achieves high-quality, often near-optimal, outcomes with low worker regret, benefiting both platforms and workers.

0.40

A Compute Center Anyone Can Join: A Peer-to-Peer System for AI Inference

cs.AI cs.CRcs.DCcs.GT ·2026-11-01 ·Yimo Lin, Zhen Zhang
similarity 0.57
Abstract · 13 pages, 2 figures, 1 table. Ancillary files: model script reproducing all numerical results, and black-box probe data

Today, most people obtain AI inference by buying it from a small number of organizations that run large data centers, while many GPUs owned by individuals and small institutions sit idle for much of the day. Bitcoin showed that strangers can contribute resources under shared rules and receive checkable rewards, but it relies on an asymmetry: proof-of-work is expensive to produce and cheap to verify. Useful inference has no such asymmetry. We propose the Open Inference Market (OIM), which replaces the missing asymmetry with an economic mechanism. A worker delivers a result without knowing whether it will be audited; its unsettled earnings serve as collateral during a challenge window; and confirmed cheating forfeits all of it. We call this principle earnings as collateral. In a simplified model we show three things. The number of audits needed for deterrence is a constant per worker per day, independent of the worker's throughput, so the audited share falls as the network gets busier. A new worker can join with a short period of intensive auditing and a very small bond. And whether the mechanism works at all depends only on the ratio of the audit judge's false-flag rate to its detection rate. Under example parameters, about 0.3 replays per worker per day are enough to make cheating unprofitable for a rational worker. On this basis we lay out a path that hands four powers back to participants one at a time: owning compute, writing history, judging work, and releasing value. A compute center need not be a building; it can be a protocol that anyone can join.

0.33

Certified Corruption Budgets: Anytime-Valid Leaderboard Claims under Adaptive Rigging

cs.CR cs.AIstat.ME ·2026-10-06 ·Hamed Khosravi, Xiaoming Huo
benchmark similarity 0.57
Abstract

Public leaderboards for AI models are read continuously, and attackers can see every published standing. Vote rigging, selective disclosure of private variants, and benchmark contamination can each move a ranking. Existing guarantees assume genuine records or bound the corruption per step, which an attacker who corrupts in bursts evades. We introduce the certified corruption budget, a tolerance $\widehat{B}_t$ computed after $t$ records and published with each pairwise claim. With probability at least $1-α$, simultaneously at all times, the claim is correct or more than $\widehat{B}_t$ records were corrupted. It holds against attackers who watch every certificate, with no bound on their budget. Forged records and records altered once seen require different certificates: the certificate for forgeries fails, with probability approaching one, against an attacker who flips votes it has seen, while one that charges roughly twice as much per record remains valid, with constant bets even against attackers who see the future, and no smaller charge is valid at every level. The certified budget grows nearly as fast as any valid method allows: with a win fraction $\frac{1}{2}+δ$, each new record adds close to $2δ$ to the number of forged records the claim can withstand ($δ$ flipped). Publishing the best of $V$ private variants costs only an amount growing like $\log V$. In replays on 1.8 million Chatbot Arena votes, a few hundred rigged votes make standard confidence intervals certify false orderings, while ours stays valid. On real votes, our certificate shows that clearly separated models withstand about 2,000 forged votes.

0.36

Beyond Identity Creation: Bilinear Sybil Cost in Identities and Time

cs.CR ·2026-11-04 ·Homayoun Maleki, Nekane Sainz, Jon Legarda, Igor Santos-Grueiro
theory similarity 0.57
Abstract · 16 pages, 4 figures. Main paper followed by the supplementary material. Submitted to IEEE Transactions on Information Forensics and Security

Sybil defenses price the creation of an identity, yet influence goes, again and again, to active identities. We study the cost of maintaining influence. A defense has a bilinear Sybil cost with ratio $A$ if keeping $s$ identities active for $T$ periods costs at least $sT/A$ honest units: the average cost per identity-window is at least $1/A$ times an honest participant's cost. Recurrence alone does not guarantee this cost. The cost can be carried over from earlier periods, shared among many identities, or be negligible when fast hardware does the work of thousands of honest devices. We give four sufficient conditions for a defense that checks every identity each period to achieve bilinear Sybil cost: identity binding, freshness, a shared deadline, and sequential, non-batchable work. They yield two guarantees: a bilinear total cost, with $A$ the speed advantage of the adversary's fastest hardware, and, because the work must be fresh and finished by a common deadline, a bound on the identities active in a period by the processors running at that time. We prove that none of the four follows from the other three. A verifiable delay function on an identity-bound input meets all four without payments, with $A$ of 2 to 8 for CPUs and about 28 for a hypothetical ASIC, against $10^3$ to $10^7$ for hash puzzles. We measure one active identity per core per period against about 80,000 under a signed heartbeat, no gain from batching up to 1,000 identities, and rejection of all tested attacks.

0.20

Sustained Participation as a Security Resource: The Bounded Participation Channel

cs.CR ·2026-09-28 ·Homayoun Maleki, Nekane Sainz, Jon Legarda, Igor Santos-Grueiro
theory similarity 0.56
Abstract · 19 pages, 3 figures. Version 1

Can sustained, per-identity participation be engineered into a security resource? Most anti-Sybil defenses price identity creation rather than identity survival. Once admitted, an adversary may sustain many identities without paying a recurring cost. We introduce the Bounded Participation Channel (BPC), a formal primitive for repeatedly verifying participation window by window. BPC issues fresh, identity-bound challenges under a strict deadline and enforces four structural properties: identity binding, freshness, real-time response, and bounded per-channel throughput. Together, these yield a provable cost theorem: sustaining $s$ identities over $T$ windows requires $C(s,T) \geq sT/τ_h$ participation channel-windows. The guarantee is solver-agnostic: a channel may be operated by a human, an AI system, or a hybrid. We give a hash-based construction with publicly verifiable participation proofs, characterize four admissible challenge families, and evaluate two against GPT-4o, Gemini 2.5 Flash, and Claude Sonnet 4.5 across 600 trials. Despite near-perfect accuracy (97--100%) on the perceptual tasks, the evaluated automated channels remain throughput-bounded under the tested deployment conditions. The results illustrate a key distinction: solvability does not imply unlimited throughput. By requiring participation to be re-earned by every identity in every time window, BPC turns sustained participation into a measurable security resource with a linear structural cost floor, independent of whether the participation is supplied by humans, AI systems, or hybrids.

0.25