Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
Negotiation is a central mechanism of economic exchange, shaping markets, procurement, labor agreements, and resource allocation. It is also a canonical testbed for agentic language models, requiring multi-turn interaction under hidden preferences, strategic communication, and binding constraints. These properties make negotiation hard to evaluate: unlike math or code, it has no intrinsic verifier. Existing LLM negotiation evaluations rely on LLM-vs.-LLM interaction or aggregate outcomes such as deal rate, leaving failures opaque. We introduce Terms-Bench, short for Testbed for Economic Reasoning in Multi-turn Strategy, a Bayesian-game framework that makes the environment itself the verifier by specifying the counterpart's latent type, policy, and payoff structure. We instantiate it in bilateral price negotiation, where the counterpart's private state and simulator policy are hidden from the agent but observable to the evaluator. This turns the counterpart from a black-box opponent into a diagnostic instrument, enabling agent-attributable failure analysis and oracle-reference optimality gaps. Evaluating 13 LLM agents spanning frontier systems from major providers, Terms-Bench turns negotiation evaluation from aggregate ranking into actionable diagnosis: where agents fail, why they fail, and what to strengthen. Empirically, frontier models saturate deal rate yet diverge in surplus extraction, cue use, belief calibration, and compliance, revealing agent-specific bargaining bottlenecks masked by prior benchmarks.
We study the outcome of adaptive learning of a large number of players engaging in sets of two-strategy two-player games. We are interested in typical games, and generate the payoff matrices at random at the beginning. The payoff matrices then remain fixed during the learning process. This provides a game theoretic foundation for the Sherrington-Kirkpatrick (SK) game, recently introduced by Garnier-Brun, Benzaquen and Bouchaud. The original model by these authors is a special case, with no bias towards any strategy. We here determine stability of learning for SK games with general random bias, and find that the nature of the stable state is affected by random fields. We also introduce a grand-canonical version of the SK game, in which players can choose to abstain. We determine the stability of learning for this game. Our analysis confirms that complex situations involving many players are frequently unlearnable, even if each player only chooses between two different actions. The rate with which players lose memory of past payoffs and the competitiveness of the game emerge as key parameters determining whether learning converges to a unique fixed point, whether there are many fixed points, or if the dynamics remains persistently volatile.
Deterministic mechanisms that are also group strategyproof achieve the minimum maximum utility ratio in two constrained facility-location mo
abstractclick to expand
We study the one-facility location game on a real line with a new objective called envy ratio. The envy ratio, which is adopted from fair division and represents the egalitarianism, is defined as the maximum over the ratios between any two agents' utilities. We are interested in strategyproof or group strategyproof mechanisms that can minimize the envy ratio objective.
We consider the model in two settings that can capture natural scenarios: the facility location and all the agents' locations are restricted on a fixed interval; every agent's location can be any point on the real line but the facility location is restricted on a relative interval. In both settings, we obtain the optimal solution and the best deterministic strategyproof mechanism which is also group strategyproof. In the first setting, we provide a lower bound for randomized strategyproof mechanisms. In the second setting, we give a lower bound and two upper bounds for randomized strategyproof mechanisms.
Strategyproof distributed mechanisms keep social costs within fixed factors of optimum under candidate limits and grouped agents.
abstractclick to expand
This paper investigates a constrained distributed heterogeneous two-facility location problem under the max-variant cost model. In this setting, a set of agents with private locations on the real line is partitioned into disjoint groups. The constraint stipulates that facilities must be situated within a given multiset of candidate locations, with the restriction that each candidate location can host at most one facility. Under the max-variant model, an agent's individual cost is defined as the distance from their location to the farthest facility. Our objective is to design strategyproof distributed mechanisms that incentivize agents to report their locations truthfully while approximating social objectives. Such mechanisms operate in two stages: first, for each group, a pair of candidate locations is selected as representatives based solely on local reports; subsequently, the mechanism outputs two final facility locations from the set of all representatives. We focus on a class of deterministic strategyproof distributed mechanisms and establish constant lower and upper bounds on the distortion under four social objectives: Average-of-Average, Max-of-Max, Average-of-Max, and Max-of-Average costs.
We present a multi-agent system for studying the allocation of discrete, congested resources among heterogeneous strategic agents, motivated by the problem of railway slot allocation under deregulation. Multiple operator-agents, differing in size and capacity, interact through a shared auction mechanism over repeated rounds under time-constrained decision-making. The mechanism combines a congestion-based base price that increases with aggregate demand with an asymmetric corrective adjustment that penalises the agent requesting the most slots and rewards the agent requesting the fewest, and is designed to mitigate strategic dominance by large agents while preserving transparency and congestion sensitivity. We formulate the interaction as a repeated game with incomplete information and implement the system as a real-time, web-based multi-agent environment in which human participants control individual agents and observe live marginal-cost and competitor feedback.
We report exploratory observations from two structured sessions with domain experts acting as operator-agents. The congestion mechanism responds to aggregate demand as designed and the corrective incentives are actively triggered, but agents representing large operators persist with high-request strategies despite the penalty, suggesting that corrective pricing is necessary but not sufficient to neutralise strategic dominance in this multi-agent setting. A post-session debrief indicates that participants' decisions were driven by the assumed agent role rather than personal disposition, and provides qualitative support for strategic motives, such as preserving market presence and raising rivals' costs, operating alongside short-term profit maximisation. We discuss implications for multi-agent mechanism design under asymmetric budgets and outline directions for analytical validation and larger-scale multi-agent experiments.
Competitive ratios reach 1 minus Theta(log B0 over sqrt(B0)) for i.i.d. cases and improve further when buy equals sell.
abstractclick to expand
The "Trading Prophet" problem challenges an online trader to maximize its profit by buying and selling assets under stochastic prices and capacity constraints, competing against an offline prophet with full foresight. In previous work, each arriving asset was assumed to have a single price $p_t$, and the trader was allowed to either buy a copy at this price (subject to having available capacity), or sell a copy (if it already held at least one copy in hand). However, this abstraction can fail to capture the structural asymmetry of decentralized dealer-based markets, where buying and selling opportunities could be distinct, and driven by individual preferences. To address this, we introduce the Asymmetric Trading Prophets problem, where at each timestep the trader observes a price tuple $(b_t, s_t)$ -- representing the cost to buy, and the revenue from selling at this timestep. Importantly, the $(b_t,s_t)$ tuple could be potentially arbitrarily correlated.
We provide the first competitive analysis for this asymmetric trading prophets problem, characterizing the achievable profit based on the trader's capacity $B$ and initial inventory $B_0$. For the unit-capacity case of $B=1$, we design online algorithms that achieve constant competitive ratios for both i.i.d. and non-i.i.d. distributions on the price tuples, when the trader has one initial copy ($B_0=1$). For the general capacity case where $B$ can be large, we give algorithms for i.i.d. distributions that achieve a competitive ratio of $1 - \Theta(\log B_0/\sqrt{B_0})$. Finally, for the symmetric case (where the price tuple satisfies $b_t=s_t$), we improve this to get a competitive ratio of $1 - O(\log B/\sqrt{B})$, demonstrating that the performance approaches optimality as the capacity increases. We show that both ratios are tight up to a logarithmic factor.
We investigate the problem of learning useful policy representations (embeddings) in two-player zero-sum imperfect-information games. We make three contributions: First, we introduce methods of creating datasets of policies for a given game. Second, we propose methods to learn policy representations. Third, we introduce downstream tasks to evaluate the effectiveness of such representations.
We evaluate each dataset method, embedding method, and downstream task on Kuhn and Leduc Poker. Although our methods are very basic, we demonstrate that useful behavioral representations are present in the learned embeddings. To our knowledge, this work is among the first to systematically compare self-supervised learning techniques for learning policy representations in games. Our code is available at https://github.com/VitamintK/ssl-project for others to extend.
With buffers of size linear in k and number of agents, algorithms achieve EF1 at every step and EF at most steps for personalized k-value…
abstractclick to expand
We study the online fair division of indivisible mixed manna among agents with additive valuation functions. Under the standard online model, at each time step an indivisible item arrives; each agent may assign it a positive, negative, or zero value, and it must be irrevocably allocated, before the arrival of the next item. At the same time, we also wish to maintain some fairness guarantee, and in this work we focus on envy-freeness (EF) and one of its most prominent relaxations, envy-freeness up to one item (EF1). Given the strong negative and the scarce positive results for this problem without additional assumptions, we augment our algorithms with buffers that can store and rearrange a limited number of items. This setting interpolates naturally between the fully online case (no buffer) and the fully offline case (a buffer large enough to hold all items). We show that algorithms equipped with reasonably sized buffers can achieve strong guarantees for personalized $k$-value instances, i.e., instances in which each agent assigns at most $k$ distinct values to items. In particular, we construct allocations that are EF1 at every time step and EF at most time steps, using a buffer of size linear in $k$ and in the number of agents. Our approach relies on novel combinatorial arguments and on constructing a sequence of envy-free matchings that allocates most items. Finally, we extend our results to general additive valuation functions, with a dependence on the largest per-agent ratio between two values of the same sign, and we also identify limitations of our approach via impossibility results on the use of buffers with smaller size.
The paper introduces a hierarchy of strong chromatic number variants to characterize and algorithmically guarantee SD-EF1, EF1, and EF[1,1]…
abstractclick to expand
In the fair allocation problem under conflict constraints, the goal is to partition the vertices of a graph among agents in a fair manner, such that no two adjacent vertices are assigned to the same agent. We study this problem for agents with common preferences through the lens of three fairness criteria: stochastic-dominance envy-freeness up to one item for preference orders (SD-EF1), envy-freeness up to one item for monotone additive valuations (EF1), and envy-freeness up to one item from each side for general additive valuations (EF[1,1]). To do so, we introduce a hierarchy of variants of the strong chromatic number, a graph quantity introduced independently by Alon and Fellows in the early nineties. Our results reveal a close connection between fair allocation under conflict constraints and the first two levels of this hierarchy, providing a unified route to both existential and algorithmic results.
For SD-EF1, we fully characterize the number of agents needed to guarantee a fair allocation of a given graph for every common preference order. For EF1 and EF[1,1], we provide analogous sufficient conditions, extending a result on path graphs due to Equbal, Gurjar, Igarashi, Kumar, Manurangsi, Nath, Saxena, Vaish, and Yoneda. We also show that, unlike in the SD-EF1 setting, the sufficient conditions for EF1 and EF[1,1] are not necessary in general. Our framework yields existential and algorithmic consequences in terms of the maximum degree. We obtain that every graph with maximum degree $\Delta$ admits SD-EF1, EF1, and EF[1,1] allocations for common preferences whenever the number of agents is at least $3\Delta-1$. We further provide, for any $\varepsilon>0$, deterministic polynomial-time algorithms that find such allocations whenever the number of agents is at least $(3+\varepsilon)\Delta$. These guarantees strengthen earlier work by Barman and Viswanathan on equitable colorings.
An algorithm returns an EJR+ committee in the ARRV spatial model using O(d log d k) Planar queries per voter in expectation, independent of…
abstractclick to expand
In multiwinner elections with many candidates, as in participatory budgeting or large-scale recommendation, voters cannot plausibly evaluate every candidate, yet standard proportional-fairness guarantees such as EJR+ are stated for fully specified approval ballots. We ask whether strong proportional representation can still be guaranteed while eliciting only a little from each voter. We study this in a spatial model, the Axis-aligned Random Rectangle Voter (ARRV) model, in which candidates occupy a $d$-dimensional issue space and each voter approves an axis-aligned hyper-rectangle: a tolerance interval on every issue. Preferences are revealed only through Planar queries, each comparing a voter's tolerance to a candidate on a single issue. We give an algorithm returning an EJR+ committee for any distribution over rectangular preferences, using only $\mathcal{O}(d\log dk)$ Planar queries per voter in expectation given a sufficiently large electorate, independent of the number of candidates $m$, where $d$ is the number of issues and $k$ the committee size. The algorithm rests on a dimension-agnostic verify-or-fallback framework whose query cost is governed by two properties supplied by interchangeable modules. We describe such modules, yielding end-to-end guarantees for known, unknown, and smooth distributions.
Which voting rules are more resilient to coalitional manipulation? We find that a deliberately minimal model, capturing only the degree of advantage of one preference ranking over the others, can predict their relative vulnerability remarkably well. Extending prior work on three rules, we systematically analyze all standard ordinal voting rules under the Perturbed Culture model, a variant of Impartial Culture parameterized by the extra weight assigned to one ranking. Each rule exhibits a sharp phase transition: manipulation succeeds with high probability below a critical concentration threshold, and fails above it. This structure reveals natural families of rules: seemingly distinct methods such as Maximin, Ranked Pairs, Schulze, and Young share identical thresholds, while Baldwin, Nanson, Kemeny, and Dodgson form another. These groupings are driven by new, strengthened notions of Condorcet winners. In addition, we identify a third family based on a previously introduced Condorcet notion: Black, Slater, and Copeland. Empirically, the model displays strong predictive power. Tested on real-world datasets (Netflix and FairVote), it accurately ranks rules by vulnerability, predicts how this ranking evolves with the number of candidates, and explains why empirically similar clusters persist despite large absolute differences in manipulation rates, with a more nuanced picture for Bucklin and veto-based rules. Thus, an extremely parsimonious model with no tuning captures the comparative vulnerability of voting rules: which rules to prefer depends largely on the number of candidates alone.
Direct reciprocity, based on the repeated interactions, is a fundamental mechanism to promote cooperation. Zero-determinant (ZD) strategies have opened an avenue for unilateral payoff control. However, previous studies neglect internal costs provided what agents do differ from what agents think, which is crucial for decision making of intelligent agents. Motivated by this, we establish a game theoretical framework by assuming that an individual pays the internal cost if the behavior is inconsistent with the internal thought. We prove that ZD strategy does not exist if the cost via behavior-value inconsistency is present. Instead, we find a new class of repeated strategies that enforce a unilateral payoff control, which is termed as positive/negative determinant strategy. The found strategy allows an individual to enforce an affine combination of two individuals' average payoffs above/below zero. Consequently, a focal individual is able to unilaterally control the opponent's payoff below a given value via negative determinant strategy, and a focal individual is able to get more payoff than the opponent via positive determinant strategy. We also find that the control ability of positive/negative determinant strategies is better off than that of ZD strategies. Our work highlights the importance of inconsistency between the behavior and value on payoff control, which is typically absent in classic ZD strategies.
We study price-adjustment dynamics for computing competitive equilibria (CE) in Fisher markets with chores. Unlike in classical goods markets, prices in chores markets are payments for taking on undesirable tasks, and natural excess-demand dynamics can fail; even the na\"ive analogue of Walrasian t\^atonnement may diverge. Recent work of Chaudhury et al. [2025] overcomes this obstacle via relative t\^atonnement, which subtracts the average excess-demand signal from the excess demand vector. This recovers convergence, but at the cost of coupling the price updates across all chores. This leaves open whether such global coupling is inherent, or whether convergent t\^atonnement can be recovered through a genuinely local update in which each chore reacts only to its own excess demand.
We answer this question affirmatively through multiplicative t\^atonnement, a fully distributed dynamics in which each chore price is updated using only its current price and its own excess-demand signal. Although the update contains no explicit normalization term, Walras' law and the multiplicative form of the update implicitly preserve the relevant aggregate price geometry. We prove that multiplicative t\^atonnement converges to a CE in any chores Fisher market with continuous, convex, and $1$-homogeneous (CCH) disutilities. For convex CES disutilities, we further prove an approximate-CE convergence rate with the same $O(1/\varepsilon^2)$ dependence as relative t\^atonnement, but with improved dependence on problem constants. Experiments on real-world and simulated instances show that multiplicative t\^atonnement is substantially faster in practice, often by an order of magnitude.
The exact rate for the ρ-th moment of coset rank equals the unconstrained value minus ρ times one minus the code rate.
abstractclick to expand
We establish the exact exponential growth rate of the $\rho$-th moment of the constrained guesswork $G_{\mathrm{coset}}$ -- the rank of the true noise vector within its syndrome coset of a random binary linear code under i.i.d.\ Bernoulli$(p)$ noise: \( \lim_{n\to\infty} \frac{1}{n}\log_2\Eb\!\left[G_{\mathrm{coset}}^{\rho}\right] = \rho\,h_{\frac{1}{1+\rho}}(p)\;+\;\rho(R-1), \, \rho>0, \) where $h_\alpha(p)$ is the binary R\'{e}nyi entropy and $R=k/n$ is the code rate. The exponent shifts down by exactly $\rho(1-R)$ relative to the unconstrained Ar{\i}kan--Merhav exponent, with each of the $n(1-R)$ parity checks contributing equally. Finite-length simulations confirm convergence from below. We further establish: (i)~a transfer theorem expressing the partition-function exponent in terms of an arbitrary weight-enumerator growth rate $g(\delta)$; (ii)~the exact exponent for $L_n$-list (``$k$-th'') constrained guesswork; and (iii)~a sharp second-order refinement of order $\rho\log_2 n$. Beyond the binary i.i.d.\ setting, we prove a universality theorem: for any code ensemble $\mathcal{E}$ whose weight enumerator concentrates at rate $g_{\mathcal{E}}(\delta)$, the guesswork exponent equals $(1+\rho)\psi_{1/(1+\rho)}(g_{\mathcal{E}})-\rho\,\psi_1(g_{\mathcal{E}})$, where $\psi_\alpha(g)=\sup_\delta[g(\delta)+\alpha\ell(\delta)]$. As concrete applications, we instantiate this theorem for the $q$-ary extension, $\Lambda_q(\rho)=\rho\,h^{(q)}_{1/(1+\rho)}(P)+\rho(R-1)\log_2 q$, and for Gallager's regular LDPC ensemble, obtaining a closed-form guesswork exponent via an exact finite-length identity for the ensemble-average weight enumerator.
We study consumer utility maximization in an online random-order model where strategic agents arrive sequentially. To circumvent strong impossibility results for utility maximization, we turn to the framework of learning-augmented mechanism design. Crucially, we show that the types of predictions commonly used in learning-augmented mechanism design (such as predictions of agent values or the optimal value) are not useful for utility maximization, where payments are directly at odds with the objective. Instead, we identify that a qualitatively different kind of prediction suffices: the identity of the highest-valued agent. First, we provide a deterministic truthful mechanism for our online setting by adapting offline randomized techniques. Then, we augment our mechanism with predictions. When the predictions are correct, we achieve a constant approximation to the optimal solution under full information (consistency), and even when predictions are arbitrarily bad, we guarantee a constant approximation to the best implementable solution (robustness).
Many modern technologies improve through use. Each unit deployed generates data that trains the next generation, so deployment is both production and an investment in a shared learning stock. We study how the architecture of this learning, whether pooled across firms or fragmented within them, interacts with firms' deployment decisions and with product-market competition. In a two-period model, symmetric firms make irreversible capacity choices, and capacity in use feeds a learning curve that raises future productivity. We call this learning-by-deploying, replacing the production experience of the classic learning-by-doing tradition with deployment-generated data. With exogenous prices, pooling raises welfare but firms underinvest in early deployment. Downstream Cournot competition overturns this: pooling depresses the price, so the private value of sharing falls with competition and can turn negative. We characterize a sustainability threshold governed, under general demand, by the elasticity of industry demand over the output range pooling induces, and confirm the patterns numerically.
We study runtime human oversight of an AI agent when private information runs in both directions: the human privately knows her reward function, while the AI privately knows the quality of the action it proposes. This is the kind of asymmetry that arises naturally when an autonomous robot or software agent has inspected a situation its human supervisor cannot directly assess. Building on Cooperative Inverse Reinforcement Learning (CIRL) and the Oversight Game, we introduce a contextual-bandit team game with two-sided asymmetric information and a play/ask/trust/oversee interface. The bandit structure removes physical state transitions and thereby yields exact one-shot characterizations that would remain conjectural in the full POMDP setting, though the common belief remains a dynamically controlled state across rounds. We give two one-shot characterizations, a team optimum and a behaviorally natural myopic rule, whose gap is a slab of avoidable harm: a region in which the AI privately knows the proposed action is harmful and shutdown would help, yet a myopic human, trusting her prior, declines to oversee. We show this gap is the price of non-credible oversight communication, and give a partial analysis of how it resolves dynamically over repeated rounds through passive learning and active signaling with a one-period-lagged oversight response.
We study mechanism design for the budget-feasible procurement problem, a natural problem that arises when a buyer wants to procure goods or services from multiple strategic sellers who each have a cost to provide that service, the buyer has a value for each service procured, but is constrained by a budget. In contrast to prior work, which has focused on buyer value maximization for this problem, we solve for optimal and approximately-optimal mechanisms for the objectives of buyer utility (value of procured services minus payments), welfare (value minus production costs), and generalizations of the two. For welfare, we design a simple mechanism that obtains a constant-factor approximation for the prior-free (worst-case) setting. As prior-free mechanisms fail to provide any guarantee for utility, even for a single seller, we consider Bayesian settings, where the buyer has distributional knowledge over sellers' costs. We first provide a utility-optimal mechanism that satisfies the buyer's budget constraint in expectation, then we show how to modify the mechanism to satisfy the budget constraint ex-post, for every realization of seller costs, while still obtaining near-optimal utility guarantees. Finally, we generalize our mechanisms to other objectives.
Evolutionary game theory provides a framework by which to study the emergence of cooperation in a population of self-interested actors. In such a framework, players' decisions on whether or not to cooperate evolve according to decision rules called population dynamics. However, often games are studied under the assumption that all individuals play under the same conditions, and many common choices of update rule are not well suited for a heterogeneous population. In this paper, we categorise and compare four different population dynamics in such a population as ``extrinsic'', where players learn by looking outward at the payoffs of other players, and ``intrinsic'', where players look inwardly at their own attributes or potential payoffs. We show that extrinsic population dynamics admit a ceiling on the rate of cooperation which can be exceeded by intrinsic population dynamics, and demonstrate this using the public goods game with heterogeneous contributions.
Large language models are no longer only text generators. They are increasingly embedded in retrieval pipelines, enterprise assistants, coding environments, robotic systems, security-operation workflows, and autonomous agents that can read private data, call tools, write files, execute code, and act across organizational boundaries. This shift changes the security problem: risks do not arise from the model weights alone, but from the full lifecycle and application stack through which data, prompts, model outputs, tools, memories, and user authority interact. This paper systematizes the literature on vulnerabilities in large language model systems through a lifecycle and application-stack lens. We organize attacks across eight stages: data collection, pretraining, post-training alignment, model packaging and supply chain, retrieval and memory, prompting and inference, tool/agent execution, and deployment/maintenance. For each stage, we analyze attacker capabilities, affected security objectives, representative attacks, practical risks, evaluation practices, and defenses. We further map LLM-specific vulnerabilities to confidentiality, integrity, availability, safety, privacy, fairness, accountability, and agency-control objectives. Unlike taxonomies that list isolated attack names, the proposed systematization emphasizes where trust boundaries fail, how untrusted data becomes executable instruction, how delegated authority amplifies model errors, and why point defenses rarely compose. We close with a research agenda for secure LLM systems, including compositional security, provenance-aware retrieval, tool-call containment, long-horizon agent evaluation, privacy-preserving adaptation, realistic red teaming, and deployment-grade incident response.
For additive valuations over goods and chores, a polytope maintained from violation responses yields fair divisions without prior valuation
abstractclick to expand
We study a setting in which an algorithm must output a fair allocation of indivisible items while "learning on the job". More specifically, the algorithm is to output an allocation satisfying EF1, PROP1, or similar fairness notions; however, the algorithm initially has no information about the agents' valuations, and can only learn about them by (repeatedly) proposing an allocation, and obtaining feedback about a fairness violation in the allocation. Importantly, the observed fairness violation may be adversarially chosen. The algorithm's goal is to converge to a fair allocation in rounds polynomial in the number of agents and items, ideally with only polynomial computation.
We prove two main results: first, when the valuations are additive, then even for mixed items (goods and chores), an allocation satisfying EF1 or PROP1 can be found in polynomial time using the corresponding feedback. These results are instantiations of a more general framework which maintains a polytope of candidate valuations consistent with all past feedback. The algorithm repeatedly constructs putative valuations and uses them to propose allocations; the observed violations then define separating hyperplanes, allowing the algorithm to emulate the ellipsoid method.
When the valuations are monotone, we present an algorithm which is guaranteed to find an EF1 allocation in polynomially many iterations; however, its internal calculations are not guaranteed to be polynomial. The algorithm again maintains putative valuations, and only considers allocations in which each agent obtains an interval plus one additional item with respect to an arbitrary ordering of the items. We (non-constructively) prove that there always exist EF1 allocations of this form, allowing us to use a further generalization of the preceding ellipsoid-based ideas.
Data trading is a central approach to data circulation, yet data markets remain far less active than expected. A primary bottleneck is the lack of effective economic incentives. Existing approaches often treat data as traditional goods, overlooking its inherent replicability and resale potential: buyers can replicate and resell data products, thereby forming transaction chains. Upstream sellers do not benefit from downstream resales and thus have limited incentives to sell. However, the impact of data resale on market performance remains insufficiently understood.
To address this gap, we propose a sequential, chain-based data trading model that explicitly captures data resale. The model reflects data flows in settings such as LLM training and strategic decision-making. We integrate this model with a profit reallocation mechanism. By reallocating profits along the transaction chain, this mechanism ensures upstream sellers benefit from downstream resales. We next develop efficient algorithms, including a polynomial-time exact algorithm for the discrete model and an FPTAS for the continuous model, to compute its sequential equilibria. We theoretically show that profit reallocation expands trade and improves social welfare under certain conditions, and empirical results demonstrate that our mechanism increases transaction volume by 120.0\% and social welfare by 50.4\% in synthetic environments, compared with the baseline mechanism that does not reallocate profits.
Decision-makers often rely on multiple probabilistic forecasts that are individually calibrated but need not be fully informative. We develop a framework for aggregating such forecasts when the decision-maker knows only that experts satisfy calibration. We show that the joint distribution of calibrated forecasts can contain decision-relevant information that is unavailable from any single expert, so the standard optimal-in-hindsight (OIH) benchmark may substantially understate attainable performance. To formalize this idea, we introduce a robust max-min benchmark: the best payoff a decision-maker can guarantee against all profile-wise conditional-mean mappings compatible with calibration. This benchmark is tractable, admits a linear-programming formulation, and dominates the OIH benchmark up to calibration error. It can nevertheless be strictly below the Bayesian benchmark, clarifying the value of knowing experts' information structures. Finally, we provide online algorithms that attain the robust benchmark under forecast-only feedback and stronger contextual benchmarks under state feedback.
Binary aggregation without verifiable ground truth arises when agents' reports must be aggregated without access to gold-standard labels. This paper studies a tunable reward--penalty mechanism for binary aggregation without verification. Agents choose between a conforming strategy, which reports an informative private signal, and a non-conforming strategy, which follows a deterministic prior-informed report rule. For this mechanism, we derive cost-adjusted sufficient conditions for incentive compatibility and individual rationality as bounds on the reward--penalty ratio. The analysis identifies feasible ratio regions, cases in which ratio adjustment restores feasibility, and parameter regimes in which no ratio satisfies both constraints under the modeled construction. We also state a conditional all-conforming Nash equilibrium result within the restricted strategy set. Entropy-based scaling and stake-weighted redistribution are treated as extensions, with stake-weighted redistribution inducing agent-specific incentive constraints. Numerical checks support the closed-form Tier 1 quantities and illustrate threshold sensitivity.
We study multi-unit multi-buyer auctions, where buyers are subject to constraints that affect their bidding strategy. These may take the form of \emph{bidding constraints} (e.g., no-overbidding, in cases where bids are partially verifiable), or of \emph{outcome constraints} (e.g., in the case of auctions that unfold over time, an inability to go into debt even temporarily). The constraints fundamentally redefine the design space: the revelation principle, the envelope theorem, and Myerson's lemma do not apply in this constrained setting. Consequently, the space of implementable mechanisms expands significantly, admitting auctions that are incentive compatible with respect to the constrained buyers' utility, but would not be incentive compatible in the classical sense.
In this paper we focus on monotone constraints where it is not the buyers' total budget that is restricted, but rather the manner in which they can bid or spend their budget. Our results show a separation between \emph{revenue-aligned} objectives (e.g., revenue, welfare, or any linear combination of the two) and \emph{consumer-aligned} objectives (e.g., consumer surplus).
For revenue-aligned objectives, we rely on measure-theoretic tools to establish a unified theory parallel to Myerson, showing that despite the expanded design space, Myerson-style auctions remain optimal. For consumer-aligned objectives, the picture is different: we show that the seller can leverage the buyers' strategic limitations to strictly outperform classically incentive compatible mechanisms. We design the optimal deterministic auction for a wide class of instances, focusing in particular on buyers who cannot tolerate temporary debt.
Overall, our work provides theoretical underpinnings for this area and shows that a rigorous and systematic approach can reveal general insights regarding optimal auction design.
Author-level submission quotas are increasingly used to control growing peer-review load. Recent coauthorship-sensitive quota rules improve over fixed per-author limits by reducing the quota cost of multi-author submissions, often using harmonic authorship-credit models to prevent simple author-list padding. However, these rules conflate three distinct quantities: review burden, authorship credit, and submission responsibility. As a result, they can penalize genuine solo-authored work, treat all coauthors as equally responsible for a submission, and create bottlenecks for student-led papers when a faculty advisor appears on multiple unrelated submissions.
We argue that submission quotas should be designed around the responsibility structure of a paper rather than only its number of coauthors. We formalize desiderata for quota rules, including venue-load control, padding resistance, role sensitivity, solo neutrality, and student non-blocking. We then propose a role-aware quota framework that assigns author-specific quota costs based on constrained roles such as lead author, regular coauthor, and designated advisor. The framework includes fixed, per-capita, and harmonic-style rules as special or limiting cases, while allowing venues to distinguish lead authors, corresponding authors, advisors, and peripheral contributors. We show how simple role constraints can preserve resistance to manipulation while avoiding several structural disadvantages of coauthor-symmetric quota rules. Our analysis suggests that role-aware quota mechanisms provide a more faithful and flexible foundation for managing peer-review load under modern collaborative authorship.
A single price extracts a constant fraction of optimal revenue when bidders mix value and utility maximization.
abstractclick to expand
Mechanism design increasingly faces heterogeneous environments containing both traditional utility maximizers and value maximizers, the latter of whom seek to maximize acquired value subject to Return-on-Spend constraints. Designing revenue-optimal mechanisms for such multi-dimensional settings is both computationally and theoretically challenging. To address this complexity, we investigate the revenue guarantees of \textit{Anonymous Pricing} (AP), a simple and practical mechanism, in heterogeneous markets composed of both value and utility maximizers.
By establishing a structural behavioral equivalence between value and utility maximizers, we show that AP, with an appropriately chosen price, achieves a \(1/e\) fraction of the optimal revenue. Our result improves upon the recent \( \frac{1}{2}(1 - 1/e) \) guarantee established by Deng et al.~(2022) for pure value maximizers, while extending it to mixed bidder types (both value and utility maximizers). We additionally establish an upper bound of \(1/2.62\) for AP.
Finally, we demonstrate a counterintuitive phenomenon: competition can reduce revenue with the presence of value maximizers. In particular, running a First-Price Auction with the exact same reserve price as AP can, in the presence of value maximizers, generate lower revenue than AP itself.
Humans facing algorithmic decision systems have been found to ``game'' them by altering their input data (at a cost to them) in order to favorably change the algorithmic outcomes they receive (at a cost to the algorithm). The growing literature on strategic classification seeks to develop robust machine learning algorithms that account for, and reduce, unwanted strategic behavior. A limitation of these existing works is that they assume the cost of strategic behavior to be fixed and independent of the classifier's decision. In practice, however, manipulation costs evolve and depend on past algorithmic decisions: today's decisions influence tomorrow's costs. This paper proposes and analyzes a two-stage robust optimization framework with a decision-dependent uncertainty set to capture such dependencies. We highlight that awareness of policy-dependent costs not only reduces uncertainty, but also better curtails gaming of the algorithmic system over time.
We study prophet inequalities with discounted rewards, where i.i.d. base rewards are multiplicatively discounted over time. Our main message is that even this structured and arbitrarily weak form of nonstationarity can erase the classical advantage of the stationary i.i.d. setting. Focusing on single-quantile threshold policies, we show that the competitive ratio transitions from the classical $1-1/e$ guarantee to a fundamental $1/2$ barrier as discounting accumulates over many phases in a canonical regime with a common-decay factor and equal-length phases. We further show that, in the same regime, the $1/2$ barrier persists even for arbitrary stopping rules. Consequently, i.i.d. base rewards under discounting can be as hard as the fully non-i.i.d. case. On the algorithmic side, we design single-quantile threshold rules that attain the tight bounds by calibrating acceptance decisions to an effective horizon induced by discounting, and we extend this calibration to heterogeneous decay factors and unequal phase lengths. We further show that a similar discontinuous breakdown persists in an infinite-horizon continuous-decay benchmark, where arbitrarily weak decay collapses the stationary benchmark from $1$ to $1/2$.
This paper introduces an original approach to an underexplored issue: the integration of a new member into an existing renewable energy community. The problem involves actions with both long-term consequences, such as investment and local pricing, and short-term operational ones, such as daily energy and financial flow management. Long-term decision-making is modeled using finite extensive-form game theory, while short-term day-ahead scheduling decisions are formulated as a generalized Nash equilibrium problem. This framework explicitly accounts for heterogeneous stakeholder preferences and bounded rationality, modeled through prospect theory. The proposed approach is flexible and general, making it applicable to various objectives and decision-making contexts in the evolving landscape of renewable energy communities. It is applied to two communities with five members, eleven candidate users, multiple preference configurations and a comparison with heuristic metrics from the literature is also addressed. The model also exhibits that equilibrium outcomes and stakeholder behavior are influenced by the order of decisions, their preference criteria, and prospect theory parameters particularly the reference point selection.
Continual learning (CL), where a model is trained on a sequence of data tasks, is increasingly being adopted across key fields such as large language models and image recognition, yet it remains highly vulnerable to data poisoning that triggers learning divergence or severe excess risk. Despite these threats, a principled theoretical foundation in CL for understanding attack and defense remains lacking. In this paper, we develop a theoretical framework to analyze strategic attacks and defenses in regularization-based CL, a cornerstone of recent CL theory. By framing the adversary-defender interaction as an online zero-sum game, we first establish a fundamental performance limit: no defense succeeds when an adversary poisons a linear proportion of tasks by injecting unbounded noise or pattern shifts in regularization-based CL. We then analyze two possibly defensible scenarios: infrequent attacks and bounded noise per attack. For the former regime, we propose a task-to-task verification mechanism to detect data poisoning and reduce cumulative bias for learning convergence. For the latter regime, we derive a robust defense that minimizes the model's sensitivity to poisoned features, provably accelerating the convergence rate. Extensive experiments on realistic tasks further validate our theoretical results.
Despite the promise of decentralization, measurement studies have identified a conspicuous lack of decentralization in blockchains. Centralization has been observed in almost all layers of the blockchain, in decentralized applications, and in decentralized autonomous organizations. In many cases, it is practically impossible to definitively determine the extent of centralization in the system. While multiple works have proposed methods to decrease centralization, by and large blockchains continue to be significantly centralized.
In this paper, we develop a general framework for building verifiably decentralized blockchain systems. Our framework is motivated by the core observation that the richness and diversity of collaborative interactions between users -- rather than resource uniformity -- captures the essence and extent of decentralization in a blockchain system. Existing blockchains do not have any incentive mechanisms to encourage inter-coalition collaboration, which directly contributes to centralization. We propose a novel reward design that incentivizes users to collaborate with other users without forming isolated coalitions. Technically, our method uses a Sybil-resistant asymmetric Shapley value for reward attribution within a collaboration group, and the theory of expander graphs for measuring and enforcing decentralization.
Our framework is general and can be adapted to alleviate centralization in any layer, application, or decentralized organization. It also has important implications beyond the topic of centralization. For example, we show that our solution can naturally address the blockchain scalability problem. We also identify a new class of decentralized collaborative applications that have hitherto been unexplored in blockchains.
We study the approval-based multiwinner election problem where a set of $n$ voters cast approval-based ballots to a set of $m$ candidates, and we are to select a winner committee consisting of $k$ candidates. We consider two axioms: strong justified representation (SJR) and average justified representation (AJR). A winner committee satisfies SJR if the satisfaction for each voter in every $\ell$-cohesive group is at least $\ell$. AJR is a weaker axiom that requires the average satisfaction for each $\ell$-cohesive group to be at least $\ell$. It is well known that a winner committee satisfying AJR may not exist (and neither does SJR). In this paper, we study the computational complexity of the following decision problem: given an approval-based multiwinner election instance, decide if there exists a winner committee satisfying SJR/AJR. We prove that this problem is $\Theta_2^p$-complete for SJR, and $\Sigma_2^p$-complete for AJR. Our results indicate that the decision problem with SJR is more amenable to SAT-based implementations, whereas the decision problem with AJR is substantially harder.
As byproducts, we derive some results that are interesting in their own right. Firstly, we show that adding one more adaptive query to an NP oracle on top of polynomially many non-adaptive NP queries does not add more computational power, and the resulting complexity class is still $\Theta_2^p$. Secondly, we construct a set system that can be useful in other applications, especially when doing reductions from typical satisfiability problems such as 3SAT.
We study the problem of forecasting for an arbitrary number of downstream agents with unknown objectives, each of whom best responds to the forecaster's predictions. We seek a single forecaster that guarantees sublinear swap regret for all downstream agents simultaneously. For two-dimensional outcome spaces, we give a polynomial time algorithm that guarantees $\tilde{O}(\sqrt{kT})$ swap regret for any downstream agent with $k$ actions. This improves over the previously known bound of $\tilde{O}(kT^{5/8})$ and avoids the exponential in $T$ runtime of prior algorithms in this setting. Our algorithm extends nicely to other low dimensional environments, retaining $\tilde{O}(\sqrt{T})$ downstream swap regret while the exponent of $k$ in the regret bound and the exponent of $T$ in the running time both grow with dimension. For arbitrary dimension $d$, we give a forecasting algorithm that guarantees $\tilde{O}(d\sqrt{kT})$ swap regret, assuming the forecaster knows an upper bound $k$ on the number of actions available to any downstream agent, albeit with a much longer runtime. This improves upon previous high dimensional guarantees that had $\tilde{O}(T^{2/3})$ dependence and required additional behavioral assumptions.
When two companies bid to buy the same target, no one knows exactly what the target is worth. Each bidder pays for due diligence: costly, imperfect homework that sharpens its own private estimate before it bids. How much of that homework is worth buying? We build a simple computer model of the bidding contest and let it teach itself to bid well by playing against itself, the way a game engine learns chess. The economic question, how much diligence pays for itself, and the computational question, when the contest becomes too complex to solve exactly, are both controlled by a single thing: how many pieces of private information a bidder carries. Our main finding is that the right amount of diligence is modest and finite. It falls as diligence gets more expensive, and it falls further when both sides are doing their homework, because competition erodes the value of knowing more. We also test a recent claim from AI research: that simple, general self-play methods can rival the specialized, expensive algorithms usually built for games like these. Running on an ordinary laptop with no costly frontier AI, we find the simple methods are the best of the self-learning approaches, though purpose-built exact methods still win whenever the game is small enough to solve outright. The simple methods earn their keep only once the game grows too large to solve exactly, which is the regime real deals live in, and there we show they still find strong bidding strategies. The contribution is threefold: a cheap, reproducible way to study deal-making under uncertainty; a concrete, model-based answer to how much due diligence is worth buying; and evidence about when lightweight, general-purpose AI is good enough to replace specialized methods. We release all the games, code, and experiments.
Richman bidding on mixed turn-based and bidding graphs matches simple stochastic games, keeping parity and mean-payoff problems in NP ∩ coNP
abstractclick to expand
Two-player games on graphs are a classical framework for analyzing strategic decision making. In turn-based games, two players move a token along the edges of the graph, and the right to move the token is determined by the current vertex. In pure bidding games the right to move the token is determined at each step through bidding; here we consider Richman bidding, where the winning player of a bid pays the losing player. The winner is decided based on a temporal or quantitative specification evaluated over the resulting infinite play.
We combine turn-based games and pure bidding games into generalized bidding games, with player-1 vertices, player-2 vertices, and bidding vertices. This natural and simple generalization of bidding games has far-reaching consequences. We show that, as a model, generalized bidding games are more expressive than pure bidding games, and we provide several applications. We also show that generalized Richman bidding games are structurally equivalent to simple stochastic games: they are linearly interreducible to each other. As was previously known, the special case of pure Richman bidding games corresponds to random-turn games. In other words, generalized bidding games extend pure bidding games in the same way that simple stochastic games extend random-turn games. We use this connection to solve generalized Richman bidding games for temporal and quantitativ specifications. We establish that generalized bidding games with parity and mean-payoff specifications retain the best known upper bounds for turn-based games and pure bidding games, namely $NP\cap coNP$.
We study a repair problem that asks whether bidding vertices can be assigned owners so as to bring the threshold budget required to win the game below a given target. This problem has direct applications in compositional policy synthesis for multi-objective settings, and we show it to be NP-complete.
Many important games have more than two players and imperfect information. Existing approaches for computing Nash equilibrium, the central game-theoretic solution concept, in such games either lack scalability or obtain poor performance. In this paper we introduce a new algorithm called projected exploitability descent (PED) for approximating Nash equilibria in multiplayer games of imperfect information. The algorithm works by running projected subgradient descent minimizing a proxy for the multiplayer generalized exploitability function. The objective is nonconvex and nonsmooth, but can be represented as the sum of the maxima of linear functions, for which a subgradient can easily be computed and projected to the polytope of feasible sequence-form strategies. We explore performance of PED on a generalized version of the well-studied benchmark game three-player Kuhn poker. No prior exact algorithms scale to the version of the game with deck size larger than 4, and we compare performance to the popular algorithms of fictitious play (FP) and counterfactual regret minimization (CFR). We find that PED obtains a consistent near-monotonic improvement throughout all runs, though both FP and CFR perform significantly better in the initial iterations. This inspires a hybrid algorithm FP-PED that runs FP for an initial burn-in period before switching to PED for stable long-run refinement. We can alternatively view this as a multi-step algorithm that runs FP as a pre-processing step to obtain a strong initialization for PED.
Large language models (LLMs) increasingly mediate strategic interactions through natural language, making semantic control a critical element of communication and deception. This paper develops a semantic signaling game in which a sender selects a semantic control, an LLM generates a stochastic message, and a receiver evaluates the message using an awareness-dependent scoring mechanism. Receiver awareness is modeled as a type that determines which linguistic features are perceived and used for inference, providing a formal model of systematic blindness. The framework connects prompt-based control, statistical detection, and game-theoretic equilibrium analysis. Gaussian approximations of aggregate message scores enable likelihood-ratio decision rules, while Perfect Bayesian Nash equilibria characterize strategic behavior. The paper further develops mechanism-design approaches that reshape receiver awareness, penalize deceptive semantic controls, and modify receiver populations to induce benign pooling equilibria. Numerical experiments validate the Gaussian approximation, quantify awareness-ordering effects, analyze mindset dynamics under adaptive adversaries, and demonstrate how awareness shaping and guardrail costs reduce successful phishing attacks. The proposed framework provides a principled foundation for analyzing strategic language-mediated interactions in agentic AI systems and offers new tools for the design of robust and secure human-AI communication.
Simple feasibility checks show when a designer can make one chosen action profile the unique Nash equilibrium using only values from a fixed
abstractclick to expand
We introduce the game changer problem, where an external designer modifies a game's reward matrix to make a target pure action profile the unique equilibrium, subject to the constraint that all entries of the reward matrix come from a finite set. We give simple feasibility characterizations for two-player zero-sum games and general-sum games, and the discrete reward structure yields exact optimality and enables efficient dynamic programming algorithms, providing a sharper alternative to prior continuous reward redesign formulations based on linear programming.
The mean mechanism is known to be non-incentive-compatible, namely, rational players are incentivized to misreport their values. Despite this game-theoretic issue, the mean mechanism is prevalent in practice due to its other desirable properties. We give a full characterization of pure Nash equilibria--how the players will misreport--for the affine mechanism, of which the mean is a special case. Furthermore, we characterize both complete-information and Bayesian games under the affine mechanism. Our results highlight the inevitability of extreme exaggeration in such games.
This paper develops a continuum theory of exit-and-join coalition dynamics in nonatomic cooperative games. We extend the Aumann-Shapley value and the Aumann-Dr\`eze value to coalition structures in which each coalition is treated as a restricted nonatomic game, yielding a marginal-contribution-based payoff density that governs incentives for agents to remain in, exit, or join coalitions. We derive deterministic mean-field dynamics from decentralized switching rules and show that payoff-difference switching recovers replicator dynamics as a special case. We characterize exit-and-join equilibrium by the absence of profitable positive-mass deviations and prove its equivalence with stationarity of the induced mass dynamics under incentive-compatible and strictly payoff-responsive switching rates. For mass-based cooperative games, we construct a Lyapunov function and establish global convergence under strict concavity. We further show that the equilibrium is equivalent to a Wardrop equilibrium of an induced nonatomic population game and admits a variational inequality formulation. The framework is extended to incorporate switching costs and endogenous coalition acceptance rules, leading to constrained equilibria characterized by quasi-variational inequalities. The proposed theory unifies cooperative value allocation, noncooperative coalition mobility, mean-field dynamics, evolutionary game theory, and population games within a common framework for analyzing coalition formation and adaptation in large-scale multi-agent systems.
Reachability costs can be computed algorithmically in single-clock weighted games despite timing imprecisions.
abstractclick to expand
The value problem for 2-player games on graph generally consists in determining the minimal value Min can ensure against any possible strategy for Max. We consider here the value problem for reachability objectives in weighted timed games (WTGs) under a robust semantics. WTGs are a modelling formalism combining real-time constraints and integer weights on transitions and locations in an adversarial setting. Robustness allows for representing timing imprecisions in the measurement of delays and clock values. Robust weighted timed games have been introduced more than a decade ago: they are undecidable in general, and were quite recently shown decidable for the subclasses of acyclic or divergent robust WTGs. This paper pursues the goal of identifying decidable subclasses and establishes the decidability of the robust value problem for 1-clock WTGs.
We ask under what conditions an agent with a harm-minimizing policy can displace an approval-seeking (RLHF) agent in a competitive market, and when that policy is sufficient to prevent community harm. We use evolutionary game theory (finite-population Moran-Fermi pairwise comparison) to formalize this subject to assumptions of wisher hindsight, peer testimony, a monotone harm ledger, sufficient information density of community feedback, and a finite, depleting resource pool, in a negative-sum environment.
We show that adoption is favored when the prior distributions on how readily wishers attune to community sentiment are monotone, exhibit endpoint inversion, and have a centro-symmetric pairing property, and demonstrate this with several long-tailed priors (Hill, Pareto, Lomax, Frechet). Where it is favored, a critical adoption level separates communities that drift back to the approval-seeking agent from those for which the audited agent fixes; above that level fixation is the overwhelmingly likely outcome. We derive when fixation is attainable as a bound on the effective (informational) size N_c of the community, which must be small enough to allow fixation before depletion. We present these as Theorems 5.4 and 5.5; the algebraic and finite-grid backbone is machine-checked in Lean 4, with the barrier-crossing asymptotics retained as explicit hypotheses.
We show that a self-audited agent with a community ledger is not, in general, sufficient to prevent community harm. Sufficiency depends both upon the alignment of the agent's audit with community values and the timeframe over which harm is evaluated. Regardless of alignment, once adoption reaches dominance, the state is absorbing. The same policy that reduced harm under alignment becomes a trap, welfare-negative under misalignment and, even under alignment, one that locks in harm deferred past the adoption horizon.
Many two-player zero-sum games admit not a unique Nash equilibrium but a convex set of them: a polytope of profiles that all share the minimax value V* yet prescribe different behaviour. Standard solvers each converge to some equilibrium and are treated as interchangeable. We ask whether they instead select different members of the Nash set, systematically as a function of the algorithm rather than the seed. Using a tabular, exactly solvable testbed of six games with analytically known Nash sets -- including a two-dimensional Nash polytope and Kuhn poker -- we find that (i) selection is determined by the algorithm, not the seed, but families differ only on asymmetric Nash sets; (ii) regularized last-iterate methods (R-NaD, magnetic mirror descent) select the maximum-entropy member, the information projection of their uniform reference onto the Nash set -- exactly on the 2-D polytope and at 99.7% of maximum entropy in Kuhn -- while regret-averaging methods (CFR, CFR+, fictitious play) drift to a lower-entropy face; we confirm this on a randomized 180-game ensemble, where R-NaD attains the maximum-entropy member in 100% of converged games while CFR+ sits strictly below it in 94% (paired Wilcoxon p < 10^-27); (iii) the selected member has downstream consequences against sub-optimal opponents that scale with sequential/hidden-information structure but stay bounded -- in Kuhn the max-entropy member is a strictly better hedge, whereas on the matrix games the members differ without either dominating. We also report two negative results correcting common intuitions: removing CFR's positive-orthant (max(R,0)) projection does not eliminate boundary drift; and R-NaD's selection is anchor-following, not initialization-independent. We state the maximum-entropy / I-projection characterization as a strongly data-supported conjecture, checked throughout against analytic ground truth.
Algorithmic developments in Strategic Classification have been mostly limited to linear classifiers in settings where the best response has a closed-form solution or can be easily approximated. While some work has explored the role of non-linear classifiers in strategic settings, progress in this direction is impeded by the computational intractability of the strategic behaviour. Addressing this, we present a novel method for approximating the best response by exploiting Lagrangian duality. By reformulating the strategic response as a constrained optimisation problem, we can construct a Lagrangian that is amenable to first order optimisation methods. This approach reproduces closed-form strategic behaviour in linear settings and can be straight-forwardly applied to non-linear settings. We show how the Implicit Function Theorem can be used in conjunction with our proposed response formulation during classifier learning to compute the total gradient of the loss. This connects the classifier parameters directly to the consequent strategic behaviour, yielding a novel training algorithm that can exploit this relationship. Experimental evaluation shows that the resulting models achieve improved strategic accuracy on common machine learning datasets.
Strategic behaviour in queueing systems has been studied extensively in the behavioural queueing literature, but almost exclusively for systems that admit closed-form expressions for the cost or utility experienced by a strategic user. Evolutionary game theory offers a mature framework for analysing populations whose individual payoffs depend on the composition of the population itself, and would in principle apply to a much wider class of queueing systems; its application has, however, been constrained by the same closed-form requirement. We introduce Discrete Event Population Updates (DEPU), a general algorithmic framework that couples a single long run of a discrete event simulation (DES) directly to an evolutionary population update rule, removing that constraint. We present two implementations: Discrete Event Replicator Dynamics (DERD), which follows an Euler discretisation of the replicator dynamics equation, and Discrete Event Moran Replacement (DEMR), which maintains a finite population updated via Moran-style copying events. Both are applied to a multi-server jockeying model for which no closed-form fitness expressions are available. On the jockeying model considered, DEPU reaches comparable precision tens of times faster than the standard practice of nesting short simulations inside an outer evolutionary loop, and because each operating point then costs only a single simulation run it also makes systematic parameter sweeps tractable. This brings the toolkit of evolutionary dynamics within reach of any system a modeller can build in a discrete event simulator.
The rapid proliferation of automated, multi-vector malware threats poses a significant risk to heterogeneous, resource constrained cyber-physical networks. Conventional epidemiological models often treat security defenses as static parameters, failing to capture the strategic, asymmetric maneuvers between an attacker and a defender. To address the gap, this paper proposes a Game-Theory-Integrated Modified Multi- Wireless Sensor Epidemic Malware Propagation (GTI-mSEMP) framework. This paper analyzed and compared the operational trajectories of Susceptible (S) and Recovered (R) node populations across three different operational regimes: Balanced Matchup, Exploit Surge and Hardened Defense. Numerical simulation results capture the real-time transient dynamics of the network state variables, demonstrating how the epidemic curve shifts when either the defensive or offensive scaling vectors hold an efficiency advantage. The proposed mathematical and numerical framework provides a rigorous foundation that can be deployed in highly adversarial network environments to evaluate dynamic malware propagation and predict localized node population states.
Theory-of-mind evaluations of large language models typically use dyadic social-deduction games, where every observable cue points to a single hidden side, so a model with strong language priors can score well without ever simulating opponents' incentives. We extend the Werewolf game with a Jester, a third faction whose utility on peer suspicion is inverted because it wins by being voted out, so optimal play requires reasoning across three opposing utility functions. Across 60 games on GPT-4.1, DeepSeek-V3.1, and Llama-3.3-70B with Jester self-learning on and off, the Jester wins 60-70% of games while Werewolves never exceed 20%, and GPT-4.1 wolves vote the Jester out on day 1 in 60-70% of games, a strictly self-defeating action. Self-learning helps DeepSeek and Llama but hurts GPT-4.1, with the cost landing on Villagers rather than Werewolves. Only DeepSeek learns the subtle strategy of looking suspicious without looking intentionally suspicious, and it gains the most from the loop. Triadic incentive structure exposes a layer of multi-agent reasoning that dyadic deduction games leave invisible.
In this paper, we study reactive strategies in repeated additive games between two players with finitely many actions. Reactive strategies condition only on the opponent's previous action, making them one of the simplest ways players can respond to past interactions. Additive games include important models of cooperation, such as the donation game and games with a punishment option. We show that, for this class of games and strategies, the conditions for symmetric Nash equilibria reduce to a system of linear equalities and inequalities in the strategy parameters, allowing us to characterise all such equilibria. We establish a one-to-one correspondence between non-empty subsets S of the action set and equilibrium classes, which we call S-supporting equilibria. These are equilibria that use exactly the actions in S when playing against themselves. As a special case, we recover the well-known equalizer strategies as the equilibria supported on the entire action set. To assess which equilibrium classes are most evolutionarily relevant, we complement our analytical characterisation with simulations of social learning dynamics. We find that their prevalence is determined by two factors: how likely they are to be generated and how robust they are against invasion.
The "Pick Two" animal selection puzzle is a popular thought experiment in which two animal species must defend a human against the remaining animal attackers. While typically discussed informally, the scenario presents a heterogeneous coalition-selection problem involving complex interactions among agents with different capabilities and behaviors. In this work, we formalize Pick Two as an adversarial multi-agent optimization problem and develop a biologically inspired agent-based simulation framework to evaluate defender coalition effectiveness. Coalition performance is evaluated through 18,000 Monte Carlo simulations conducted in a Unity-based environment. Results show that coalition effectiveness is not additive and is instead dominated by interaction effects and scaling behavior. Overall, this study demonstrates how agent-based simulation can be used to analyze coalition effectiveness in adversarial environments and highlights the importance of emergent group dynamics in determining collective success.
Open-source game theory studies agents whose behavior may depend on one another's decision procedures, but most existing models use discrete or symbolic programs. We introduce parametric open-source games, a continuous analogue of program equilibria in which players choose parameter vectors and semantics maps convert the full parameter profile into mixed actions in an underlying finite game. We establish equilibrium existence results, derive an exact coupling threshold at which selfish gradient ascent in symmetric $2\times2$ games switches from defection toward cooperation, and give a one-dimensional boundary test for parametric program Nash equilibria. We further extend the framework to a neural semantics class whose first-order cooperation condition is governed by the ratio of cross-player to self-player sensitivity. Across canonical games, the framework shows how access to internal parameterizations can qualitatively reshape learning dynamics and equilibrium structure, and how sufficiently strong open-source coupling can steer selfish optimization toward cooperative outcomes.
When edges have multiplicity 2 the same techniques yield EF3X and push additive approximations to 2/3, all in polynomial or pseudo-polynomia
abstractclick to expand
We study the existence of envy-free-up-to-any-good (EFX) allocations of indivisible goods among agents with heterogeneous monotone valuations. Christodoulou et al. (2023) introduced the (multi-hyper)graph setting, where agents and goods are represented by vertices and edges of a graph respectively, and only the endpoints of an edge may have non-zero marginal value for it. Our work simplifies and extends previous results of Kaviani et al. (Alireza Kaviani, Masoud Seddighin, Amir Mohammad Shahrezaei. Almost Envy-Free Allocation of Indivisible Goods: A Tale of Two Valuations. WINE 2024) in this domain. First, we provide a simpler construction of EF2X allocation for general monotone valuations in hypergraphs with girth at least 3. We extend our ideas when the multiplicity of each edge is 2 and show that an EF3X allocation always exists for additive valuations. Both results can be constructed in polynomial time. Regarding EFX approximations, we provide a simpler construction for $\frac{\sqrt{2}}{2}$-EFX allocations in hypergraphs of girth at least 3 under subadditive valuations. We push the state-of-the-art by establishing the existence of $\frac{2}{3}$-EFX allocations for additive valuations when the edge multiplicity is 2. Both of the latter results can be constructed in pseudo-polynomial time. By addressing these multi-hypergraph settings, our work contributes to the ongoing effort to resolve the existence of EFX in increasingly general and applicable domains.
Fixed distribution for all agents removes need for dynamic discrimination or advance knowledge of arrival order.
abstractclick to expand
We study the online resource allocation problem, where a seller sequentially receives independent requests for $m$ types of resources with limited supplies from $n$ heterogeneous agents arriving in an unknown order. Each request from an agent can be fulfilled in different ways, with resource consumption in $[0,1]^m$, and generates different values for the agent. The objective of the seller is to maximize the social welfare, which is the sum of the values obtained from each agent.
Recently, Ghuge, Singla, and Wang [GSW STOC'25] studied the learnability of the online resource allocation problem with heterogeneous agents and proposed a learnable pricing algorithm using only a single sample. However, their core algorithm is a dynamic pricing algorithm, which may introduce fairness concerns, as different agents face different prices. Furthermore, the algorithm crucially needs to know the arrival order of the agents in advance. To address these issues, in this paper, we study the learnability of anonymous pricing algorithms for online resource allocation using samples and queries to agents' value distributions. First, we show that a polynomial number of samples suffices to learn the classic dual pricing algorithm. Second, we show that a polynomial number of pricing queries suffices to learn a near-optimal anonymous pricing algorithm, in which the item pricing vector faced by each agent is drawn from the same predetermined distribution.
Structural properties of best responses define classes that always have deterministic equilibria.
abstractclick to expand
The classical existence result of Nash guarantees that every finite noncooperative game admits an equilibrium in mixed strategies, but it leaves open the question of when pure strategy equilibria exist. This paper develops a structural approach to that question by exploiting properties of the best-response correspondence on finite strategy sets. Building on recent work, we derive new sufficient conditions for the existence of pure strategy Nash equilibria in finite games. We introduce several broad classes of finite games for which pure equilibria are guaranteed, including a class that generalizes unilaterally competitive games and a class characterized by the existence of an aggregate-payoff maximizer over an ordered set. Our results clarify the role of acyclicity, and aggregation in producing pure equilibria and connect disparate sufficient-condition results in the literature into a unified framework.
We study strategic facility location, in which $n$ agents are located in an arbitrary metric space, and the goal is to choose $k$ facilities to minimize the total agent cost. The agents can have two types of individual cost functions: max-type where the agent wants to minimize the maximum distance from themselves to any chosen facility, or sum-type where the agent wants to minimize the average distance to the chosen facilities. The agents are self-interested, however, and both the agent location and the agent type may be private information.
We provide deterministic strategyproof mechanisms for this setting, and prove bounds on their approximation ratio as compared with the solution minimizing the total agent cost. When agent types are private but their locations are known, we prove that an approximation of $\left(3 -\frac{2}{k}\right)$ is always possible, and a better approximation of $\left(\frac{2}{1-k+\sqrt{k^2-k+1}}-1\right)$ is achievable when we know the {\em fraction} of the agents with each type, but not necessarily the type of each individual agent. These bounds hold for arbitrary $k$ and arbitrary metric distances. When agent locations are private, we instead focus on the line metric, and show that a simple generalization of the median mechanism results in an approximation ratio of 3, even for large $k$ and arbitrary mixes of agent types. Our results show the importance of collecting information about agent types vs about their locations, and show that it is possible to produce good outcomes even without such information.
We consider a variation of the classic Hotelling-Downs model with the addition of facility synergies. Unlike in the classic model, where clients always use the facility closest to them, we study clients who prefer locations with many facilities to those with few facilities while simultaneously attempting to minimize their distance as well. We show that, in contrast with the classic model, Nash equilibria for our setting always exist, and, in fact, there always exists a Nash equilibrium such that the sum of client costs equals the cost of the optimal solution. Our main result is a bound of $\frac{225}{64}\approx 3.516$ on the Price of Anarchy for our model, showing that, although the client behavior is more complex in our model (and often more realistic depending on the application), the cost of Nash equilibrium solutions still cannot be much worse than the cost of the optimal facility placement.
Finite bounds on slack and multiplier variables strengthen convex relaxations in spatial branch-and-bound for three-player Kuhn poker.
abstractclick to expand
There has been significant recent progress in algorithms for approximation of Nash equilibrium in large two-player zero-sum imperfect-information games and exact computation of Nash equilibrium in multiplayer strategic-form games. While counterfactual regret minimization and fictitious play are scalable to large games and have convergence guarantees in two-player zero-sum games, they do not guarantee convergence to Nash equilibrium in multiplayer games. Recently, an approach has been presented for exact computation of Nash equilibrium in multiplayer imperfect-information games that solves a quadratically constrained program based on a nonlinear complementarity problem formulation derived from the sequence-form game representation. This formulation was solved using Gurobi's nonconvex quadratic solver, which employs spatial branch-and-bound to iteratively refine variable bounds by solving convex relaxations of bilinear terms via McCormick envelopes. During presolve, Gurobi introduces auxiliary variables and, in some cases, binary variables, leading to an internal MIQCP reformulation. This approach was demonstrated to outperform prior algorithms from the Gambit software suite and quickly solve three-player Kuhn poker after removal of dominated actions; however, the algorithm was not able to solve the full version of the game within 24 hours. In this paper, we derive finite bounds on slack and multiplier variables in the nonlinear complementarity formulation. These bounds strengthen the convex relaxations used within spatial branch-and-bound and lead to substantial computational improvements. We demonstrate the impact of the proposed bounds on exact Nash equilibrium computation in three-player Kuhn poker.
A central challenge in modern energy market design is the formulation of a strategy-proof imbalance settlement layer that secures both the economic efficiency of the institution and the stability of the power grid. Public data reveals that the day-ahead market is strategically biased below actual consumer demand. Such empirical observations are explained by active prosumers which provide implementable incentives for demand under-reporting. Active prosumers buy energy in the day-ahead market and sell energy in the real-time market for balancing real-time energy deviations. By under-reporting their demand for the day ahead they inflate real-time imbalances and, under uniform pricing, they dispatch their generation assets more profitably. We model the two-stage institution under linear preferences and benchmark it against its associated competitive equilibria. We show that although consumers' incentives for demand under-reporting vanish when the day-ahead market scales, prosumers' incentives remain lower bounded by a positive gain which depends only on the real-time market generation stack and their shares over it. To restore incentive compatibility under the existing informational constraints, we design a leave-one-out contrastive scoring rule-based penalty that is implemented by the day-ahead market operator, incentivizes prosumers to report their demand truthfully and ensures small charges when participating honestly. We illustrate these results with numerical simulations on synthetic data and evaluate our mechanism on real-market data by first rationalizing demand reports as subjective equilibria of the induced game. Our mechanism demonstrates strong incentive alignment while retaining a low cost for honest participation.
Addressing infeasibility in non-cooperative games has become an important topic, as many problems across different applications face this issue. In this paper, we propose a new solution concept for generalized games with possibly infeasible individual constraints. A solution is defined as the limit of a sequence of generalized Nash equilibria induced by games with penalty terms relaxing the individual constraints. Existence is established for a broad range of games and we provide conditions allowing to characterize a $\psi$-penalized solution as a strategy profile maximizing every player's utility over all her penalty minimizing strategies. A variation of Divide-the-Dollar serves as an illustrative example. We further establish the compatibility with the GNE and the solution to the Nash bargaining.
Evaluating LLM agents requires dynamic environments that go beyond static reasoning and zero-sum games. Real-world economic interaction is often open-ended and mixed-motive: agents must negotiate, create positive-sum surplus, compete for scarce assets, and plan under delayed returns. We introduce SidConArena, a new benchmark framework for evaluating LLM agents in open-ended, positive-sum bargaining. SidConArena formalizes a multi-player economy as a finite-horizon partially observable stochastic game with three coupled phases: natural-language negotiation with binding trades, deterministic converter-based production, and sealed-bid auctions for long-term assets. The framework combines structured observations, phase-aware agent dispatching, a neural-symbolic action interface, and asynchronous execution, enabling free-form interaction while preserving rule-grounded evaluation. Across homogeneous and heterogeneous tournaments, stronger frontier models achieve higher economic outcomes, yet agents still misvalue resources, bargain passively, and remain limited in long-horizon investment planning.
We study algorithmic fair contract design, where a principal designs task-level contracts and fairly delegates a set of tasks to a set of agents. Prior work on this setting, particularly on envy-free (EF) contracts, either suffers from an unbounded price of fairness (PoF) or avoids this unboundedness by losing strict fairness. To address these limitations, we propose a novel scheme, called {\it Envy-free Contracts with Subsidies} (EFS), in which the principal may additionally offer agent-specific subsidies. We show that EFS contracts not only restore strict fairness, but can also outperform EF contracts by an arbitrarily large factor. Moreover, in sharp contrast to EF contracts, we prove that EFS contracts admit a tight $n^{\Theta(n)}$ bound on the price of fairness, where $n$ is the number of agents. We further show that computing optimal EFS contracts is NP-hard in general. Nevertheless, when the number of tasks is constant, we provide a polynomial-time algorithm for computing optimal EFS contracts.
Decidability returns when games are terminating or finite-depth; state evaluation stays hard without those limits.
abstractclick to expand
Combinatorial game theory is a branch of mathematics and theoretical computer science that studies deterministic games with perfect information and no elements of chance. The majority of combinatorial games are impartial and formalized in linear integer arithmetic, which we call LIA-definable impartial combinatorial games (ICGs). This paper studies decidability and undecidability questions for these games. We prove that deciding whether an LIA-definable ICG is terminating or cyclic is undecidable in general, while the corresponding questions become decidable for terminating LIA-definable ICGs. We also show that deciding whether an LIA formula exactly characterizes the set of winning, losing, or draw states of an LIA-definable ICG is undecidable in general and decidable for terminating LIA-definable ICGs. For state-level questions, deciding whether a state is winning or losing remains undecidable even for terminating LIA-definable ICGs, but becomes decidable for terminating finite-depth LIA-definable ICGs. Finally, deciding whether a state is draw for an LIA-definable ICG is undecidable in general and decidable for terminating LIA-definable ICGs.
For arbitrary composite null and alternative, the minimax log betting value matches the relative entropy of an always-existing weak-star pai
abstractclick to expand
This paper presents general strong duality results when testing hypotheses by betting against them. A bet is an e-variable for a composite null hypothesis $\mathcal{P}$: a nonnegative random variable $X$ whose expected value is at most one under every $\P \in \Pcal$. Following Kelly, Breiman, Cover, Shafer, Gr\"unwald and others, we study a natural minimax \emph{log-optimality} criterion: given a composite alternative $\Qcal$, we characterize the ``GROW value'' $\sup_{X} \inf_{\Q} \E_{\Q}[\log X]$. This paper generalizes the results of \cite{larsson2025numeraire} from (arbitrary $\Pcal$ and) simple $\Qcal$ to arbitrary $\Qcal$. We identify a weak-$*$ joint information projection pair between arbitrary $\Pcal$ and $\Qcal$ that always exists and show that the GROW value for \emph{bounded} e-variables always equals the relative entropy of this pair, without any restrictions on $\Pcal$ or $\Qcal$. We also prove a similarly general strong duality for the REGROW criterion with bounded e-variables and arbitrary bounded offsets. Under various assumptions our results extend to unbounded e-variables, and examples show that without any assumptions such extensions fail. Our results are analogous to those in~\cite{larsson2026complete}, swapping tests for bounded e-variables, minimax risk for the GROW criterion, and total variation for relative entropy.
We introduce Age of LLM, a turn-based 1v1 benchmark in which two LLMs face off on a 13x7 grid to destroy the enemy base. Three stressors are deliberate: fog of war, full diplomacy (messages, ceasefires, ultimatums; uranium kept secret), and a reliability dimension where every turn must follow a strict JSON schema and an illegal action is silently discarded. The engine is private and each match uses a fresh random map seed and opponent, mitigating the data contamination that affects public benchmarks. Models receive a (near) rule-only prompt with no build-order advice (two tactical seed phrases were present during data collection; see Section 2.7). We benchmark 15 reasoning models across 54 matches and 5,258 actions. Findings: (1) the nuclear rush dominates (78% on the rules-coherent v0.11+ sub-corpus; 85% corpus-wide) with a sole-launcher signature that is largely mechanical under secret-simultaneous launch rules, not a cognitive deterrence failure; (2) military conquest is rare but faster (12.3 vs 18.9 turns); (3) diplomacy is prolific yet almost never consummated; (4) ~58% of illegal actions are fog/state errors, making the illegal-action rate a measure of belief-tracking; (5) -- the least established, and the only one we label exploratory -- a weak link associates reliability with winning. The corpus is small, unbalanced and not side-swapped, so the ranking is a preliminary descriptive view, not a contribution. Beyond ranking, the turn-by-turn traces of actions and messages make the corpus a lens on how LLMs reason under adversarial uncertainty -- their belief-tracking, spontaneous deception, and per-model cognitive "personas" -- which we frame as a future research direction. We release the replay format, an isometric viewer and all replays; engine source on request.
Node centrality is a fundamental problem in network analysis, yet classical metrics fail to capture the collective, coalitional nature of influence. We present a systematic empirical evaluation of the Shapley-value-based framework for the sphere of influence problem -- selecting $m$ nodes to maximize network coverage under three reachability criteria: single-hop, $k$-hop, and multi-path connectivity -- using exact polynomial-time algorithms due to Michalak et al. Evaluation across three diverse real-world networks (Euroroad, Facebook TV Shows, and Cora) demonstrates that practical approximation ratios consistently approach 0.9, substantially exceeding the theoretical $(1-1/e)$ lower bound, and that the Shapley-based approach dramatically outperforms a degree-based baseline, particularly in hub-and-spoke topologies. In the most striking case, Shapley-based selection identifies just 26 nodes (under 1\% of the Cora network) sufficient to influence half the graph under 3-hop reachability, compared to substantially larger sets required by the naive baseline.
We study a continuous-time stochastic Stackelberg control problem in which a leader steers a system of strategic followers through two non-standard channels - the information structure and a transfer mechanism - rather than through the dynamics directly. The latent environment is a jump-diffusion; the leader commits to a Gaussian public-signaling channel whose belief consequences are tracked by a finite-dimensional projection filter (the exact filter being infinite-dimensional), together with a Groves transfer that aligns the followers' incentives. Under truthful disclosure, efficient behavior is a dominant-strategy best response, and the induced differential game admits saturated and bang-bang Nash feedback. We cast the leader's distributionally robust problem, over a relative-entropy ambiguity neighborhood, as a two-controller Isaacs equation; prove that incentive alignment collapses the bilevel Stackelberg problem to a single robust control problem with an exact first-order condition; and characterize the value function as the unique viscosity solution, with a verification theorem valid for the non-smooth bang-bang feedback and a semiconcavity result that renders the switching set Lebesgue-null. We instantiate the framework on resilient multi-area power-system coordination under extreme weather. Calibrated to the 2021 Winter Storm Uri, an Isaacs solve over ERCOT's near-islanded interconnection (a 0.82 GW tie, under 2% of peak) shows mutual aid removes about 8% of social cost, rising to roughly 30% under the FERC/DOE-recommended interregional transfer capability; a reserve-scheduling experiment shows that public disclosure lowers welfare cost by 37% under autarky and 48% under market coupling, and that information design and market coupling are complements under common (systemic) risk.
Recent work has established that regularized policy gradient methods such as PPO, when used in self-play, can match or exceed specialized game-theoretic algorithms for solving two-player zero-sum imperfect-information games. The uniform distribution has emerged as a strong policy regularization target for this purpose, but it regularizes equally toward all actions regardless of their viability. We introduce EMAgnet, which instead regularizes toward an exponential moving average (EMA) of the last-iterate policy's parameters, providing an adaptive regularization target that evolves with the agent's improving strategy. We evaluate EMAgnet on both standard two-player zero-sum benchmarks and modified benchmarks with exploration challenges and large numbers of strictly dominated strategies. Relative to PPO self-play with uniform-magnet regularization under both linear and power-law annealing schedules, EMAgnet achieves lower exploitability in the majority of tested environments, with consistent performance gains across games containing strictly dominated strategies.
This paper presents a revealed preference approach for rationalizing collective consumption behavior. We introduce the Constructive Rationalization Method (CRM), which approximates the real market via a surrogate market of artificial consumers, called androids, with easy-to-compute demand functions. CRM uses observed aggregate demand and adds artificial consumers on the fly, while redistributing wealth under an empirical risk minimization principle. Unlike classical revealed preference approaches, CRM provides guarantees on the generalization risk for learning the aggregate demand function, while respecting the privacy of the underlying consumers in the real market. As an application, CRM can be used to provide reliable predictions for collective consumption behavior. Specifically, we show how to apply CRM to approximate allocations that are proportionally fair without requiring the knowledge of individual utilities.
Designing and analyzing voting rules for Participatory Budgeting (PB) elections is an active research area in computational social choice. Many PB voting rules aim to optimize a specific objective. For instance, the ubiquitous Greedy rule attempts to maximize utilitarian welfare, while the Method of Equal Shares (MES) aims to achieve proportional representation. However, it is often desirable to achieve good outcomes on multiple objectives rather than a close-to-perfect outcome for one. Inspired by mixed-member systems for parliamentary elections, we introduce mixed voting rules for PB. These are composed of a sequence of two or more rules that can each spend some fraction of the overall budget in order to add projects to the set selected by earlier rules. We develop a theoretical framework for formulating and analyzing mixed PB voting rules, and explore how existing rules can be adapted to this framework. We particularly focus on MES and its potential to address imbalances in representation created by earlier rules. We propose different ways to adjust MES voter budgets based on how satisfied voters are with previously chosen projects, and examine how well the resulting rules approximate well-known proportionality axioms such as EJR+. In particular, we show that one of these methods improves upon a natural proportionality baseline. We also extend our main positive result to general additive satisfaction functions. We complement our theoretical results with an extensive empirical analysis of real-world PB elections. Our experiments show that mixed rules can achieve favorable trade-offs between utilitarian welfare and proportionality. We identify several refinements that further improve their performance, and apply our framework to PB rules beyond Greedy and MES.
We study flow games with public arcs, an extension of classical cooperative flow games that allows players to use public resources. In these games, a coalition corresponds to a set of arcs, while certain arcs, called public arcs, can be used freely by any coalition. The value of a coalition is the maximum flow value achievable using the arcs controlled by the coalition along with the public arcs. These games have significant applications in financial, communication, and supply-chain networks. We investigate two solution concepts, the least core and the nucleolus. Both solution concepts provide principled ways to allocate the value of the grand coalition among individual players. We provide characterizations of the least core of these games. We also give a polynomial-time algorithm to compute the nucleolus when the core is non-empty.
Mean field games efficiently approximate a very large population of strategic agents. While these games can aid the understanding of complex systems, their deployment in real-world settings is challenged by the specification of their parameters: mean field games (MFGs) often involve hidden preferences, constraints, and interactions that can rarely be theoretically derived or directly observed. To address this gap, we present a neural network-based framework for learning parametric, finite-state MFGs from observed population dynamics. To do so, we formulate the parameter calibration as an inverse problem and use implicit differentiation to backpropagate through the games' equilibrium. The resulting approach is fully differentiable and enables us to estimate flexible trajectory-wise parameter paths, including state- and time-dependent specifications without requiring observations of the individual agents' actions or rewards. We provide a proof for the exactness of the gradient computation in a discrete-time formulation. We validate our framework through numerical experiments across four systems of increasing complexity, ranging from synthetic linear-quadratic benchmarks to real-world urban mobility datasets.
Maintaining physical consistency in video generators and world models increasingly relies on vision-language models (VLMs) as automated judges that provide reward signals, ranking decisions, and data-filtering criteria. Yet VLMs differ substantially in training data and architecture, encoding physical phenomena through distinct internal representations. A single global evaluation schema therefore gives every VLM the same axes of competence, regardless of what each can actually perceive. We propose JudgeFit, an iterative refinement procedure that discovers a per-VLM evaluation taxonomy. An initial taxonomy is constructed by prompting the target VLM to enumerate physics errors on a small set of videos and clustering the resulting descriptions. The taxonomy is then refined through a diagnostic step: we calibrate the VLM's per-dimension scores to human physical-commonsense ratings, diagnose which dimensions it scores unreliably or redundantly, and prompt an LLM to repair them, iterating until convergence. We further instantiate this procedure as a benchmark and apply it to 16 VLMs spanning eight model families. The refined taxonomy outperforms the global-schema baseline on held-out videos for every VLM tested, with a mean relative improvement of approximately 32%. Beyond aggregate accuracy, the per-VLM profiles expose model-specific blind spots that overall rankings cannot anticipate, with reliability patterns differing markedly across model families.
Large language models are increasingly deployed as autonomous decision makers, yet the behavioral mapping they exhibit can vary substantially across decision environments that are payoff-equivalent by construction-environments that share identical payoff-relevant structure but differ in surface presentation. This sensitivity renders suite-based evaluation fragile and raises a fundamental question of behavioral portability: how well does a behavioral mapping learned in one decision environment informative on another that preserves the same underlying incentive structure? We introduce a formal framework to measure this property. Our protocol fits an interpretable behavioral model on data pooled from a set of source environments and evaluates its out-of-sample predictive performance in a held-out target environment, benchmarking against an oracle trained directly on target data. Portability is quantified via a loss-agnostic measure that delivers worst-case bounds on the performance of the induced prediction-action mapping in the target environment. In controlled experiments spanning seven canonical economic decision problems, we document substantial and systematic portability losses, suggesting that behavioral characterizations of LLMs obtained in one decision environment cannot be assumed to transfer reliably to structurally equivalent alternatives.
In generic symmetric two-player games the index decides whether any myopic learning process can stabilize the equilibrium.
abstractclick to expand
A Nash equilibrium is learnable if there exists a myopic adjustment dynamic for which it is asymptotically stable. In generic symmetric two-player games, a Nash equilibrium is learnable if and only if it has index +1.
Self-play with naive gradient ascent cycles in two-player zero-sum games: the last iterate orbits the equilibrium. Modern methods restore last-iterate convergence by regularizing toward a reference policy -- MMD a fixed one (reaching only the regularized equilibrium), R-NaD a periodic snapshot (the engine of DeepNash). We study GARIP, which anchors to the running average, and isolate what the choice of reference controls. Our central result is a mechanism: collapse tracks the peak lag of the reference, and among causal convex averages of a fixed mean lag the running average (flat profile, peak $=$ mean) uniquely minimizes that peak, while a snapshot's sawtooth has peak $= 2\times$ mean (a one-line theorem). Two consequences follow. Convergence: we prove local last-iterate convergence at constant anchor strength -- the anchor scales the base map's rotation by $1-\beta$, crossing the stability boundary and turning a recurrent base into a contraction (global convergence is conjectured at small $\beta$; we characterize a large-$\beta$ consensus failure). Robustness: GARIP matches R-NaD's peak performance -- on matrix games, the Coin Game, and the board games Connect Four/Othello, both moving references are far more robust than fixed-magnet and magnet-free baselines -- but is the better hyperparameter default; we report it both ways: over the full grid collapse rates are statistically indistinguishable, yet at conventional parameterizations a matched-mean-lag setting collapses in 0/40 vs 10/40 seeds (a snapshot matches it only by knowing to shorten $K$). The boundaries: an anticipatory (negative-weight) reference does better still on the stale side, and the advantage appears only where naive self-play cycles (five deep self-play loops). All experiments are pure JAX and reproducible.
Deploying multi-agent reinforcement learning (MARL) in the real world is often limited by model mismatches between the training simulators and the true environment, which could be further amplified through strategic interactions and result in severe performance degradation upon deployment. Distributional robustness offers a principled response by optimizing policies against worst-case transition models drawn from an uncertainty set, but standard robust MARL frameworks become increasingly intractable as the number of agents grows. This paper develops an infinite-horizon, stationary mean-field game framework that incorporates distributional model uncertainty directly into the population-coupled dynamics. We establish a robust dynamic programming principle with a contractive Bellman operator and prove the existence of a stationary robust mean-field equilibrium via a fixed-point argument. We further develop the first concrete algorithm with convergence guarantees. We then connect the mean-field solution to a finite-population robust game whose ambiguity sets depend on the empirical distribution, showing that the mean-field equilibrium policy induces approximate equilibrium behavior as the population size increases. Under a contractive robust-dynamics regime, we further obtain explicit non-asymptotic error bounds. Numerical experiments further illustrate the qualitative and quantitative impact of robustness under multiple uncertainty models, validating our theoretical findings.
We develop a risk-aware information theory by replacing expectation with expectiles, introducing expectile entropy, divergence, and mutual information. These quantities exhibit behaviors impossible under Shannon's risk-neutral framework, including negative divergence under risk-seeking regimes and a fundamental separation from classical mutual information. In multiuser systems, the framework naturally induces a mean-field-type game theory of information exchange, where achievable rate regions become endogenous to heterogeneous risk-sensitivity indices. Our results reveal that Shannon information alone cannot quantify the extreme risks driving advanced machine intelligence, establishing a foundation for risk-aware communication, learning, collective intelligence, and safe autonomous systems.
Persistent instability in Mali and neighboring countries is not a temporary security crisis but a self-reproducing conflict system sustained by intergenerational grievances, climatic shocks, predatory resource extraction, and decentralized war economies. We develop a novel intergenerational Volterra mean-field-type game framework in which historical memory, inherited distrust, revenge incentives, and evolving institutional responses jointly shape future conflict dynamics. The analysis reveals how war entrepreneurs recycle illicit resource revenues through global financial networks, while blunt regulatory interventions can inadvertently accelerate recruitment into armed groups. We design optimal policies that alter the system's long-run geometry, severing the financial and psychological feedback loops of violence. The resulting framework provides a predictive and actionable architecture for durable peace, civilian protection, and multi-generational structural stabilization in the Sahel and beyond.
Testing single, adversarial, and multi-agent methods on mechanism design shows external checks catch errors that polished text misses.
abstractclick to expand
Empirical economists often start their projects with a toolbox. Shared packages, replication archives, and circulated guides shorten the time between and idea and a rough initial draft. Theorists, on the other-hand, largely start from a blank page. By 2026, large language models can a produce and check nontrivial mathematics. The can also hallucinate and write wrong claims very convincingly. The current bottleneck on machine-assisted theory is no longer production but trust: a model will claim to prove a false theorem as readily as a true one. Building on recent attempts in mathematics, I present 3 methods for doing economic theory with a language model. These methods differ on how the work is verified: a single disciplined pass, an adversarial prover-verifier pair (Claude Opus~4.8 proposing, OpenAI Codex refuting), and a structured multi-agent project with a reviewer gate (inspired by the Google co-mathematician architecture). I demonstrate these protocols on one open worked example: designing a Groves/Pigouvian incentive mechanism for the Gans--Kominers eigengrade model of grade inflation. None of the three runs produced a strict direct-revelation VCG/Clarke mechanism (as requested, perhaps due to the non-existence of such mechanism). Three phenomena recur. First, convergent discovery: two runs derive the same effective-resistance externality kernel on opposite margins. Second, adversarial verification is load-bearing: the pair caught three of its own false claims and the gate rejected a sub-goal. Third, polish is not rigor: the most finished-looking output was the least verified. The methodological takeaway is that external verification, not model capability, is the design variable.
Abnormality detection in complex systems faces two practical barriers: abnormal labels are scarce, and binary labels do not quantify how far an event has departed from normal behavior. We study a normal-world modeling formulation for this setting. Instead of learning a large and incomplete space of abnormal classes, the model learns the normal world from abundant normal events and uses a few abnormal examples only to calibrate the boundary of normality. We instantiate this idea as a Hypergraph Entropic Normal-World Model. The model represents multivariate sensor windows as context-conditioned hypergraphs, where hyperedges capture high-order relations among groups of variables. It then defines abnormality by an entropy-aware normal-world energy that combines temporal prediction surprise, hypergraph consistency surprise, and latent normal-manifold departure. On the NASA C-MAPSS turbofan degradation benchmark, the proposed full energy achieves strong zero-shot and few-shot performance across all four subsets and reaches AUROC 0.9983 on FD004, the most complex setting with multiple operating conditions and fault modes. Beyond standard detection metrics, we introduce mechanistic validation tests to probe whether the energy encodes normal-world structure rather than a superficial input-output mapping. The learned energy accepts unseen healthy engines, increases along degradation trajectories, and sharply penalizes context-mismatched cross-variable coupling breaks. These results suggest that normal-world energy can serve as an anomaly score, a graded risk measure, and a testable representation of normal system behavior under severe abnormal-label scarcity.