Doctor of Science Dissertation
Logic Programming, Decisions and Games
December 2001
Department of Computer Science
Vrije Universiteit Brussel
Pleinlaan 2
B-1050 Brussels
This work was funded by the Fund for Scientific Research
Flanders (FWO)
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
- Introduction
- Motivation
- Overview
- Preliminary Mathematical Notions
- Logic Programming
- Introduction
- Positive Logic Programs
- Introducing Negation as Failure
- Disjunctive Logic Programming
- Stable Model Semantics
- Possible Model Semantics
- Extended Disjunctive Logic Programs
- Beyond Rules
- Conclusions
- Game Theory
- Introduction
- Strategic Games
- Introduction
- Nash Equilibria
- Mixed Strategy Nash Equilibria
- Extensive Games with Perfect Information
- Introduction
- Nash Equilibria
- Subgame Perfect Equilibria
- Game Theory and Logic
- Logic Games
- Game Logic
- Conclusions
- Choice Logic Programming
- Introduction
- Choice Logic Programs
- Simulating Semi-Negative Logic Programs
- Unfounded sets and Stable Models
- Unfounded Sets
- A Fixpoint-Operator for G
- Unfounded Sets and Stable Models
- A Fixpoint Semantics for Stable Models
- An Algorithm for Computing Stable Models
- Choice Logic Programs and Game Theory
- Relationship with Other Approaches
- Logic Programming Formalisms
- Logic Programming and Strategic Games
- Conclusions
- Ordered Choice Logic Programming
- Introduction
- Ordered Choice Logic Programs
- The Stable Model Semantics
- Definition
- Fixpoint Characterization
- Extending Unfounded sets
- Detecting Stable Models
- Stable Models as Fixpoints
- Procedural Semantics
- The Algorithm
- Skeptical vs. Credulous
- The Answer Set Semantics
- A Credulous Fixpoint Characterization
- Assumption sets
- Assumption Sets for Answer Set Detection
- Answer Sets as Fixpoints
- Procedural Declaration
- The Credulous Algorithm
- Logic Programming in OCLP
- OCLP and Game Theory
- Modeling Extensive Games with Perfect Information
- Cautious Equilibria
- Relationship with Other Approaches
- Ordered Logic Programming
- OCLP and Game Theory
- Preferences/Order
- Conclusions
- DOP-CLP
- Introduction
- DOP-CLP
- An Application of DOP-CLPs: Game theory
- Relationships to Other Approaches
- Logic Programming
- Priorities
- Uncertainty
- Games
- Conclusions
- Logic Programming Agents
- Introduction
- Agents
- Playing Games
- Phase 1: OCLPs Representing Games
- Phase 2: Player Based OCLPs
- Phase 3: Multi-agent Systems
- Relationship with Other Approaches
- Conclusions
- Conclusions and Future Research
- General Conclusions
- Further Research
Thesis text
The dissertation is available online