Doctor of Science Dissertation

Logic Programming, Decisions and Games

December 2001

Department of Computer Science
Vrije Universiteit Brussel
Pleinlaan 2
B-1050 Brussels

Abstract

In this dissertation we investigate logic programming to model decision-making. To this extent, we introduce three formalisms with increasing expressiveness. The most basic one, called choice logic programming, allows circumstance-dependent decisions. The stable models of the program correspond to the rational solutions of the represented decision-problem. To support dynamic preference-based decision-making, we extend our formalism to ordered choice logic programming. To accommodate the various ways two equally preferred alternatives are dealt with, both the skeptical stable model semantics and the more credulous answer set semantics are introduced. Decisions often have to be made without complete information. In order to deal with uncertainty, dynamically ordered probabilistic choice logic programs are presented. The stable models of these programs represent those solutions that deal with uncertainty in a rational manner. Game theory, a collection of analytical tools for studying the interaction of decision-makers, is used to demonstrate the effectiveness of our formalisms. Strategic games and extensive games with perfect information can be elegantly represented in our formalism such that the equilibria of the games can be retrieved as the stable models or answer sets of the programs. These equilibria are not player-deterministic in the sense that a single player, given the other players' actions, could rationally leave an equilibrium state. We introduce player-deterministic, called cautious, Nash and subgame perfect equilibria as the skeptical stable models of the transformed game. To study the decision-process and the interaction between various decision-makers, we introduce a framework for logic programming agents. When applied to game theory, this enables us to monitor and reason about the knowledge and beliefs of each single player.

Supervisor

Prof. Dirk Vermeir (Vrije Universiteit Brussel)

Viva Committee

• Prof. Bernard Manderick (Vrije Universiteit Brussel, Belgium), Chair
• Prof. Luc Steels (Vrije Universiteit Brussel, Belgium and Sony Research Labs, Paris, France)
• Prof. Dirk Vermeir (Vrije Universiteit Brussel, Belgium), Supervisor
• Prof. Jean Paul Van Bendegem (Vrije Universiteit Brussel, Belgium
• Prof. Vladimir Lifschitz (University of Texas at Austin, US)
• Prof. Johan Van Benthem (University of Amsterdam, The Netherlands and Stanford University, CA, US)
• Prof. Stefania Costantini (University of L'Aquila, Italy)

Table of Contents

• Abstract
• Acknowledgements

1. Introduction
1. Motivation
2. Overview
2. Preliminary Mathematical Notions
3. Logic Programming
1. Introduction
2. Positive Logic Programs
3. Introducing Negation as Failure
4. Disjunctive Logic Programming
1. Stable Model Semantics
2. Possible Model Semantics
5. Extended Disjunctive Logic Programs
6. Beyond Rules
7. Conclusions
4. Game Theory
1. Introduction
2. Strategic Games
1. Introduction
2. Nash Equilibria
3. Mixed Strategy Nash Equilibria
3. Extensive Games with Perfect Information
1. Introduction
2. Nash Equilibria
3. Subgame Perfect Equilibria
4. Game Theory and Logic
1. Logic Games
2. Game Logic
5. Conclusions
5. Choice Logic Programming
1. Introduction
2. Choice Logic Programs
3. Simulating Semi-Negative Logic Programs
4. Unfounded sets and Stable Models
1. Unfounded Sets
2. A Fixpoint-Operator for G
3. Unfounded Sets and Stable Models
4. A Fixpoint Semantics for Stable Models
5. An Algorithm for Computing Stable Models
5. Choice Logic Programs and Game Theory
6. Relationship with Other Approaches
1. Logic Programming Formalisms
2. Logic Programming and Strategic Games
7. Conclusions
6. Ordered Choice Logic Programming
1. Introduction
2. Ordered Choice Logic Programs
3. The Stable Model Semantics
1. Definition
2. Fixpoint Characterization
1. Extending Unfounded sets
2. Detecting Stable Models
3. Stable Models as Fixpoints
4. Procedural Semantics
5. The Algorithm
4. Skeptical vs. Credulous
1. The Answer Set Semantics
2. A Credulous Fixpoint Characterization
1. Assumption sets
2. Assumption Sets for Answer Set Detection
3. Answer Sets as Fixpoints
4. Procedural Declaration
5. The Credulous Algorithm
5. Logic Programming in OCLP
6. OCLP and Game Theory
1. Modeling Extensive Games with Perfect Information
2. Cautious Equilibria
7. Relationship with Other Approaches
1. Ordered Logic Programming
2. OCLP and Game Theory
3. Preferences/Order
8. Conclusions
7. DOP-CLP
1. Introduction
2. DOP-CLP
3. An Application of DOP-CLPs: Game theory
4. Relationships to Other Approaches
1. Logic Programming
2. Priorities
3. Uncertainty
4. Games
5. Conclusions
8. Logic Programming Agents
1. Introduction
2. Agents
3. Playing Games
1. Phase 1: OCLPs Representing Games
2. Phase 2: Player Based OCLPs
3. Phase 3: Multi-agent Systems
4. Relationship with Other Approaches
5. Conclusions
9. Conclusions and Future Research
1. General Conclusions
2. Further Research

Thesis text

The dissertation is available online