A comparison of the notions of optimality in soft constraints and graphical games

Open Access
Authors
Publication date 2008
Host editors
  • F. Fages
  • F. Rossi
  • S. Soliman
Book title Recent Advances in Constraints
Book subtitle 12th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2007 Rocquencourt, France, June 7-8, 2007 : revised selected papers
ISBN
  • 9783540898115
ISBN (electronic)
  • 9783540898122
Series Lecture Notes in Computer Science
Event 12th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming (CSCLP 2007), Rocquencourt, France
Pages (from-to) 1-16
Publisher Berlin: Springer
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
Abstract
The notion of optimality naturally arises in many areas of applied mathematics and computer science concerned with decision making. Here we consider this notion in the context of two formalisms used for different purposes and in different research areas: graphical games and soft constraints. We relate the notion of optimality used in the area of soft constraint satisfaction problems (SCSPs) to that used in graphical games, showing that for a large class of SCSPs that includes weighted constraints every optimal solution corresponds to a Nash equilibrium that is also a Pareto efficient joint strategy.
We also study alternative mappings including one that maps graphical games to SCSPs, for which Pareto efficient joint strategies and optimal solutions coincide.
Document type Conference contribution
Language English
Published at https://doi.org/10.1007/978-3-540-89812-2_1
Downloads
296990.pdf (Accepted author manuscript)
Permalink to this page
Back