Семинар “Алгебра и логика”
26 март @ 13:00 - 14:30
На 26 март 2021 г. (петък) от 13:00 часа ще се проведе дистанционно заседание на семинара по „Алгебра и логика”.
Доклад на тема
Some axioms about rationality in infinite concurrent multiplayer games with ordered objectives and temporary coalitions in QCTL*
ще изнесе Димитър Гелев (ИМИ – БАН).
Резюме. Temporal winning conditions appear in both terminating and infinite games. Reachability (guarantee) winning conditions appear in terminating games. Safety conditions and conditions higher up in the (Manna & Pnueli, 1989) hierarchy appear in non-terminating games. In a multiplayer game, the latter classes of winning conditions are natural to drive players into forming permanent coalitions as the longevity of a coalition needs to match the duration of its agenda, which may take entire infinite plays to implement. However, a lifelong joint agenda is often inconsistent with the ability of players to change alliances, especially if there are multiple objectives with preference. The dedicated constructs of established logical notations for strategic behaviour such as Alternating-time Temporal Logic (ATL, Alur Henzinger and Kupferman, ICALP 1997, J. of the ACM, 2002) and Strategy Logic (SL, Chatterjee, Henzinger and Piterman, I& C, 2010, Mogavero, Murano and Vardi, FST TCS 2010), in their now many variants and extensions, are off-the-shelf for permanent coalitions only. To the best of our knowledge, no dedicated constructs such as those of ATL and SL are available for temporary coalitioning.
In this talk we fall back onto Quantified Computation Tree Logic, QCTL*, which admits embeddings of both ATL and SL, and is now an established intermediate notation for logics for strategic ability, largely because of its decidability on the unwindings of finite models (French, Australian AI 2001, Ph.D. Thesis 2006, Laroussinie and Markey, LMCS 2014). The embedding of ATL was introduced in (Da Costa Lopez et al, CONCUR 2012), and independently by myself in (Guelev, SR 2013). Elements can be identified already in the correspondence between ATL’s 2002 and 1997 semantics in (Goranko and Jamroga, Synthese 2004).
We propose a vocabulary which extends this embedding to allow temporary coalitions. We illustrate its use to formulate example sufficient conditions for the rationality of shifting coalition structure and decisions in the extension of QCTL* by a temporal form of a binary preference operator after (Von Wright, 1963) which we introduced in (Guelev, CoRR 2020). The conditions reflect naive game-theoretic reasoning and are considered to become part of analogons to backward induction to infinite concurrent games with ordered objectives. We adopt ordered objectives from the thorough study of pure Nash equilibria concurrent ω-regular games without coalitioning in (Bouyer, Brenguier and Markey and Ummels, FoSSaCS 2012, LMCS 2015).
Keywords: strategic ability, temporary coalitions, rational synthesis, ordered objectives, concurrent multiplayer games
Семинарът ще се проведе посредством платформата Zoom и всеки желаещ може да се присъедини като последва линка:
Topic: Онлайн семинар на секция “Алгебра и логика”
Time: Mar 26, 2021 01:00 PM Sofia
Meeting ID: 851 3737 5021
От секция „Алгебра и логика” на ИМИ – БАН