Computer Science and Game Theory

Authors and titles for December 2019

[1] arXiv:1912.00011 [pdf, other]

Title: Heuristic Strategies in Uncertain Approval Voting Environments

Jaelle Scheuerman, Jason L. Harman, Nicholas Mattei, K. Brent Venable

Comments: arXiv admin note: text overlap with arXiv:1905.12104

Subjects: Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI); Multiagent Systems (cs.MA); General Economics (econ.GN)

[2] arXiv:1912.00251 [pdf, other]

Title: Smooth Fictitious Play in $N\times 2$ Potential Games

Brian Swenson, H. Vincent Poor

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

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

Title: Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations

Samuel Bismuth, Ivan Bliznets, Erel Segal-Halevi

Comments: Full version of a paper accepted to SAGT 2024

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

[4] arXiv:1912.00733 [pdf, other]

Title: On the Equilibria and Efficiency of Electricity Markets with Renewable Power Producers and Congestion Constraints

Hossein Khazaei, X. Andy Sun, Yue Zhao

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

[5] arXiv:1912.01548 [pdf, other]

Title: Experimental Evidence for Asymptotic Non-Optimality of Comb Adversary Strategy

Zachary Chase

Comments: 3 pages, 1 figure

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

[6] arXiv:1912.02000 [pdf, other]

Title: On games with coordinating and anti-coordinating agents

Martina Vanelli, Laura Arditti, Giacomo Como, Fabio Fagnani

Comments: 8 pages, 6 figures

Journal-ref: 21st IFAC World Congress, Berlin (2020), pp. 10975-10980

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

[7] arXiv:1912.02007 [pdf, other]

Title: On stability of users equilibria in heterogeneous routing games

Leonardo Cianfanelli, Giacomo Como

Comments: Extended version of conference paper accepted at CDC 2019

Subjects: Computer Science and Game Theory (cs.GT); Dynamical Systems (math.DS)

[8] arXiv:1912.02797 [pdf, other]

Title: One Dollar Each Eliminates Envy

Johannes Brustle, Jack Dippel, Vishnu V. Narayan, Mashbat Suzuki, Adrian Vetta

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

[9] arXiv:1912.03564 [pdf, other]

Title: Anchoring Theory in Sequential Stackelberg Games

Jan Karwowski, Jacek Mańdziuk, Adam Żychowski

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

[10] arXiv:1912.04056 [pdf, other]

Title: Maximal Information Propagation with Budgets

Haomin Shi, Yao Zhang, Zilin Si, Letong Wang, Dengji Zhao

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

[11] arXiv:1912.04493 [pdf, other]

Title: Memory depth of finite state machine strategies for the iterated prisoner's dilemma

T.J. Gaffney, Marc Harper, Vincent A. Knight

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

[12] arXiv:1912.04771 [pdf, other]

Title: Optimally Resilient Strategies in Pushdown Safety Games

Daniel Neider, Patrick Totzke, Martin Zimmermann

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

[13] arXiv:1912.04797 [pdf, other]

Title: Ride the Lightning: The Game Theory of Payment Channels

Zeta Avarikioti, Lioba Heimbach, Yuyi Wang, Roger Wattenhofer

Comments: In Proceedings of Financial Cryptography and Data Security (FC) 2020

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

[14] arXiv:1912.04867 [pdf, other]

Title: Robust Market Equilibria with Uncertain Preferences

Riley Murray, Christian Kroer, Alex Peysakhovich, Parikshit Shah

Comments: Extended preprint of an article accepted to AAAI-20. Contains supplementary material as appendices. Due to figures, this manuscript is best printed in color

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

[15] arXiv:1912.05770 [pdf, other]

Title: Algorithmic Price Discrimination

Rachel Cummings, Nikhil R. Devanur, Zhiyi Huang, Xiangning Wang

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

[16] arXiv:1912.06202 [pdf, other]

Title: Optimal, Truthful, and Private Securities Lending

Emily Diana, Michael Kearns, Seth Neel, Aaron Roth

Subjects: Computer Science and Game Theory (cs.GT); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Computational Finance (q-fin.CP)

[17] arXiv:1912.06244 [pdf, other]

Title: Screening of Informed and Uninformed Experts

Jorge Barreras (1 and 2), Alvaro Riascos (2 and 3) ((1) Department of Mathematics, University of Pennsylvania, (2) Quantil Research, Bogota, Colombia, (3) Department of Economics, Universidad de Los Andes)

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

[18] arXiv:1912.06370 [pdf, other]

Title: Toward an Automated Auction Framework for Wireless Federated Learning Services Market

Yutao Jiao, Ping Wang, Dusit Niyato, Bin Lin, Dong In Kim

Comments: 14 pages

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

[19] arXiv:1912.06428 [pdf, other]

Title: Reducing Inefficiency in Carbon Auctions with Imperfect Competition

Kira Goldner, Nicole Immorlica, Brendan Lucier

Comments: To appear in the 11th Innovations in Theoretical Computer Science (ITCS 2020)

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

[20] arXiv:1912.06513 [pdf, other]

Title: Reducing selfish routing inefficiencies using traffic lights

Charlotte Roman, Paolo Turrini

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

[21] arXiv:1912.07859 [pdf, other]

Title: Controlling network coordination games

Stephane Durand, Giacomo Como, Fabio Fagnani

Comments: submitted to the conference IFAC

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

[22] arXiv:1912.09584 [pdf, other]

Title: Quantal Response Equilibria in Binary Choice Games on Graphs

Andrey Leonidov, Alexey Savvateev, Andrew G. Semenov

Comments: 15 pages and no figures

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

[23] arXiv:1912.09905 [pdf, other]

Title: No-Regret Learning from Partially Observed Data in Repeated Auctions

Orcun Karaca, Pier Giuseppe Sessa, Anna Leidi, Maryam Kamgarpour

Journal-ref: IFAC-PapersOnLine, 53(2), 14-19, 2020

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

[24] arXiv:1912.10069 [pdf, other]

Title: Learning Reserve Prices in Second-Price Auctions

Yaonan Jin, Pinyan Lu, Tao Xiao

Comments: To appear in ITCS'23

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

[25] arXiv:1912.10208 [pdf, other]

Title: Influence in Weighted Committees

Sascha Kurz, Alexander Mayer, Stefan Napel

Comments: 27 pages, 10 figures, 4 tables

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

[26] arXiv:1912.10563 [pdf, other]

Title: Fair Matching in Dynamic Kidney Exchange

Irena Gao

Comments: 7 pages, 2 figures

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

[27] arXiv:1912.10967 [pdf, other]

Title: How Quantum Information can improve Social Welfare

Berry Groisman, Michael Mc Gettrick, Mehdi Mhalla, Marcin Pawlowski

Comments: 11 pages, 1 figure

Subjects: Computer Science and Game Theory (cs.GT); Information Theory (cs.IT); Quantum Physics (quant-ph)

[28] arXiv:1912.11575 [pdf, other]

Title: Hopping-Proof and Fee-Free Pooled Mining in Blockchain

Hongwei Shi, Shengling Wang, Qin Hu, Xiuzhen Cheng, Junshan Zhang, Jiguo Yu

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

[29] arXiv:1912.11620 [pdf, other]

Title: An Uncertainty- and Collusion-Proof Voting Consensus Mechanism in Blockchain

Shengling Wang, Xidi Qu, Qin Hu, Weifeng Lv

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

[30] arXiv:1912.12541 [pdf, other]

Title: Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings

Jugal Garg, Pooja Kulkarni, Rucha Kulkarni

Comments: Full version of SODA 2020 paper

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

[31] arXiv:1912.13249 [pdf, other]

Title: Generalized Rental Harmony

Erel Segal-Halevi

Comments: Generalized all results to "compensable tenants" - a class that contains both miserly and quasilinear tenants

Journal-ref: American Mathematical Monthly, 2022, 403--414

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

[32] arXiv:1912.00082 (cross-list from cs.DS) [pdf, other]

Title: Algorithms for flows over time with scheduling costs

Dario Frascaria, Neil Olver

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

[33] arXiv:1912.00225 (cross-list from cs.DS) [pdf, other]

Title: Mix and Match: Markov Chains & Mixing Times for Matching in Rideshare

Michael J. Curry, John P. Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, Yuhao Wan, Pan Xu

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

[34] arXiv:1912.00400 (cross-list from physics.soc-ph) [pdf, other]

Title: Critical mass effect in evolutionary games triggered by zealots

Alessio Cardillo, Naoki Masuda

Comments: 15 pages, 11 figures. Final version accepted for publication

Journal-ref: Phys. Rev. Research 2, 023305 (2020)

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

[35] arXiv:1912.00786 (cross-list from cs.DS) [pdf, other]

Title: On Clearing Prices in Matching Markets: A Simple Characterization without Duality

Xiaoming Li, Tao Lin

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

[36] arXiv:1912.00803 (cross-list from cs.AI) [pdf, other]

Title: Policies for constraining the behaviour of coalitions of agents in the context of algebraic information theory

Christopher Goddard

Comments: 27 pages

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

[37] arXiv:1912.01215 (cross-list from cs.CR) [pdf, other]

Title: Decentralized Common Knowledge Oracles

Austin K. Williams, Jack Peterson

Comments: 22 pages, 11 figures

Journal-ref: Ledger 4 (2019) 157-190

Subjects: Cryptography and Security (cs.CR); Computer Science and Game Theory (cs.GT)

[38] arXiv:1912.01809 (cross-list from math.OC) [pdf, other]

Title: Deep Fictitious Play for Finding Markovian Nash Equilibrium in Multi-Agent Games

Jiequn Han, Ruimeng Hu

Subjects: Optimization and Control (math.OC); Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG); Mathematical Finance (q-fin.MF)

[39] arXiv:1912.01854 (cross-list from cs.DS) [pdf, other]

Title: Popular Branchings and Their Dual Certificates

Telikepalli Kavitha, Tamás Király, Jannik Matuschke, Ildikó Schlotter, Ulrike Schmidt-Kraepelin

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

[40] arXiv:1912.02954 (cross-list from cs.CR) [pdf, other]

Title: Selfish Behavior in the Tezos Proof-of-Stake Protocol

Michael Neuder, Daniel J. Moroz, Rithvik Rao, David C. Parkes

Comments: Presented at Cryptoeconomic Systems Conference 2020. To appear in Cryptoeconomic Systems Journal Issue 0

Subjects: Cryptography and Security (cs.CR); Computer Science and Game Theory (cs.GT)

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

Title: Alternative Function Approximation Parameterizations for Solving Games: An Analysis of $f$-Regression Counterfactual Regret Minimization

Ryan D'Orazio, Dustin Morrill, James R. Wright, Michael Bowling

Comments: 11 pages, includes appendix

Journal-ref: Nineteenth International Conference on Autonomous Agents and Multi-Agent Systems, 9-13 May 2020, Auckland, New Zealand

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

[42] arXiv:1912.03132 (cross-list from cs.LG) [pdf, other]

Title: New Potential-Based Bounds for the Geometric-Stopping Version of Prediction with Expert Advice

Vladimir A. Kobzar, Robert V. Kohn, Zhilei Wang

Comments: To appear in MSML2020. arXiv admin note: text overlap with arXiv:1911.01641

Subjects: Machine Learning (cs.LG); Computer Science and Game Theory (cs.GT); Analysis of PDEs (math.AP); Optimization and Control (math.OC); Machine Learning (stat.ML)

[43] arXiv:1912.03295 (cross-list from cs.AI) [pdf, other]

Title: Tools for Mathematical Ludology

Paul Riggins, David McPherson

Comments: 20 pages, 9 figures; minor corrections and clarifications

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

[44] arXiv:1912.03350 (cross-list from cs.DS) [pdf, other]

Title: Online Vector Balancing and Geometric Discrepancy

Nikhil Bansal, Haotian Jiang, Sahil Singla, Makrand Sinha

Comments: Appears in STOC 2020

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

[45] arXiv:1912.03460 (cross-list from math.OC) [pdf, other]

Title: Continuous-time Discounted Mirror-Descent Dynamics in Monotone Concave Games

Bolin Gao, Lacra Pavel

Comments: 8 pages, 9 figures. This work has been submitted to the IEEE for possible publication

Journal-ref: IEEE Transactions on Automatic Control, vol 66 (11), 2021

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

[46] arXiv:1912.03729 (cross-list from cs.CC) [pdf, other]

Title: The Classes PPA-$k$: Existence from Arguments Modulo $k$

Alexandros Hollender

Comments: Final journal version. Preliminary version appeared at WINE 2019

Journal-ref: Theoretical Computer Science, 885:15-29 (2021)

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

[47] arXiv:1912.04165 (cross-list from math.OC) [pdf, other]

Title: Distributed Forward-Backward algorithms for stochastic generalized Nash equilibrium seeking

Barbara Franci, Sergio Grammatico

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

[48] arXiv:1912.04764 (cross-list from cs.NI) [pdf, other]

Title: Competition between tenants with strategic resource allocation in 5G network slicing

Luis Guijarro, Jose R. Vidal, Vicent Pla

Subjects: Networking and Internet Architecture (cs.NI); Computer Science and Game Theory (cs.GT)

[49] arXiv:1912.05164 (cross-list from econ.GN) [pdf, other]

Title: Third-Degree Price Discrimination Versus Uniform Pricing

Dirk Bergemann, Francisco Castro, Gabriel Weintraub

Comments: 26 pages, 5 figures

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

[50] arXiv:1912.05356 (cross-list from quant-ph) [pdf, other]

Title: Quantum voting and its physical interpretation

Woong-seon Yoo

Subjects: Quantum Physics (quant-ph); Computer Science and Game Theory (cs.GT)