NeurIPS 2026 Papers

We consider a data seller who designs pricing mechanisms over multiple datasets to maximize revenue from budget-constrained buyers. The seller offers multiple datasets and assigns each a pricing function that maps the quantity purchased to a total payment. The goal is to design these pricing functions to maximize revenue, anticipating that buyers—who trade off accuracy gains against cost—choose bundles optimally subject to their budget constraints. Prior work [Chaudhury et al., 2026] studies such optimal pricing under the restriction that each dataset is assigned a linear price, and shows that computing optimal linear prices is computationally intractable. In contrast, we allow each dataset to be priced via a general function and show that this additional flexibility can not only increase the revenue but also restore tractability, yielding a surprising simultaneous improvement in economic performance and computational efficiency. Even when pricing functions are only required to be monotone and lower-continuous, optimal pricing admits a highly structured and simple form: each pricing function is piecewise linear and convex (PLC), and the optimal solution can be computed in polynomial time. Moreover, the total number of kinks across all pricing functions is bounded by the number of buyers. Consequently, when datasets significantly outnumber buyers, most pricing functions are effectively linear. We further empirically study the structure of optimal pricing by analyzing the number of kinks and the revenue gap between optimal nonlinear pricing and optimal linear pricing on simulations generated from a real dataset.

A planner in a network of strategic agents faces three entangled challenges: the optimum depends on agents' private information, queried agents may misreport to steer the outcome, and exact computation does not scale. We study these challenges in multi-activity network games with heterogeneous private technologies, in which the planner sets non-discriminatory prices. We show that the optimal prices admit a centrality-based decomposition of the welfare kernel: each agent's contribution scales with its squared centrality in a network reweighted by agents' preferences across activities. This decomposition motivates `Poll`, a polling algorithm in which the planner samples one agent per round, walks briefly through the agent's neighborhood, and updates the price from a local report. From the same decomposition flow three forms of efficiency: computationally, `Poll` uses significantly fewer operations than exact computation and other distributed methods; statistically, its query complexity scales with topology and preference heterogeneity rather than with population size; and economically, it converges to welfare-maximizing prices while inducing truthful reports and detecting adversarial deviations.

The integration of AI Overviews into search engines enhances user experience but diverts traffic from content creators, potentially discouraging high-quality content creation and causing user attrition that undermines long-term search engine profit. To address this issue, we propose a game-theoretic model of creator competition with costly effort, characterize equilibrium behavior, and design two incentive mechanisms: a \emph{citation mechanism} that references sources within an AI Overview, and a \emph{compensation mechanism} that offers monetary rewards to creators. For both cases, we provide structural insights for profit-maximizing mechanisms. Evaluations parameterized by real click data show that although AI Overviews harm long-term search engine profit, interventions based on our proposed mechanisms can increase long-term profit across a range of realistic scenarios, pointing toward a more sustainable trajectory for AI-enhanced search ecosystems.

Linear contextual bandit algorithms are typically built around pointwise optimism: the exploration bonus is chosen large enough to upper-bound the value of every action with high probability. We study an alternative principle of quasi-optimism, in which the index is deliberately allowed to be smaller than a valid confidence bound. We analyze the algorithmic framework, EQOL, that replaces the usual confidence-radius bonus with the capped quadratic bonus min(c₁,t ‖x‖²_{V_t⁻¹}, c₂,t ‖x‖_{V_t⁻¹}). This index is generally not optimistic, since its quadratic branch can be pointwise smaller than the OFUL bonus. We prove a general regret bound for arbitrary schedules (c₁,t, c₂,t), separating the exploration cost from the quasi-optimistic residual. With a single gap-agnostic tuning, EQOL recovers the high-probability minimax O(d√T) regret bound and, under a positive contextual margin, a uniform gap-dependent O(d²/Δ_min,T) bound. We also provide a geometric interpretation of EQOL through action-dependent ellipsoids, clarifying how quasi-optimism differs from simply shrinking a UCB bonus. Experiments on synthetic and real-data contextual bandit benchmarks show that EQOL substantially outperforms existing algorithms.

We consider learning-augmented mechanism design for facility location in the standard setting of locating a single facility on the line. Leveraging the given (imperfect) prediction on the optimal facility location, our goal is to design strategyproof (SP) mechanisms that truthfully elicit agent location preferences and determine facility locations that approximately minimize the $L_p$-norm social cost for $p \in (1, +\infty)$, achieving high \emph{consistency} (i.e., approximation ratios when the prediction is correct) and \emph{robustness} (i.e., approximation ratios when the prediction is incorrect). For deterministic SP mechanisms, we propose a family of generalized median mechanisms parameterized by a fraction \(t \in (0,1)\) of phantom points placed at the predicted location \(\pi\). We show that this mechanism achieves $\big(1+\big(\frac{1-t}{1+t}\big)^{\frac{1}{p-1}}\big)^{\frac{p-1}{p}}$-consistency and $\big(1+\big(\frac{1+t}{1-t}\big)^{\frac{1}{p-1}}\big)^{\frac{p-1}{p}}$-robustness and that no deterministic SP mechanism with the same consistency can obtain a better robustness. For randomized SP mechanisms, we analyze the upper bounds for several special cases, including (1) two-agent and (2) the squared cost settings, and provide a lower bound on consistency-robustness tradeoffs.

Motivated by modern marketplaces, where the platform or the seller routinely gathers detailed user profiles, we study a novel learning theoretic model that simultaneously involves information and mechanism design. Specifically, we consider the economic setting recently introduced by Bergemann et al, where in addition to the menu of quality-price pairs, the seller offers information on the value of the match between product quality and buyer's taste via a signaling scheme. We relax the assumption that the seller knows the buyers' belief about the distribution of tastes and study the sample requirements of designing a revenue maximizing scheme. We consider both the batch setting where we have access to data from a set of i.i.d. buyers and an online demand query model where we observe the buyers behaviors to seller's schemes. Despite the apparent non-convexity of the problem, we also give the first FPTAS to compute a scheme that maximizes the revenue within an arbitrarily small additive loss, which was unknown even in the previous result of Bergemann et al. Overall, this brings a new learning perspective in asymmetric economic settings where buyers and sellers know different types of information.

We study how to choose a probability distribution, or lottery, over $m$ alternatives for $n$ agents when each agent's acceptable lotteries form an unknown linear halfspace of the simplex. The learner observes only binary accept/reject membership queries. Prior work asks whether there exists a lottery accepted by every agent; we study the relaxation that minimizes the number of agents who reject the lottery. We first show that this problem is APX-hard even when all halfspaces are explicitly known and scores are binary. We then give exact algorithms under additional structure: fixed $m$, and a margin condition under which an optimal lottery can be replaced by one supported on $\mathcal{O}(\log n/\gamma^2)$ alternatives. With limited queries, uniform sampling of agents gives additive population guarantees after recovering the sampled agents' normalized halfspaces. For arbitrary $m$, we give a polynomial-time LP based on a one-sided margin penalty and prove a population guarantee depending on the number of true violations and the number of agents near their thresholds. Finally, we prove a tight deterministic lower bound: without a stochastic link between queried and unqueried agents, querying only $K$ distinct agents cannot guarantee additive gap below $n-K$, and this gap is achievable.

Randomization is often used to compromise among fixed policies, classifiers, or interventions, but affected stakeholders may be unable or unwilling to report utilities over all alternatives. We study a weaker feedback model in which, for each proposed lottery, each stakeholder reports only whether it is acceptable. Unlike prior work focused on finding a unanimously acceptable lottery when one exists, we allow unanimity to be impossible and seek lotteries that minimize aggregate acceptability violations. We model each stakeholder's acceptable lotteries by an unknown linear threshold rule over the lottery simplex, and the learner may only ask accept/reject queries. Since binary labels do not reveal utility shortfalls, and such shortfalls are not comparable across stakeholders, we measure violation geometrically: the Euclidean distance, within the affine hull of the simplex, to the stakeholder's normalized acceptance hyperplane. These distances are aggregated using the power mean. Our results characterize exactly which boundary information can be learned from these queries. A deterministic algorithm uses $\mathcal{O}(nm\log(m/\varepsilon))$ queries to recover the normalized boundary whenever violation distances are identifiable from query answers. Otherwise, queries determine the acceptable face but not the rate at which violation grows away from it; this ambiguity is unavoidable. When no ambiguity arises, the aggregate violation objective can be optimized exactly. When it does, we optimize a convex worst-case upper bound objective based on distance to the learned acceptable set and prove an additive loss bound of $\sqrt{2}(|B|/n)^{1/p}$. We also prove structural properties of optimal lotteries, including a support-size bound of $n+1$, and give a limited-budget algorithm with additive-$\alpha$ guarantees. Synthetic experiments illustrate the resulting breadth-depth tradeoff and the effect of the power-mean parameter $p$ on violation distribution.

As powerful AI systems reach and sometimes surpass the abilities of human experts across a range of cognitively demanding tasks, the problem of accurate oversight and supervision of these systems has become increasingly urgent. One promising approach is AI debate, which seeks to leverage a debate between two powerful AIs to break complex questions down into simpler claims that can be easily judged directly. Theoretical work on debate has formalized this intuition in the language of computational complexity theory, where the goal is to design protocols (i.e. rules of the debate game) that provide rigorous guarantees on correctness for judging solutions to complex problems with limited supervision. Specifically, the current best protocol has been shown to work for all problems that have sufficiently-stable decompositions into subproblems. In this paper we design a new protocol for this same class of problems that improves on the prior work in several ways. First, correctness holds in a worst-case rather than an average-case sense. Second, honesty and correctness is a dominant-strategy equilibrium for both debaters, rather than a Stackelberg equilibrium. Finally, we prove black-box lower bounds, showing that our new protocol is instance-wise optimal. That is, no protocol for this class of problems can outperform ours while making only black-box queries to human judgments. We obtain these results by relating the notion of stable problem decompositions to the concept of fractional block sensitivity from query complexity.

The trend towards larger training setups has brought a renewed interest in partially asynchronous two-phase optimizers which optimize locally and then synchronize across workers. Additionally, recent work suggests that the one-worker version of one of these algorithms, DiLoCo, shows promising results as a (synchronous) optimizer. Motivated by these studies we present an analysis of LA-DiLoCo, a simple member of the DiLoCo family, on a high-dimensional linear regression problem. We show that the one-worker variant, LA, provides a different tradeoff between signal and noise than SGD, which is beneficial in many scenarios. We also show that the multi-worker version generates more noise than the single worker version, but that this additional noise generation can be ameliorated by appropriate choice of hyperparameters. We conclude with an analysis of SLA --- LA with momentum --- and show that stacking two momentum operators gives an opportunity for acceleration via a non-linear transformation of the ``effective'' Hessian spectrum, which is maximized for Nesterov momentum. Altogether our results show that two-phase optimizers represent a fruitful new paradigm for understanding and improving training algorithms.

The *Game of Twenty Questions* is a classical problem where a questioner must identify a hidden item by asking binary questions. Although simple in form, the game is strategically challenging, especially when the questions are expressed in natural language. It is also a useful abstraction for realistic information-seeking tasks, such as medical diagnosis and troubleshooting. Existing approaches often rely on simplifying assumptions that degrade *worst-case* performance. This is an issue with serious implications in high-stakes applications. In this work, we introduce *Strategic Language Search* (SLS), an adversarial counterpart of Twenty Questions, and formalize it and its variants as two-player zero-sum extensive-form games. We then propose *Game of Thought* (GoT), a framework that applies game-theoretic techniques to approximate a Nash equilibrium (NE) strategy for the restricted variant of the game. Empirical results demonstrate that our approach consistently improves worst-case performance compared to (1) direct prompting-based methods and (2) heuristic-guided search methods across all tested settings.

The classic paradigm of language identification in the limit models learning as a game between an adversary, who reveals strings from an unknown target language, and a learner tasked with identifying that language. The recently introduced framework of language generation in the limit shifted the objective to better reflect modern language modeling, requiring the learner to produce valid, unseen strings from the target language. Related work highlighted a fundamental tension: a broad coverage of the target often comes at the cost of validity. We introduce a new notion of precision and recast this problem as the classic recall--precision trade-off. We analyze generation in the limit under varying constraints on enumeration, novelty, and validity, aimed at reflecting settings closer to those encountered by large language models. A key contribution is our analysis of learners that are not eventually valid: we allow infinitely many mistakes, provided their frequency tends to zero so that precision remains $1$. We show this relaxation can strictly increase recall when the adversary permanently withholds a large portion of the target language. We also study a continuous relaxation of the novelty constraint, requiring only that a fixed fraction of outputs are novel. Taken together, our results move toward a more realistic model of language generation where occasional errors and repetitions are unavoidable, but their rates are controlled.

Frontier AI systems are increasingly capable and deployed in high-stakes multi-agent environments. However, existing AI safety benchmarks largely evaluate single agents, leaving multi-agent risks such as coordination failure and conflict poorly understood. We introduce GT-HarmBench, a benchmark of 1,535 high-stakes scenarios spanning game-theoretic structures such as the Prisoner's Dilemma, Stag Hunt and Chicken. Scenarios are drawn from realistic AI risk contexts in the MIT AI Risk Repository. Across 15 frontier models, agents fail to choose socially beneficial actions in 38% of high-stakes cases, such as military escalation, election manipulation, and medical malpractice. We measure sensitivity to game-theoretic prompt framing and ordering, and analyze reasoning patterns driving failures. We further show that game-theoretic interventions improve socially beneficial outcomes by up to 18%. Our results highlight substantial reliability gaps and provide a broad standardized testbed for studying alignment in multi-agent environments.

We aim to design revenue-maximizing single-item auctions that are deterministic, strategy-proof, and ex post individually rational --- the quintessential fundamental model for optimal mechanism design. While Myerson's seminal work solved this model for independent bidders, straightforward extensions to correlated settings often result in non-monotonic, and therefore non-strategy-proof allocations. Critically, optimal allocation design for correlated bidders is NP-hard to approximate, rendering theoretical optimality guarantees in this domain computationally intractable. We establish a new standard of empirical rigor for this theoretically hard model by proposing an empirical pipeline. We synthesize neural interpolation of Myerson's greedy allocation based on marginal profits (the correlated variant of virtual valuation), formal neural verification to enforce exact strategy-proofness, and a constructive repair procedure. Empirically, our method is highly effective, consistently achieves near-optimal revenue across a wide range of distributions, including synthetic, adversarial, and real-world (consumer, financial, and industrial) datasets. Compared to existing manual and neural baselines, our approach shows substantial improvement, often reducing the revenue gap by an order of magnitude. Our study is also the first to introduce (unattainable) greedy revenue as a rigorous upper bound for empirical benchmarking, providing a definitive quantitative performance measure where true optima remain theoretically elusive. We demonstrate the generality of our approach by extending it to multi-unit auctions with unit demand and integrating our verification techniques into RegretNet to achieve exact strategy-proofness.

Deep learning systems are known to exhibit *implicit regularization* (alt. *implicit bias*), favoring simple solutions instead of merely minimizing the loss function. In some cases, we can analytically derive the implicit regularization -- connecting it to an equivalent penalty that augments the learning objective. However, modern deep learning systems are complex, carrying modifications to the training procedure and architecture (e.g. early stopping, minibatching, dropout) whose effects are not always directly interpretable. Although estimating the resulting implicit regularization could aid theorists in algorithm design and practitioners in interpreting their hyperparameter choices, this problem has received little direct attention. It is also tractable: regularization makes weight updates deviate from loss gradients, promising a signal for identifying implicit bias. Here we provide gradient matching methods that can be used to empirically estimate the implicit regularization. Our method works on networks with known regularization, recovering popular explicit penalties like $\ell_1$ and $\ell_2$. It also replicates known implicit effects, like the quadratic weight penalty induced by early stopping in gradient descent, demonstrating that it can be used to test theories of implicit regularization. Crucially, because our method is empirical, it can handle implicit regularization in arbitrary networks. We demonstrate this use by characterizing the effects of dropout in deep networks, showing implicit $\ell_2$ effects in this popular method. Our work shows that practitioners can use gradient matching to understand regularization in networks with implicit biases that are too complicated to derive analytically.

Recently, social choice theory has been found broadly useful for AI alignment and evaluation, often based on the axiomatic properties for combining preferences provided by social choice functions. However, for many sets of axioms, functions which $\textit{never}$ violate the axioms are known to not exist, e.g., Arrow's Impossibility Theorem. Recent work on learning novel rules to $\textit{minimize}$ axiom violations shows the effectiveness of machine learning but explores a limited class of axioms. In this work we show the effectiveness of standard social choice data structures as features for learning existing voting rules, resulting in networks that have better accuracy than past approaches while using an order of magnitude fewer parameters. Subsequently, we develop a process for $\textit{adding axiomatic properties}$ to existing voting rules. By building novel axiomatic loss functions we are able to use transfer learning to fine-tune existing voting rules in a way that quantitatively preserves their original behaviour while also exhibiting strong adherence to previously absent axiomatic properties, resulting in novel voting rules that are $\textit{closer}$ to the impossibility frontier than those in the machine learning or theoretical literature.

World models require state tracking, which is the ability to maintain a correct latent state across action sequences. Existing benchmarks are often synthetic or language-based, limiting their value as tests of structured state updates in realistic domains. We introduce Chess-World-Model, a large-scale state-tracking benchmark built from $10$ million real chess games, where models predict the exact board state reached after a sequence of legal moves. Alongside a held-out real-game split, we include an out-of-distribution split from uniformly random legal play, which tests whether models learn the transition rules rather than shortcuts from common human positions. Prior theoretical and empirical work has shown that Transformers struggle to state-track, while input-dependent linear RNNs require expressive state-transition matrices to do so. We therefore benchmark a causal Transformer, block-diagonal SLiCE, Mamba-3, and Gated DeltaNet with negative eigenvalues under a matched interface and training protocol. The recurrent models strongly outperform the Transformer at $3$ and $8$ million parameters. Real-game performance saturates above $18$ million parameters, but the random-uniform split remains discriminative up to $38$ million, exposing failures otherwise hidden by scale. Additionally, ablations show that less expressive state-transition mechanisms reduce performance on the out-of-distribution split for all three recurrent models. Together, these results establish Chess-World-Model as a practical large-scale benchmark for state tracking that exposes failures model scale would otherwise conceal.

Language model agents are becoming proficient executors at isolated, short-horizon tasks such as software engineering and customer service. Yet real-world challenges require a combination of sophisticated skills that remain largely untested in agents: (1) navigating long horizons amid uncertainty; (2) acquiring information in noisy environments; (3) adapting to a changing world; (4) orchestrating multiple moving parts toward a coherent goal. We introduce CEO-Bench, which evaluates these capabilities together by simulating a representative real-world task: operating a startup for 500 days. Given diverse and realistic company management tools, business databases, and social media, an agent needs to design pricing strategies, allocate operating budgets, analyze business data, respond to unexpected competitor moves, and more. Our evaluation shows that most state-of-the-art models struggle to succeed in this environment, and only one model (GPT-5.5) finishes the simulation above its $1M starting balance. CEO-Bench reimagines the role of AI in the future, shifting from solving isolated tasks to driving sustained, adaptive progress over time. We open source full code and trajectory.

Training powerful AI systems to exhibit desired behaviors hinges on the ability to provide accurate human supervision on increasingly complex tasks. A promising approach to this problem is to amplify human judgement by leveraging the power of two competing AIs in a debate about the correct solution to a given problem. Prior theoretical work has provided a complexity-theoretic formalization of AI debate, and posed the problem of designing protocols for AI debate that guarantee the correctness of human judgements for as complex a class of problems as possible. Recursive debates, in which debaters decompose a complex problem into simpler subproblems, hold promise for growing the class of problems that can be accurately judged in a debate. However, existing protocols for recursive debate run into the *obfuscated arguments problem*: a dishonest debater can use a computationally efficient strategy that forces an honest opponent to solve a computationally intractable problem to win. We mitigate this problem with a new recursive debate protocol that, under certain stability assumptions, ensures that an honest debater can win with a strategy requiring computational efficiency comparable to their opponent.