Logic Journal of IGPL Advance Access originally published online on May 18, 2009
Logic Journal of IGPL 2009 17(3):299-321; doi:10.1093/jigpal/jzp009
Logics for Qualitative Coalitional Games
University of Bergen, Norway.
E-mail: thomas.agotnes{at}infomedia.uib.no
University of Liverpool, United Kingdom.
E-mail: wiebe{at}csc.liv.ac.uk,mjw{at}csc.liv.ac.uk
*Corresponding author. Address: Department of Information Science and Media Studies, University of Bergen, PB 7800, 5007 Bergen, Norway.
Qualitative Coalitional Games (QCGs) are a variant of coalitional games in which an agent's desires are represented as goals that 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. Our goal in this paper is to develop and study logics for reasoning about QCGs. We begin by introducing a logic for reasoning about "static" QCGs, where participants play a single game, and we then 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, called 
(TQCG). We give a complete axiomatisation of (TQCG), use it to investigate the properties of TQCGs, identify its expressive power, establish its complexity, characterise classes of TQGCs with formulas from our logical language, and use it to formulate several (temporal) solution concepts for TQCGs.
Key Words: modal logic • temporal logic • coalitional games • repeated games
References
-
[1] Ågotnes Thomas, van der Hoek Wiebe, Wooldridge Michael. Reasoning about coalitional games. Artificial Intelligence (2009) 173(1):45–79.[CrossRef][Web of Science]
[2] Ågotnes Thomas, Wooldridge Michael, van der Hoek Wiebe. Temporal qualitative coalitional games. Stone P, Weiss G, eds. (May 2006) Japan, ACM Press: Hakodate. 177–184. Proceedings of the Fifth International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
[3] Alur Rajeev, Henzinger Thomas A, Kupferman Orna, Vardi Moshe Y. Alternating refinement relations. (1998) Berlin, Germany: Springer-Verlag. 163–178. Proceedings of the 9th International Conference on Concurrency Theory (CONCUR'98), volume 1466 of Lecture Notes in Computer Science.
[4] Axelrod R. The Evolution of Cooperation (1984) New York: Basic Books.
[5] Binmore K. Fun and Games: A Text on Game Theory (1992) Lexington: D. C. Heath and Company.
[6] Blackburn P, de Rijke M, Venema Y. Modal Logic (2001) Cambridge: Cambridge University Press.
[7] Finger M, Gabbay DM. Adding a temporal dimension to a logic system. Journal of Logic, Language, and Information (1992) 1:203–233.[CrossRef]
[8] Gabbay DM, Kurucz A, Wolter F, Zakharyaschev M. Many-Dimensional Modal Logics: Theory and Applications (2003) Elsevier.
[9] Gabbay Dov, Pnueli Amir, Shelah Saharon, Stavi Jonathan. On the temporal analysis of fairness. (January 1980) New York, USA: ACM Press. 163–173. Conference Record of the Seventh ACM Symposium on Principles of Programming Languages (POPL '80).
[10] Klusch M, Gerber A. Dynamic coalition formation among rational agents. IEEE Intelligent Systems (June 2002) 17(3):42–47.
[11] Manna Z, Pnueli A. The Temporal Logic of Reactive and Concurrent Systems (1992) Berlin, Germany: Springer-Verlag.
[12] Osborne MJ, Rubinstein A. A Course in Game Theory (1994) Cambridge, MA: The MIT Press.
[13] Pauly M. Axiomatising judgement aggregation procedures in a minimal logical language. Unpublished paper.
[14] Sandholm T. Distributed rational decision making. In: Multiagent Systems—Wei G, ed. (1999) Cambridge, MA: The MIT Press. 201–258.
[15] Sandholm T, Larson K, Andersson M, Shehory O, Tohmé F. Coalition structure generation with worst case guarantees. Artificial Intelligence (1999) 111(1–2):209–238.[CrossRef][Web of Science]
[16] Shehory O, Kraus S. Methods for task allocation via agent coalition formation. Artificial Intelligence (1998) 101(1–2):165–200.[CrossRef][Web of Science]
[17] Sistla AP, Clarke EM. The complexity of propositional linear temporal logics. Journal of the ACM (1985) 32(3):733–749.[CrossRef][Web of Science]
[18] van der Hoek W, Pauly M. Modal logic for games and information. In: Handbook of Modal Logic—Blackburn P, van Benthem J, Wolter F, eds. (2006) Amsterdam, The Netherlands: Elsevier Science Publishers B.V. 1077–1148.
[19] Wooldridge M. Reasoning about Rational Agents (2000) Cambridge, MA: The MIT Press.
[20] Wooldridge M, Dunne PE. On the computational complexity of qualitative coalitional games. Artificial Intelligence (2004) 158(1):27–73.[CrossRef][Web of Science]
CiteULike 
Connotea 
Del.icio.us What's this?
| ||||||||||||||||||||||||||||||||||||||||||||||||