|Summer School on Game Theory and Social Choice
June 21 - June 24 and July 9 - July 13, 2021
Title: Efficient, Fair, and Incentive-Compatible Healthcare Rationing
Speaker: Haris Aziz, University of New South Wales
Abstract: In this talk, I will report on ongoing work on healthcare rationing algorithms. Fair and efficient rationing of healthcare resources has emerged as an important issue that has been discussed by medical experts, policy-makers, and the general public. We consider a healthcare rationing problem where medical units are to be allocated to patients. Each unit is reserved for one of several categories and the categories may have different priorities for the patients. We present flexible allocation rules that respect the priorities, comply with the eligibility requirements, allocate the largest feasible number of units, and do not incentivize agents to hide that they qualify through a category. To the best of our knowledge, these are the first known rules with the aforementioned properties. One of our rules characterizes all possible outcomes that satisfy the first three properties. Moreover, the rules are polynomial-time computable. This is based on joint work with Florian Brandl. A preliminary version of the project will be presented at ACM EC 2021.
> Date & Time: 24 June 2021 (Thursday), 14:00-15:00
Speaker Bio: Haris Aziz is a Scientia Associate Professor at UNSW Sydney and leader of the Algorithmic Decision Theory group. His research interests lie at the intersection of artificial intelligence, theoretical computer science and mathematical social sciences ---, especially computational social choice and algorithmic game theory. Haris is a recipient of the Scientia Fellowship (2018 - ), CORE Chris Wallace Research Excellence Award (2017) and the Julius Career Award (2016 - 2018). In 2015, he was selected by the Institute of Electrical and Electronics Engineers (IEEE) for the AI 10 to Watch List. He is on the board of directors of IFAAMAS and is an associate editor of major journals including AIJ, JAIR, JAAMAS, and Social Choice & Welfare.
Title: New Design Decisions for Modern AI Agents
Speaker: Vincent Conitzer, Duke University
Abstract: Consider an intelligent virtual assistant such as Siri, or perhaps a more capable future version of it. Should we think of all of Siri as one big agent? Or is there a separate agent on every phone, each with its own objectives and/or beliefs? And what should those objectives and beliefs be? Such questions reveal that the traditional, somewhat anthropomorphic model of an agent – with clear boundaries, centralized belief formation and decision making, and a clear given objective – falls short for thinking about today’s AI systems. We need better methods for specifying the objectives that these agents should pursue in the real world, especially when their actions have ethical implications. I will discuss some methods that we have been developing for this purpose, drawing on techniques from preference elicitation and computational social choice. But we need to specify more than objectives. When agents are distributed, systematically forget what they knew before (say, for privacy reasons), and potentially face copies of themselves, it is no longer obvious what the correct way is even to do probabilistic reasoning, let alone to make optimal decisions. I will explain why this is so and discuss our work on doing these things well. (No previous background required.)
Date & Time: 23 June 2021 (Wednesday), 09:00-10:00
Speaker Bio: Vincent Conitzer is the Kimberly J. Jenkins Distinguished University Professor of New Technologies and Professor of Computer Science, Professor of Economics, and Professor of Philosophy at Duke University, as well as Head of Technical AI Engagement at the Institute for Ethics in AI, and Professor of Computer Science and Philosophy, at the University of Oxford. Much of his work has focused on AI and game theory. More recently, he has started to work on AI and ethics: how should we determine the objectives that AI systems pursue, when these objectives have complex effects on various stakeholders? He received his doctorate from Carnegie Mellon University in 2006. He has received the 2021 ACM/SIGAI Autonomous Agents Research Award, the Social Choice and Welfare Prize, a Presidential Early Career Award for Scientists and Engineers (PECASE), the IJCAI Computers and Thought Award, and an honorable mention for the ACM dissertation award.
Title: Impartial selection, additive approximation guarantees, and priors
Speaker: Ioannis Caragiannis, Aarhus University
Abstract: We study the problem of impartial selection, a topic that lies at the intersection of computational social choice and mechanism design. The goal is to select the most popular individual among a set of community members. The input can be modelled as a directed graph, where each node represents an individual, and a directed edge indicates nomination or approval of a community member to another. An impartial mechanism is robust to potential selfish behaviour of the individuals and provides appropriate incentives to voters to report their true preferences by ensuring that the chance of a node to become a winner does not depend on its outgoing edges. The goal is to design impartial mechanisms that select a node with an in-degree that is as close as possible to the highest in-degree. Recent progress has identified impartial selection rules with optimal approximation ratios. It was noted, though, that worst-case instances are graphs with few nodes. Motivated by this fact, we propose the study of additive approximation, the difference between the highest number of nominations and the number of nominations of the selected member, as an alternative measure of quality. We present randomized impartial selection mechanisms with additive approximation guarantees of o(n), where n is the number of nodes in the input graph. We further demonstrate that prior information on voters' preferences can be useful in designing simple (deterministic) impartial selection mechanisms with good additive approximation guarantees. In this direction, we consider different models of prior information and analyze the performance of a natural selection mechanism that we call approval voting with default (AVD).
Date & Time: 22 June 2021 (Tuesday), 16:00-17:00
Speaker Bio: Ioannis Caragiannis is a professor at the Department of Computer Science of Aarhus University since August 2020. Before, he was a faculty member at the Department of Computer Engineering and Informatics of the University of Patras (since 2006). His research interests include the design and analysis of algorithms, economics and computation, and foundations of machine learning and artificial intelligence. He has published more than 160 papers in conference proceedings, scientific journals, and books and has participated in basic research projects funded by the European Commission and the Greek state. He regularly serves as a program committee member in conferences at the interface of theoretical computer science, artificial intelligence, and economics, such as the ACM Conference on Economics and Computation (EC) and the International Joint Conference on Artificial Intelligence (IJCAI). Currently, he is the organizer and program co-chair of the 14th International Symposium on Algorithmic Game Theory (SAGT 2021). Ioannis Caragiannis is a member of the Association for Computing Machinery (ACM, SIGACT, SIGECOM), the Association for the Advancement of Artificial Intelligence (AAAI), and the European Association for Theoretical Computer Science (EATCS).
Title: Limit of Learning in Market Making
Speaker: Xiaotie Deng, Peking University
Abstract: Game theory has played a key role building the conceptual framework of social and economic studies at its early stage. The advance of AI has provided new tools market agents may use to their advantage at economic markets and to increase the level of their decision rationality. In this talk, we explore the changes we may have to make for the game theory methodology to adapt to the new age of machine intelligence.
Date & Time: 13 July 2021 (Tuesday), 14:00-15:00
Speaker Bio: Xiaotie Deng is a chair professor of Center on Frontiers of Computing Studies, Peking University. Deng received his BSc from Tsinghua University, MSc from Chinese Academy of Sciences, and PhD from Stanford University. He has taught at Shanghai Jiaotong University of China, the University of Liverpool, City University of Hong Kong, and York University. He was an NSERC international fellow at Simon Fraser University. Deng's current research focuses on algorithmic game theory with applications to Internet economics. His work covers algorithmic game theory, online algorithms, parallel algorithms, and combinatorial optimization. He is an M.A.E., an ACM Fellow and an IEEE Fellow.
Title: Keeping Your Friends Close: Land Allocation with Friends
Speaker: Edith Elkind, University of Oxford
Abstract: We examine the problem of assigning plots of land to prospective buyers who prefer living next to their friends. They care not only about the plot they receive, but also about their neighbors. This externality results in a highly non-trivial problem structure, as both friendship and land value play a role in determining agent behavior. We examine mechanisms that guarantee truthful reporting of both land values and friendships. We propose variants of random serial dictatorship (RSD) that can offer both truthfulness and welfare guarantees. Interestingly, our social welfare guarantees are parameterized by the value of friendship: if these values are low, enforcing truthful behavior results in poor welfare guarantees and imposes significant constraints on agents' choices; if they are high, we achieve good approximation to the optimal social welfare.
Based on joint work with Neel Patel, Alan Tsang and Yair Zick.
Date & Time: 21 June 2021 (Monday), 14:00-16:00
Speaker Bio: Edith Elkind is a Professor of Computer Science at the University of Oxford (UK). She obtained her PhD from Princeton (USA) in 2005, and has worked in the UK, Israel and Singapore before joining Oxford in 2013. Prof Elkind's research interests lie in the field of computational social choice and coalition formation. She has published over 100 papers in leading computer science conferences and journals, chaired major conferences in AI and algorithmic game theory, and has served or is serving on editorial boards of top journals in AI, algorithmic game theory, and social choice.
Title: Prophet and Secretary Online Algorithms for Matching in General Graphs
Speaker: Michal Feldman, Tel Aviv University
Abstract: A common tension in market scenarios is choosing the right timing to commit to a decision. This tension is captured by the mathematical literature of optimal stopping theory, within two models that have become to be known as the secretary problem and the prophet inequality. In these models, a sequence of originally-unknown values arrive one by one. Upon arrival, the online algorithm observes the value and should decide whether or not to accept it. In secretary settings, the value sequence is arbitrary, but the values arrive in a uniformly random order. In prophet settings, every value is drawn from a known probability distribution, but the arrival order is arbitrary. In this talk I will review the basic settings of secretary and prophet, as well as previous extensions to matching in bipartite graphs with 1-sided vertex arrival. I will then present our recent work, which studies online algorithms (in both secretary and prophet settings) for matching in *general* graphs. We provide tight competitive ratios for both secretary and prophet matching scenarios under vertex arrival. Under edge arrival, we provide competitive ratios that improve upon the state of the art. Based on joint work with Tomer Ezra, Nick Gravin and Zhihao Tang.
Date & Time: 24 June 2021 (Tuesday), 15:00-16:00
Speaker Bio: Michal Feldman is the Computation and Economics Professor of Computer Science in the Blavatnik School of Computer Science at Tel Aviv University and a visiting scholar at Microsoft Research (MSR) Herzliya. Her research spans computer science, economics, game theory and operations research. She received her Ph.D. from the University of California at Berkeley in 2005. She was a visiting professor at Harvard University and Microsoft Research New England (2011-13). She is an Associate Editor in Games and Economic Behavior, Mathematics of Operations Research, ACM Transactions on Economics and Computation, and Journal of Computer and System Sciences. She served as Vice Chair of ACM SIGecom, and PC chair of ACM EC 2015. She is an alumna of the Global Young Academy of Sciences, and the Israeli Young Academy of Sciences (and its management committee). She is the recipient of two ERC grants of the European Research Council, Marie Curie IOF, Alon, ISF, NSF-BSF and Amazon Research Award. She was listed in Forbes' list of the 50 most influential women in Israel (2016), and in the The Marker's list 40 under 40 (2014).
Title: Simple Mechanisms for Non-linear Agents
Speaker: Jason Hartline, Northwestern University
Abstract: I will discuss a framework that approximately extends the classical theory of mechanism design for linear agents (following Myerson, 1981) to broad families of non-linear agent preferences. Optimal mechanism design for non-linear agents is generally analytically intractable. On the other hand, the presented framework shows that intuitions from linear agents approximately extend to non-linear agents. The talk will motivate the approach and analysis framework and sketch the main ideas that go into proving such approximation results. The research talk is based on joint work with Yiding Feng and Yingkai Li.
Date & Time: 13 July 2021 (Tuesday), 10:00-11:00
Speaker Bio: Prof. Hartline received his Ph.D. in 2003 from the University of Washington under the supervision of Anna Karlin. He was a postdoctoral fellow at Carnegie Mellon University under the supervision of Avrim Blum; and subsequently a researcher at Microsoft Research in Silicon Valley. He joined Northwestern University in 2008 where he is a professor of computer science. He was on sabbatical at Harvard University in the Economics Department during the 2014 calendar year and visiting Microsoft Research, New England for the Spring of 2015. Prof. Hartline codirects the Institute for Data, Econometrics, Algorithms, and Learning (an NSF HDR TRIPODS institute) and is a cofounder of virtual conference organizing platform Virtual Chair.
Title: Algorithmic Mechanism Design of Combinatorial Auctions
Speaker: Piotr Krysta, University of Liverpool
Abstract: In this talk I will present an introduction and overview of the design of approximate truthful mechanisms for combinatorial auctions. I will present two different settings: one with a fixed number of goods and another without this assumption and with general bidders, and present different techniques to mathematically analyze such auctions. Among these techniques, we will discuss randomization, reinforcement learning, rounding and enumeration.
In the first setting we design and analyze deterministic truthful approximation mechanisms for multi-unit combinatorial auctions (CAs) with only a constant number of distinct goods, each in arbitrary limited supply. Prospective buyers (bidders) have preferences over multisets of items, i.e. for more than one unit per distinct good. Our objective is to determine allocations of multisets that maximize the Social Welfare. Despite the recent theoretical advances on the design of truthful combinatorial auctions (for several distinct goods) and multi-unit auctions (for a single good), results for the combined setting are much scarcer. Our main results are for multi-minded and submodular bidders.
In the second, general setting, we design combinatorial auctions in an online model with sequentially arriving bidders, where the arrivals’ order is either random or adversarial. The bidders’ valuations are given by demand oracles. Previously known online mechanisms for CAs assume that each item is available at a certain multiplicity b > 1. Typically, one assumes b = Ω(log m), where m is the number of different items. We present the first online mechanisms for CAs guaranteeing competitiveness without assumptions about the minimum multiplicity. We introduce an online variant of oblivious randomized rounding enabling us to prove competitive ratios that are close to or even beat the best known offline approximation factors for various CAs settings. Our mechanisms are universally truthful, and they significantly improve on the previously known mechanisms.
This talk is based on joint work with Orestis Telelis, Carmine Ventre and Berthold Voecking.
Date & Time: 13 July 2021 (Tuesday), 16:00-17:00
Speaker Bio：Piotr Krysta is a Professor of Computer Science at the University of Liverpool in the U.K. He has done his PhD at the Max Planck Institute for Computer Science in Saarbruecken and his Habilitation degree in Computer Science at Dortmund University in Germany. He was an Emmy Noether Fellow of the German Science Foundation in Theoretical Computer Science heading an independent research group in Algorithmic Game Theory for 5 years at the Universities of Dortmund and Liverpool. He was a funding member and head of the Economics and Computation research group in Liverpool. His research interests include combinatorial and continuous optimisation, algorithmic mechanism design, computational economics, approximation algorithms for hard optimisation problems, randomised algorithms and computational complexity. For his research in algorithmic mechanism design, he has been awarded best paper awards at ICALP 2012 and at AAMAS 2013. He has been program committee member of many conferences in Theoretical Computer Science and Algorithmic Game Theory and a member of the editorial board of Theoretical Computer Science journal (Elsevier).
Title : from portionment to apportionment under ordinal preferences
Speaker: Jérôme Lang, Université Paris-Dauphine
Abstract: When a public divisible resource (such as a monetary budget) is to be divided among alternatives (such as projects), a portioning rule decides on a distribution of the budget. Examples of such portioning problems are participatory budgeting, time shares, and parliament elections. In the latter case, an integral seat assignment must be found from the (real-valued) output of the portioning rule: this is the apportionment phase. We wil show how both processes (portionment/apportionment) can be `plugged' into each other. We focus on rules for which voters have ordinal preference rankings over alternatives. Based on joint work with Stéphane Airiau, Haris Aziz, Ioannis Caragiannis, Justin Kruger and Dominik Peters.
Date & Time: 24 June 2021 (Thursday), 16:00-17:00
Speaker Bio: Jérôme Lang is a CNRS senior scientist. He is affiliated with the LAMSADE research institute (PSL, Université Paris-Dauphine, France). His research interests are within artificial intelligence, and more precisely computational social choice, algorithmic game theory, and knowledge representation. He was the program chair of IJCAI-ECAI-2018. He is the author or coauthor of more than 200 publications, and a co-editor of the Handbook of Computational Social Choice.
Title: Differentiable Economics
Speaker: David Parkes, Harvard University
Abstract: In this talk I will introduce a research agenda that seeks to make use of differentiable representations of economic rules, together with suitable objectives, architectures, and constraints, to learn rules that approximately optimize various kinds of desiderata. I plan to illustrate this framework to the settings of revenue-optimal auction design, two-sided matching, and indirect mechanism design, and I will suggest some directions for future work. This talk represents work with various wonderful collaborators, including Gianluca Brero, Paul Duetting, Alon Eden, Zhe Feng, Matthias Gerstgrasser, Vincent Li, Harikrishna Narasimhan, Sai Srivatsa Ravindranath, and Duncan Rheingans-Yoo.
Date & Time: 13 July 2021 (Tuesday), 09:00-10:00
Speaker Bio: David Parkes is George F. Colony Professor of Computer Science in the Paulson School of Engineering and Applied Sciences at Harvard University, where he is also Co Faculty-Director of the Harvard Data Science Initiative and co-chair of the Harvard Business Analytics Program. His research focuses on AI and economics and he founded Harvard's EconCS research group. A Fellow of the ACM and the AAAI, Parkes is also a recipient of the 2017 ACM/SIGAI Autonomous Agents Research Award, the NSF Career Award, the Alfred P. Sloan Fellowship, the Thouron Scholarship, and Harvard's Roslyn Abramson Award for Teaching. He was the Chair of the ACM SIG on Electronic Commerce from 2011 to 2016. Parkes currently serves on the CRA's Computing Community Consortium and earlier served on the inaugural panel of the "Stanford 100 Year Study on Artificial Intelligence." Parkes has degrees from the University of Oxford and the University of Pennsylvania, and serves on several international scientific advisory boards and as a technical advisor to a number of start-ups.
Title: Democracy and the Pursuit of Randomness
Speaker: Ariel Procaccia, Harvard University
Abstract: Sortition is a storied paradigm of democracy built on the idea of choosing representatives through lotteries instead of elections. In recent years this idea has found renewed popularity in the form of citizens' assemblies, which bring together randomly selected people from all walks of life to discuss key questions and deliver policy recommendations. A principled approach to sortition, however, must resolve the tension between two competing requirements: that the demographic composition of citizens' assemblies reflect the general population and that every person be given a fair chance (literally) to participate. I will describe our work on designing, analyzing and implementing randomized participant selection algorithms that balance these two requirements. I will also discuss practical challenges in sortition based on experience with the adoption and deployment of our open-source system, Panelot.
Date & Time: 24 June 2021 (Thursday), 09:00-10:00
Speaker Bio: Ariel Procaccia is Gordon McKay Professor of Computer Science at Harvard University. He works on a broad and dynamic set of problems related to AI, algorithms, economics, and society. His distinctions include the Social Choice and Welfare Prize (2020), a Guggenheim Fellowship (2018), the IJCAI Computers and Thought Award (2015), and a Sloan Research Fellowship (2015). To make his research accessible to the public, he has founded the not-for-profit websites Spliddit.org and RoboVote.org, and he regularly contributes opinion pieces.
Title: Multiagent reasoning for social impact: Results from deployments for public health and conservation
Speaker: Milind Tambe, Harvard University
Abstract: With the maturing of AI and multiagent systems research, we have a tremendous opportunity to direct these advances towards addressing complex societal problems. I focus on the problems of public health and conservation, and address one key cross-cutting challenge: how to effectively deploy our limited intervention resources in these problem domains. I will present results from work around the globe in using AI for HIV prevention, Maternal and Child care interventions, TB prevention and COVID modeling, as well as for wildlife conservation. Achieving social impact in these domains often requires methodological advances. To that end, I will highlight key research advances in multiagent reasoning and learning, in particular in, computational game theory, restless bandits and influence maximization in social networks.In pushing this research agenda, our ultimate goal is to facilitate local communities and non-profits to directly benefit from advances in AI tools and techniques.
Date & Time: 22 June 2021 (Tuesday), 09:00-10:00
Speaker Bio: Milind Tambe is Gordon McKay Professor of Computer Science and Director of Center for Research in Computation and Society at Harvard University; concurrently, he is also Director "AI for Social Good" at Google Research India. He is a recipient of the IJCAI John McCarthy Award, ACM/SIGAI Autonomous Agents Research Award from AAMAS, AAAI Robert S Engelmore Memorial Lecture award, INFORMS Wagner prize, Rist Prize of the Military Operations Research Society, Columbus Fellowship Foundation Homeland security award, over 25 best papers or honorable mentions at conferences such as AAMAS, AAAI, IJCAI and meritorious commendations from agencies such as the US Coast Guard and the Los Angeles Airport. Prof. Tambe is a fellow of AAAI and ACM.
Title: Approximate Mechanism Design: the impact of real world constraints
Speaker: Toby Walsh, University of New South Wales
Abstract: Wherever people or bots interact, we can design a mechanism to mediate this interaction. It would be desirable to have mechanisms that are strategy proof, meaning that it is in everyone's best interests to behave sincerely and not to try to manipulate the outcome. Unfortunately, there are many impossibility results that demonstrate strategy proofness is incompatible with other desirable properties like efficiency. An attractive compromise, proposed by Procaccia and Tenenholtz is to insist on strategy proofness but look instead for mechanisms that return solutions that are not necessarily optimal. I survey recent work in this area, focusing on the problem of facility location, and the impact of real world constraints. For instance, how do capacity constraints impact on approximate mechanism design? And how does moving away from simple 1-d distance metrics to 2 or more dimensions complicate such approximate mechanism design?
Date & Time: 13 July 2021 (Tuesday), 15:00-16:00
Speaker Bio: Toby Walsh is a Laureate Fellow, Scientia Professor of AI at the University of New South Wales, Fellow of the Australian Academy of Science, Fellow of the ACM, Fellow of AAAI, Fellow of EurAI and Fellow of the American Association for Advancement of Science. He was improbably named by the Australian newspaper as a "rock star" of Australia's digital revolution. Professor Walsh is a strong advocate for limits to ensure AI is used to improve our lives. He has, for example, been a leading voice in the discussion about killer robots, speaking at the UN in New York and Geneva on the topic. He appears regularly on TV and radio. He has authored two books on AI for a general audience, the most recent titled "2062: The World that AI Made" which is available in Arabic, Chinese, English, German, Japanese, Korean, Polish, Romanian, Russian, Turkish and Vietnamese.
Title: Mechanism Design for Constrained Matching
Speaker: Makoto Yokoo, Kyushu University
Abstract: The theory of two-sided matching (e.g., assigning residents to hospitals, students to schools) has been extensively developed, and it has been applied to design clearinghouse mechanisms in various markets in practice. As the theory has been applied to increasingly diverse types of environments, however, researchers and practitioners have encountered various forms of distributional constraints. As these features have been precluded from consideration until recently, they pose new challenges for market designers. One example of such distributional constraints is a minimum quota, e.g., school districts may need at least a certain number of students in each school in order for the school to operate. In this talk, I present an overview of research on designing mechanisms that work under distributional constraints.
Date & Time: 23 June 2021 (Wednesday), 10:00-11:00
Speaker Bio: Makoto Yokoo received the B.E., M.E., and Ph.D. degrees in 1984, 1986, and 1995, respectively, from the University of Tokyo, Japan. He is currently a Distinguished Professor of Information Science and Electrical Engineering, Kyushu University, Japan. He served as a general co-chair of International Conference on Autonomous Agents and Multi-Agent Systems in 2007 (AAMAS-2007), and as a program co-chair of AAMAS-2003. He is the past president of International Foundation for Autonomous Agent and Multiagent Systems (IFAAMAS), which is a hosting organization of AAMAS conference series. He is a fellow of the Association for Advancement of Artificial Intelligence (AAAI). He received the ACM SIGART Autonomous Agents Research Award in 2004, and the IFAAMAS influential paper award in 2010.
Title: Recent Advances in Fair Division
Speaker: Xiaohui Bei, Nanyang Technological University
Abstract: Fair division refers to the problem of fairly allocating a set of scarce resources to a set of self-interested agents with different preferences. Despite its seemingly simple setting, the problem compasses rich structures and has been a central topic in resource allocation for many decades. In this talk, I will give an overview of some recent research on this topic. The goal is to give the audience a taste of different fair division challenges and explain how computational thinking could help in addressing them. Among other things, I will take a game-theoretic viewpoint and discuss the challenge of designing truthful fair division algorithms. I will also discuss the challenge of defining fairness and designing fair division algorithms when the resources contain both divisible and indivisible goods.
Date & Time: 21 June 2021 (Monday), 14:00-16:00
Speaker Bio: Xiaohui Bei is currently a Nanyang Assistant Professor at Nanyang Technological University. He got his Ph.D. from Tsinghua University at Beijing in 2012. Then he spent two years as a research fellow at NTU, and one year as a researcher at Max Planck Institute for Informatics. His research interests include topics in resource allocation, computational economics, and general algorithm design.
Title: Computational Game Theory and Its Applications
Speaker: Hau Chan, University of Nebraska-Lincoln
Abstract: We Don't Live In A Vacuum! We interact with other agents in our environment to make rational decisions. For example, selecting the quickest or easiest route to go from your apartment to campus, selecting the best amount to bid in an eBay auction, determining whether to fold in a 2-player poker game, or selecting a winning move in a Rock-paper-scissors game. In all of these examples, we must interact with other agents when making decisions. In particular, our best strategy depends on the behavior of other agents in the environment (e.g., the chosen route depends on the number of others are using those routes, play rock if my opponent plays scissors). How do we make rational decisions when facing other strategic agents in a given environment? What is the best strategy? Game theory helps us to answer these questions.
Game theory is a mathematical tool that allows us to reason about the strategic interaction of self-interest and rational agents in a given environment. The construct provides a set of frameworks that characterizes the rational outcomes in such an environment of strategic agents. While the area of game theory is originated from the economic literature, computer scientists have made significant contributions to this area from the modeling and computational perspectives in the last decades (which led to computational game theory). Moreover, numerous applications of game theory have deployed in the real world (e.g., allocating policing resources to checkpoints in the LAX airport, allocating patrollers to protect wild animals in Africa, and predicting the voting behavior of the senators in the U.S. for a bill).
The audiences will be
(1) introduced to fundamental game-theoretic decision-making tools for modeling and understanding the strategic interaction of self-interested and strategic agents;
(2) exposed to the modeling tools’ solution concepts and how they can be used to predict decision-making behavior of agents;
(3) introduced to computational aspects of computing these solution concepts;
(4) exposed to some of the main applications of game theory to security and social science domains.
In addition, if time permits, the lecture will cover more advanced topics including solving games with complex strategy spaces, learning in games, price of anarchy, dynamic games of complete information, static games of Incomplete Information, dynamic games of incomplete information.
Date & Time: 21 June 2021 (Monday), 09:00-11:00
Speaker Bio: Hau Chan is an assistant professor in the Department of Computer Science and Engineering at the University of Nebraska-Lincoln. His current research aims to address the modeling and computational aspects of societal problems (e.g., game-theoretic models for social science domains, fair resource distributions/allocations, and housing allocations for homeless youth) from AI, data mining, and machine learning perspectives. He received his Ph.D. in computer science from Stony Brook University in 2015 and completed three years of postdoctoral fellowships, most recently at the Laboratory for Innovation Science at Harvard University in 2018. He is a recipient of an NSF Graduate Research Fellowship, an NSF East Asia and Pacific Summer Fellowship, a 2015 SDM Best Paper Award, a 2016 AAMAS Best Student Research Paper Award, and a 2018 IJCAI Distinguished PC Member Recognition. He has given several tutorials on computational game theory at AAMAS 2019-2020 and IJCAI 2019-2021. He has served as a co-chair for the 2021 AAMAS Doctoral Consortium and a co-chair for the 2021 AAMAS Scholarships.
Title: Information elicitation without verification
Speaker: Yuqing Kong, Peking University
Abstract: This tutorial will introduce a research area called information elicitation without verification, i.e., peer prediction. In the setting where participants are asked possibly multiple subjective questions (e.g. Do you like Panda Express?), peer prediction aims to design reward systems that incentivize people to tell the truth, even they belong to a minority group.
This tutorial will first introduce two basic settings in peer prediction, the single-task setting and multi-task setting. This tutorial will then talk about the formal model, assumptions and problem statements in the above two settings. Finally, this tutorial will cover a series of peer prediction mechanisms as well as an information-theoretic view of these mechanisms.
Date & Time: 9 July 2021 (Friday), 14:00-16:00
Speaker Bio: Bio: Yuqing Kong is currently an assistant professor at The Center of Frontier Computing Science (CFCS), Peking University. She obtained her Ph.D. degree from the Computer Science and Engineering Department at University of Michigan in 2018 and her bachelor degree in mathematics from University of Science and Technology of China in 2013.
Her research interests lie in the intersection of theoretical computer science and the areas of economics: information elicitation, prediction markets, mechanism design, and the future applications of these areas to crowdsourcing and machine learning. Her papers were published in several conferences include WINE, ITCS, EC, SODA, AAAI, NeurIPS, ICLR, ECCV, IJCAI.
Title: Algorithmic Fair Division: From Goods to Bads
Speaker: Bo Li, Hong Kong Polytechnic University
Abstract: Algorithmic fair division for indivisible resources (goods) has been a central problem in computational social choice and algorithmic game theory, which stimulated the study of fair chores (bads) division in the recent years. Despite the two parallel problems seeming to be similar, they are intrinsically different, both technically and practically. In this tutorial, we will discuss several fundamental fair division models for allocating chores and survey some recent developments through the lens of designing algorithms.
Date & Time: 23 June 2021 (Wednesday), 15:00-17:00
Speaker Bio: Bo Li is currently an assistant professor in the Department of Computing at The Hong Kong Polytechnic University. Formerly, he was a Postdoctoral Fellow at University of Oxford and University of Texas at Austin. He received his PhD in Computer Science from Stony Brook University. He is broadly interested in algorithms, AI and game theory.
Title: Learning to Design Auction Mechanisms
Speaker: Weiran Shen, Renmin University
Abstract: Mechanism design is an important research topic at the interface of economics and computer science. In recent years, using machine learning techniques to solve mechanism design problems has attracted much research attention. In this talk, I will first briefly discuss why designing auction mechanisms is a challenging task. Then I will present some recent results in applying machine learning to different mechanism design settings, including multi-dimensional mechanism design, dynamic mechanism design, and multi-objective mechanism design.
Date & Time: 12 July 2021 (Monday), 14:00-16:00
Speaker Bio: Weiran Shen, an assistant professor at Renmin University of China. He obtained his Bachelor's degree from the Department of Electronic Engineering and his Ph.D. from IIIS, both at Tsinghua University. He was a post-doc researcher at Carnegie Mellon University from 2019 to 2020. His research interest includes multi-agent system, game theory, mechanism design, and machine learning. His research in mechanism design has already been adopted by online advertising platforms such as Baidu and ByteDance.
Title: Tournaments in Computational Social Choice
Speaker: Warut Suksompong, National University of Singapore
Abstract: Tournaments are commonly used to select winning alternatives in scenarios involving pairwise comparisons such as sports competitions and political elections. In this tutorial, I will introduce two lines of work-tournament solutions and single-elimination tournaments-with a focus on how computational social choice has brought new frameworks and perspectives into these decades-old studies.
Date & Time: 12 July 2021 (Monday), 14:00-16:00
Speaker Bio: Warut Suksompong is an assistant professor in the School of Computing at the National University of Singapore. Previously, he was a postdoctoral researcher in computer science at the University of Oxford. He completed his PhD at Stanford University and his bachelor's and master's degrees at the Massachusetts Institute of Technology. His research interests include algorithmic game theory, mechanism design, social choice theory, and other problems at the interface between computer science and economics.
Title: Strategic Voting and Single-Peaked Preferences
Speaker: Taiki Todo, Kyushu University
Abstract: Strategic voting is one of the research trends in the social choice theory, whose purpose is to design voting rules that are resistant to strategic behaviors of voters. This tutorial will first briefly review traditional results on strategic voting in the literature of social choice theory, including the Gibbard-Satterthwaite Theorem and the characterization theorem of strategy-proof voting rules under single-peaked preference domain. Then some approximation results in the algorithmic game theory literature will be summarized, and further recent findings for extended models, including variable populations and multiple voting, will be explained.
Date & Time: 22 June 2021 (Tuesday), 14:00-16:00
Speaker Bio: Taiki Todo is an assistant professor of Graduate School of Information Science and Electrical Engineering (ISEE), Kyushu University. He obtained masters and Ph.D.degrees of Information Science at Kyushu University, in 2010 and 2012, respectively. His main research field is multi-agent systems, a subfield of artificial intelligence. His research interest lies at the intersection between computer science and game theory, especially mechanism design, i.e., designing incentive mechanisms for various market situations such as auctions, barter exchange, school choice and voting. He is serving as a senior program committee member of both AAAI'21 and IJCAI'21, invited to give an Early Career Spotlight Talk at IJCAI-PRICAI'20, and selected as a Senior Member of the Information Processing Society of Japan in 2020.
Title: Game theory in Machine Learning
Speaker: Haifeng Xu, the University of Virginia
Abstract: This lecture will have two parts. The first part covers basics of game theory including equilibrium concepts, inefficiency of Nash equilibrium, duality theory and zero-sum games, etc. The second part will use these basic concepts to analyze machine learning problems, including the equilibrium of GANs and handling strategic behaviors in machine learning tasks such as classification.
Date & Time: 12 July 2021 (Monday), 09:00-11:00
Speaker Bio: Haifeng Xu is the Alan Batson Assistant Professor in Computer Science at the University of Virginia. His research focuses on designing informationally intelligent algorithms/agents that can effectively elicit, process and exploit information, particularly in strategic interactions. He has published extensively in top machine learning and game theory venues including ICML, NeurIPS, STOC, EC, AAAI, etc. Prior to UVA, he was a postdoc at Harvard and obtained his PhD in Computer Science from the University of Southern California. His research has been recognized by multiple awards, including a Google Faculty Research Award, honorable mention for both the ACM SIGecom Dissertation Award and IFAAMAS Victor Lesser Distinguished Dissertation Award, Google PhD fellowship, and several best paper awards.
Title: Mechanism Design Powered by Social Interactions
Speaker: Dengji Zhao, ShanghaiTech University
Abstract: Mechanism design has traditionally assumed that the set of participants are fixed and known to the mechanism (the market owner) in advance. However, in practice, the market owner can only directly reach a small number of participants (her neighbours). Hence the owner often needs costly promotions to recruit more participants in order to get desirable outcomes such as social welfare or revenue maximization. In this talk, we propose to incentivize existing participants to invite their neighbours to attract more participants. However, they would not invite each other if they are competitors. We discuss how to utilize the conflict of interest between the participants to incentivize them to invite each other to form larger markets. We will highlight the early solutions and open the floor for discussing the fundamental open questions in the settings of auctions, coalitional games, matching and voting.
Date & Time: 22 June 2021 (Tuesday), 10:00-12:00
Speaker Bio: Dengji Zhao is a Tenure-track Assistant Professor at ShanghaiTech University, China since 2017. He received double Ph.D. (2012) degrees in Computer Science from University of Western Sydney and University of Toulouse, and received double M.Sc. (2009) degrees in Computational Logic from Technische Universität Dresden and Universidad Politécnica de Madrid. Before joining ShanghaiTech, he was a postdoc (2013-2014) working with Prof. Makoto Yokoo and a research fellow (2014-2016) working with Prof. Nick Jennings. Most of Zhao's research is on artificial intelligence (especially multi-agent systems) and algorithmic game theory (especially mechanism design and its applications in the sharing economy).