EFX and PMMS guarantee exactly 10/17 of MMS
A charging argument pins the worst-case fairness of two envy notions to one number, tied to machine covering.
cs.GT
Computer Science and Game Theory
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.
sort pith recommended most recent
Best workers first, prices by backward induction: optimal
A sort plus a backward pass beats 'low-ball' offers, exactly for many cost laws and near-optimally for all.
· “Sequential Offering in On-Demand Platforms: On the Optimality of Greedy Ranking”
One lottery, no mixing, hits voting distortion 2.13713
A single equilibrium distribution comes within 0.025 of the best provable bound on election quality.
· “Stable Voting Rules on the Edge of Optimal Metric Distortion”
Budgets can grow without bound
Rewards make the play space infinite, but an EXP algorithm still computes the minimal winning budget.
· “Bidding Games with Rewards: Taming Infinite Configuration Space”
Independent learning in discounted games hits a quasi-polynomial barrier
Under ETH for PPAD, polynomial CCE computation is impossible; first radically uncoupled algorithm matches the hardness bound.
· “Independent Reinforcement Learning in Discounted Markov Games”
No PMMS allocation exists for 3 agents
With additive preferences, pairwise-maximin fairness fails at 3 agents, and no approximation above 0.987 survives.
· “PMMS Allocations Need Not Exist for 3 Agents with Additive Valuations”
Algorithm guarantees proportional spending up to one project
A polynomial-time rule achieves FJR1+ for additive utilities and arbitrary costs.
· “Strengthening Proportionality in Participatory Budgeting with Additive Utilities”
Optimal PAV committee problems are Δ₂^P and #·OptP complete
For approval elections, three natural questions about optimal committees are shown to require an NP oracle or to count optimal solutions…
Reciprocal rules keep 75% of quality in proportional voting
New axioms scale voter entitlements by candidate quality, enabling proportional committees with constant-factor quality guarantees at no…
· “Approval-Based Multiwinner Voting with Candidate Qualities”
A policy loop finds near-Nash play in multi-player zero-sum games
Last-iterate guarantee matches two-player speed: no equilibrium solver at any state-stage pair.
· “Last-Iterate Convergence of Policy Dynamics in Zero-Sum Networked Separable Markov Games”
Comparison queries hit 13/11-MMS for chores
Logarithmic query complexity achieves state-of-the-art fairness with only bundle comparisons.
Risk-seeking learners lock onto the high-payoff equilibrium
In coordination games, one risk parameter flips long-run selection between the efficient and the safe outcome.
· “Entropic Risk-Sensitive Evolutionary Learning and Equilibrium Selection in Coordination Games”
One certificate vouches for many winning strategies at once
Any strategy following an ASCert meets its probability target, even after runtime re-adaptation.
· “Towards Actionable Strategy Certificates in Stochastic Parity Games”
2/(1+k) ratio is tight for strategyproof bridge-building
Randomized mechanism gives ≤5 social-cost ratio independent of population size; real-line model bounds improved
· “Strategyproof Mechanisms for Connecting Impassable Regions”
Interaction-rank selection certified from offline logs
SIRV returns the smallest model rank with a target-risk bound and a CCE gap certificate, abstaining when data is insufficient.
· “Rank Without an Oracle: Deviation-Aware Interaction-Rank Selection from Offline Multi-Agent Logs”
Fair and efficient voting together is NP-hard
No polynomial-time rule guarantees both justified representation and Pareto optimality unless P=NP.
Subquadratic subsidies for all agent counts
O(n^{3/2}\sqrt{\log n}) subsidy bound for envy-free allocation with nonnegative or nonpositive valuations
· “Subquadratic Subsidies for Nonnegative or Nonpositive Valuations”
This paper introduces GRAF, a greedy algorithm for recommending contests to crowdsourcing…
A greedy contest-recommendation framework whose scoring rule is evolved by an LLM achieves near-optimal overall effort with low worker…
· “Guiding Worker Self-Selection in Crowdsourcing Contests: An LLM-Augmented Algorithmic Approach”
Polynomial-time algorithm for approval committees with EJR+ and 1.346-fPO
Combines concave optimization, pipage rounding, and local search to match the best of PAV without its NP-hardness.
· “Finding Representative and Approximately Efficient Committees”
Four agents, 52 goods: no pairwise fair-share split exists
A tuned instance settles the open question of exact PMMS existence for additive valuations in the negative.
Hiding map data drops flag captures to zero
An observation-masking oracle turns fixed defenders into a zero-capture defense on grid and street maps.
· “Games Over Observation Spaces in Multi-Agent Capture the Flag”
UAV picks scientifically valuable cells under battery limits
A utility-driven framework selects high-value sensor cells while respecting UAV energy constraints.
· “Utility-Driven Spatial Data Sampling for UAV-Assisted Scientific Smart Farming”
Perpendicular square lottery yields optimal √2 ratio
A randomized mechanism proves that truthful facility location on the plane is easier than on the line, with a tight approximation guarantee.
Approval core exists when voters dislike at most two
New bound on the open problem of core nonemptiness in multi-winner elections.
Every nine-seat approval election has a stable core
Known only up to eight seats before; an exact computer-checked proof now closes the nine-seat case.
· “The Deterministic Hare Core Is Nonempty for Nine-Seat Approval Elections”
This paper determines the computational cost of deciding whether a multiplayer…
For concurrent multiplayer reachability games with memoryless strategies, the equilibrium realizability problem is NP-complete under…
96.8% simulated defense success when guards plan as a game
Treating intruders as rational opponents, not fixed targets, closes 41% of the gap to perfect defense in simulation.
· “Game-Theoretic Drone Swarm Defense: A Case Study in Applied Differential Game Theory”
Polynomial samples yield equilibria (or a proof none exist)
Two-player games with unknown dynamics: learn a near-optimal equilibrium, or a sound proof that none exists.
LLM builds game abstractions without human expertise
Using only a rules description, the pipeline beats standard baselines in poker and a novel game by up to 62% less exploitability.
Regret stops growing: constant bound for any game
The paper discovers that by designing an optimistic predictor that is a discounted (N+1)-th order finite difference of past payoffs…
· “Constant regret in general games via higher-order optimism”
Constant bi-criteria ratios for batched Pandora's Box
Algorithms achieve (1-1/e) and 0.52 guarantees despite NP-hardness
When goods are tiny, EF1 allocations are nearly optimal
Small-item condition yields 1−O(ε²) approximation; deep RL matches top heuristic
Victory impact metric balances turn-based game units automatically
New framework TBCA tunes attack and defense stats to yield fair gameplay across random teams.
· “Turn-Based Combat Arena: A New Framework for Multiagent Training and Game Balancing”
Bayesian equilibrium catches 28% of insider threats before exfiltration
Despite sparse data, the game-theoretic mechanism detects malicious users 1.7–4.5 days earlier than rational baselines with <1.6% false…
· “A Bayesian Correlated Equilibrium for Early Insider-Threat Detection”
Constant-factor GFT in multidimensional bilateral trade
Simple mechanisms achieve at least 1/44 and 1/1033 of first-best gains from trade.
· “Approximately Efficient Multidimensional Bilateral Trade”
Near-envy-free shares always exist when goods and chores mix
The paper settles the open question and yields a finite lottery that is fair in expectation, nearly fair in every draw.
A fair stable matching algorithm that satisfies everyone's interests
Nash social welfare maximization over stable matchings runs in O(n^4 log n) and beats existing measures in practice.
Fully Justified Representation strongly NP-hard for 0-5 utilities
First strong NP-hardness for any justified representation axiom; sequential rules cannot achieve stronger axioms.
· “The Complexity of Justified Representation with Additive Utilities”
Sharing helps when error shrinks faster than rescue
A single ratio of residual errors decides whether pooling signals beats keeping independent attempts—but equilibrium selection also matters.
Revelation principle and cycle conditions define implementable AI behavior
A new mechanism-design framework shows how to incentivize both honesty and obedience in AI agents with unknown preferences and capabilities.
Fair division up to one item always exists for weighted mixed manna
Items mix valued goods and dreaded chores under unequal claims; the open case is now closed, in polynomial time.
Regular languages capture every Grundy value on right-linear grammars
The maximum Grundy value was undecidable for linear grammars; on right-linear ones a DFA settles it.
Stable coloring needs Θ(log n) colors for trees
New graph invariant bridges Grundy number and reachability; planar graphs O(log² n)
Stable committees always exist for up to eight voters
A candidate-weighted Nash welfare scheme plus an exact computer check settles the last open eight-voter case.
A versatile new move in Rock-Paper-Scissors yields only 55.5% wins
Capbility does not equal value: the new move is played rarely, and its threat mainly helps existing moves.
· “Rock, Paper, Scissors, ... Dynamite - A Model of Disruption from New Technologies”
Constant regret is now achievable in every finite game
A deterministic uncoupled algorithm bounds each player's regret independently of how long the game runs.
EF1 fairness always possible for 3 agents under laminar matroids
New reduction cuts the problem to a single small case, solved by exhaustive check; transversal matroids work for any number of agents.
· “Constrained Fair Allocations via Partition Matroid Reductions”
Reallocation budget erases usual gap between EF1 and EF
When you must move few goods, achieving EF1 becomes as hard as achieving full envy-freeness in most settings.
Regularized policy gradients bound test-time reasoning safety
Neural gadget games scale subgame solving and prove exploitability cannot blow up under fixed regularization
· “Test-time Reinforcement Learning in Imperfect Information Games”
Language instructions boost joint bidding and pricing by up to 6.5%
LangBP's target-state execution and effect-grouped optimization beat all baselines on AuctionNet and in live A/B tests
· “LangBP: Language-Guided Reasoning and Acting for Joint Bidding and Pricing”
Best possible 2-approximation for facility location with a preexisting site
Strategy-proof mechanism guarantees no agent can gain by lying while placing a new facility near an existing one on a line.
· “Mechanism Design for Facility Location Games Under a Prelocated Facility”
Exact ratio of residual to classic maximin share is λ_n
The worst-case guarantee forms odd-even plateaus and converges to 2/3, setting a hard limit on dynamic fair division algorithms.
· “Residual Maximin Share: Exact Finite-Agent Frontier, Sparse Extremizers, and Threshold Cuts”
This preprint turns fair division of indivisible goods into a list-coloring problem on…
Rival-injective endpoint ownership is exactly support-list coloring, and with maximum-singleton dominance it yields sufficient…
· “Rival-Injective Allocations: Support-List Structure and Maximum-Anchor EFX₀ Certificates”
Find a proportional committee in only k rejected proposals
Rejection counts depend only on committee size k, never on the number of voters or candidates.
· “Learning Proportional Committees from Violation Feedback”
Non-traceable graphs guarantee EF1_outer allocations
First infinite family without Hamiltonian paths has universal fair division, plus a full threshold characterization for trees.
EF1 and EFX existence tied to number of normalized agents
Under two-level (Boolean) valuations, the count of agents who place low value on the empty set determines which envy-free variants are…
· “Fair Division Under Boolean Valuations: Beyond Normalization”
Distributed GNE algorithm converges without multiplier exchange
New method for multi-robot placement finds generalized Nash equilibria with lower communication and stronger privacy.
· “Fully Distributed GNE Algorithms for Multi-Robot Placement without Consensus on Multipliers”
Belief-state search reaches Pokémon VGC ladder at human level
Adapting the Student of Games framework with exact chance enumeration yields an agent that achieves 1350–1400 Elo on the live Showdown…
· “PokaiTrainer: Scaling Belief-State Search to Competitive Pok\'emon VGC”
Two-factor Droop core always exists for agent-center clusterings
Scarf's theorem yields a fractional core, then greedy rounding achieves the optimal 2-approximation.
· “Optimally Selecting Representative Agents from a Metric Space”
Borda: O(√m) queries suffice
Score-threshold queries certify Borda winners near-optimally, while Condorcet-consistent rules resist sublinear elicitation.
Oversight needs exactly k agents
A polynomial-time algorithm finds the minimum number of agents that guarantee k-oversight in any sequential decision process.
Exact defense value found for two-attack General Lotto game
A model with networked resource effectiveness yields a closed-form equilibrium and tight bounds for general n.
· “Networked Multi-Resource Defense Capabilities in a General Lotto Game”
Guaranteed-utility mechanism beats AGV on collusion
TU-GUM achieves efficiency, budget balance, and collusion-proofness in dynamic stochastic projects – and is a special case of a simple…
GR(1) games learn and adapt to environment assumptions at runtime
Precomputed strategy library combined with asymptotic liveness monitors gives exponential speedup over doubly-exponential baseline
DP computes cheapest multi-round test to stop AI cheaters
Multi-round testing at increasing security levels guarantees honest top-k selection at minimal total proctoring cost
· “Optimal Adversarial Testing: Extracting Honest Test Results from Dishonest Test Takers”
Plurality-poll approval hits 4.236 distortion
A two-round protocol using only top-choice shares achieves distortion 2+√5, improving bounds for Bucklin and majoritarian compromise.
· “A Constant Metric Distortion Protocol for Approval Voting Given Plurality Polls”
Autobidding beats actor-critic with LLM-inspired method
Critic-free RL method boosts autobidding performance on three benchmarks.
· “Fine-Tuning Autobidders with Group Relative Policy Optimization”
AI alignment is a game no rival can beat
A survey maps alignment methods onto game theory, separating formal guarantees from loose analogy.
Best coordination networks for two types of agents are stochastic block models
When humans and machines have different rationality, the optimal graphon is piecewise constant with at most three connection densities
Sufficient discounting contracts mean-field games on every horizon
A single exponential-weighting condition now covers finite and infinite horizons, with explicit error bounds between them.
· “Horizon-Independent Contraction for Continuous-Time Discounted Regularized Mean-Field Games”
Three voters beat any challenger in planar distance votes
A new piercing result shows three chosen peers defeat every rival under Manhattan and maximum-coordinate metrics.
· “Condorcet-Winning Sets and Peer Selection in Planar Metric Elections”
Key proportionality axioms become equivalent when candidates can be repeated
Approval-based apportionment reveals a simpler axiom hierarchy, with implications for the harder committee-elections setting.
· “Approval-Based Apportionment: Like Portioning, Approximately like Committee Voting”
Auction embeds advertisers into every token of LLM output
LAMA proves Markov DSIC and near-optimal welfare, enabling generation-native advertising at token granularity.
Deposits restore cooperation in finitely repeated games
Voluntary stakes, forfeited after a deviation, let finite-horizon games support cooperative equilibria for patient enough players.
· “Refundable Deposits: How to Restore Cooperation in Finitely Repeated Games”
AI bidders can learn tacit collusion in power markets
When lines bind, independent learning agents sustain supra-competitive prices, and no one told them to collude.
· “AI agents in Algorithmic Electricity Markets: On the Emergence of Tacit Collusion”
Short uniform lists approach 5/2 distortion in metric voting
A compression theorem yields O(ε⁻³) candidates for distortion 5/2+ε, independent of voter and candidate counts.
· “Robust Lottery Compression for Metric Voting: A Transfer Principle for Bounded Randomness”
A fair-division guarantee jumps from 5/9 to 3/5
New algorithm gives every agent 60 percent of the maximin share even when agents disagree on what can be split.
· “A lone divider allocation algorithm with subjective divisibility”
AI advice raises prices 29% only in women's markets
A lab experiment finds gender composition determines whether sellers follow algorithmic pricing recommendations.
Short VDF delays fail economic security tests for randomness beacons
Rational attackers profit by accelerating hardware to capture MEV, so delays must exceed cost-based thresholds derived from an optimal-stop
· “Economic Security of VDF-Based Randomness Beacons: Models, Thresholds, and Design Guidelines”
Data-augmented starts cut exploitability in hard-to-explore games
Sampling intermediate states from offline demonstrations lets regularized gradients find lower-exploitability equilibria under fixed compute
· “Data-Augmented Game Starts for Accelerating Self-Play Exploration in Imperfect Information Games”
