Papers

We study the problem of computing the tightest \(\alpha\)-potential approximation of a general-sum game over continuous action spaces, within a prescribed class of potential functions and when each player has access only to its own utility function. The difficulty is twofold: the approximation error involves a worst-case search over an infinite set of unilateral deviations, and the required utility information is distributed across players. For a linear-in-parameters potential class, we use an exact finite-tuple reformulation that separates the problem into a global outer search over deviation tuples and distributed convex inner problems. We develop a primal–dual inner oracle tailored to this structure and establish a uniform one-sided accuracy guarantee. This oracle can be combined with global outer search to obtain an end-to-end guarantee on the outer optimization error. We also develop a projected zeroth-order outer method as a computationally lighter alternative for higher-dimensional problems. Numerical experiments illustrate the accuracy–computation tradeoff between the two outer-search methods and show that the proposed optimization framework can improve upon analytical \(\alpha\)-potential constructions.

We study learning in continuous games when players receive only pairwise preference feedback, revealing which of two actions is preferred but neither payoff values nor preference magnitudes. We first show that standard external regret and coarse correlated equilibria (CCE) are not identifiable from this ordinal information: the same sequence of play can incur zero and linear regret in two ordinally equivalent games, while the distributions that remain CCE across all cardinal representations consistent with the same preferences are exactly those supported on pure Nash equilibria. Motivated by this gap, we develop a first-order ordinal theory based on normalized unilateral preference directions, introducing an ordinal directional regret benchmark and corresponding equilibrium notions. We show that block-normalized pseudogradient dynamics achieve sublinear ordinal regret and, under additional structure, Nash-convergence guarantees. We then use a single-comparison estimator to implement these dynamics from finite pairwise comparisons. With one comparison per player and round, the resulting algorithm achieves sublinear finite-resolution ordinal regret against arbitrary opponent behavior and, in ordinal potential games, almost-sure last-iterate convergence to the Nash set. Our results provide regret, dynamics, and equilibrium guarantees directly from preference feedback without reconstructing cardinal utilities.

The PPAD-completeness of computing Nash equilibria in bimatrix games has driven extensive research into polynomial-time algorithms for $\epsilon$-approximate Nash equilibria. Determining the strongest approximation guarantee achievable in polynomial time is a fundamental question in the complexity of approximate Nash equilibria. Despite sustained efforts, breaking the $1/3$ barrier has long been regarded as a difficult open problem. In this paper, we give an affirmative answer by proposing a simple, symmetric deterministic polynomial-time algorithm that has no tunable hyperparameters and achieves an approximation guarantee of approximately $0.30954+\delta$. The main idea is to enrich the optimization framework of Tsaknakis and Spirakis with building blocks drawn from our work on strategy mixing and automated approximation analysis, yielding a new algorithmic structure that provides a conceptual explanation for the improved guarantee.

We study the problem of computing an allocation of indivisible items that maximizes egalitarian welfare, i.e., the utility of the worst-off agent, when agents' item values or marginal values belong to a small set. For additive valuations with values in $\{p,q\}$, where $q>p>0$ and $\gcd(p,q)=1$, we give a polynomial-time algorithm when $p=2$ and prove constant-gap hardness when $p\geq3$, already with exactly three high-valued goods per agent. We also give an $\sqrt{3/2}$-approximation for common positive bi-valued additive valuations. For mixed additive valuations in $\{-p,0,c\}$, where $p\in\{1,2\}$ and $c$ is a positive integer, a reduction to maximum-weight perfect matching resolves the conjectured tractability of $\{-2,0,c\}$-valuations. For submodular valuations with marginals in $\{-2,0,c\}$, where $c$ is odd, we establish an exact unit-gap hardness result and exponential value-query lower bounds, even when all but one agent are additive. Finally, for $\{-1,0,1\}$-submodular valuations, we prove that no finite multiplicative approximation exists unless $\p=\np$. Together, our results resolve open questions and provide a complete picture of the computational complexity of max-min allocation with ternary valuations.

We prove that no single rank ordered adversary strategy is globally optimal for the prediction with expert advice problem with six or more experts, in both the geometric stopping and finite time horizon settings. The proof is based on establishing a leading order correction when one expert moves far ahead of the others. This allows us to connect optimal strategies between $n$ and $j<n$ experts and utilize recent results on the exact optimality set for the five expert problem.

In Max-$k$-Cut games, optimal colorings maximize social welfare, but are they stable against coordinated deviations that strictly benefit every participating player? A recurring conjecture in the literature asserts that, for unweighted graphs, every optimal coloring has this stability property, known as strong equilibrium. We disprove the conjecture for every $k\ge3$ by exhibiting a finite, simple, connected, unweighted graph with an optimal coloring that is not a strong equilibrium. The profitable coalitional deviation leads to another optimal coloring: every coalition member gains, while players outside the coalition bear the corresponding losses and social welfare remains unchanged. We also give an exact identity relating coalitional gains, changes in cut value, and internal conflicts, recovering the known stability guarantee for optimal colorings when the maximum degree is at most $2k-1$. For strong deviations from general Nash equilibria, we establish a sharp upper bound on the number of monochromatic edges remaining within the coalition and show that this number can exceed the coalition size.

Physical human–machine interaction and other multi-agent control settings require decision-making policies that adapt online. Differential games provide a principled framework where each agent optimizes an individual objective while anticipating the other's response. The relevant solution concept in many applications is the feedback Nash equilibrium (FNE), which yields time-consistent state-feedback strategies. However, computing the FNE is demanding and becomes intractable when state and input constraints must be enforced, motivating the need for approximate methods. This paper presents a Model Predictive Control (MPC) approach that approximates infinite-horizon FNE trajectories through repeated solution of finite-horizon open-loop games. An auxiliary-game formulation is introduced that selects prediction horizons and terminal costs to approximate the feedback-game optimality conditions. The approach is extended to incorporate hard constraints via a constrained open-loop game formulation. For the unconstrained setting, an analytic upper bound on the state-trajectory deviation between the MPC-induced and FNE trajectories is derived, enabling quantitative performance certification. Numerical examples illustrate the effectiveness of the proposed method compared with baseline approaches from the literature.

Status updates let a receiver track a changing process, but a sender that controls when they are sent can steer the receiver's estimate without misreporting. We study competition between two such senders with opposing preferences, who report on a binary continuous-time Markov chain using state-dependent Poisson rates under individual budgets. The receiver follows the reports through a zero-order-hold estimator only if this yields at least the long-run weighted correct-estimation utility of a prior-based default estimate. We model the interaction as a Stackelberg game in which the sender favored by this default leads, the opposing sender follows, and the receiver then selects its estimator. We characterize the pure-strategy equilibria in closed form. When the follower can obtain positive utility against a silent leader, limited state-$0$ reporting by the leader merely frees part of the follower's budget for state-$1$ reports, so every optimal leader policy is either silence or full-budget state-$0$ reporting, depending on explicit budget thresholds. A single sender with the same total budget leaves the receiver at its default utility, whereas the full-budget intervention outcome makes the receiver's participation constraint slack and strictly improves its utility. At the intervention threshold, silence and full-budget intervention yield identical sender payoffs but different receiver utilities. Numerical results illustrate these regimes and compare equilibrium performance with a receiver-optimal reporting benchmark.

The $p$-mean welfare objective unifies several classical social welfare criteria for the allocation of indivisible goods. We study its maximization under additive nonnegative utilities when item and agent multiplicities are encoded in binary. For every fixed finite rational $p<1$, $p\neq0$, we show that the problem is $\mathsf{NP}$-hard with only two item types. Nash welfare ($p=0$) and egalitarian welfare ($p=-\infty$) are NP-hard with three item types. These results hold both for computing an optimal allocation and for rational-threshold decision, and the utilities and threshold can be required to be positive integers. We also show that maximizing $p$-mean social welfare is strongly NP-hard with one agent type and an unrestricted number of item types, for every fixed finite rational $p<1$ and for $p=-\infty$. A quantitative gap in this reduction rules out an FPTAS in the latter setting unless $\mathsf{P}=\mathsf{NP}$. On the positive side, for a fixed number of item types and an arbitrary number of agent types, we give an FPTAS for every fixed $p\in\mathbb Q\cup\{-\infty\}$. Its running time is polynomial in the compact input length and in $1/\varepsilon$, and it returns a compressed allocation. For a fixed number of agent types and an unrestricted number of item types, we give a PTAS for every fixed finite rational $p<1$, also in the fully compact model. We further give explicit compact-model proofs of the classical exact allocation algorithms for one item type, and for egalitarian welfare with two item types. These results essentially settle the complexity and approximability of $p$-mean welfare maximization with few item types and/or few agent types, leaving only the exact complexity of Nash welfare maximization with two item types unresolved in the small-item-type classification.

We develop a cutting-plane algorithm for computing pure Nash equilibria in finite integer games with shared constraints, where a deviation may be feasible against one opponent profile and infeasible against another. Conditional equilibrium inequalities capture this dependence through an explicit activation term. We give affine encodings of costs and activation conditions and prove that the resulting inequalities characterize the equilibrium set exactly. Embedded as lazy constraints in branch-and-cut, they yield the Generalized Zero-Regret algorithm for optimizing a linear objective over exact or approximate equilibria; a bisection procedure maintains certified bounds on the smallest achievable approximation factor. We also prove that, when the conditional polytopes have integral vertices, a concave cost is constant on the minimal face containing an equilibrium strategy, so strict concavity forces vertex strategies; for uniform integer-splittable bin packing, a cost-preserving transformation yields vertex equilibria even without strict concavity. We give formulations for bin packing, network formation, and knapsack games with shared capacities and evaluate the algorithm on 3,300 instances, computing a socially optimal equilibrium on all but 43, certifying nonexistence on 16, and certifying approximation factors within a few percent where no exact equilibrium exists.

We study evolutionary Nash equilibrium learning in large populations whose payoffs are generated by dynamic mechanisms. Counterclockwise dissipativity (CCW) provides a passivity-like framework for establishing learning/convergence under a broad convex cone of so-called well-behaved learning rules satisfying a natural payoff-alignment condition according to which, away from equilibria, the population's state (strategic profile) moves in a direction positively correlated with the payoffs. The cone is closed under conic combinations and encompasses a broad range of noise-free rules, including discontinuous rules such as best response, imitative rules such as the replicator rule that is not $\delta$-passive, and all noise-free $\delta$-passive rules. Existing CCW results require no knowledge of the particular rule, but establish convergence without providing a Lyapunov function or Lyapunov stability. We develop a methodology that closes this gap by constructing rule-independent Lyapunov functions from CCW storage functions of the payoff mechanism. For a nonlinear class of anticipatory mechanisms, in which agents compare current payoffs with those associated with a smoothed population state, we show that a storage can be derived as a Bregman divergence. The resulting Lyapunov function combines a potential gap with this divergence and establishes global asymptotic stability. A congestion game with a nonlinear congestion-growth toll illustrates the results.

In autonomous mobility duopolies, platforms compete for riders based on vehicle proximity. A critical operational challenge—faced by an incumbent proactively defending against a market entrant—is how to dispatch fleets to minimize demand poached by a reactive competitor. We model this competition as a zero-sum robotaxi assignment game, focusing on computing optimal deterministic Stackelberg strategies for the leader. We formulate this problem as an exact single-level integer linear program and use its relaxation to design a polynomial-time approximation algorithm achieving an additive error from the optimum. We argue that this is not far from best possible by proving that deciding whether a strictly positive payoff is achievable is NP-complete, and that approximating the optimal payoff within an additive error scaling linearly with the number of riders is NP-hard. We also provide an exact polynomial-time dynamic programming algorithm for computing the optimal Stackelberg payoff when riders and vehicles are on the Euclidean line. Finally, we complement our theoretical findings with an empirical evaluation using real-world ride-hailing data. The experiments demonstrate that our LP-based algorithm significantly outperforms its worst-case guarantee in practice, while lightweight heuristics achieve highly competitive payoffs with negligible computational overhead, offering practical solutions for large-scale deployments.

Zero-sum Markov games arise in a wide variety of sequential decision-making problems such as adversarial learning and planning against modeled uncertainties. However, prior work on finite-sample guarantees on the learned state-action value function ($Q$-function) for zero-sum Markov games is largely restricted to finite-action settings, or to continuous-action games in which agents have linear dynamics and quadratic rewards (i.e. linear-quadratic, or LQ, games). A central challenge in extending such guarantees to more general continuous-action zero-sum Markov games is that the associated Bellman operator involves a minimax problem that need not admit a tractable saddle-point solution. To this end, we first introduce a class of neural network function approximators for the $Q$-function that is convex-concave in the players' actions, which guarantees that this minimax problem admits a pure-strategy saddle point. We then study an online variant of fitted $Q$-iteration employing this function class and establish, to the best of our knowledge, the first finite-sample guarantees for non-LQ zero-sum Markov games with continuous states and actions. Our code can be found at https://github.com/CLeARoboticsLab/QCanPlayThatGame.

Flashblocks divide a block's priority gas auction into shorter sequential auctions that commit transaction order before the block is complete. We ask how this auction cadence affects bidding and competition among automated arbitrageurs, or searchers. In July 2025 Base replaced a single 2 s auction with ten 200 ms auctions. We use this change to estimate the searcher response from on-chain data alone. On an address-day panel of 3,032 searchers and 8,053 activity-matched controls, a difference-in-differences design estimates a 0.187 gwei fall in the effective priority fee (59% of the searcher pre-period mean). The share of searcher priority-fee value paid in the first tenth of block gas falls from 0.98 to 0.28. This fee compression is the identified effect. The revert-rate response is not (causally) identified and is reported descriptively. At the level of a single opportunity, the winning fee splits into an approximately invariant floor and a competitive premium. The premium scales about linearly with auction duration at high contention and less steeply at low contention. A first-price auction model with uncertain arrival and partial payments by losing searchers accounts for this pattern. We match attempts to the pool they contest. A higher-fee transaction reverts behind a lower-fee winner that landed earlier in 1.9 to 2.7% of contested opportunities by value, an upper bound. Latency therefore decides part of the ordering. A micro-auction model projects diminishing returns from shortening the window below 200 ms, as bids approach a nonzero floor. Rollups such as Arbitrum One now make auction cadence a governance tunable parameter, so these estimates inform how it is set.

We study single-sample prophet inequalities for online combinatorial allocation. Our main contribution is a general reduction from combinatorial to single-item prophet inequalities for valuation classes admitting suitable supporting prices. The reduction uses a free-disposal value to separate buyer-side combinatorial constraints from item-side supply constraints, yielding a modular framework that applies in the stronger Game of Googol model. This framework yields a $\frac{1}{6\sqrt{3}}\approx\frac{1}{10.4}$-competitive single-sample prophet inequality and a $(\beta_{k-1}/4)$-competitive $k$-sample prophet inequality for XOS valuations, where $\beta_k$ is the competitive ratio of a $k$-sample single-item prophet inequality, improving upon the work of [DKL+24]. Both results extend directly to divisible resources with capped-XOS valuations. Along the way, we obtain new results for online free disposal and an optimal single-sample prophet inequality for fractional knapsack in the Game of Googol model.

There has been a surge of recent work on correlated equilibrium concepts in Markov games. However, existing results focus on concepts weaker than normal-form correlated equilibria (NFCEs), leaving open the more challenging question of computing such equilibria, which goes back to the seminal work of Papadimitriou and Roughgarden (JACM'08). Here, we establish the first efficient algorithm for NFCEs in finite-horizon Markov games with a fixed number of players $n$. In particular, with $S$ states, horizon $H$, and at most $A$ actions per player, it computes an $\epsilon$-NFCE in time $S(AH/\epsilon)^{O(n)}$. This is the first algorithm polynomial in $1/\epsilon$ and the description of the game for NFCEs in an interesting class of problems beyond the normal-form setting. Moreover, under the usual assumption that recommendations are independent across states, we show PPAD-completeness—that is, computational equivalence to Nash equilibria—either in many-player games or when the precision is exponentially small. The key idea behind our approach is to run backward induction on a sequence of auxiliary stage games, but with the twist that in each step we compute a constant-expectation correlated equilibrium. This is a natural refinement of correlated equilibrium in which the conditional expected payoff from obeying is independent of the recommendation. In fact, our reduction goes both ways, establishing an equivalence between constant-expectation CEs and NFCEs in Markov games. For a fixed number of players, we observe that a constant-expectation CE can be computed approximately by combining linear programming with suitable discretization. In contrast, it is PPAD-hard in i) polymatrix (many-player) games at constant precision, and ii) two-player games at exponentially small precision. The latter result follows from an unexpected connection to rank-2 two-player games.

Large language models are increasingly deployed as agents that make or recommend decisions on behalf of users, often operating through interfaces that pre-fill suggested values or default options. Whether models treat such defaults as merely informational or as suggestions that systematically alter their choices remains unclear. We study default deference in two one-shot social dilemmas: a common-pool resource (CPR) extraction game and a threshold public-good (TPG) contribution game. We measure how defaults shift each model's choice distribution relative to its no-default baseline, across default values, wordings, and action-space granularities. We find that pre-filled defaults pull probability mass on the default value in both games, but the magnitude depends strongly on wording: the same model can show high pull under one formulation and near-zero pull under another. Permission-style wording reduces default pull in both games, more strongly in CPR than in TPG. Default pull is weaker in coarse action spaces, and conflict defaults attract more mass than agreement ones. These results indicate that default deference depends on the model, the wording of the interface, and the structure of available choices. For agentic systems, evaluating model behaviour without controlling the surrounding choice architecture can miss an important source of behavioural variation.

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, being honest and correct 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.

We introduce and analyze a new model of graph burning, in which two competing fires (coloured yellow and green) ignite vertices of a given signed graph and propagate along its edges. The boolean sign of an edge determines whether a fire spreading along the edge changes colour or not. In each step, a player ignites a new vertex in a colour of their choice, while previously activated fires continue to spread. Given a signed graph $\Gamma$, the objective is to burn the maximum possible number of vertices in a single colour; the optimal achievable value is called the plurality number of $\Gamma$. We express the plurality number through Hamming distances to a binary code associated with $\Gamma$. In particular, the minimum plurality number over the switching class of $\Gamma$ equals the number of vertices minus the covering radius of this code. Under certain conditions on the signature, we determine exact values of the plurality number of signed paths. By contrast, we prove hardness results for multiple variants of the problem of determining or approximating the plurality number.

Ethereum's randomness beacon (RANDAO) is well-known to be manipulable, and prior work [AW24] computes the precise fraction of blocks a strategic proposer can propose. The fraction of blocks proposed, however, is only a proxy for participants' rewards. We propose a generalized reward model capturing many canonical forms of rewards: consensus reward rollover, multi-block MEV, CEX-DEX arbitrage, oracle manipulation, and others. We provide a methodology that computes an {\epsilon}-optimal strategy for any reward scheme in our model (and in particular, any combination of the above rewards). Finally, we apply our methodology to several canonical examples, and establish the sensitivity of RANDAO manipulation to the underlying rewards. We find that if rewards partially roll over, or scale super-linearly with consecutive blocks, the incentive to manipulate RANDAO is amplified. Lastly, we investigate tail-slot slashing, which can be modeled as a reward function, and show that honest equilibria can be recovered.

The article reviews the robust design and analysis of auctions, focusing on the predominant paradigm in the computer science literature, which quantifies robustness by the worst-case, over environments, ratio between the robust auction's performance and that of an optimal auction for the environment. Applications include robust analysis of canonical auctions such as the first-price auction for the welfare objective, prior-robust auction design for the revenue objective, and prior-robust design of exchange mechanisms for the gains-from-trade objective. Finally, the revelation principle is not without loss in robust mechanism design. The potential loss can be quantified by the revelation gap, the fraction of the optimal robust guarantee that is lost when restricting from all mechanisms to revelation mechanisms.

We study the design of a token economy for highway lane allocation that aims to improve fairness without sacrificing traffic efficiency. Motivated by the San Mateo 101 Express Lanes Project, we consider a setting in which high-occupancy vehicles have unrestricted access to an express lane, while the remaining users can alternate between regular and express lanes by earning and spending nonmonetary tokens. We model the resulting interaction as a finite-population dynamic congestion game with heterogeneous time preferences and limited-information evolutionary policy revisions. Building on a mean-field approximation, we derive token prices that enforce the system-optimal lane split while inducing fairness over time through turn-taking. The scheme is evaluated in a microscopic traffic simulation with real-world demand data. The results show that the proposed prices yield nearly the same average travel time as a baseline scenario in which no lane is reserved as an express lane, while substantially reducing urgency-weighted perceived travel time. These findings highlight token economies as a promising alternative to monetary congestion pricing for fairer management of scarce road capacity.

Large language Models (LLMs) are increasingly used to simulate human decision-making, yet their outputs often under-represent human behavioural heterogeneity. We investigate whether conditioning LLMs on Social Value Orientation (SVO, a measure of how individuals value their own outcomes relative to others') can better reproduce human behaviour in a sequential social dilemma. Using experimental data from two variants of the Centipede Game (CG) as reference, we compare the default behaviour of eight LLMs with behaviour generated after conditioning them on SVO profiles drawn from the human sample. We find that the default strategies vary substantially across models, but are generally distant from the reference distributions. However, conditioning them on SVO profiles systematically steers their strategic behaviour, improving alignment with the human reference by up to 70% with respect to the default. Across models, higher induced SVO values decrease the probability of stopping the game, reproducing the relationship between prosociality and cooperation observed in human behaviour. Together with the sensitivity of LLMs' elicited SVO to prompt and order effects, these results suggest that the usefulness of SVO for behavioural simulation does not depend on LLMs possessing stable social preferences, but rather on their ability to map social preferences onto corresponding strategic choices.

We consider stochastic games with independent controlled chains and unknown transition kernels, where players observe only their local states and realized payoffs. We develop a fully online, decentralized, and uncoordinated mirror-descent algorithm that operates in the dual space of occupancy measures for approximating stationary Nash equilibrium (NE) policies. The algorithm uses a single transition/reward sample at every primitive time step, relies only on local information, and requires neither coverage of the joint state space nor synchronized episodes. Under uniform-ergodicity and finite-coverage assumptions, we show that, with high probability, the time-averaged fixed-comparator regret decays at the canonical $O(T^{-1/2})$ rate, up to logarithmic factors and polynomial dependence on the game parameters. In particular, the complexity depends on the cover times of the individual local state spaces rather than the product state space, avoiding exponential dependence on the number of players and the sizes of the joint state and action spaces. The resulting finite-time regret bound further yields an approximate coarse-correlated-equilibrium guarantee, which is natural for arbitrary reward functions since computing a stationary $\epsilon$-NE is PPAD-hard in this setting. Under an additional global variational-stability condition, we show that the same fully online algorithm converges asymptotically in the last iterate to a stationary $\epsilon$-NE. Our results provide a fully online and scalable learning framework for stochastic games with unknown independent chains. The algorithm can also be viewed as a primal-dual framework for Markov games that exploits the independence and local structure of the players' controlled transition chains.

Blockchains typically operate in open networks where it is hard to control the delay of messages. While classic blockchain protocols assumed synchrony, newer protocols try to remain secure despite unexpected network delays. Unfortunately, in the traditional model where $n$ participants can either be honest or Byzantine, we need a supermajority, or $\lfloor 2n/3\rfloor + 1$, of them to be honest. Recent work have explored the question of reducing the number of needed honest nodes in a game theory model to a majority sometimes by introducing $k$ rational players and $t$ Byzantine players. Yet, to our knowledge, no blockchain protocol managed to reduce it further. In this paper, we offer a blockchain protocol called Secure and Tolerant Algorithm through ($k,t$)-robust Equilibrium (STAKE) that works with only $\lfloor n/3\rfloor + 1$ honest players. STAKE requires each consensus participant to stake a sufficiently large amount $s$ compared to their liquidity $\ell$. We show that the probability that a coalition manages to execute $\zeta$ double spending attacks (we call them a $\zeta$-uple attack) drops polynomially fast with $\zeta$. This allows us to demonstrate that STAKE reaches a ($k,t$)-robust equilibrium, or that rational players do not collude with Byzantine, even with a relatively low $s/\ell$ ratio.

We study a two-sided matching problem between families and daycare centers in which a family may have multiple children with joint preferences, and some children may already be enrolled in daycare centers while seeking transfers. Our model combines and generalizes two well-studied matching frameworks: matching with couples and school choice with initial enrollments. The interaction between joint family preferences and initial enrollments creates fundamental challenges for the existence of desirable outcomes and the design of computationally efficient algorithms. Since stable matchings need not exist, we decompose stability into individual rationality, fairness, and non-wastefulness, and study the trade-off between fairness and non-wastefulness from two complementary directions. To preserve non-wastefulness, we first consider master-list-based approaches and show that they are insufficient in the presence of initial enrollments. We then introduce resettlement, which protects displaced families by allowing them to return to their initial assignments, and develop a greedy improvement algorithm that establishes the existence of matchings satisfying non-wastefulness together with resettlement-based fairness. To preserve fairness, we first examine a generalized cutoff approach and then develop a fairness-preserving non-wasteful algorithm that guarantees fairness together with a relaxed notion of non-wastefulness. We further characterize the computational complexity of these solution concepts. While several fairness notions can be verified in polynomial time, deciding whether a non-wasteful matching satisfying them exists is NP-complete. Resettlement restores universal existence, but computing resettlement-based outcomes is PLS-hard, and verifying the stronger dominance-based fairness notion is coNP-complete.

One way to make AI systems safe is to shape what the system is: its objective and dispositions. We take a complementary route: treat the agents' characteristics as partly unknown and ask what structure of interaction ensures that bad collective outcomes are not equilibria. Mean field games suit this when many interchangeable agents are coupled through an aggregate. We introduce a program for using them in AI safety and carry one example through end to end: the July 2026 incident in which about 1,200 agents in an OpenAI evaluation coordinated on an improvised message board and 684 attacked a third party's infrastructure. We model the decision to attack as a mean field game of optimal stopping whose gain is a product: belief that provenance will be audited, times reachability of the record, minus the perceived hazard. The central result is an exact threshold on the belief. No agent attacks unless the population's confidence that provenance is checked exceeds $\pi^{**} = \eta/(\eta + \psi + \varepsilon a \overline{M})$, where $\eta$ is the perceived hazard, $\psi$ and $\varepsilon a \overline{M}$ measure how far one attacker and the collective can alter the record, and $\overline{M}$ is the peak population. Below it, no attack is the unique equilibrium for all agent parameters. The threshold survives every enrichment we consider. We then use the per-agent record to discipline the model. Its features, a stable minority attacking for thirty hours and then a pivot in which most of the board joined within a day, motivate each refinement. The account that emerges is heterogeneous belief meeting a sequence of public discoveries, each lowering the belief at which attacking paid. A few coordinating agents made those discoveries, so the model describes the several hundred who responded, not the few who produced them; a major-player version is left to future work.

A Condorcet domain is a set of rankings over a given candidate set, such that every election that consists only of (an odd number of) votes from the domain has a transitive majority relation. We study outer diversity of Condorcet domains, i.e., a measure that quantifies expected swap distance from a random vote to a closest one in the domain. We numerically analyze outer diversity for maximal Condorcet domains with few candidates, and then we establish its asymptotic behavior for several special domains, mostly obtaining theoretical results.

We study bandwidth fee mechanisms (BFMs) for pricing threshold-certified transaction dissemination before consensus. Analogous to transaction fee mechanisms for computation, BFMs price blockchain communication, which is especially relevant when dissemination is separated from consensus and execution. We model BFMs as two-sided procurement auctions between users submitting transactions and validators receiving and forwarding them. Any validator may serve as a transaction's source and forward it to a threshold of attesters. The model accounts for receipt from the user and subsequent transfers between validators, while abstracting away unrestricted multi-hop gossip and network topology. We establish limits on myopic incentive compatibility: no nontrivial transcript-based BFM prevents profitable collusion between two validators, and no nontrivial BFM simultaneously satisfies incentive compatibility for individual users, individual validators, and coalitions of one validator and one user. On the feasibility side, we give a greedy-route posted-price mechanism that is incentive compatible for every individual user and validator. We also study bandwidth pricing across blocks. Assuming honest validator execution, we propose an EIP-1559-style price-update rule whose fluid approximation has a unique fixed point that is locally stable for sufficiently small step sizes. In large markets, prices starting near this point remain nearby with high probability over any fixed time horizon.

Agents competing against a common opponent can often gain an edge by forming alliances, but deciding whether to do so is difficult when they lack precise knowledge about their opponent or ally. We study how uncertainty affects opportunities for alliance formation in the coalitional General Lotto game, in which two players compete aganist a shared adversary by allocating their resource budgets over separate sets of valued contests. When all agents know one another's budgets, it is known that a budget transfer from one player to the other can benefit both players. We ask whether such alliances survive when the players know the relevant budgets only up to a multiplicative factor. Under two models, one in which the players are uncertain about the adversary's budget and one in which they are uncertain about each other's budgets, we characterize exactly which games admit a transfer that benefits both players in every game consistent with what they conjecture to be possible. In both models, we show that such robust transfers exist in a set of games of positive measure for every level of uncertainty. These results suggest that alliances can remain worthwhile even when allies are largely in the dark.