"ReLaX" Workshop on Games

Keynote sessions:

1. Véronique Bruyère (Univ. Mons, Mons) – Bio

   Véronique Bruyère is Full Professor at the University of Mons, Belgium, since 2012, and head of the Theoretical Computer Science laboratory since 2001. She is active in the fields of theoretical computer science and formal methods, with a strong interest in game theory and its applications in computer-aided verification and synthesis, in verification and control of timed and hybrid systems, and in theory of automata with its applications to arithmetic and logic. She is author or co-author of more than 80 papers published in peer-reviewed conference proceedings and journals.

   
   First talk (survey): Synthesis of Nash equilibria and subgame perfect equilibria in games played on graphs Abstract
   In this survey, we consider games played on finite graphs by several players who aim at satisfying their own objective. We focus on two important solution concepts: Nash equilibria and subgame perfect equilibria. We present several algorithmic/complexity results about their existence, possibly constrained by some conditions on the objectives, and illustrate them by some examples. In this context, the players play in a turn-based way, use pure strategies, and their objectives are either qualitative or quantitative.
   Slides
   Second talk: Nash equilibria and subgame perfect equilibria in reachability games Abstract
   In this talk, we consider multi-player games played on a finite graph equipped with target sets of vertices, one for each player. In those reachability games, it is known that there always exist a Nash equilibrium and a subgame perfect equilibrium. But sometimes several such equilibria may coexist and it is therefore useful to design efficient algorithms deciding whether there exists one equilibrium satisfying certain constraints. We present our recent decision algorithms for both qualitative and quantitative reachability games.
   Slides-Talk 1     Slides-Talk 2
2. T. Parthasarathy (CMI, Chennai)
   First talk: A survey on stochastic games
   Second talk: Finite algorithm for some classes of stochastic games Abstracts of the two talks:

   Stochastic game was introduced by Lloyd Shapley in a seminal paper (published in Proc. Natl. Academy of Sciences, U.S.A, 1953). Around the same time Dr.Gillette studied the same problem from a different view point. We will briefly present a survey on this class of games. This class of games are of interest to researchers in OR, Mathematical economics and Computer science. In the second talk we will present example to show how stochastic games differ from the usual matrix games studied by von Neumann and Dantzig. We will present some classes of stochastic games which behave like matrix games. We will also pose some open problems at the end.

   Slides   Video
3. Jérôme Renault (TSE, Toulouse) – Bio

   Jérôme Renault received his PhD in 1998 from Université Paris 1 Panthéon-Sorbonne, and then became Maître de Conférences at Université Paris-Dauphine. He has hold a game theory chair at Ecole Polytechnique, and is since 2009 a math professor at Toulouse School of Economics, Université Toulouse Capitole.

   He has been the head of the CNRS research group in Game Theory from 2012 to 2015, and is now head of the chair « Game Theory and Artifical Intelligence » within the new Toulouse institute ANITI.

   He contributes in particular to the theory of repeated games, stochastic games, games with signals, Markov decision processes, strategic transmission of information and games with incomplete information.

   
   Long-term value in stochastic games Abstract

   We consider 2-player stochastic games, and first present a standard convergence result for the value when the players become extremely patient (the time horizon tends to infinity or the discount rate goes to zero).

   We also show stronger results in the one-player case, and counter-examples for compact state spaces, hidden states or non-zero sum payoffs. Properties and problems regarding the stronger notion of uniform value will also be mentioned.

   Part of the talk will be based on recent results with B. Ziliotto.

   Slides   Video
4. Arunava Sen (ISI, Delhi) – Bio

   Arunava Sen is Professor at the Indian Statistical Institute (ISI), Delhi for more than 30 years. His research interests are Game Theory, Social Choice Theory, Mechanism Design, and Voting and Auctions. He completed his Ph.D in Economics from Princeton University, his M.Phil (Economics) from Oxford University, his M.A from the Delhi School of Economics and his B.A. from St.Stephen's College, University of Delhi. He is a Fellow of the Econometric Society and an Economic Theory Fellow. He was awarded the Mahalanobis Memorial Medal of the Indian Econometric Society in 2000 for his contribution to Economics. He is also a recipient of the 2012 Infosys Prize in the Social Sciences category for his work on "game-theoretic analyses of mechanism design for implementing social choice rules, when individuals have diverse information and incentives."

   https://unravelecon.com/2020/04/15/interview-insights-dr-arunava-sen/

   
   Implementation in undominated Strategies with Bounded Mechanisms Abstract

   The first lecture will introduce the problem and the second will describe some current research.

   Slides   Video
5. Sitabhra Sinha (IMSC, Chennai) – Bio

   Sitabhra Sinha is Professor of Theoretical Physics and Dean of Computational Biology at the Institute of Mathematical Sciences (IMSc), Chennai and was earlier also adjunct faculty of the National Institute of Advanced Studies (NIAS), Bangalore and Department of Computer Science, Indian Institute of Technology, Kharagpur. He did his PhD at the Indian Statistical Institute, Kolkata and postdoctoral research at the Indian Institute of Science, Bangalore and the Weill Medical College of Cornell University, New York City, joining the faculty of IMSc in 2002. His research falls broadly under complex systems, nonlinear dynamics and statistical physics with applications to systems biology, epidemiology, economic & social sciences and computational linguistics.

   
   The temptation of Mr Spock: Solution frameworks for non-cooperative games among rational agents Abstract

   Understanding how cooperation can emerge in a population whose individual members are only interested in maximizing their personal well-being is one of the fundamental problems in evolutionary biology and social sciences. The ever present temptation to not cooperate (thereby avoiding the associated cost) while enjoying the benefits of the cooperative acts of others appears to make it unlikely that cooperation will persist - even if it somehow arises occasionally by chance. Yet cooperation is seen to occur widely in nature, ranging from communities of micro-organisms, cellular aggregates and synthetic ecologies to primate societies.

   The conventional theoretical approach to the problem, based on analysis of games such as the Prisoners Dilemma (PD), suggests that rational individuals will not cooperate even in situations where mutual cooperation may result in a better outcome for all. This incompatibility between individual rationality and collective benefit lies at the heart of the puzzle of evolution of cooperation, as illustrated by PD and similar games.

   We have recently shown that this apparent incompatibility is due to an inconsistency in the standard Nash framework for analyzing non-cooperative games and have proposed a new paradigm - that of the co-action equilibrium. As in the Nash solution, agents know that others are just as rational as them and taking this into account leads them to realize that others will independently adopt the same strategy, in contrast to the idea of unilateral deviation central to Nash equilibrium thinking. The co-action equilibrium results in radically different collective outcomes (compared to Nash) for games representing social dilemmas, with relatively "nicer" strategies being chosen by rational selfish individuals. In particular, the dilemma of PD gets resolved within this framework, suggesting that cooperation can evolve in nature as the rational outcome even for selfish agents, without having to take recourse to additional mechanisms (such as reciprocity or reputation) for promoting it. When extended to an iterative situation, we show that even in the absence of initial symmetry among agents, their behavior can converge to cooperation as a result of repeated interactions. In particular, the co-action solution for the iterative PD between 2 players corresponds to a win-stay, lose-shift behavioral rule, thereby providing a rational basis for this Pavlovian strategy.

   Slides   Video
6. Tristan Tomala (HEC, Paris) – Bio

   I obtained a PhD in applied Mathematics at Université Paris Sorbonne in 1996. I was then assistant professor at Université Paris Dauphine until 2007. I am now Professor at HEC Paris and member of the Economics and Decision Sciences Department.

   I am area editor (Game Theory) for Operations Research Letters and associate editor for: Dynamic Games and Applications, International Journal of Game Theory, Theory and Decision.

   
   Bayesian Games, Information Design and Persuasion. Abstract

   In Bayesian Games, or games with incomplete information, players have private and imperfect information about the state parameters of the game.

   In a first part, we will first review two important classes of Bayesian Games: Zero-sum repeated games and Sender-receiver games.

   The second part of the talk will be about information design: how to choose the information to disclose to the players in order to maximize some payoff criterion. We will study in detail the case of Bayesian Persuasion and the links with repeated games. Finally, we will show recent results on games between information designers. In situations where multiple information designers compete for influencing players, we will study the equilibrium outcomes.

   Slides   Video

Technical sessions:

1. John Augustine (IIT-Madras, Chennai)
   Game Theoretic Challenges in Distributed Trust Abstract

   Thanks to bitcoin and the underpinning blockchain technology, cryptocurrencies have become popular in the last decade. More broadly, blockchains find applications in a variety of distributed trust applications like smart contracts and electronic forms of voting, governance, and asset ownership. One of the main challenges in a distributed trust setup is to ensure that the incentives of the various players are aligned towards the right global outcome. In this talk, I will give a brief overview of blockchains, the primary technology upon which modern distributed trust systems are designed, and discuss a variety of game-theoretic challenges that might be of interest to a theoretically inclined audience. I will not be assuming any prior knowledge in blockchains or distributed trust.

   Slides   Video
2. Dietmar Berwanger (LSV, Paris Saclay) – Bio

   PhD thesis on seeing fixed point logics through infinite games, CNRS researcher at LSV, on a quest for understanding strategic coordination, imperfect information in games played with automata.

   
   Automatic Information Structures Abstract

   We explore a model of repeated games with private monitoring that features explicit communication actions, by which a player can send his entire observation history to another player. Such full-information protocols are typical for asynchronous distributed systems with causal memory; here we consider a synchronous setting with the aim of synthesising finite-state strategies. The challenge is that the message space is infinite, for games of infinite duration. This poses an obstacle to using classical automata-theoretic methods which rely on finite observation alphabets.

   In the talk, we describe a finite-state representation for games with full-information protocols, and address synthesis and implementability issues for approachable cases. Our technique relies on modelling information structures with perfect recall by indistinguishability relations recognised by synchronous two-tape automata. We highlight the expressive power of the new model in comparison with the more standard one featuring monitoring functions definable by sequential automata.

   Video
3. Umang Bhaskar (TIFR, Mumbai) – Bio

   Umang is a faculty in the School of Technology and Computer Science at TIFR Mumbai since 2015. Before this he was a postdoc at Caltech and University of Waterloo, and a PhD student at Dartmouth. Umang works primarily in algorithms and algorithmic game theory.

   
   Optimal Bounds on the Price of Fairness for Indivisible Goods Abstract

   In the allocation of resources to agents, how do fairness guarantees impact the social welfare? A quantitative measure of this impact is the price of fairness. While initially studied for divisible goods, recent work on the price of fairness also studies the setting of indivisible goods. Our work resolves the price of fairness for two well-studied fairness notions: envy-freeness up to one good (EF1), and approximate maximin share (MMS). For both EF1 and approximate MMS guarantees, we show, via different techniques, that the price of fairness is $O(\sqrt{n})$, where $n$ is the number of agents. From previous work, it follows that our bounds are tight. This resolves an open problem posed by Bei et al.~(2019).

   This is joint work with Siddharth Barman and Nisarg Shah.

   Slides   Video
4. Sujata Ghosh (ISI Chennai) – Bio

   associated with indian statistical institute, chennai. research interests include logics of knowledge, belief, games and strategies, and social cognition

   
   On game equivalences: Algebraic and logical perspectives Abstract

   In this talk, we will focus on different kinds of game equivalences where games are modelled in terms of strategic powers of players expressed as state-set relations. In process, we will deal with certain game logics and game algebras.

   Slides   Video
5. Valentin Goranko (Stockholm University) – Bio

   VG got his Phd in mathematics (mathematical logic) from Sofia University (Bulgaria) in 1989. Since then he has worked in mathematics departments at universities in Bulgaria and South Africa, then in the computer science department at the Technical University of Denmark, and since 2014 he is a professor of logic at the department of philosophy of Stockholm university. His research has spanned theory and applications of logic across these 3 fundamental disciplines, and logics for games and multi-agent systems is his main research area for the past 20 years.

   
   The temporal logic of coalitional goal assignments in concurrent multi-player games
   (joint work with Sebastian Enqvist) Abstract

   I will present a natural extension of the Alternating time temporal logic ATL, called Temporal Logic of Coalitional Goal Assignments (TLCGA). It features just one, but quite expressive, coalitional strategic operator, viz. the coalitional goal assignment operator, which is based on a mapping assigning to each set of players in the game its coalitional goal, formalised by a path formula of the language of TLCGA, i.e. a formula prefixed with a temporal operator X, U, or G, representing a temporalised objective for the respective coalition, describing the property of the plays on which that objective is satisfied.

   I will illustrate the use of the logic TLCGA with some examples, will discuss its expressiveness and will present fixpoint characterizations of the temporal goal assignments in a mu-calculus extension of TLCGA. Time permitting, I will then outline our main technical results for that logic: bisimulation invariance and Hennessy-Milner property with respect to a suitably defined notion of bisimulation; a sound and complete axiomatic system, and decidability via finite model property.

   Slides   Video
6. Sushmita Gupta (IMSc Chennai) – Bio

   Sushmita Gupta received her PhD in Computer Science (2008), from the University of Southern Denmark, Denmark. She spent a year as a Postdoctoral Fellow at Univ of Kyoto, and then three years at University of Bergen, Norway. She is now a faculty member at IMSc.

   
   To fix a tournament: A parameterized complexity perspective. Abstract

   A knockout tournament is a standard format of competition, common in sports, elections and decision making. The inherently competitive nature of these scenarios naturally attracts bettors and various stake holders. There are many ways to manipulate the outcome of a tournament, and many different ways to study them. In this talk we will discuss some frameworks for manipulation and a multivariate approach towards analysing them.

   Slides   Video
7. Deepak Khemani (IIT-Madras, Chennai) – Bio

   Deepak Khemani is a Professor in the Department of Computer Science and Engineering, IIT Madras, India. He graduated with three degrees from IIT Bombay, including two in Computer Science. His areas of research are broadly in Artificial Intelligence. He is the author of a textbook 'A First Course in Artificial Intelligence'.

   His research focus is in the areas of knowledge, memory, reasoning and planning. He plans to employ these to build articulate systems that can take a problem-solving approach to teaching by a machine, especially in the areas of high school mathematics and science. More recently he has worked in the domain of multi-agent systems where an agent has to reason with what other agents know and believe. He is working towards implementing a contract bridge playing program that reasons like a human expert. The human-level contract bridge playing agent will be required to do epistemic planning while collaborating with a team member and competing against opponents in an environment of incomplete information.

   
   Contract Bridge: Par and Beyond Abstract

   If contract bridge were like chess it would be just another board game. But it is not. The main difference being that it is an incomplete information team game, played with a regular pack of fifty two cards. Another is that the starting position is always different, with negligible probability of a deal being repeated. A corollary is that the notion of a win is not clearly defined. If the four players could see all cards, one could define a par outcome. One still does, in the post mortem, but in practice players strive not just to reach par, but even beat it. This is because the payoff is by compaision. How did opponents play the same hand? Given the hidden cards, bridge is essentially a game dealing with information, reasoning, planning, and intent recognition. Partners communicate with each other. Communication is susceptible to interception. And interception paves the way for deception. We present a glimpse of this fascinating game.

   Slides   Video
8. Maël Le Treust (ETIS,Cergy) – Bio

   Maël Le Treust earned his Diplôme d'Etude Approfondies (M.Sc.) degree in Optimization, Game Theory & Economics (OJME) from the Université de Paris VI (UPMC), France in 2008 and his Ph.D. degree from the Université de Paris Sud XI in 2011, at the Laboratoire des signaux et systèmes (joint laboratory of CNRS, Supélec, Université de Paris Sud XI) in Gif-sur-Yvette, France. Since 2013, he is a CNRS researcher at ETIS laboratory UMR 8051, Université Paris Seine, Université Cergy-Pontoise, ENSEA, CNRS, in Cergy, France. In 2012, he was a post-doctoral researcher at the Institut d'électronique et d'informatique Gaspard Monge (Université Paris-Est) in Marne-la-Vallée, France. In 2012-2013, he was a post-doctoral researcher at the Centre Énergie, Matériaux et Télécommunication (Université INRS ) in Montréal, Canada. From 2008 to 2012, he was a Math T.A. at the Université de Paris I (Panthéon-Sorbonne), Université de Paris VI (UPMC) and Université Paris Est Marne-la-Vallée, France. His research interests are strategic coordination, information theory, Shannon theory, game theory, physical layer security and wireless communications.

   
   Persuasion with limited communication capacity (joint work with Tristan Tomala, HEC Paris) Abstract

   We consider a Bayesian persuasion problem where the persuader and the decision maker communicate through an imperfect channel which has a fixed and limited number of messages and is subject to exogenous noise. Imperfect communication entails a loss of payoff for the persuader. We establish an upper bound on the payoffs the persuader can secure by communicating through the channel. We also show that the bound is tight: if the persuasion problem consists of a large number of independent copies of the same base problem, then the persuader can achieve this bound arbitrarily closely by using strategies which tie all the problems together. We characterize this optimal payoff as a function of the information-theoretic capacity of the communication channel.

   Slides   Video
9. Neeldhara Misra (IIT, Gandhinagar)– Bio

   Neeldhara is a faculty member with the discipline of Computer Science and Engineering at IIT Gandhinagar. Previously, she was an INSPIRE Faculty Fellow at the Indian Institute of Science. She graduated from the Institute of Mathematical Sciences. Her research usually addresses issues involving coping with computational intractability and her toolkit for this has predominantly been parameterized algorithms. She typically works on problems involving graphs, games, and sometimes both.

   
   Party Nominations Abstract
   Consider a fixed voting rule R. In the Possible President problem, we are given an election where the candidates are partitioned into parties, and the problem is to determine if, given a party P, it is possible for every party to nominate a candidate such that the nominee from P is a winner of the election that is obtained by restricting the votes to the nominated candidates. In the Necessary President problem, we would like to find a nominee who wins no matter who else is nominated. In this talk, we explore the complexity of these problems, which can be thought of as the two natural extremes of the party nomination problem, with an emphasis on a parameterized perspective and algorithms on structured profiles.
   Video
10. Youssouf Oualhadj (Université Paris-Est Créteil Val de Marne)
    Games Where You Can Play Optimally with Finite Memory Abstract

    For decades, two-player zero-sum games on finite graphs have been a framework of choice for many important problems in theoretical computer science. A notorious one is controller synthesis, which can be rephrased through the game-theoretic metaphor as the quest for a winning strategy of the system in a game against its antagonistic environment. Depending on the specification, optimal strategies might be simple or quite complex, for example having to use (possibly infinite) memory. Hence, research strives to understand which settings allow for simple strategies.

    In 2005, Gimbert and Zielonka provided a complete characterization of preference relations (a formal framework to model specifications and game objectives) that admit memoryless optimal strategies for both players. In the last fifteen years however, practical applications have driven the community toward games with complex or multiple objectives, where memory --- finite or infinite --- is almost always required. Despite much effort, the exact frontiers of the class of preference relations that admit finite-memory optimal strategies still elude us.

    In this talk, I will present a complete characterization of preference relations that admit optimal strategies using arena-independent finite memory, generalizing the work of Gimbert and Zielonka to the finite-memory case. I will also present an equivalent to their celebrated corollary: if both players have optimal (arena-independent-)finite-memory strategies in all one-player games, then it is also the case in all two-player games.

    Slides   Video
11. Rohit Parikh (CUNY)
    The Sorites paradox, Fuzzy Logic, and Wittgenstein's Language Games Abstract

    We look at the history of research on vagueness and the Sorites paradox.

    Various solutions to that paradox have been proposed, including the epistemic version of Kit Fine and the Fuzzy Logic of Lotfi Zadeh. But these solutions have not been entirely successful because they have focused on finding a semantics and a logic, neither of which really exist. (They do sort of, but break down if we put pressure on them).

    On the other hand, we do use vague terms like red, tall, etc in real life and more or less well. Why does this happen if there is no meaning to words like red and tall? Following Wittgenstein we show that the notion of a successful language game works. Such games can fit inside the project for social software. The fact that these games work can give us the illusion that there is a semantics and a logic. But there isn't.

    Hopefully, existing theories of program correctness can be adapted to vagueness.

    Slides     Video
12. Sunil Simon (IIT Kanpur)– Bio

    Sunil Simon received his PhD from the Institute of Mathematical Science, Chennai and is currently working in the department of computer science and engineering at IIT Kanpur. His research interests include logical foundations of multiple-agent systems and computational analysis of games.

    
    On externalities in one-sided markets Abstract

    Fair division of indivisible goods among rational agents is one of the most fundamental problems in social choice theory, with applications in distributed systems, housing allocation, etc. A special case of this problem is that of one-sided markets, a classic model proposed by Shapley and Scarf, where each agent is allocated exactly one item. In this work, we study the problem of allocating indivisible items to a set of rational agents where agents have cardinal non-transferable utilities associated with each allocation. We extend the one-sided market model to the network setting where agents' utilities depend on their neighbourhood externalities that are item specific and pairwise separable.

    We show that, unlike in the case of classical one-sided markets, stable allocations may not always exist in the graphical model. When rewards are equally shared, a 2-stable allocation is guaranteed to exist and any decentralised mechanism where pairs of rational agents agree to exchange items terminate in such an allocation. We show that computing a 2-stable allocation is PLS-complete and further identify subclasses which are tractable. In the general case of reward sharing, we show that it is NP-complete to check if a 2-stable allocation exists. We then identify structural restrictions where stable allocations always exist and can be computed efficiently.

    This is joint work with Sagar Massand.

    Slides   Video