Rational Synthesis

          @misc{ scivideos_17246,
            doi = {},
            url = {https://simons.berkeley.edu/talks/tbd-267},
            author = {},
            keywords = {},
            language = {en},
            title = {Rational Synthesis},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2021},
            month = {feb},
            note = {17246 see, \url{https://scivideos.org/Simons-Institute/17246}}
          }
          

Abstract

In the traditional approach to synthesis, the system has to satisfy its specification in all environments. Thus, the components that compose the environment can be seen as if their only objective is to conspire to fail the system. In real life, the components that compose the environment are often entities that have objectives of their own. The approach taken in the field of game theory is to assume that interacting agents are rational, and thus act to achieve their own objectives. Adding rationality to the synthesis setting softens the universal quantification on the environments, and motivates the study of rational synthesis. There, we seek a system that satisfies its specification in all rational environments. The above can be formalized in two different ways. The first is cooperative rational synthesis, where the desired output is a stable profile of strategies to all components in which the objective of the system is satisfied. The second is non-cooperative rational synthesis, where the desired output is a strategy for the system such that its objective is satisfied in every stable profile where she follows this strategy.  The talk introduces the two types of rational synthesis and surveys their game-theoretical aspects. In particular, we discuss quantitative rational synthesis and relate cooperative and non-cooperative  rational synthesis with the two notions of equilibrium inefficiency in game theory, namely price of stability and price of anarchy.  The talk is based on joint work with Shaull Almagor, Dana Fisman, Yoad Lustig, Giuseppe Perelli, and Moshe Y. Vardi.