Temporal qualitative coalitional games

ABSTRACT

Qualitative Coalitional Games (QCGs) are a version of coalitional games in which an agent's desires are represented as goals which are either satisfied or unsatisfied, and each choice available to a coalition is a set of goals, which would be jointly satisfied if the coalition made that choice. A coalition in a QCG will typically form in order to bring about a set of goals that will satisfy all members of the coalition. In this paper, we introduce and study Temporal QCGs (TQCGs), i.e., games in which a sequence of QCGs is played. In order to represent and reason about such games, we introduce a linear time temporal logic of QCGs, known as £ (TQCG). We give a complete axiomatization of £ (TQCG), use it to investigate the properties of TQCGs in a small example, identify its expressive power, establish its complexity, characterise classes of TQGCs with formulas from our logical language, and formulate several (temporal) solution concepts for TQCGs.

REFERENCES

• 1: Rajeev Alur , Thomas A. Henzinger , Orna Kupferman , Moshe Y. Vardi, Alternating Refinement Relations, Proceedings of the 9th International Conference on Concurrency Theory, p.163-178, September 08-11, 1998
• 2: R. Axelrod. The Evolution of Cooperation. Basic Books: New York, 1984.
• 3: K. Binmore. Fun and Games: A Text on Game Theory. D. C. Heath and Company: Lexington, MA, 1992.
• 4: M. Finger and D. M. Gabbay. Adding a temporal dimension to a logic system. Journal of Logic, Language, and Information, 1:203--233, 1992.
• 5: D. M. Gabbay, A. Kurucz, F. Wolter, and M. Zakharyaschev. Many-Dimensional Modal Logics: Theory and Applications. Elsevier, 2003.
• 6: Dov Gabbay , Amir Pnueli , Saharon Shelah , Jonathan Stavi, On the temporal analysis of fairness, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.163-173, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567462]
• 7: Matthias Klusch , Andreas Gerber, Dynamic Coalition Formation among Rational Agents, IEEE Intelligent Systems, v.17 n.3, p.42-47, May 2002 [doi>10.1109/MIS.2002.1005630 ]
• 8: Zohar Manna , Amir Pnueli, The temporal logic of reactive and concurrent systems, Springer-Verlag New York, Inc., New York, NY, 1992
• 9: M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press: Cambridge, MA, 1994.
• 10: M. Pauly. Axiomatising Judgement Aggregation Procedures in a Mininal Logical Language. Unpublished paper.
• 11: Tuomas W. Sandholm, Distributed rational decision making, Multiagent systems: a modern approach to distributed artificial intelligence, MIT Press, Cambridge, MA, 1999
• 12: Tuomas Sandholm , Kate Larson , Martin Andersson , Onn Shehory , Fernando Tohmé, Coalition structure generation with worst case guarantees, Artificial Intelligence, v.111 n.1-2, p.209-238, July 1999 [doi>10.1016/S0004-3702(99)00036-3]
• 13: Onn Shehory , Sarit Kraus, Methods for task allocation via agent coalition formation, Artificial Intelligence, v.101 n.1-2, p.165-200, May 1998 [doi>10.1016/S0004-3702(98)00045-9 ]
• 14: A. P. Sistla , E. M. Clarke, The complexity of propositional linear temporal logics, Journal of the ACM (JACM), v.32 n.3, p.733-749, July 1985 [doi>10.1145/3828.3837]
• 15: Michael Wooldridge , Paul E. Dunne, On the computational complexity of qualitative coalitional games, Artificial Intelligence, v.158 n.1, p.27-73, September 2004 [doi>10.1016/j.artint.2004.04.002]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

General Terms:
Theory

Keywords:
coalitional games, logic, repeated games