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 12
On testing the incentive compatibility of single-parameter allocation mechanisms
This paper is the first work at the intersection of game theory and property testing, giving algorithms and lower bounds for efficiently testing whether an allocation mechanism is incentive…A 3.1462-Competitive Algorithm for Matroid Secretary
The matroid secretary problem asks an online algorithm to select a high-weight independent set from elements arriving in uniformly random order, with immediate and irrevocable decisions.An explicit solution of the five-expert prediction PDE and the exact optimality set of COMB
In this paper, we derive an explicit solution of the stationary prediction with expert advice PDE for five experts.High-Probability Nash Regret for Decentralized Learning in Markov $α$-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
We study decentralized learning of Nash equilibria (NE) in infinite-horizon discounted Markov games under bandit feedback, focusing on Markov $α$-potential games.Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets
We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history.Tight Subsidy Bounds for Weighted Proportional Allocation of Mixed Manna
We study the problem of fairly allocating m indivisible items among n agents with possibly unequal entitlements in the mixed manna setting, where each item may be perceived as a good or a chore by…Delegating Authorization to Misaligned Agents: Coalitional Alignment and Safe Control
Long-running AI agents create a control problem: each action they take changes the state, which in turn affects the trajectory of future actions.On the Hardness of Maximin Share Allocations
The maximin share (MMS) guarantee is a central fairness benchmark for allocating indivisible items.The fixed-point bundle method over product-of-simplex domains arising from game equilibria
This paper extends the fixed-point bundle framework for finite-dimensional variational inequalities (VIs) from the simplex domain to the product-of-simplex domain, which is directly applicable to…Symmetric solution of the Bellman optimality equation for repeated harmony game
In social dilemma games, additional rewards or punishments have been studied as means of promoting cooperation.Approximating Optimal Welfare in Complementary Allocation under Decentralized Information
Complementary resources are often allocated by agencies that see different coordinates of an individual's needs.Degree-Parameterized Analysis of Sampling-Based Online Matching
We study edge-weighted online bipartite matching under random arrival order, parameterized by the maximum offline degree $d$ and sampling fraction $θ$.The Matroid Secretary Conjecture is True
We resolve the matroid secretary conjecture, giving an online algorithm that accepts each element of the offline optimum with probability at least $1/4$.Pathwise Individual Rationality in Federated Learning: A Mechanism-Architecture Co-Design
Participation in federated learning (FL) comes at a cost.Decentralized Optimal Equilibrium Learning Over Dynamic Networks
This paper studies decentralized learning of socially optimal equilibria in finite normal-form games over dynamic communication networks.Stabilizing Performative Feedback Loops with Minimal Model Deployments
When algorithmic predictions inform people's decisions, the models we deploy are performative and actively shape the data we see.Adaptive Agent Design
We consider an agent acting against a general non-Markovian environment.Distortion of AI Alignment Revisited: RLHF is a Decent Utilitarian Aligner
While Reinforcement Learning from Human Feedback (RLHF) is the standard paradigm for aligning large language models with human preferences, its effectiveness in pluralistic settings has been called…Truncated Noisy Best-Response Algorithms: Toward Game Theoretic Learning with Safety Guarantees
We consider a game theoretic approach to solve multi-agent coordination problems with submodular maximization objectives.GPU-CFR: 80x Faster Counterfactual Regret Minimization by Compiling the Game to Static Dataflow and CUDA Graph Replay
Counterfactual regret minimization (CFR) is one of the few large numerical workloads that still runs faster on CPUs than on GPUs.