The Indian Association for Research in Computing Science and the Programme Committee of FSTTCS 2020 announce a pre-conference workshop on Strategies for Uncertainty (SUN) organized online on 13–14 December 2020.

Aim and Scope

How to design processes so that they interact well over time, if they set out with private, incomplete knowledge of their environment and have limited communication resources? Interdependent, dynamic decisions under imperfect information are a main challenge to distributed computing, and game theory offers a grip where probabilistic models struggle.

In this workshop, we illuminate some classical and some modern approaches from game theory and computing science for representing and reducing uncertainty, and to living with it.

Invited speakers

Programme

All the times given below are in Indian Standard Time (IST), which is UTC +5:30.

Sun 13 DEC 14:00 – 14:10
Opening

Sun 13 DEC 14:10 – 15:10
Rosemarie Nagel How to Harness Zero Intelligence: Idiosyncratic Signals in Beauty Contest Games Chair: Dietmar Berwanger

We introduce the Beauty Contest Game by inviting the audience to play several versions of that game before the conference. It is best to participate in such games without reading the related literature. The different treatments implemented show how behavior reacts to the rules of the game, although the equilibrium is held constant across games. A level-k theory, an iterated best-reply model with a reference point based on Zero-Intelligence agents (ZI), can explain most of the deviations from the Nash equilibrium in the different versions. After 25 years of research, we finally develop a model to harness ZI in a Beauty Contest with idiosyncratic signals, a simplified version of a General Equilibrium model with sentiments.

The talk is based on joint work with Jess Benhabib (NYU), Christoph Buehren (Clausthal University of Technology and University of Kassel) John Duffy (UC-Irvine).

Sun 13 DEC 15:30 – 16:30
Michel De Lara Games in Product Form and Kuhn's Equivalence Theorem Chair: Amaldev Manuel

Game theory offers a mathematical formalism to study strategic interactions. In such models of competition, information (who knows what and before whom) plays a crucial role.

In the fifties, H. W. Kuhn used trees to define a game in extensive form (GEF); in a GEF, the information of a player is represented by a partition of the player node moves. In the seventies, H. S. Witsenhausen used agents, a product set and a product sigma-field to define the so-called intrinsic model (IM) in multi-agent stochastic control problems; in an IM, the information of an agent is represented by a subfield of the product sigma-field.

In this talk, we introduce games in product form (GPF) as an alternative (based on IM) to GEF.

We advocate the relevance of GPF for game theory by providing a case of game form that is playable, but that cannotbe written on a tree, illustrating with examples the easiness and flexibility of GPF to model games (Alice and Bob, principal-agent models), discussing how to represent stochastic and Bayesian games inside the GPF formalism.

Then, we stress that, by replacing what R. Aumann called the "cumbersome tree model" with a product set, GPF can naturally be decomposed with respect to subgroups of agents. Such potential for decomposition, be it hierarchical or parallel, is certainly relevant for computational methods. We illustrate its theoretical interest by providing a definition of perfect recall, of behavioral strategies "à la Aumann" and by proving a Kuhn's Equivalence Theorem for GPF.

We conclude with a possible research program for GPF (Nash equilibrium, backward induction, subgame, subgame perfect equilibrium).

Sun 13 DEC 17:00 – 18:00
Yoram Moses From Bounds to Indirect Coordination Chair: Madhavan Mukund

Asynchronous systems do not provide guaranteed bounds on the time that messages spend in transit and on duration of events. As a result, information about events at remote sites can only be obtained via explicit communication consisting of messages and message chains. When time bounds are available, information can flow in richer patterns. This talk will illustrate two scenarios in which bounds allow for coordination without explicit message chains.

Mon 14 DEC 14:00 – 15:00
Orna Kupferman Games with Full, Longitudinal, and Transverse Observability Chair: S P Suresh

Design and control of multi-agent systems correspond to the synthesis of winning strategies in games that model the interaction between the agents. In games with full observability, the strategies of players depend on the full history of the play. In games with partial observability, strategies depend only on observable components of the history. We survey two approaches to partial observability in two-player turn-based games with behavioral winning conditions. The first is the traditional longitudinal observability, where in all vertices, the players observe the assignment only to an observable subset of the atomic propositions. The second is the recently studied transverse observability, where players observe the assignment to all the atomic propositions, but only in vertices they own.

Mon 14 DEC 15:30 – 16:30
Bernhard von Stengel Coordination with Noisy Signals Chair: Sunil Simon

We consider a coordination game between an informed sender and an uninformed receiver who communicate over a noisy channel with given transmission errors. The sender's strategy, called a code, maps states of nature to signals. The receiver's best response is to decode the received channel output as the state with highest expected receiver payoff. Given this decoding, an equilibrium or "Nash code" results if the sender encodes every state as prescribed. We show two theorems that give sufficient conditions for Nash codes, such as a receiver-optimal code, or arbitrary (possibly bad) codes for binary channels.

Compared to standard information theory, our game-theoretic approach requires that the code is also optimal for the sender. For further research, it may be of interest to study the evolution of such a Nash code as a model of language, to identify the sources and role of noise in this context, and to clarify the meaning of the communicated "states of nature".

Joint work with Penélope Hernández, Valencia, published as: P. Hernández and B. von Stengel (2014), Nash codes for noisy channels. Operations Research 62(6), 1221-1235.

Mon 14 DEC 17:00 – 18:30
A Session of Lightning Talks Chair: R. Ramanujam
Marco Faella, Università di Napoli “Federico II”, Italy Skill vs Luck: Average controllability in one-player games

I will discuss several ways to measure the extent to which a player can exert control over a one-player stochastic game, relating them to the existing literature on the “skill vs chance” dichotomy. I will focus on measures that depend only on the rules of the games, and not on how people actually play them. After outlining a set of desirable properties, I will observe that two statistical measures of effect size, known as “percentage of standard deviation explained” and “percentage of absolute deviation explained”, satisfy them but give rise to two different orders between games. Finally, I will present numerical estimates of these measures for several well-known games and a sport. This talk is based on a paper presented at AAMAS 2016.

Sasha Rubin, The University of Sydney, Australia Assumptions in synthesis and planning

In synthesis and planning the agent has a representation of the world which it uses when devising its plans. In other words, the agent assumes that the world works in some way, and exploits this to achieve its goals. In this brief talk I will refer to these representations as environment assumptions, and will promote the idea that an environment assumption should be thought of as a set of environment strategies.

Anup Basil Mathew, BITS-Pilani, Goa, India Architecture Restrictions to Epistemic Models

It is known that the synthesis problem for distributed systems is decidable only if the 'architecture' of the distributed system is restricted; an 'architecture' is a way of specifying the interactions in a distributed system. In this talk we consider one such (epistemic) restriction on architectures and give a structural characterisation of distributed systems over such architectures.

Sujata Ghosh, ISI Chennai, India On negotiation games

This talk will introduce certain classes of negotiation games that are being used for an ongoing negotiation training experiment. The possibility of applying higher-order of theory of mind to achieve more effective negotiation outcomes will be explored. This is based on ongoing work with Aishwarya Ghosh, Rineke Verbrugge and Harmen de Weerd.

Laurent Doyen, CNRS, ENS Paris-Saclay, France Graph Planning with Expected Finite Horizon

A classical problem in discrete planning is to consider a weighted graph and construct a path that maximizes the sum of weights for a given time horizon T. However, in many scenarios, the time horizon in not fixed, but the stopping time is chosen according to some distribution such that the expected stopping time is T. If the stopping time distribution is not known, then to ensure robustness, the distribution is chosen by an adversary, to represent the worst-case scenario. A stationary plan for every vertex always chooses the same outgoing edge. For fixed horizon T, stationary plans are not sufficient for optimality. Quite surprisingly we show that when an adversary chooses the stopping time distribution with expected stopping time T, then stationary plans are sufficient. While computing optimal stationary plans for fixed horizon is NP-complete, we show that computing optimal stationary plans under adversarial stopping time distribution can be achieved in polynomial time. Consequently, our polynomial-time algorithm for adversarial stopping time also computes an optimal plan among all possible plans.

Organizers

Participation

Participation in the workshop is open to everyone and will be limited only by logistic constraints. There is no separate registration for the workshop, please register from the FSTTCS site.

Live streaming link

Sponsors

IARCS IMSC CNRS ENS Paris-Saclay