FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
SR ON SATURDAY, JULY 7TH
Days:
next day
all days

View: session overviewtalk overviewside by side with other conferences

09:00-10:30 Session 23M: SR Invited tutorial: Edith Elkind
09:00
Strategic behavior in social choice - Part 1

ABSTRACT. Applications of voting systems range from political elections to ranking universities and making funding decisions. In this tutorial, we will discuss various aspects of strategic behavior in voting, with a focus on the analysis of voting equilibria.

10:30-11:00Coffee Break
11:00-12:30 Session 26N: SR Invited tutorial: Edith Elkind
11:00
Strategic behavior in social choice - Part 2

ABSTRACT. Applications of voting systems range from political elections to ranking universities and making funding decisions. In this tutorial, we will discuss various aspects of strategic behavior in voting, with a focus on the analysis of voting equilibria.

12:30-14:00Lunch Break
14:00-15:30 Session 28L: Determinacy, compositionality
Chair:
14:00
Compositional Game Theory
SPEAKER: Neil Ghani

ABSTRACT. We introduce open games as a compositional foundation of economic game theory. A compositional approach potentially allows methods of game theory and theoretical computer science to be applied to large-scale economic models for which standard economic tools are not practical. An open game represents a game played relative to an arbitrary environment and to this end we introduce the concept of coutility, which is the utility generated by an open game and returned to its environment. Open games are the morphisms of a symmetric monoidal category and can therefore be composed by categorical composition into sequential move games and by monoidal products into simultaneous move games. Open games can be represented by string diagrams which provide an intuitive but formal visualisation of the information flows. We show that a variety of games can be faithfully represented as open games in the sense of having the same Nash equilibria and off-equilibrium best responses.

14:40
Concurrent games and semi-random determinacy

ABSTRACT. Consider concurrent, infinite duration, two-player win/lose games played on graphs. If the winning condition satisfies some simple requirement, the existence of Player 1 winning (finite-memory) strategies is equivalent to the existence of winning (finite-memory) strategies in finitely many derived one-player games. Several classical winning conditions satisfy this simple requirement.

Under an additional requirement on the winning condition, the non-existence of Player 1 winning strategies from all vertices is equivalent to the existence of Player 2 stochastic strategies winning almost surely from all vertices. Only few classical winning conditions satisfy this additional requirement, but a fairness variant of o

15:30-16:00Coffee Break
16:00-18:00 Session 31P: Multiple-player games
16:00
Verification of Multi-agent Systems with Imperfect Information and Public Actions

ABSTRACT. We analyse the verification problem for synchronous, perfect recall multi-agent systems with imperfect information against a specification language that includes strategic and epistemic operators. While the verification problem is undecidable, we show that if the agents' actions are public, then verification is 2 EXPTIME -complete. To illustrate the formal framework we consider two epistemic and strategic puzzles with imperfect information and public actions: the muddy children puzzle and the classic game of battleships. This paper has been accepted for publication at AAMAS2017.

16:40
Local Equilibria in Logic-Based Multi-Player Games

ABSTRACT. Game theory provides a well-established framework for the analysis of multi-agent systems. Typically, the analysis of a multi-agent system involves computing the set of equilibria in the associated multi-player game representing the behaviour of the system. As systems grow larger, it becomes increasingly harder to find equilibria in the game -- which represent the rationally stable behaviours of the multi-agent system (the solutions of the game). To address this issue, in this paper, we study the concept of local equilibria, which are defined with respect to (maximal) stable coalitions of agents for which an equilibrium can de found. We focus on the solutions given by the Nash equilibria of Boolean games and iterated Boolean games, two logic-based models for multi-agent systems, in which the players' goals are given by formulae of propositional logic and LTL, respectively.

17:20
Beyond admissibility: Dominance between chains of strategies
SPEAKER: Arno Pauly

ABSTRACT. Admissible strategies, i.e. those that are not dominated by any other strategy, are a typical rationality notion in game theory. In many classes of games this is justified by results showing that any strategy is admissible or dominated by an admissible strategy. However, in games played on finite graphs with quantitative objectives (as used for reactive synthesis), this is not the case.

We consider increasing chains of strategies instead to recover a satisfactory rationality notion based on dominance in such games. We start with some order-theoretic considerations establishing sufficient criteria for this to work. We then turn our attention to generalised safety/reachability games as a particular application. We propose the notion of maximal uniform chain as the desired dominance-based rationality concept in these games. Decidability of some fundamental questions about uniform chains is established.

19:45-22:00 Workshops dinner at Balliol College

Workshops dinner at Balliol College. Drinks reception from 7.45pm, to be seated by 8:15 (pre-booking via FLoC registration system required; guests welcome).

Location: Balliol College