Computer Science and Game Theory

Authors and titles for March 2025

[1] arXiv:2503.00078 [pdf, html, other]

Title: Equilibrium and Selfish Behavior in Network Contagion

Yi Zhang, Sanjiv Kapoor

Subjects: Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC)

[2] arXiv:2503.00170 [pdf, other]

Title: Elastic Restaking Networks

Roi Bar-Zur, Ittay Eyal

Subjects: Computer Science and Game Theory (cs.GT); Distributed, Parallel, and Cluster Computing (cs.DC)

[3] arXiv:2503.00227 [pdf, html, other]

Title: The Learning Approach to Games

Melih İşeri, Erhan Bayraktar

Comments: 32 pages, 2 figures. Related repositories are this http URL and this http URL

Subjects: Computer Science and Game Theory (cs.GT); Theoretical Economics (econ.TH); Optimization and Control (math.OC)

[4] arXiv:2503.00788 [pdf, html, other]

Title: Taming Infinity one Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs

Michal Ajdarów, James C. A. Main, Petr Novotný, Mickael Randour

Comments: 55 pages

Subjects: Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI); Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO); Probability (math.PR)

[5] arXiv:2503.00885 [pdf, html, other]

Title: Social Welfare Maximization in Approval-Based Committee Voting under Uncertainty

Haris Aziz, Yuhang Guo, Venkateswara Rao Kagita, Baharak Rastegari, Mashbat Suzuki

Subjects: Computer Science and Game Theory (cs.GT)

[6] arXiv:2503.01368 [pdf, html, other]

Title: The Complexity of Extending Fair Allocations of Indivisible Goods

Argyrios Deligkas, Eduard Eiben, Robert Ganian, Tiger-Lily Goldsmith, Stavros D. Ioannidis

Comments: 19 pages; Accepted to AAAI 2025

Subjects: Computer Science and Game Theory (cs.GT); Data Structures and Algorithms (cs.DS)

[7] arXiv:2503.01529 [pdf, html, other]

Title: Online Two-Sided Markets: Many Buyers Enhance Learning

Anna Lunghi, Matteo Castiglioni, Alberto Marchesi

Subjects: Computer Science and Game Theory (cs.GT)

[8] arXiv:2503.01701 [pdf, other]

Title: Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond

Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti

Subjects: Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG)

[9] arXiv:2503.01976 [pdf, html, other]

Title: Learning a Game by Paying the Agents

Brian Hu Zhang, Tao Lin, Yiling Chen, Tuomas Sandholm

Subjects: Computer Science and Game Theory (cs.GT)

[10] arXiv:2503.01985 [pdf, html, other]

Title: Proportionality in Thumbs Up and Down Voting

Sonja Kraiczy, Georgios Papasotiropoulos, Grzegorz Pierczyński, Piotr Skowron

Subjects: Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI)

[11] arXiv:2503.02088 [pdf, other]

Title: Online Fair Division: Towards Ex-Post Constant MMS Guarantees

Pooja Kulkarni, Ruta Mehta, Parnian Shahkar

Comments: 41 pages

Subjects: Computer Science and Game Theory (cs.GT); Data Structures and Algorithms (cs.DS); Multiagent Systems (cs.MA)

[12] arXiv:2503.02089 [pdf, other]

Title: Improved MMS Approximations for Few Agent Types

Jugal Garg, Parnian Shahkar

Comments: 27 pages

Subjects: Computer Science and Game Theory (cs.GT); Data Structures and Algorithms (cs.DS); Multiagent Systems (cs.MA)

[13] arXiv:2503.02326 [pdf, html, other]

Title: A differential model of $N$ player games concerning ethical dilemmas

Ramkrishna Joshi, Aniruddha Joshi

Comments: 21 pages

Subjects: Computer Science and Game Theory (cs.GT); Physics and Society (physics.soc-ph)

[14] arXiv:2503.02429 [pdf, other]

Title: The Inversion Paradox and Ranking Methods in Tournaments

Guillaume Chéze (IMT), Etienne Fieux (IMT)

Subjects: Computer Science and Game Theory (cs.GT); Multiagent Systems (cs.MA)

[15] arXiv:2503.02592 [pdf, html, other]

Title: Succinct Ambiguous Contracts

Paul Duetting, Michal Feldman, Yarden Rashti

Subjects: Computer Science and Game Theory (cs.GT); Theoretical Economics (econ.TH)

[16] arXiv:2503.03082 [pdf, html, other]

Title: A Linear Theory of Multi-Winner Voting

Lirong Xia

Subjects: Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG); Theoretical Economics (econ.TH)

[17] arXiv:2503.03676 [pdf, html, other]

Title: Optimally Installing Strict Equilibria

Jeremy McMahan, Young Wu, Yudong Chen, Xiaojin Zhu, Qiaomin Xie

Subjects: Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG)

[18] arXiv:2503.04202 [pdf, html, other]

Title: Computational Intractability of Strategizing against Online Learners

Angelos Assos, Yuval Dagan, Nived Rajaraman

Comments: 32 pages

Subjects: Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG)

[19] arXiv:2503.04542 [pdf, html, other]

Title: Inducing Efficient and Equitable Professional Networks through Link Recommendations

Cynthia Dwork, Chris Hays, Lunjia Hu, Nicole Immorlica, Juan Perdomo

Comments: 34 pages, 4 figures

Subjects: Computer Science and Game Theory (cs.GT); Computers and Society (cs.CY)

[20] arXiv:2503.04661 [pdf, html, other]

Title: Control for Coalitions in Parliamentary Elections

Hodaya Barr, Eden Hartman, Yonatan Aumann, Sarit Kraus

Subjects: Computer Science and Game Theory (cs.GT); Theoretical Economics (econ.TH)

[21] arXiv:2503.05338 [pdf, html, other]

Title: Using "Failure Costs" to Guarantee Execution Quality in Competitive and Permissionless Order Flow Auctions

Alex Watts, Davide Sinesi, Jacob Greene

Subjects: Computer Science and Game Theory (cs.GT); Theoretical Economics (econ.TH)

[22] arXiv:2503.05695 [pdf, other]

Title: On Almost Fair and Equitable Allocations of Indivisible Items for Non-monotone Valuations

Vittorio Bilò, Martin Loebl, Cosimo Vinci

Subjects: Computer Science and Game Theory (cs.GT); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)

[23] arXiv:2503.06017 [pdf, html, other]

Title: Welfare Approximation in Additively Separable Hedonic Games

Martin Bullinger, Vaggos Chatziafratis, Parnian Shahkar

Comments: Appears in: Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025)

Subjects: Computer Science and Game Theory (cs.GT); Data Structures and Algorithms (cs.DS)

[24] arXiv:2503.06942 [pdf, other]

Title: A Practical Guide to Budget Pacing Algorithms in Digital Advertising

Yuanlong Chen

Subjects: Computer Science and Game Theory (cs.GT)

[25] arXiv:2503.07387 [pdf, other]

Title: Are System Optimal Dynamic Flows Implementable by Tolls?

Lukas Graf, Tobias Harks, Julian Schwarz

Subjects: Computer Science and Game Theory (cs.GT); Optimization and Control (math.OC)

[26] arXiv:2503.07558 [pdf, html, other]

Title: Incentive-Compatible Recovery from Manipulated Signals, with Applications to Decentralized Physical Infrastructure

Jason Milionis, Jens Ernstberger, Joseph Bonneau, Scott Duke Kominers, Tim Roughgarden

Subjects: Computer Science and Game Theory (cs.GT); Emerging Technologies (cs.ET); Machine Learning (cs.LG); Theoretical Economics (econ.TH); Trading and Market Microstructure (q-fin.TR)

[27] arXiv:2503.08385 [pdf, html, other]

Title: Distributed Satellites Dynamic Allocation for Grids with Time Windows: A Potential Game Approach

Weiyi Yang, Yingwu Chen, Xiaolu Liu, Jun Wen, Lei He

Comments: 19 pages, 12 figures

Subjects: Computer Science and Game Theory (cs.GT)

[28] arXiv:2503.08416 [pdf, html, other]

Title: A Distributed Clustering Algorithm based on Coalition Game for Intelligent Vehicles

Weiyi Yang, Xiaolu Liu, Lei He, Yonghao Du, Yingwu Chen

Comments: 8 pages, 4 figures

Subjects: Computer Science and Game Theory (cs.GT)

[29] arXiv:2503.09039 [pdf, html, other]

Title: Incentive Analysis for Agent Participation in Federated Learning

Lihui Yi, Xiaochun Niu, Ermin Wei

Subjects: Computer Science and Game Theory (cs.GT); Systems and Control (eess.SY)

[30] arXiv:2503.09538 [pdf, other]

Title: Differentially Private Equilibrium Finding in Polymatrix Games

Mingyang Liu, Gabriele Farina, Asuman Ozdaglar

Subjects: Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI); Cryptography and Security (cs.CR); Machine Learning (cs.LG)

[31] arXiv:2503.00313 (cross-list from eess.SY) [pdf, html, other]

Title: Communication and Control Co-design in Non-cooperative Games

Shubham Aggarwal, Tamer Başar, Dipankar Maity

Comments: Submitted to IEEE for possible publication

Subjects: Systems and Control (eess.SY); Computer Science and Game Theory (cs.GT); Optimization and Control (math.OC)

[32] arXiv:2503.00632 (cross-list from cs.CY) [pdf, html, other]

Title: Policy Design in Long-Run Welfare Dynamics

Jiduan Wu, Rediet Abebe, Moritz Hardt, Ana-Andreea Stoica

Subjects: Computers and Society (cs.CY); Computer Science and Game Theory (cs.GT); General Economics (econ.GN)

[33] arXiv:2503.01053 (cross-list from econ.TH) [pdf, html, other]

Title: Commitment, Conflict, and Status Quo in Bargaining

Harry Pei

Subjects: Theoretical Economics (econ.TH); Computer Science and Game Theory (cs.GT)

[34] arXiv:2503.02327 (cross-list from eess.SP) [pdf, html, other]

Title: A Game-Theoretic Approach for High-Resolution Automotive FMCW Radar Interference Avoidance

Yunian Pan, Jun Li, Lifan Xu, Shunqiao Sun, Quanyan Zhu

Subjects: Signal Processing (eess.SP); Computer Science and Game Theory (cs.GT)

[35] arXiv:2503.02582 (cross-list from cs.AI) [pdf, html, other]

Title: Playing games with Large language models: Randomness and strategy

Alicia Vidler, Toby Walsh

Comments: 9 pages

Subjects: Artificial Intelligence (cs.AI); Computer Science and Game Theory (cs.GT)

[36] arXiv:2503.02646 (cross-list from stat.ML) [pdf, html, other]

Title: A Tight Regret Analysis of Non-Parametric Repeated Contextual Brokerage

François Bachoc, Tommaso Cesari, Roberto Colomboni

Comments: AISTATS 2025

Subjects: Machine Learning (stat.ML); Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG)

[37] arXiv:2503.02825 (cross-list from cs.LG) [pdf, html, other]

Title: On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games

Yang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, Haipeng Luo, Weiqiang Zheng

Comments: 33 pages

Subjects: Machine Learning (cs.LG); Computer Science and Game Theory (cs.GT); Optimization and Control (math.OC)

[38] arXiv:2503.02952 (cross-list from cs.CY) [pdf, html, other]

Title: A Theoretical Model for Grit in Pursuing Ambitious Ends

Avrim Blum, Emily Diana, Kavya Ravichandran, Alexander Williams Tolbert

Subjects: Computers and Society (cs.CY); Data Structures and Algorithms (cs.DS); Computer Science and Game Theory (cs.GT); Applications (stat.AP)

[39] arXiv:2503.03184 (cross-list from stat.ML) [pdf, other]

Title: PAC Learning with Improvements

Idan Attias, Avrim Blum, Keziah Naggita, Donya Saless, Dravyansh Sharma, Matthew Walter

Comments: 40 pages, 13 figures

Subjects: Machine Learning (stat.ML); Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG)

[40] arXiv:2503.03401 (cross-list from cs.LG) [pdf, html, other]

Title: Evolutionary Prediction Games

Eden Saig, Nir Rosenfeld

Comments: Comments are welcome

Subjects: Machine Learning (cs.LG); Computers and Society (cs.CY); Computer Science and Game Theory (cs.GT)

[41] arXiv:2503.03774 (cross-list from cs.AI) [pdf, html, other]

Title: Fair Play in the Fast Lane: Integrating Sportsmanship into Autonomous Racing Systems

Zhenmin Huang, Ce Hao, Wei Zhan, Jun Ma, Masayoshi Tomizuka

Subjects: Artificial Intelligence (cs.AI); Computer Science and Game Theory (cs.GT); Robotics (cs.RO); Systems and Control (eess.SY)

[42] arXiv:2503.03866 (cross-list from cs.AI) [pdf, html, other]

Title: Learning to Negotiate via Voluntary Commitment

Shuhui Zhu, Baoxiang Wang, Sriram Ganapathi Subramanian, Pascal Poupart

Comments: AISTATS 2025

Subjects: Artificial Intelligence (cs.AI); Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG); Multiagent Systems (cs.MA)

[43] arXiv:2503.04196 (cross-list from cs.DS) [pdf, html, other]

Title: Revisiting Ranking for Online Bipartite Matching with Random Arrivals: the Primal-Dual Analysis

Bo Peng, Zhihao Gavin Tang

Subjects: Data Structures and Algorithms (cs.DS); Computer Science and Game Theory (cs.GT)

[44] arXiv:2503.04759 (cross-list from cs.LO) [pdf, html, other]

Title: Games with $ω$-Automatic Preference Relations

Véronique Bruyère, Christophe Grandmont, Jean-François Raskin

Subjects: Logic in Computer Science (cs.LO); Computer Science and Game Theory (cs.GT)

[45] arXiv:2503.04840 (cross-list from cs.CL) [pdf, html, other]

Title: Framing the Game: How Context Shapes LLM Decision-Making

Isaac Robinson, John Burden

Subjects: Computation and Language (cs.CL); Artificial Intelligence (cs.AI); Computer Science and Game Theory (cs.GT)

[46] arXiv:2503.05381 (cross-list from econ.TH) [pdf, html, other]

Title: Construction of Compromise Values for Cooperative Games

Robert P. Gilles, René van den Brink

Subjects: Theoretical Economics (econ.TH); Computer Science and Game Theory (cs.GT)

[47] arXiv:2503.05925 (cross-list from cs.LG) [pdf, html, other]

Title: ElementaryNet: A Non-Strategic Neural Network for Predicting Human Behavior in Normal-Form Games

Greg d'Eon, Hala Murad, Kevin Leyton-Brown, James R. Wright

Comments: 14 pages. Submitted to EC 2025

Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computer Science and Game Theory (cs.GT)

[48] arXiv:2503.05963 (cross-list from cs.AI) [pdf, html, other]

Title: Bayesian Graph Traversal

William N. Caballero, Phillip R. Jenkins, David Banks, Matthew Robbins

Comments: 26 pages, 7 tables, 2 figures

Subjects: Artificial Intelligence (cs.AI); Computer Science and Game Theory (cs.GT); Other Statistics (stat.OT)

[49] arXiv:2503.06582 (cross-list from econ.TH) [pdf, html, other]

Title: The Role of the Marketplace Operator in Inducing Competition

Tiffany Ding, Dominique Perrault-Joncas, Orit Ronen, Michael I. Jordan, Dirk Bergemann, Dean Foster, Omer Gottesman

Subjects: Theoretical Economics (econ.TH); Computer Science and Game Theory (cs.GT)

[50] arXiv:2503.07013 (cross-list from cs.RO) [pdf, html, other]

Title: Learning Nash Equilibrial Hamiltonian for Two-Player Collision-Avoiding Interactions

Lei Zhang, Siddharth Das, Tanner Merry, Wenlong Zhang, Yi Ren

Comments: Accepted by 2025 ACC

Subjects: Robotics (cs.RO); Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG)