Theory & Algorithms · Computer Science & AI
Computer Science & Game Theory
The newest papers in Computer Science & Game Theory that ReadSearch has read, newest first. Each links to its own page, with its authors, date, where it was published and the original.
252 papers, from 4 September 2026 to 5 November 2026: 252 arXiv preprints.
Get the few papers worth your time in Computer Science & Game Theory every morning.
Follow Computer Science & Game Theory and ReadSearch reads its new papers each day, then brings you the few worth reading, each with its key finding in a sentence.
Newest papers, page 8
Trading with the STARS: Algorithm Design & Spectrum of Fundamental Limits for Trading with Storage
We study an online trading problem where a trader, given a sequence of i.i.d. prices drawn from a known distribution $F$ on $[0,1]$, must make irrevocable buy, sell, or hold decisions subject to…Who Bears the Burden? Learning Responsibility for Shared Constraints in Multi-Agent Reinforcement Learning
When multiple agents share a cost budget, a common Lagrange multiplier can enforce the aggregate constraint but does not determine how its penalty should be allocated across agents.On prediction from expert advice with more than five experts
We prove that no single rank ordered adversary strategy is globally optimal for the prediction with expert advice problem with six or more experts, in both the geometric stopping and finite time…Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations
We study the problem of computing an allocation of indivisible items that maximizes egalitarian welfare, i.e., the utility of the worst-off agent, when agents' item values or marginal values belong…Learning in Continuous Games from Pairwise Preference Feedback
We study learning in continuous games when players receive only pairwise preference feedback, revealing which of two actions is preferred but neither payoff values nor preference magnitudes.Distributed Algorithms for $α$-Potential Functions in General-Sum Games
We study the problem of computing the tightest \(α\)-potential approximation of a general-sum game over continuous action spaces, within a prescribed class of potential functions and when each…Prime factorisation of stable-matching instances: uniqueness, simultaneous products, and an exact census
Every balanced instance of the stable marriage problem with strict complete preferences has a unique finest partition into prime blocks, and that single partition simultaneously factors three…Trust-Gated Capability Control: Breaking the Trust-Vulnerability Paradox in Multi-Agent LLM Systems
Layered trust models for multi-agent LLM systems remain largely conceptual: they name which dimensions of trust matter but not how layers combine, how their importance is set at runtime, or how…Maximizing $p$-Mean Social Welfare in the High-Multiplicity Setting: Few Agent Types and Few Item Types
The $p$-mean welfare objective unifies several classical social welfare criteria for the allocation of indivisible goods.Normal-Form Correlation in Markov Games
There has been a surge of recent work on correlated equilibrium concepts in Markov games.Single-Sample Prophet Inequalities: A Combinatorial to Single-Item Reduction
We study single-sample prophet inequalities for online combinatorial allocation.Priority Gas Auction Cadence and Searcher Competition: Evidence from Flashblocks on Base
Flashblocks divide a block's priority gas auction into shorter sequential auctions that commit transaction order before the block is complete.$Q$ Can Play That Game: Online Fitted $Q$-Iteration for Continuous-Action Zero-Sum Markov Games with Convex-Concave Function Approximation
Zero-sum Markov games arise in a wide variety of sequential decision-making problems such as adversarial learning and planning against modeled uncertainties.Mean field games as a tool for AI safety: a worked example from the July 2026 Hugging Face incident
One way to make AI systems safe is to shape what the system is: its objective and dispositions.Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains
We consider stochastic games with independent controlled chains and unknown transition kernels, where players observe only their local states and realized payoffs.How to Have a Sensitive Debate: An Instance-Optimal Protocol for AI Debate
As powerful AI systems reach and sometimes surpass the abilities of human experts across a range of cognitively demanding tasks, the problem of accurate oversight and supervision of these systems…Decentralized Decision-Making among Heterogeneous Autonomous Vehicles: An $α$-Potential Game Framework
We study noncooperative multi-vehicle games among heterogeneous autonomous vehicles, where each vehicle adopts a decentralized closed-loop policy based on its own state, and optimizes an objective…Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games
Optimistic matrix mirror-prox (OMMP) computes $ε$-approximate Nash equilibria in quantum zero-sum games with an $O(1/\varepsilon)$ average-iterate guarantee [arXiv:2311.10859].RSIGame: Autonomous Agentic Game Development with Recursive Self-improvement
Recent advances in large language models have made automatic game generation increasingly feasible, yet reliably improving generated games beyond a playable version remains challenging.Inference Auctions
When inference demand exceeds available compute capacity, model providers must decide which requests should be served first.