p7cs.GT

Category

cs.GT

137 papers

Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learning

Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita-Rotaru, Bo Li

1804.00308

Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction

Jacob Steinhardt, Gregory Valiant, Moses Charikar

1606.05374

Consensus Halving is PPA-Complete

Aris Filos-Ratsikas, Paul W. Goldberg

1711.04503

The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

1511.03592

A Size-Free CLT for Poisson Multinomials and its Applications

Constantinos Daskalakis, Anindya De, Gautam Kamath, Christos Tzamos

1511.03641

Universally Utility-Maximizing Privacy Mechanisms

Arpita Ghosh, Tim Roughgarden, Mukund Sundararajan

0811.2841

Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness

Michael Kearns, Seth Neel, Aaron Roth, Zhiwei Steven Wu

1711.05144

Which Training Methods for GANs do actually Converge?

Lars Mescheder, Andreas Geiger, Sebastian Nowozin

1801.04406

On the convergence of single-call stochastic extra-gradient methods

Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos

1908.08465

Tree Polymatrix Games are PPAD-hard

Argyrios Deligkas, John Fearnley, Rahul Savani

2002.12119

Consensus-Halving: Does It Ever Get Easier?

Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, Manolis Zampetakis

2002.11437

Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent

James P. Bailey, Gauthier Gidel, Georgios Piliouras

1907.04392

Last-iterate convergence rates for min-max optimization

Jacob Abernethy, Kevin A. Lai, Andre Wibisono

1906.02027

Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents

Argyrios Deligkas, Aris Filos-Ratsikas, Alexandros Hollender

2007.15125

Inapproximability of Nash Equilibrium

Aviad Rubinstein

1405.3322

Computing Approximate Nash Equilibria in Polymatrix Games

Argyrios Deligkas, John Fearnley, Rahul Savani, Paul Spirakis

1409.3741

Fair and Efficient Cake Division with Connected Pieces

Eshwar Ram Arunachaleswaran, Siddharth Barman, Rachitesh Kumar, Nidhi Rathi

1907.11019

Approximating Nash Equilibria in Tree Polymatrix Games

Siddharth Barman, Katrina Ligett, Georgios Piliouras

1604.02676

Settling the complexity of computing approximate two-player Nash equilibria

Aviad Rubinstein

1606.04550

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

Alexandros Hollender

1912.03729

Hardness Results for Consensus-Halving

Aris Filos-Ratsikas, Soren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang

1609.05136

Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash

Yakov Babichenko, Christos Papadimitriou, Aviad Rubinstein

1504.02411

The Hairy Ball Problem is PPAD-Complete

Paul W. Goldberg, Alexandros Hollender

1902.07657

Inapproximability of NP-Complete Variants of Nash Equilibrium

Per Austrin, Mark Braverman, Eden Chlamtac

1104.3760

Approximate Well-supported Nash Equilibria below Two-thirds

John Fearnley, Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen

1204.0707

Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization

Constantinos Daskalakis, Ioannis Panageas

1807.04252

Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games

Yun Kuen Cheung, Georgios Piliouras

1905.08396

The Complexity of Non-Monotone Markets

Xi Chen, Dimitris Paparas, Mihalis Yannakakis

1211.4918

The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches

Aris Filos-Ratsikas, Paul W. Goldberg

1805.12559

Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games

Xi Chen, Yu Cheng, Bo Tang

1511.00785

Cycles in adversarial regularized learning

Panayotis Mertikopoulos, Christos Papadimitriou, Georgios Piliouras

1709.02738

Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks

Tengyuan Liang, James Stokes

1802.06132

Communication complexity of approximate Nash equilibria

Yakov Babichenko, Aviad Rubinstein

1608.06580

The Mechanics of n-Player Differentiable Games

David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, Thore Graepel

1802.05642

Learning with Opponent-Learning Awareness

Jakob N. Foerster, Richard Y. Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, Igor Mordatch

1709.04326

Symmetric Strategy Improvement

Sven Schewe, Ashutosh Trivedi, Thomas Varghese

1501.06484

The Complexity of Fairness through Equilibrium

Abraham Othman, Christos Papadimitriou, Aviad Rubinstein

1312.6249

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Mika Göös, Aviad Rubinstein

1805.06387

Re-evaluating Evaluation

David Balduzzi, Karl Tuyls, Julien Perolat, Thore Graepel

1806.02643

Fast Convergence of Regularized Learning in Games

Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, Robert E. Schapire

1507.00407

Envy-Freeness in House Allocation Problems

Jiarui Gan, Warut Suksompong, Alexandros A. Voudouris

1905.00468

Graphical Cake Cutting via Maximin Share

Edith Elkind, Erel Segal-Halevi, Warut Suksompong

2105.04755

Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning

Battista Biggio, Fabio Roli

1712.03141

Constant Inapproximability for PPA

Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos

2201.10011

Fair Cake Division Under Monotone Likelihood Ratios

Siddharth Barman, Nidhi Rathi

2006.00481

A faster algorithm for finding Tarski fixed points

John Fearnley, Dömötör Pálvölgyi, Rahul Savani

2010.02618

Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity

Kaiqing Zhang, Sham M. Kakade, Tamer Başar, Lin F. Yang

2007.07461

Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games

Umang Bhaskar, Yu Cheng, Young Kun Ko, Chaitanya Swamy

1512.03543

Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations

Haris Aziz, Chun Ye

1307.2908

Differentiable Game Mechanics

Alistair Letcher, David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, Thore Graepel

1905.04926

Multi-Agent Learning in Network Zero-Sum Games is a Hamiltonian System

James P. Bailey, Georgios Piliouras

1903.01720

Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile

Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, Georgios Piliouras

1807.02629

The Frontiers of Fairness in Machine Learning

Alexandra Chouldechova, Aaron Roth

1810.08810

A short proof of correctness of the quasi-polynomial time algorithm for parity games

Hugo Gimbert, Rasmus Ibsen-Jensen

1702.01953

Reachability Switching Games

John Fearnley, Martin Gairing, Matthias Mnich, Rahul Savani

1709.08991

The Communication Complexity of Local Search

Yakov Babichenko, Shahar Dobzinski, Noam Nisan

1804.02676

On the Complexity of Nash Equilibria in Anonymous Games

Xi Chen, David Durfee, Anthi Orfanou

1412.5681

Inapproximability Results for Approximate Nash Equilibria

Argyrios Deligkas, John Fearnley, Rahul Savani

1608.03574

Composable and Efficient Mechanisms

Vasilis Syrgkanis, Eva Tardos

1211.1325

Optimization, Learning, and Games with Predictable Sequences

Alexander Rakhlin, Karthik Sridharan

1311.1869

An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms

Oliver Friedmann

1106.0778

A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning

Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Perolat, David Silver, Thore Graepel

1711.00832

Pure-Circuit: Tight Inapproximability for PPAD

Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos

2209.15149

Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planning

Anton Bakhtin, David J Wu, Adam Lerer, Jonathan Gray, Athul Paul Jacob, Gabriele Farina, Alexander H Miller, Noam Brown

2210.05492

Send Mixed Signals -- Earn More, Work Less

Peter Bro Miltersen, Or Sheffet

1202.1483

Mixture Selection, Mechanism Design, and Signaling

Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng

1508.03679

Mitigating Manipulation in Peer Review via Randomized Reviewer Assignments

Steven Jecmen, Hanrui Zhang, Ryan Liu, Nihar B. Shah, Vincent Conitzer, Fei Fang

2006.16437

A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents

Haris Aziz, Simon Mackenzie

1604.03655

Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria

Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis

1909.03210

Coulomb GANs: Provably Optimal Nash Equilibria via Potential Fields

Thomas Unterthiner, Bernhard Nessler, Calvin Seward, Günter Klambauer, Martin Heusel, Hubert Ramsauer, Sepp Hochreiter

1708.08819

Generative Social Choice

Sara Fish, Paul Gölz, David C. Parkes, Ariel D. Procaccia, Gili Rusak, Itai Shapira, Manuel Wüthrich

2309.01291

Independent Learning in Stochastic Games

Asuman Ozdaglar, Muhammed O. Sayin, Kaiqing Zhang

2111.11743

Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games

Stefanos Leonardos, Will Overman, Ioannis Panageas, Georgios Piliouras

2106.01969

The Computational Complexity of Random Serial Dictatorship

Haris Aziz, Felix Brandt, Markus Brill

1304.3169

Incentive Compatible Two Player Cake Cutting

Avishay Maya, Noam Nisan

1210.0155

Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence

Dongsheng Ding, Chen-Yu Wei, Kaiqing Zhang, Mihailo R. Jovanović

2202.04129

On the Hardness of Signaling

Shaddin Dughmi

1402.4194

Adaptive extra-gradient methods for min-max optimization and games

Kimon Antonakopoulos, E. Veronica Belmega, Panayotis Mertikopoulos

2010.12100

V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL

Chi Jin, Qinghua Liu, Yuanhao Wang, Tiancheng Yu

2110.14555

Multi-agent Reinforcement Learning in Sequential Social Dilemmas

Joel Z. Leibo, Vinicius Zambaldi, Marc Lanctot, Janusz Marecki, Thore Graepel

1702.03037

Multi-Agent Cooperation and the Emergence of (Natural) Language

Angeliki Lazaridou, Alexander Peysakhovich, Marco Baroni

1612.07182

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

Paul W. Goldberg, Alexandros Hollender, Warut Suksompong

1911.05416

Bandit learning in concave $N$-person games

Mario Bravo, David S. Leslie, Panayotis Mertikopoulos

1810.01925

Human-Level Performance in No-Press Diplomacy via Equilibrium Search

Jonathan Gray, Adam Lerer, Anton Bakhtin, Noam Brown

2010.02923

Stochastic bandits robust to adversarial corruptions

Thodoris Lykouris, Vahab Mirrokni, Renato Paes Leme

1803.09353

Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure

Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik

1107.2248

Bayesian Games and the Smoothness Framework

Vasilis Syrgkanis

1203.5155

Robust and Verifiable Proportionality Axioms for Multiwinner Voting

Markus Brill, Jannik Peters

2302.01989

OpenSpiel: A Framework for Reinforcement Learning in Games

Marc Lanctot, Edward Lockhart, Jean-Baptiste Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafiei, Daniel Hennes, Dustin Morrill, Paul Muller, Timo Ewalds, Ryan Faulkner, János Kramár, Bart De Vylder, Brennan Saeta, James Bradbury, David Ding, Sebastian Borgeaud, Matthew Lai, Julian Schrittwieser, Thomas Anthony, Edward Hughes, Ivo Danihelka, Jonah Ryan-Davis

1908.09453

No-regret learning and mixed Nash equilibria: They do not mix

Lampros Flokas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Thanasis Lianeas, Panayotis Mertikopoulos, Georgios Piliouras

2010.09514

Simultaneous Auctions are (almost) Efficient

Michal Feldman, Hu Fu, Nick Gravin, Brendan Lucier

1209.4703

Dividing a Graphical Cake

Xiaohui Bei, Warut Suksompong

1910.14129

When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?

Ziang Song, Song Mei, Yu Bai

2110.04184

What game are we playing? End-to-end learning in normal and extensive form games

Chun Kai Ling, Fei Fang, J. Zico Kolter

1805.02777

Millimeter Wave V2V Communications: Distributed Association and Beam Alignment

Cristina Perfecto, Javier Del Ser, Mehdi Bennis

1612.04217

Decentralized Q-Learning in Zero-sum Markov Games

Muhammed O. Sayin, Kaiqing Zhang, David S. Leslie, Tamer Basar, Asuman Ozdaglar

2106.02748

Bayesian Sequential Auctions

Vasilis Syrgkanis, Eva Tardos

1206.4771

Safe and Nested Subgame Solving for Imperfect-Information Games

Noam Brown, Tuomas Sandholm

1705.02955

Training Generative Adversarial Networks via stochastic Nash games

Barbara Franci, Sergio Grammatico

2010.10013

Differentially Private Fair Learning

Matthew Jagielski, Michael Kearns, Jieming Mao, Alina Oprea, Aaron Roth, Saeed Sharifi-Malvajerdi, Jonathan Ullman

1812.02696

Convergence of Learning Dynamics in Stackelberg Games

Tanner Fiez, Benjamin Chasnov, Lillian J. Ratliff

1906.01217

Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games

Lampros Flokas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Georgios Piliouras

1910.13010

Almost Envy-Free Allocations with Connected Bundles

Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, William S. Zwicker

1808.09406

Computational Hardness of the Hylland-Zeckhauser Scheme

Thomas Chen, Xi Chen, Binghui Peng, Mihalis Yannakakis

2107.05746

A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agents

Haris Aziz, Simon Mackenzie

1508.05143

The Complexity of Pacing for Second-Price Auctions

Xi Chen, Christian Kroer, Rachitesh Kumar

2103.13969

Modeling Strong and Human-Like Gameplay with KL-Regularized Search

Athul Paul Jacob, David J. Wu, Gabriele Farina, Adam Lerer, Hengyuan Hu, Anton Bakhtin, Jacob Andreas, Noam Brown

2112.07544

Nash Learning from Human Feedback

Rémi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Andrea Michi, Marco Selvi, Sertan Girgin, Nikola Momchev, Olivier Bachem, Daniel J. Mankowitz, Doina Precup, Bilal Piot

2312.00886

Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization

Shicong Cen, Yuting Wei, Yuejie Chi

2105.15186

Modelling Behavioural Diversity for Learning in Open-Ended Games

Nicolas Perez Nieves, Yaodong Yang, Oliver Slumbers, David Henry Mguni, Ying Wen, Jun Wang

2103.07927

Learning Multi-item Auctions with (or without) Samples

Yang Cai, Constantinos Daskalakis

1709.00228

$α$-Rank: Multi-Agent Evaluation by Evolution

Shayegan Omidshafiei, Christos Papadimitriou, Georgios Piliouras, Karl Tuyls, Mark Rowland, Jean-Baptiste Lespiau, Wojciech M. Czarnecki, Marc Lanctot, Julien Perolat, Remi Munos

1903.01373

Sequential Auctions and Externalities

Renato Paes Leme, Vasilis Syrgkanis, Eva Tardos

1108.2452

Efficient computation of approximate pure Nash equilibria in congestion games

Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik

1104.2690

From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization

Julien Perolat, Remi Munos, Jean-Baptiste Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, Georgios Piliouras, Marc Lanctot, Karl Tuyls

2002.08456

Combining Deep Reinforcement Learning and Search for Imperfect-Information Games

Noam Brown, Anton Bakhtin, Adam Lerer, Qucheng Gong

2007.13544

Keep Your Distance: Land Division With Separation

Edith Elkind, Erel Segal-Halevi, Warut Suksompong

2105.06669

Bounding the inefficiency of outcomes in generalized second price auctions

Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos, Maria Kyropoulou, Brendan Lucier, Renato Paes Leme, Éva Tardos

1201.6429

Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent

Lampros Flokas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Georgios Piliouras

2101.05248

Fictitious play in zero-sum stochastic games

Muhammed O. Sayin, Francesca Parise, Asuman Ozdaglar

2010.04223

The Disparate Effects of Strategic Manipulation

Lily Hu, Nicole Immorlica, Jennifer Wortman Vaughan

1808.08646

How to Sample Approval Elections?

Stanisław Szufa, Piotr Faliszewski, Łukasz Janeczko, Martin Lackner, Arkadii Slinko, Krzysztof Sornat, Nimrod Talmon

2207.01140

Non-Price Equilibria in Markets of Discrete Goods

Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Noam Nisan

1103.3950

Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation

Tanner Fiez, Lillian Ratliff

2009.14820

Theoretical and Practical Advances on Smoothing for Extensive-Form Games

Christian Kroer, Kevin Waugh, Fatma Kilinc-Karzan, Tuomas Sandholm

1702.04849

The Conference Paper Assignment Problem: Using Order Weighted Averages to Assign Indivisible Goods

Jing Wu Lian, Nicholas Mattei, Renee Noble, Toby Walsh

1705.06840

The Price of Connectivity in Fair Division

Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, Warut Suksompong

1908.05433

Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division

Elad Aigner-Horev, Erel Segal-Halevi

1901.09527

On Fair Division under Heterogeneous Matroid Constraints

Amitay Dror, Michal Feldman, Erel Segal-Halevi

2010.07280

Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games

Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos, Michael I. Jordan

2002.09806

Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling

Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos

2003.10162

An Algorithmic Framework for Approximating Maximin Share Allocation of Chores

Xin Huang, Pinyan Lu

1907.04505

On the Complexity of Fair House Allocation

Naoyuki Kamiyama, Pasin Manurangsi, Warut Suksompong

2106.06925

Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes

Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, Xiao Wang

2002.06768

Closing Gaps in Asymptotic Fair Division

Pasin Manurangsi, Warut Suksompong

2004.05563

Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints

Ayumi Igarashi, Dominik Peters

1811.04872

Mind the Gap: Cake Cutting With Separation

Edith Elkind, Erel Segal-Halevi, Warut Suksompong

2012.06682