Monday, Sept. 30 - Tutorials
09:30 - 09:50 Registration
09:50 - 10:00 Opening
10:00 - 11:00
Learning in Zero-Sum Games Revisited: The Connection to Physics and Conservative Systems

Abstract: We revisit one of most classic questions in game theory and online learning. How do standard learning dynamics such as Multiplicative Weights Update or Gradient Descent behave in zero-sum games? The standard textbook answer to this question is that these dynamics "converge" in a time-average sense to Nash equilibria. We will provide a tutorial on some recent results that analyze the day-to-day behavior and show how dynamics in zero-sum games have formal connections to the physics of closed systems. As in the case of e.g. pendulums, the time-average position and speed of these systems may agree with their equilibrium values but these time-averages do not tell the full story.

The continuous-time analogues of these dynamics (e.g. replicator dynamics/MWU) are Poincaré recurrent. Informally, the trajectories are "cycles" of constant distance from the Nash equilibrium which lies at the center of the "cycle". In fact, the dynamics conserve a hidden energy function that remains constant on all trajectories. These results extend in a natural way to multiplayer generalizations of zero-sum games. In discrete-time, the classical online algorithms such as MWU, move tangentially to these cycles and as a result they diverge chaotically away from Nash equilibria, contradicting the paradigm of zero-sum games as an archetype of game theoretic stability. Multiple new questions and directions emerge.

George Piliouras

Bio: Dr. Piliouras is an Assistant Professor at the Singapore University of Technology and Design (SUTD). He received his PhD in Computer Science from Cornell University in 2010. He has held postdoc positions at the Georgia Institute of Technology (GaTech, ECE Dept.) and California Institute of Technology (Caltech, Dept. of Computing and Mathematical Sciences). He has held visiting positions at UC Berkeley and DeepMind and is a collaborator of the Ethereum Foundation. He is the recipient of a Singapore NRF Fellowship (2018) and a Simons/UC Berkeley Fellowship (2015).

11:00 - 11:30 Coffee break
11:30 - 12:30 Learning in Zero-Sum Games Revisited: The Connection to Physics and Conservative Systems
George Piliouras
12:30 - 15:00 Lunch
15:00 - 16:00
Econometrics and Machine Learning

Abstract: One of the biggest promises of machine learning is the automation of decision making in many application domains such as business, healthcare and law. However, most of decision making involves making interventions and understanding the effects of such interventions. This requires understanding causal relationships among the variables in your data, which is at odds with most of machine learning techniques, which primarily target the identification of correlations and produce purely predictive, as opposed to causal models. Techniques from econometrics and causal inference can help mitigate this problem. I will survey several such techniques such as, inverse propensity scoring, double machine learning, instrumental variables, regression discontinuity designs and synthetic controls. I will outline how such techniques can be blended with machine learning approaches so as to remove the limited modeling ability of traditional econometrics and get the best of both worlds.

Vasilis Syrgkanis

Bio: Vasilis Syrgkanis is a Principal Researcher at Microsoft Research, New England, where he is co-leading the project on Automated Learning and Intelligence for Causation and Economics (ALICE). He received his Ph.D. in Computer Science from Cornell University in 2014, under the supervision of Prof. Eva Tardos and spent two years in Microsoft Research, New York as a postdoctoral researcher. His research addresses problems at the intersection of theoretical computer science, machine learning and economics. His work received best paper awards at the 2015 ACM Conference on Economics and Computation (EC’15), the 2015 Annual Conference on Neural Information Processing Systems (NIPS’15) and the Conference on Learning Theory (COLT’19).

16:00 - 16:30 Coffee break
16:30 - 17:30 Econometrics and Machine Learning
Vasilis Syrgkanis
17:30 - 18:00 Registration (Electrical and Computer Engineering Building)
18:00 - 21:00 Welcome reception (Electrical and Computer Engineering Building)

Tuesday, Oct. 1 - SAGT 2019
09:00 - 09:20 Registration
09:20 - 09:30 Opening of SAGT 2019
09:30 - 10:30 Invited talk
Machine Learning for Mechanism Design
Maria-Florina Balcan
10:30 - 11:00 Coffee break
11:00 - 12:40

Connected Subgraph Defense Games
Eleni C. Akrida, Argyrios Deligkas, Themistoklis Melissourgos and Paul Spirakis

Principal-Agent Problems with Present-Biased Agents
Sigal Oren and Dolav Soker

The online best reply algorithm for resource allocation problems
Max Klimm, Daniel Schmand and Andreas Tönnis

On a Simple Hedonic Game with Graph-Restricted Communication
Vittorio Bilò, Laurent Gourves and Jerome Monnot

12:40 - 14:30 Lunch
14:30 - 15:45

On the Existence of Nash Equilibrium in Games with Resource-Bounded Players
Joseph Halpern, Rafael Pass and Daniel Reichman

Computing Stackelberg Equilibria of Large General-Sum Games
Avrim Blum, Nika Haghtalab, Mohammadtaghi Hajiaghayi and Saeed Seddighin

On the Computational Complexity of Decision Problems about Multi-Player Nash Equilibria
Marie Louisa Tølbøll Berthelsen and Kristoffer Arnsfelt Hansen

15:45 - 16:15 Coffee break
16:15 - 17:55

On the Existence of Three-Dimensional Stable Matchings with Cyclic Preferences
Chi-Kit Lam and C. Gregory Plaxton

Maximum Stable Matching with One-Sided Ties of Bounded Length
Chi-Kit Lam and C. Gregory Plaxton

Fair Division with Subsidy
Daniel Halpern and Nisarg Shah

Stochastic Matching on Uniformly Sparse Graphs
Soheil Behnezhad, Mahsa Derakhshan, Alireza Farhadi, Mohammadtaghi Hajiaghayi and Nima Reyhani

Wednesday, Oct. 2 - SAGT 2019
09:30 - 10:30 Invited talk
Guarantees in Fair Division, under informational parsimony
Herve Moulin
10:30 - 11:00 Coffee break
11:00 - 12:40

Mechanism Design for Constrained Heterogeneous Facility Location
Maria Kyropoulou, Carmine Ventre and Xiaomeng Zhang

Facility Location for Three Agents on a Circle
Reshef Meir

Mechanism Design for Locating a Facility under Partial Information
Vijay Menon and Kate Larson

Prophet Inequalities on the Intersection of a Matroid and a Graph
Jackie Baek and Will Ma

12:40 - 14:30 Lunch
14:30 - 15:45

Best paper: The Declining Price Anomaly is not Universal in Multi-Buyer Sequential Auctions (but almost is)
Vishnu V. Narayan, Enguerrand Prebet and Adrian Vetta

Risk-Free Bidding in Complement-Free Combinatorial Auctions
Vishnu V. Narayan, Gautam Rayaprolu and Adrian Vetta

Risk Robust Mechanism Design for a Prospect Theoretic Buyer
Siqi Liu, J. Benjamin Miller and Alexandros Psomas

15:45 - 16:15 Coffee break
16:15 - 17:55

Impartial selection with additive approximation guarantees
Ioannis Caragiannis, George Christodoulou and Nicos Protopapas

The Distortion of Distributed Voting
Aris Filos-Ratsikas, Evi Micha and Alexandros Voudouris

The Convergence of Iterative Delegations in Liquid Democracy in a Social Network
Bruno Escoffier, Hugo Gilbert and Adèle Pass-Lanneau

Optimal Truth-tracking Rules for the Aggregation of Incomplete Judgments
Zoi Terzopoulou and Ulle Endriss

20:30 Conference dinner at Athiri
Thursday, Oct. 3 - SAGT 2019
09:30 - 10:30 Invited talk
From Cognitive Biases to the Communication Complexity of Local Search
Shahar Dobzinski
10:30 - 11:00 Coffee break
11:00 - 12:40

Obvious Strategy proofness, Bounded Rationality and Approximation: The Case of Machine Scheduling
Diodato Ferraioli and Carmine Ventre

Optimal On-line Allocation Rules with Verification
Markos Epitropou and Rakesh Vohra

Sharing Information with Competitors
Simina Branzei, Claudio Orlandi and Guang Yang

The Impact of Tribalism on Social Welfare
Seunghee Han, Matvey Soloviev and Yuwen Wang

12:40 - 12:50 Concluding remarks
12:50 - 14:30 Lunch
End of SAGT 2019