We study a multi-round mechanism design problem, where we interact with a set of agents over a sequence of rounds. We wish to design an incentive-compatible (IC) online learning scheme to maximize an application-specific objective within a given class of mechanisms, without prior knowledge of the agents' type distributions. Even if each mechanism in this class is IC in a single round, if an algorithm naively chooses from this class on each round, the entire learning process may not be IC against non-myopic buyers who appear over multiple rounds. On each round, our method randomly chooses between the recommendation of a weakly differentially private online learning algorithm (e.g., Hedge), and a commitment mechanism which penalizes non-truthful behavior. Our method is IC and achieves $O(T^{\frac{1+h}{2}})$ regret for the application-specific objective in an adversarial setting, where $h$ quantifies the long-sightedness of the agents. When compared to prior work, our approach is conceptually simpler,it applies to general mechanism design problems (beyond auctions), and its regret scales gracefully with the size of the mechanism class.
Erwan C. Escudie, Matthia Sabatelli, Jilles Steeve Dibangoye
Occupancy-state reductions make dynamic programming possible for zero-sum partially observable stochastic games (zs-POSGs). Existing point-based solvers usually optimise a central value function. This restores Bellman recursion, but it requires point-based updates over high-dimensional occupancy spaces. We introduce an approximate policy-iteration algorithm for finite-horizon zs-POSGs. The method maintains one policy per player and updates both jointly along occupancy trajectories induced by conservative policy updates. Instead of approximating a full central value function, each update uses a single supporting hyperplane induced by the current joint policy. The algorithm alternates local policy improvements, conservative updates, and persistent exploration. Computation is therefore concentrated on occupancy regions where the current joint policy is exploitable. On finite-horizon zero-sum POSG benchmarks, the method is competitive at small horizons and often improves the runtime-exploitability trade-off at larger horizons compared with PBVI, HSVI, and CFR+.
We study single-parameter, multi-buyer auctions in which buyers are subject to constraints that affect their bidding strategy. Such constraints arise in many real-world auction settings and fundamentally alter the auction design space: the revelation principle, envelope theorem, and Myerson's lemma no longer hold. Our focus is on a large family of constraints where the buyers do not have a hard budget-cap, but are restricted in how they can bid or spend their budget --- including no-overbidding, ex-post individual rationality (IR), and stagewise IR. We ask whether the seller can leverage the buyers' constraints to obtain improved payoff. We separate between \emph{revenue-aligned} seller objectives (revenue, welfare, or any linear combination), and \emph{consumer-aligned} seller objectives (e.g.\ consumer surplus). For the former, we establish a unified theory for all constraints in the family, which parallels Myerson's theory of optimal auctions for unconstrained buyers. We develop a new measure-theoretic technique to show that Myerson-style auctions remain optimal, despite the altered design space and failure of the classical theory's central tenets. In contrast, we show a consumer-aligned seller can leverage the buyers' strategic limitations to strictly outperform mechanisms that are classically incentive compatible. We also design an auction arbitrarily close to optimal for buyers who cannot tolerate temporary debt.
Token systems support repeated service exchange without monetary transfers, but their viability depends on the stability of token balances. We study token systems with compatibility constraints among agents. A requester is randomly sampled in each period, and only a few randomly sampled agents are available to provide service. We establish a necessary and sufficient condition for stability and show that the minimum-token rule, which selects the available provider with the lowest token balance, achieves the optimal stability region. We then apply this stability criterion to a random token system generated from stochastic block models with uniformly sampled requesters. We tightly characterize the stability regime by identifying two obstructions to stability: insufficient service opportunities for a group of communities or for an individual agent.
Xi Zheng, Yinghui Huang, Xiangyu Chang, Ruoxi Jia, Yong Tan
Modern AI model markets assemble models from heterogeneous pipeline contributions, including raw data, derivative data, and data-related services, whose value can depend on upstream inputs and inherited model states. Conventional valuation approaches focus on data contributions without explicitly accounting for these production relationships. They can therefore misattribute value by evaluating contributions outside their upstream production context. We formalize this pipeline-context valuation mismatch and develop Asymmetric Data Shapley (ADS), a unified framework for structure-aware value attribution. ADS translates documented production relationships into ordered valuation groups and evaluates contributions among peers conditional on their upstream production context. We provide an axiomatic characterization of the resulting allocation and quantify allocation uncertainty when evidence supports multiple valuation structures. To support valuation at larger scales or with costly utility evaluations, we develop a Monte Carlo estimator (MC-ADS) and a surrogate-assisted estimator (SA-MC-ADS). Experiments show that ignoring production dependencies systematically shifts value toward redundant derivative data and away from useful upstream data and services. Moreover, experiments on derivative data selection and on dataset procurement during multi-stage large language model fine-tuning show that decisions guided by ADS improve downstream model performance relative to the respective benchmarks.
Karen Frilya Celine, Warut Suksompong, Nicholas Teh
When allocating indivisible goods, the maximum Nash welfare rule is known to be the unique welfarist rule satisfying envy-freeness up to one good. We strengthen this characterization by showing that envy-freeness up to one good can be replaced by substantially weaker fairness requirements: envy-freeness up to $k$ goods or proportionality up to $k$ goods, for any fixed $k$. Our characterization holds even for profiles with identical goods.
We consider $T$ repeated second-price auctions across $n$ pacing bidders with i.i.d. item arrivals, and show that it is computationally impossible for all bidders to achieve no-regret simultaneously while satisfying their respective budget or return-on-investment constraints. Therefore, in the prominent internet auction systems where buyers simultaneously deploy pacing algorithms or automated bidding agents, we cannot hope to achieve joint no-regret guarantees in general. We establish a deterministic relationship that high variance in online bidding systems implies high regret. By showing that one can extract a pacing equilibrium from a low-variance system, we prove PPAD-hardness of attaining joint no-regret. For several widely used bidding algorithms, we also show evidence from dynamical systems and numerical simulations that they can indeed display high-variance behavior through cycling, even on simple market instances.
We present general upper and lower bounds on the optimal error exponent for the Active Simple Hypothesis Testing (ASHT) problem. ASHT has been extensively studied across diverse fields including Information Theory, Bandits, and Operations Research, a precise characterization of this optimal exponent has remained elusive. This work combines a recent Partial Differential Equation (PDE) characterization of the optimal exponent by Vijayan (2025) with the comparison principle of viscosity solutions of Hamilton-Jacobi PDEs. This leads to bounds that are parametrized by convex functions, sets and lower Hamiltonian relaxations, a flexibility that generalizes many known results in the literature.
Miner extractable value (MEV) poses a persistent challenge for blockchain ecosystems. It arises from the fact that a block builder can exploit its unilateral control over transaction inclusion and ordering to extract profit, potentially at users' expense. Recent work has explored consensus-aided mechanism design to mitigate MEV. This approach combines generic consensus-layer guarantees with application-layer mechanisms that use these guarantees to address application-specific MEV problems. Prior work exemplifies this approach for automated market makers (AMMs). When the consensus layer offers fair sequencing, which orders transactions according to their arrival times, their proposed mechanism achieves incentive compatibility (IC) and weak local efficiency (wLE). Informally, IC rules out profitable strategic deviations by users and builders. Meanwhile, wLE ensures that after execution, any order willing to trade at the initial price cannot benefit from further trade with the pool at the ending marginal price. In this work, we resolve the main open question left by prior works: whether IC and wLE can be achieved under plain consensus (e.g., current Ethereum) without fair sequencing. We prove that no deterministic, anonymous batch AMM can achieve both properties. The impossibility holds even when the consensus layer guarantees censorship resilience and block space is unlimited, establishing the first separation between censorship resilience and fair sequencing in the context of decentralized mechanism design. Our impossibility proof combines three strategic capabilities: creating Sybil identities, over-reporting budgets, and misreporting values. We further show the tightness of our impossibility result: removing any one from the strategy space restores feasibility under censorship resilience. Specifically, we construct a mechanism achieving IC and wLE for each restricted setting.
The adaptive clinching auction of Dobzinski, Lavi, and Nisan (FOCS'08) is a cornerstone of mechanism design with budget-constrained bidders, and it has since inspired a broad range of extensions to substantially richer market settings. Adaptive clinching enjoys compelling guarantees: it is Pareto optimal, and truthful bidding is a dominant strategy whenever budgets cannot be overreported. In many real-world environments, however, identities are cheap to create, making resilience to Sybil attacks an additional requirement. Whether the guarantees of adaptive clinching survive when a bidder can split its budget across fake identities has remained open. We introduce a generalized framework for adaptive clinching and prove that it satisfies Sybil-robust incentive compatibility: a bidder cannot benefit from splitting into any finite number of identities with arbitrary value reports, provided their aggregate reported budget does not exceed the bidder's enforceable true budget. Sybil resilience thus joins the list of ideal properties of adaptive clinching. Our work is motivated by practical problems in decentralized finance, where automated market makers (AMMs) are among the most widely used applications. We design a new AMM mechanism that extends classical adaptive clinching in two ways: it supports a two-sided market and protects against two-sided strategies, and it allows the supply function to depend on the auction state. Its one-sided special case is captured by our generalized adaptive clinching framework, and our proof techniques show that the full two-sided mechanism simultaneously satisfies Sybil-robust incentive compatibility and a relaxed notion of Pareto optimality. We argue that these guarantees are essentially the best possible via impossibility results. More broadly, our work reveals new connections between classical algorithmic game theory and modern decentralized blockchains.
Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis
Recent work has shown that, in zero-sum games, an optimizer can extract $Ω(\sqrt{T})$ strategic surplus---cumulative payoff above the minimax benchmark---against noiseless no-regret learners with a constant step size. However, in practice, learners often act on perturbed payoff scores and use decaying learning rates $η_t$. Since existing extraction mechanisms rely on exact scores, a natural question is whether noise shields the learner from exploitation and eliminates surplus altogether. We address this question for the widely used class of Follow-the-Regularized-Leader (FTRL) algorithms. Under standard regularity conditions, we establish three results, none of which assumes independence of the noise. First, under summability conditions, passive play of a strategy fixed independently of the horizon earns at most constant surplus. Second, we design a new mechanism that exploits the learner's noise-dependent response: a clairvoyant optimizer who knows the update rule and the limiting mean response secures $Ω(1/η_T)$ surplus whenever that mean is profitable. Third, even when that mean is not profitable, active alternating play extracts $Ω(\sum_{t<T}η_t)$ surplus by exploiting the learner's movement rather than its location, under suitable responsiveness and stability conditions. Finally, at the canonical learning rate $η_t\propto t^{-1/2}$, we recover the noiseless $Ω(\sqrt{T})$ rate for mean-zero, finite-variance perturbations---whether fresh with arbitrary temporal dependence or accumulated from i.i.d. increments---provided the limiting mean response is profitable.
We study facility location in multidimensional normed spaces with the objective of minimizing social cost, the sum of agents' distances to their nearest facility. A deterministic mechanism selects $k$ facility locations based on the reports of $n$ agents and is strategyproof (SP) if no agent can reduce her distance by misreporting her location. We establish optimal approximation ratios and impossibility results. For a single facility in the Euclidean plane, we prove that the optimal approximation ratios among deterministic SP mechanisms are exactly those obtained by Goel and Hann-Caruthers [SCW 2023] for the coordinate-wise median (CM): $\frac{\sqrt{2(n^2+1)}}{n+1}$ for odd $n\ge3$ and $\sqrt{2}$ for even $n\ge4$. We remove the anonymity assumption from their optimality result. However, CM is not always optimal in non-Euclidean spaces: we give an SP mechanism that minimizes social cost exactly in $\ell_\infty^d$, whereas CM has a tight uniform approximation ratio of $2$ already in the plane. We then consider two facilities in $\ell_p$ spaces with $1<p<\infty$ and prove two impossibility results for every $n>2$. In the plane, no deterministic SP mechanism has a finite approximation ratio. In higher dimensions, the same impossibility holds for anonymous deterministic SP mechanisms. Finally, a reduction using distant agents and a limiting argument extends both impossibility results to every $k>2$ with $n>k$.
George Christodoulou, Vasilis Christoforidis, Alkmini Sgouritsa, Ioannis Vlachos
The inefficiency of decentralized resource allocation is classically measured by the Price of Anarchy (PoA) and the Price of Stability (PoS). The most widely studied and foundational class of these models are atomic and non-atomic congestion games, for which a robust theory quantifying the inefficiency of equilibria is well-established. To mitigate the effects of selfish behavior, we employ Coordination Mechanisms, which modify resource costs to incentivize socially improved equilibria. However, standard Coordination Mechanisms assume unknown, adversarial demand, restricting positive results mainly to specialized networks such as parallel links. We address this limitation by studying learning-augmented coordination mechanisms, where the mechanism is endowed with a potentially inaccurate prediction of the demand. We study general atomic and non-atomic congestion games with polynomial latency functions of degree $d$. Our main positive result is a learning-augmented coordination mechanism tuned by a confidence parameter $β$ which achieves a "best of both worlds" type of result: approximately optimal performance for an accurate prediction without sacrificing the worst-case guarantee of a good equilibrium (PoS). We further establish bounds on PoA-Robustness (worst equilibrium performance under cost modification). Our construction relies on transforming approximate equilibria of the original game into exact equilibria of the modified game using an approximate potential function. We complement our positive results with impossibility results. We first show that requiring all equilibria to have optimal social cost under an accurate prediction precludes bounded robustness. We also show a strong error tolerance limit in non-atomic games: even infinitesimal prediction errors can cause the performance of a mechanism with optimal consistency to revert to the original PoA.
Competing firms that share a population of risky customers face a decentralized risk detection problem in which each firm holds fragmentary information whose aggregation would generate social value, but private incentives impede truthful sharing. We develop a dynamic mechanism design framework for this setting and identify three strategic frictions that distinguish it from classical mechanism design with decentralized information: compliance moral hazard, adversarial adaptation, and information destruction through intervention. A temporal value assignment (TVA) mechanism credits firms using a strictly proper scoring rule applied to discounted verified outcomes; under stated assumptions, TVA implements truthful posterior reporting as a Bayes--Nash equilibrium (uniquely optimal at each edge in large federations, with $O(1/m)$ shading in finite systems). A network Shapley characterization shows that under edge-additive coalition value, each firm's marginal contribution is proportional to its weighted cross-firm interaction degree, yielding a sharp prescription for coalition design that prioritizes inter-firm volume over firm size. Embedding TVA in a model of competition among firms, we establish a welfare ordering across four regulatory regimes (autarky, voluntary federation, mandated full sharing, TVA) and identify conditions under which information-sharing mandates without compatible incentive design reduce welfare below autarky: a ``backfiring mandate.'' We illustrate the framework on a 1.4M-transaction synthetic anti-money-laundering benchmark; the same machinery extends to platform fraud, cybersecurity threat intelligence, and supply chain risk detection.
Strategic replicators combine evaluated choice and reproductive transmission. An agent chooses among alternatives; the consequences of those choices influence continuation or reproduction; and successors receive organization that shapes later choices. Artificial intelligence makes this combination salient when agents have authority to create, configure, or retire software instances. This paper organizes the general logic around three principles: situated choice, reproductive transmission, and institution-mediated coupling. The principles are constitutive rather than predictions of growth or improvement. A common representation distinguishes carriers, inherited records, decision owners, and the mechanisms that allocate consequences. Actual parent-descendant attribution yields a selection-transmission identity. Separate compatibility results characterize when utility-maximizing choices also maximize a reproductive criterion. Gode and Sunder's zero-intelligence traders reveal the role of institutions: enforced properties can hold across different decision procedures, while aggregate efficiency alone determines neither individual gains nor descent. A worked market-rent-entry model connects institutional profits to actual offspring, with its occurrence-level ancestry bridge checked in Lean. A direct-deployment example then shows evaluated preferences undergoing selection without presupposing that every chooser values reproduction. Formal appendices develop games with endogenous players, deployment-induced tipping, endogenous electorates, and the production of institutions, with models, proofs, and examples. The paper and its supporting formal artifacts are a prototype kernel with a generative function: an instrument for constructing models of strategic replication. The results are formal; their application to deployed populations and their empirical implications remain to be tested.
Replicator dynamics, the central model of evolutionary game theory, describe populations evolving under selection and agents learning by trial and error. They also admit a third use: continuous-time Bayesian inference, in which an agent planning against an opponent accumulates evidence for each candidate strategy. Here we show that this use divides all two-player games into two classes. With the standard expected-utility payoff, the dynamics can be expressed as Bayesian updating only in games (with any number of actions) where no player has a dominant strategy. The logarithmic payoff of Ay and Erb admits the Bayesian representation in every game. Coordination, anti-coordination, and cyclic games share qualitative dynamics under both payoff definitions, with equilibria displaced and selection thresholds shifted. In contrast, the flows of every game with a dominant strategy are reversed between the payoff definitions, with the strictly dominant strategy eliminated under logarithmic payoffs. Cooperation therefore emerges in the Prisoner's Dilemma, and games of common interest converge to mutual defection. For two-action games the classification is complete and rests on an exact Hamiltonian structure shared by both payoff definitions. The structure gives a behavioural test: cycles in the classic Matching Pennies game have amplitude-independent period (isochronous) under logarithmic payoffs, but not under expected utility. Logarithmic evidence integration thus determines which strategic outcomes dynamical selection can reach, wherever learning approximates Bayesian updating.
We study how learning algorithm design shapes equilibrium selection in infinite-horizon discounted Markov games with finite states and actions. Each episode, players choose smooth best responses to beliefs about opponents' policies, test them using noisy observations, and resample rejected beliefs or explore at rates determined by increasing transformations of their discounted values. We show that stochastically stable states induce approximate stationary Nash equilibria maximizing the minimum transformed discounted value across players, with transformations governing which players selection favors. In repeated games with bounded recall of noisy public signals, longer recall weakly increases the selected minimum transformed value. In repeated Cournot games, every stochastically stable state induces an approximate public perfect equilibrium whose minimum discounted profit across firms exceeds the Cournot-Nash benchmark. Collusion is therefore inevitable under these conditions and learning dynamics. For symmetric firms, selected profits can approach the monopoly benchmark arbitrarily closely. These results offer a novel equilibrium-selection perspective on algorithmic collusion.
Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis
We study the computational complexity of clairvoyant strategy optimization against a known online learner in finite-horizon repeated games. In general-sum games with bounded payoffs, unless $\mathsf{P}=\mathsf{NP}$, no polynomial-time optimizer can achieve a reward within $cT$ of the reward of the optimal pure-action sequence for an absolute constant $c>0$, even when allowed to output explicitly represented mixed strategies at every round. Our hardness result strengthens prior work along two complementary axes: it extends to a broader class of learning dynamics, including widely used mean-based algorithms, answering an open question of Assos, Dagan, and Rajaraman (2025) for learners beyond multiplicative weights; and it permits mixed outputs while retaining the weaker pure-sequence benchmark. Thus, neither mixed strategies nor algorithmic specificity removes the computational obstruction in general-sum games. In sharp contrast, zero-sum games exhibit the reverse phenomenon: deterministic pure actions suffice for efficiently recovering the leading surplus guarantees previously obtained through mixed play against Follow-the-Regularized-Leader (FTRL) opponents. Thus, the two regimes form a striking mirror image: mixed play cannot overcome general-sum hardness even against a pure benchmark, whereas pure play retains the full surplus guarantees of mixed strategies in zero-sum games.
Improving on a baseline requires exploring away from it, precisely where its performance may be lost. We propose DUET (Doubling Under Empirical Tests), a horizon-free phased mixing scheme for combinatorial semi-bandits with arbitrary finite action sets. Two observable tests decide when to double the learning weight and when to double the empirical-regret budget and restart. We instantiate the scheme with entropy-FTRL in mixed phases and hybrid-FTRL in pure phases. Assuming the baseline selects every arm with positive probability, this instantiation keeps expected baseline regret logarithmic in $T$, while its expected regret to every fixed action is $\widetilde{O}(\sqrt{T})$ under non-anticipating adversarial losses and polylogarithmic, gap-dependent, under i.i.d. losses with a unique optimal action. All three guarantees hold at every deterministic horizon, and the algorithm knows neither the horizon, nor the gap, nor the environment type. Baseline protection, adversarial robustness, and stochastic adaptivity thus come from one scheme and two base learners, at the price of a logarithm.
Reach-avoid (RA) games have significant applications in security and defense, particularly for unmanned aerial vehicles (UAVs). These problems are inherently challenging due to the need to consider obstacles, consider the adversarial nature of opponents, ensure optimality, and account for nonlinear dynamics. Hamilton-Jacobi (HJ) reachability analysis has emerged as a powerful tool for tackling these challenges; however, while it has been applied to games involving two spatial dimensions, directly extending this approach to three spatial dimensions is impossible due to high dimensionality. On the other hand, alternative approaches for solving RA games lack the generality to consider games with three spatial dimensions involving agents with non-trivial system dynamics. In this work, we propose a novel framework for dimensionality reduction by decomposing the problem into a horizontal RA sub-game and a vertical RA sub-game. We then solve each sub-game using HJ reachability analysis and consider second-order dynamics that account for the defender's acceleration. To reconstruct the solution to the original RA game from the sub-games, we introduce a HJ-based tracking control algorithm in each sub-game that not only guarantees capture of the attacker but also tracking of the attacker thereafter. We prove the conditions under which the capture guarantees are maintained. The effectiveness of our approach is demonstrated via numerical simulations, showing that the decomposition maintains optimality and guarantees in the original problem. Our methods are also validated in a Gazebo physics simulator, achieving successful capture of quadrotors in three spatial dimensions space for the first time to the best of our knowledge.
Ioannis Panageas, Avi Shein, Shayan Taherijam, Vijay V. Vazirani
The Hylland-Zeckhauser (HZ) mechanism provides a market-based approach to one-sided matching, making efficient equilibrium computation central to its implementation. Bi-valued utilities admit a strongly polynomial-time algorithm [VY], whereas with four values per buyer, the problem is PPAD-hard under inverse polynomial approximation [CCPY]. To understand the tractability boundary, we study two extensions of the bi-valued case: a third linear utility value and separable concave utilities with two common marginal slopes. For every fixed rational $a\in(0,1)$, we prove that computing a normalized additive $\varepsilon_{*}(a)/N$-equilibrium in an $N$-buyer HZ market is PPAD-hard for some constant $\varepsilon_{*}(a)>0$, even when all utilities belong to the same prescribed set $\{0,a,1\}$. This resolves the main question left open by [VY, CCPY]: whether three utility values already suffice for PPAD-hardness. Using the same market gadgets, we show that hardness at a specified constant accuracy on the recognizable family generated by our construction is equivalent to the PCP-for-PPAD conjecture. Consequently, assuming that conjecture, general markets over $\{0,a,1\}$ admit no PTAS unless $\mathrm{PPAD}\subseteq\mathrm{P}$. For the concave extension, we compute an exact equilibrium in polynomial time with two marginal slopes common across goods for each buyer and arbitrary rational buyer--good breakpoints. The algorithm selects a cheapest utility-maximizing bundle for each buyer. With three common marginal slopes, suitable breakpoints encode the three valued linear case, yielding PPAD-hardness. Thus, our paper identifies two thresholds separating tractable and intractable cases of HZ models with utility functions specified by utility values or marginal slopes. In both cases, the tractability threshold lies between two and three.
Sai Ganesh Nagarajan, Toshinori Yamauchi, Hiroshi Kera
Shapley-value-based explanations are widely used for feature attribution in machine learning. However, in computer vision, a feature may reduce the target-class score when added to the complete genuine image, even when the predicted label remains unchanged. We formalize such features as contextual distractors and investigate their attributions under semivalues and the least core. Under a weak average marginal monotonicity assumption, we derive quantitative semivalue--least-core gap bounds and sufficient conditions based on the probability of sampling smaller contexts. We further show that shifting semivalue weights toward larger contexts decreases the signed gap. Finally, controlled image-classification experiments and evaluations on Salient ImageNet provide strong empirical support for our theoretical findings.
Dynamic creative optimization decides which creative of an ad to render for each request. Recent work places that choice before ad ranking, but relies on deterministic point predictors with no calibrated uncertainty. AI-generated content has made creatives nearly free, while feedback per creative remains sparse and selection faces a tight latency budget. We introduce a creative pre-ranker that scores every recalled creative and shortlists each campaign's pool before the per-user ranker runs. Creatives sit in a hierarchy of audience segment, advertised item, campaign and creative, so a cold creative falls back on what its parent levels have earned, and how much it borrows from its parents is set in closed form from historical logs, with one parameter per level and nothing tuned. To stay within the latency budget, the pre-ranker predicts for an audience segment rather than an individual user, from per-attribute counters. It selects by a single Thompson draw per creative, balancing exploration and exploitation so that a new creative still has a chance to be learned. Replaying Roblox Sponsored-ads traffic over campaigns with competing creatives, the shortlist lifts predicted play-through rate by 8.14% against 2.80% for an equally sized random shortlist, forwards more than 40% fewer creatives than the full pool, and adds only 0.2% to serving time. After an A/B test on live traffic, the method now serves in production at Roblox.
Many academic disciplines (in particular, mathematics and the theoretical sciences) face difficult questions about how to adapt their practices to the rise of highly capable artificial intelligence (AI). Before AI, a well-written research paper with a strong theoretical result acted as a reliable signal that its authors understood their field in depth. Now that AI is widely accessible, such signals have become cheaper to produce. As a result, they no longer reliably sort academics by their level of understanding. This has direct consequences for academic hiring. The age of AI raises a question for each side of the academic job market. Should an early-career researcher invest in a deep understanding of their field, or instead use AI to build a longer resume with many papers? Should a recruiter favor applicants with fewer papers who pass an interview aimed at probing understanding, or insist on both publication volume and a pass? In this paper, we develop a game-theoretic model of this two-sided dilemma. We classify all pure-strategy equilibria that can arise in this game and use learning simulations to identify the behaviors that populations of applicants and recruiters may learn to adopt. Our analysis provides a framework for reasoning about how academic hiring can adapt to AI and for evaluating practices that preserve the value of deep understanding.
Emile Martinez, Felipe Garrido-Lucero, Umberto Grandi, Sebastian Pérez-Salazar
We introduce the *prophet inequality with delayed and uncertain acceptance* model, a variant of the classical prophet inequality in which a decision-maker sequentially evaluates options whose acceptance is uncertain and revealed only after a random delay. At each time step, the decision-maker observes the realized value of the arriving option and must irrevocably decide whether to select it or continue searching. Once an option is selected, the process is suspended for a delay drawn from a known distribution with expectation $d$, during which no other option can be considered. When the delay expires, the selection succeeds with a known probability. If it succeeds, the decision-maker receives the realized value and the process terminates; otherwise, the search resumes. In addition to the online decision-maker, we consider two stronger benchmarks: the value-aware decision-maker, who knows all value realizations in advance but not the acceptance outcomes, and the prophet, who knows both the values and the acceptance outcomes. We show that, in the worst case, both decision-makers achieve a $1/(d + 2)$ fraction of the prophet's value, while the decision-maker achieves half of the value-aware decision-maker's value. We then turn to the no-delay case, where we establish an equivalence between our model and the classical prophet inequality, and show that the value-aware decision-maker beats the $1/2$ barrier against the prophet whenever all acceptance probabilities are bounded away from $0$.
Michel Grabisch, Elena Parilina, Agnieszka Rusinowska, Georges Zaccour
Dealing with climate change requires that all countries engage in costly efforts to reduce their emissions. Reaching this objective has so far been elusive because it is in the best interest of each country to let the others do the effort and benefit itself from a better environment. The presence of negative externalities and strategic behavior have made game theory a natural paradigm to design an international environmental agreement (IEA) that codifies what countries should do. Considering that countries are sovereign and no supranational entity can impose an agreement, a stream of literature adopted a noncooperative mode of play to the formation of an environmental coalition. On the other hand, as joint optimization of all countries' payoff leads to the best outcome, cooperative games approach has also been proposed to share the cost of climate change. Both approaches have their pros and cons.
We develop a unified framework for assortment optimization and matching under multinomial logit (MNL) choice, yielding simple algorithms and analyses across a broad class of problems. The framework centers on a single-customer assortment problem in which the firm commits to eligible products before their independent availabilities are revealed. A simple threshold policy achieves a tight $1/2$ guarantee against a benchmark that selects its assortment after observing availability and may control dependence subject to the same marginal probability bounds. This guarantee accommodates cardinality constraints and adversarial removal of excess available products. Combined with problem-specific linear programming relaxations, the framework yields $1/2$ guarantees for standard two-sided assortment optimization, customization under mixtures of MNL models, ride-hailing notifications, multi-round broadcast matching, and MNL prophet inequalities, and a $1/4$ guarantee for fully static two-sided assortment optimization. Across these applications, we improve approximation factors, extend guarantees to more general revenues and cardinality constraints, and retain existing factors against stronger benchmarks.
In token-priced language model services, users can see the prompts they submit and the answers they receive, but may also pay for internal reasoning and candidate answers that are not shown in the final response. This paper develops a three-party service model to study how charging for this intermediate computation shapes providers' decisions and social welfare. Users purchase answers from a model firm that pays an execution cloud, with either supplier controlling the computation budget. The model separates user billing from upstream payments and identifies when metered pricing encourages excessive generation, when fixed service prices restrict valuable computation, and how responsibility for execution costs changes these choices. A LiveCodeBench study measures answer quality, latency, token use, and resource consumption across five model deployments, with numerical billing comparisons for the three covered by archived tariffs. At equal average charges on the reference workload, the calibrated comparisons show that billing structure changes both service participation and the computation budgets suppliers select. For accepted services with different budgets, the measured outcomes define the user-value thresholds at which their welfare ranking reverses. Metered pricing yields higher welfare when the additional inference it induces creates net social value, whereas fixed service pricing is preferable when the costs of that computation outweigh its benefits.
Lightning routing nodes lend their channel balance for a posted fee. Operators' tools move that fee with the balance around a hand-set level, and which part of the fee drives revenue is unclear. We present Trim, which models a channel as a two-sided inventory with costly refills. Its optimal fee is a level, set by demand and replenishment, plus a balance skew, the shadow price of liquidity. The level is first order: no fee rule beats the ceiling demand and replenishment set, and on exactly solved channels the best flat fee comes within $1.6\%$ of the optimum at the median, whereas a level off by a factor of two loses tens of percent. The skew is second-order insurance: it adds at most what the flow-balancing flat fee loses to refused forwards. So the level should be chosen: Trim's rule traces the revenue--success frontier, posts one level on every channel, and adds a skew only where refills stay frequent and costly. On a 2026 snapshot with synthetic payments, no tuned tool beats that frontier by over a few percent, and a skew changes gross revenue by a few percent.
We study welfare maximization in a contract model with $m$ principals who privately value a public project's success and $n$ agents whose costly effort is unobservable. Contracts induce truthful dominant strategies for principals and equilibrium effort by agents, maximizing the expected total value of eligible principals. We develop three tools: a broker that separates payments from principals and payments to agents, an extension of Myerson's Lemma characterizing dominant-strategy incentive compatibility (DSIC), and a black-box reduction to budget-constrained single-principal contract design. When the success probability is a strictly monotone XOS function of agents' actions, these tools yield three results. First, a deterministic DSIC contract achieves a constant approximation against a benchmark that qualifies every principal and maximizes success probability using budget $\sum_j v^j$, but may violate budget balance (BB). Second, against benchmarks with budgets at least the largest principal value, deterministic DSIC and BB contracts admit no finite approximation guarantee, even with two agents. Universally DSIC and universally BB randomized contracts have an $Ω(n)$ approximation lower bound, even for a fixed number of principals. Third, using one quarter of the optimal fixed-price revenue supported by at least two principals as the benchmark budget, we obtain a universally DSIC and universally BB randomized contract with an $O(\log m)$ approximation ratio independent of $n$.