2 Search Results for "Bauters, Kim"

Document

DOI: 10.4230/LIPIcs.SAT.2025.19

An Application of SAT Solvers in Integer Programming Games

Authors: Pravesh Koirala, Aditya Shrey, and Forrest Laine

Published in: LIPIcs, Volume 341, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)

Abstract

Integer programming games (IPGs) are a popular game-theoretic tool to model an array of games where each player has a discrete strategy set. These games arise in important domains such as economics, transportation, cybersecurity, etc., but solving them is non-trivial as it is known that checking for the existence of pure Nash equilibria in an IPG is Σ₂^p-complete. Recent works have proposed a class of relaxed solution concepts for IPGs called locally optimal integer solutions (LOIS) and shown it to be an efficient alternative for pure Nash equilibria. While LOIS are significantly simpler to compute, they still do not scale when solved using traditional mathematical solvers, especially when high-quality solutions are desired. In this paper, we apply commercially available SAT solvers to find LOIS in IPGs. We investigate efficient encodings for a cybersecurity game and compare solution times when using SAT solvers vs mathematical program solvers. We also investigate the application of SAT solvers in graph games using a graph interdiction example and compare against the obtained LOI solutions against existing heuristics-based solutions. Our results indicate that with appropriate encodings, large-scale IPGs can be solved much more efficiently using SAT solvers. We also show that SAT solvers can be applied to graph games in conjunction with LOIS for obtaining high-quality solutions. Our results emphasize the potential of SAT solvers combined with LOIS to solve significant game theory problems.

Cite as

Pravesh Koirala, Aditya Shrey, and Forrest Laine. An Application of SAT Solvers in Integer Programming Games. In 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 341, pp. 19:1-19:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{koirala_et_al:LIPIcs.SAT.2025.19,
  author =	{Koirala, Pravesh and Shrey, Aditya and Laine, Forrest},
  title =	{{An Application of SAT Solvers in Integer Programming Games}},
  booktitle =	{28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)},
  pages =	{19:1--19:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-381-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{341},
  editor =	{Berg, Jeremias and Nordstr\"{o}m, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2025.19},
  URN =		{urn:nbn:de:0030-drops-237534},
  doi =		{10.4230/LIPIcs.SAT.2025.19},
  annote =	{Keywords: Game Theory, Integer Programming Games, SAT Solvers, Local Solutions, Graph Games}
}

Document

DOI: 10.4230/LIPIcs.ICLP.2010.34

Communicating Answer Set Programs

Authors: Kim Bauters, Jeroen Janssen, Steven Schockaert, Dirk Vermeir, and Martine De Cock

Published in: LIPIcs, Volume 7, Technical Communications of the 26th International Conference on Logic Programming (2010)

Abstract

Answer set programming is a form of declarative programming that has proven very successful in succinctly formulating and solving complex problems. Although mechanisms for representing and reasoning with the combined answer set programs of multiple agents have already been proposed, the actual gain in expressivity when adding communication has not been thoroughly studied. We show that allowing simple programs to talk to each other results in the same expressivity as adding negation-as-failure. Furthermore, we show that the ability to focus on one program in a network of simple programs results in the same expressivity as adding disjunction in the head of the rules.

Cite as

Kim Bauters, Jeroen Janssen, Steven Schockaert, Dirk Vermeir, and Martine De Cock. Communicating Answer Set Programs. In Technical Communications of the 26th International Conference on Logic Programming. Leibniz International Proceedings in Informatics (LIPIcs), Volume 7, pp. 34-43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bauters_et_al:LIPIcs.ICLP.2010.34,
  author =	{Bauters, Kim and Janssen, Jeroen and Schockaert, Steven and Vermeir, Dirk and De Cock, Martine},
  title =	{{Communicating Answer Set Programs}},
  booktitle =	{Technical Communications of the 26th International Conference on Logic Programming},
  pages =	{34--43},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-17-0},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{7},
  editor =	{Hermenegildo, Manuel and Schaub, Torsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2010.34},
  URN =		{urn:nbn:de:0030-drops-25813},
  doi =		{10.4230/LIPIcs.ICLP.2010.34},
  annote =	{Keywords: }
}

Refine by Type
2 Document/PDF
1 Document/HTML

Refine by Publication Year
1 2025
1 2010

Refine by Author
1 Bauters, Kim
1 De Cock, Martine
1 Janssen, Jeroen
1 Koirala, Pravesh
1 Laine, Forrest
Show More...

Refine by Series/Journal
2 LIPIcs

Refine by Classification
1 Security and privacy → Network security
1 Theory of computation → Algorithmic game theory and mechanism design

Refine by Keyword
1 Game Theory
1 Graph Games
1 Integer Programming Games
1 Local Solutions
1 SAT Solvers

2 Search Results for "Bauters, Kim"

An Application of SAT Solvers in Integer Programming Games

Abstract

Cite as

Communicating Answer Set Programs

Abstract

Cite as

Thanks for your feedback!

Could not send message