Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-20T04:06:13.229Z Has data issue: false hasContentIssue false
  • English
  • Français

Exploiting Game Theory for Analysing Justifications

Published online by Cambridge University Press:  22 September 2020

SIMON MARYNISSEN Open the ORCID record for SIMON MARYNISSEN [Opens in a new window] ,
BART BOGAERTS  and
MARC DENECKER
SIMON MARYNISSEN
Affiliation:
KU Leuven Vrije Universiteit Brussel
BART BOGAERTS
Affiliation:
Vrije Universiteit Brussel
MARC DENECKER
Affiliation:
KU Leuven
Get access Rights & Permissions [Opens in a new window]

Abstract

Justification theory is a unifying semantic framework. While it has its roots in non-monotonic logics, it can be applied to various areas in computer science, especially in explainable reasoning; its most central concept is a justification: an explanation why a property holds (or does not hold) in a model.

In this paper, we continue the study of justification theory by means of three major contributions. The first is studying the relation between justification theory and game theory. We show that justification frameworks can be seen as a special type of games. The established connection provides the theoretical foundations for our next two contributions. The second contribution is studying under which condition two different dialects of justification theory (graphs as explanations vs trees as explanations) coincide. The third contribution is establishing a precise criterion of when a semantics induced by justification theory yields consistent results. In the past proving that such semantics were consistent took cumbersome and elaborate proofs.

We show that these criteria are indeed satisfied for all common semantics of logic programming.

Keywords

justification theorypositional gameslogic programmingnon-monotonic logic
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 20 , Issue 6: 36th International Conference on Logic Programming Special Issue II , November 2020 , pp. 880 - 894
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Blair, H. A. 1995. Game characterizations of logic program properties. In Proceedings of LPNMR. 99–112.Google Scholar
Bogaerts, B. and Weinzierl, A. 2018. Exploiting justifications for lazy grounding of answer set programs. In Proceedings of IJCAI. 1737–1745.Google Scholar
Denecker, M. 1993. Knowledge representation and reasoning in incomplete logic programming. Ph.D. thesis, K.U.Leuven, Leuven, Belgium.Google Scholar
Denecker, M., Brewka, G., and Strass, H. 2015. A formal theory of justifications. In Proceedings of LPNMR. 250–264.Google Scholar
Denecker, M., Marek, V., and Truszczyński, M. 2000. Approximations, stable operators, well-founded fixpoints and applications in nonmonotonic reasoning. In Logic-Based Artificial Intelligence. 127–144.Google Scholar
Dung, P. M. 1995. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. AIJ 77, 2, 321–357.Google Scholar
Galanaki, C., Rondogiannis, P., and Wadge, W. W. 2008. An infinite-game semantics for well-founded negation in logic programming. Ann. Pure Appl. Log. 151, 2-3, 70–88.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., and Schaub, T. 2009. On the implementation of weight constraint rules in conflict-driven ASP solvers. In ICLP. 250–264.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proceedings of ICLP/SLP. 1070–1080.Google Scholar
Gimbert, H. and Zielonka, W. 2004. When can you play positionnaly? In Proceedings of MFCS. 686–697.Google Scholar
Gimbert, H. and Zielonka, W. 2005. Games where you can play optimally without any memory. In Proceedings of CONCUR. 428–442.Google Scholar
Lapauw, R., Bruynooghe, M., and Denecker, M. 2020. Improving parity game solvers with justifications. In Proceedings of VMCAI. 449–470.Google Scholar
Loddo, J. and Cosmo, R. D. 2000. Playing logic programs with the alpha-beta algorithm. In Proceedings of LPAR. 207–224.Google Scholar
Martin, D. A. 1975. Borel determinacy. Annals of Mathematics 102, 2, 363–371.Google Scholar
Marynissen, S., Bogaerts, B., and Denecker, M. 2020. Exploiting Game Theory for Analysing Justifications. arXiv e-prints, arXiv:2008.01609.Google Scholar
Marynissen, S., Passchyn, N., Bogaerts, B., and Denecker, M. 2018. Consistency in justification theory. In Proceedings of NMR. 41–52.Google Scholar
Miller, T. 2019. Explanation in artificial intelligence: Insights from the social sciences. AIJ 267, 1–38.Google Scholar
Soare, R. I. 2016. Gale-Stewart Games. Springer Berlin Heidelberg, Berlin, Heidelberg, 217–219.Google Scholar
van Emden, M. H. 1986. Quantitative deduction and its fixpoint theory. J. Log. Program. 3, 1, 37–53.Google Scholar
Van Gelder, A., Ross, K. A., and Schlipf, J. S. 1991. The well-founded semantics for general logic programs. J. ACM 38, 3, 620–650.Google Scholar