A logic of games and propositional control

ABSTRACT

We present a logic for reasoning about strategic games. The logic is a modal formalism, based on the Coalition Logic of Propositional Control, to which we add the notions of outcomes and preferences over outcomes. We study the underlying structure of powers of coalitions as they are expressed in their effectivity function, and formalise a collection of solution concepts. We provide a sound and complete axiomatisation for the logic, and we demonstrate its features by applying it to some problems from social choice theory.

REFERENCES

• 1: J. Abdou. Rectangular game forms. Working paper. ftp://mse.univ-paris1.fr/pub/mse/cahiers2002/B02114.pdf.
• 2: J. Abdou and K. Keiding. Effectivity Functions in Social Choice Theory. Kluwer Academic, Dordrecht, 1991.
• 3: Thomas Ågotnes , Wiebe van der Hoek , Michael Wooldridge, Reasoning about judgment and preference aggregation, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329228]
• 4: R. Alur, L. de Alfaro, T. A. Henzinger, S. C. Krishnan, F. Y. C. Mang, S. Qadeer, S. K. Rajamani, and S. Taşiran. mocha user manual. University of Berkeley Report, 2000.
• 5: Rajeev Alur , Thomas A. Henzinger , Orna Kupferman, Alternating-time Temporal Logic, Proceedings of the 38th Annual Symposium on Foundations of Computer Science, p.100, October 19-22, 1997
• 6: C. Areces and B. ten Cate. Handbook of Modal Logic, chapter Hybrid Logics, pp. 821--868. Elsevier Science Inc. 2006.
• 7: K. J. Arrow, A. K. Sen, and K. Suzumura, editors. Handbook of Social Choice and Welfare, volume 1. Elsevier, 2002.
• 8: Patrick Blackburn , Maarten de Rijke , Yde Venema, Modal logic, Cambridge University Press, New York, NY, 2001
• 9: E. Bonzon, M. C. Lagasquie-Shiex, and J. Lang. Efficient coalitions in Boolean games. In New Perspectives on Games and Interaction. Texts in Logic and Games, 4, pp. 283--297. Amsterdam University Press, 2007.
• 10: Jelle Gerbrandy, Logics of propositional control, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160664]
• 11: A. Gibbard. A Pareto-consistent libertarian claim. Journal of Economic Theory, 7(4), pp. 388--410, 1974.
• 12: P. Girard. Modal logic for belief and preference change. PhD thesis, Stanford University, 2008.
• 13: Helle Hvid Hansen , Marc Pauly, Axiomatising Nash-Consistent Coalition Logic, Proceedings of the European Conference on Logics in Artificial Intelligence, p.394-406, September 23-26, 2002
• 14: S. Hansson. Preference Logic. In Handbook of Philosophical Logic: Volume IV, Second edition, D. Gabbay and F. Guenthner, editors, Springer, pp. 319--393, 2001.
• 15: J. F. Horty and N. D. Belnap, Jr. The deliberative stit: A study of action, omission, and obligation. Journal of Philosophical Logic, 24(6), pp. 583--644, 1995.
• 16: E. Maskin and T. Sjöström. Handbook of Social Choice and Welfare, chapter Implementation Theory, pp. 237--288. Volume 1 of Arrow et al. {7}, 2002.
• 17: M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press, 1994.
• 18: R. Parikh. Social software. Synthese, 132(3), pp. 187--211, 2002.
• 19: M. Pauly. A modal logic for coalitional power in games. Journal of Logic and Computation, 12(1), pp. 149--166, 2002.
• 20: B. Peleg, H. Peters, and T. Storcken. Nash consistent representation of constitutions: A reaction to the Gibbard paradox. Mathematical Social Sciences, 43, pp. 267--287, 2002.
• 21: Nicolas Troquard , Wiebe Hoek , Michael Wooldridge, Model Checking Strategic Equilibria, Model Checking and Artificial Intelligence: 5th International Workshop, MoChArt 2008, Patras, Greece, July 21, 2008. Revised Selected and Invited Papers, Springer-Verlag, Berlin, Heidelberg, 2009 [doi>10.1007/978-3-642-00431-5_11]
• 22: J. van Benthem. Open problems in logic and games. In S. N. Artëmov, H. Barringer, A. S. d'Avila Garcez, L. C. Lamb, and J. Woods, editors, We Will Show Them! Essays in Honour of Dov Gabbay, volume 1, pp. 229--264. King's College Publications, London, 2005.
• 23: J. van Benthem, O. Roy, and P. Girard. Everything else being equal: A modal logic approach to Ceteris Paribus preferences. In Journal of Philosophical Logic, 38(1), pp. 83--125, 2008.
• 24: J. van Benthem, S. van Otterloo, and O. Roy. Preference Logic, Conditionals, and Solution Concepts in Games. In H. Lagerlund, S. Lindström, and R. Sliwinski, editors, Modality Matters, pp. 61--76. University of Uppsala, 2006.
• 25: Wiebe van der Hoek , Michael Wooldridge, On the logic of cooperation and propositional control, Artificial Intelligence, v.164 n.1-2, p.81-119, May 2005 [doi>10.1016/j.artint.2005.01.003]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Modal logic

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Theory

Keywords:
effectivity functions, game solvability, modal logic, propositional control, solution concepts, strategic games