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 6
Do Rollups Self-Organize? Multi-Agent Reinforcement Learning in the EIP-4844 Blob Fee Market
EIP-4844 gave Ethereum rollups a separate fee dimension for data, governed by a multiplicative update rule that targets three ``blobs'' per block.Representation Theorems for Actual Powers over Two-Agent General Concurrent Game Frames
One of the most well-known connections between logic and games is Pauly's representation theorem: the induced powers of individuals and coalitions in concurrent game frames correspond, in a precise…Improving the Bounds on Approximating Weighted Maximin Share for Chores
We investigate the problem of allocating indivisible chores among agents with arbitrary positive weights and additive nonnegative cost functions.Fair Allocation with Dichotomous Preferences over Item Complements
We study the problem of fair allocation when agents have dichotomous submodular preferences over groups of, rather than individual, items.Entropy-Regularized Mean-Field Games with Average-Reward Criterion: Span-Seminorm Contractions and Model-Free Learning
We study stationary discrete-time mean-field games with finite state and action spaces under the average-reward criterion, with an entropy-regularized objective and population-dependent dynamics and…Sample-Optimal Multi-Group Learning with an ERM Oracle
In multi-group learning, a single predictor must perform nearly as well as the best hypothesis in a class on every group in a rich, possibly infinite and overlapping, collection of subpopulations.DiffNash: Finding Nash Equilibrium in High-Dimensional Continuous Action Spaces with Diffusion Policies
Computing equilibria in high-dimensional continuous games requires learning and representing rich, multi-modal strategy distributions, something conventional neural policies struggle to achieve.Thompson Sampling for Learning in Zero-Sum Games
Thompson sampling (TS) achieves logarithmic and asymptotically optimal regret in classical stochastic bandits, but its behavior in multi-agent learning remains less understood.Diffusion-Based Auctions for Multi-Winner Banner Ads
We propose a new framework for banner ad auctions, leveraging diffusion models to allow for multiple bidders to co-win a single banner ad opportunity, and in particular influence the ad shown on the…Beyond Independent Values: Optimal Auctions with Correlated Valuations for LLM-Native Advertising
Conversational assistants are becoming the place where people ask what to buy, and sponsored content is moving into their answers.Can You Trust Your Preference Models? Stackelberg Games for Alignment
Language models are frequently aligned to human preferences via imperfect evaluators whose errors can be exploited during optimization.The False Allure of "Security by Obscurity": A Game-Theoretic Approach
"Security by obscurity," or the idea that hiding how a system works helps protect it from adversaries, has long been poorly regarded in the security community.Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies
We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and can be matched in pairs for…Limit-sure Winning in Team Games without Shared Randomness
We study concurrent stochastic games in which a team of agents plays against an adversarial environment.Algorithms with Smoothed Polynomial-Time Complexity for Deterministic Discounted-sum and Mean-payoff Games
Turn-based deterministic games on graphs are two-player zero-sum games played on finite directed graphs, where the vertex set is partitioned between the Max and the adversarial Min Player.Assortment Optimization under the Mallows Model: Independent-Utility Choice Equivalence and Its Algorithmic Implications
The Mallows model is a well-established construct in preference modeling, describing random rankings through their Kendall-Tau distance from a reference permutation.The Sample Complexity of Multicalibration with an ERM Oracle
A predictor is multicalibrated with respect to a class of subpopulations (formally, of functions on the inputs, called auditors) if, for every subpopulation in the class and every value the…Optimally Pacing Budget Spending and Learning
We establish near-optimal regret bounds for budget-constrained online learning against arbitrary classes of budget-pacing experts in the adversarial setting.Refinement as a Service: Algorithmic Predictor Refinement
Prediction aggregation aims to combine information from multiple predictors into a more informative one.Epistemic Disturbance in the Graph Model for Conflict Resolution: State-Preserving Actions, Four-Valued Assessments, and the Distinction between Capability and Intention
In the graph model for conflict resolution (GMCR), a decision maker (DM) either moves the conflict to another state or does nothing.