Program
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 SystemsAbstract: 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 PiliourasBio: 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 LearningAbstract: 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 SyrgkanisBio: 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 Principal-Agent Problems with Present-Biased Agents The online best reply algorithm for resource allocation problems On a Simple Hedonic Game with Graph-Restricted Communication |
12:40 - 14:30 | Lunch |
14:30 - 15:45 |
On the Existence of Nash Equilibrium in Games with Resource-Bounded Players Computing Stackelberg Equilibria of Large General-Sum Games On the Computational Complexity of Decision Problems about Multi-Player Nash Equilibria |
15:45 - 16:15 | Coffee break |
16:15 - 17:55 |
On the Existence of Three-Dimensional Stable Matchings with Cyclic Preferences Maximum Stable Matching with One-Sided Ties of Bounded Length Fair Division with Subsidy Stochastic Matching on Uniformly Sparse Graphs |
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 Facility Location for Three Agents on a Circle Mechanism Design for Locating a Facility under Partial Information Prophet Inequalities on the Intersection of a Matroid and a Graph |
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) Risk-Free Bidding in Complement-Free Combinatorial Auctions Risk Robust Mechanism Design for a Prospect Theoretic Buyer |
15:45 - 16:15 | Coffee break |
16:15 - 17:55 |
Impartial selection with additive approximation guarantees The Distortion of Distributed Voting The Convergence of Iterative Delegations in Liquid Democracy in a Social Network Optimal Truth-tracking Rules for the Aggregation of Incomplete Judgments |
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 Optimal On-line Allocation Rules with Verification Sharing Information with Competitors The Impact of Tribalism on Social Welfare |
12:40 - 12:50 | Concluding remarks |
12:50 - 14:30 | Lunch |
End of SAGT 2019 |