A Complete Solver for Constraint Games
Game Theory studies situations in which multiple agents having conflicting objectives have to reach a collective decision. The question of a compact representation language for agents utility function is of crucial importance since the classical representation of a $n$-players game is given by a $n$-dimensional matrix of exponential size for each player. In this paper we use the framework of Constraint Games in which CSP are used to represent utilities. Constraint Programming --including global constraints-- allows to easily give a compact and elegant model to many useful games. Constraint Games come in two flavors: Constraint Satisfaction Games and Constraint Optimization Games, the first one using satisfaction to define boolean utilities. In addition to multimatrix games, it is also possible to model more complex games where hard constraints forbid certain situations. In this paper we study complete search techniques and show that our solver using the compact representation of Constraint Games is faster than the classical game solver Gambit by one to two orders of magnitude.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On the Geometry of Games and their Solvers
A central challenge in game theory and learning systems such as GANs is understanding which algorithms can efficiently compute equilibria across the heterogeneous landscape of games. Equilibrium computation is typically …
ALGAMES: A Fast Solver for Constrained Dynamic Games
Dynamic games are an effective paradigm for dealing with the control of multiple interacting actors. This paper introduces ALGAMES (Augmented Lagrangian GAME-theoretic Solver), a solver that handles trajectory optimizati…
Autonomous DrivingModel Predictive ControlLudii and XCSP: Playing and Solving Logic Puzzles
Many of the famous single-player games, commonly called puzzles, can be shown to be NP-Complete. Indeed, this class of complexity contains hundreds of puzzles, since people particularly appreciate completing an intractab…
Rethinking the Soft Conflict Pseudo Boolean Constraint on MaxSAT Local Search Solvers
MaxSAT is an optimization version of the famous NP-complete Satisfiability problem (SAT). Algorithms for MaxSAT mainly include complete solvers and local search incomplete solvers. In many complete solvers, once a better…
Proceedings of the 2022 XCSP3 Competition
This document represents the proceedings of the 2022 XCSP3 Competition. The results of this competition of constraint solvers were presented at FLOC (Federated Logic Conference) 2022 Olympic Games, held in Haifa, Israel …