2008/10/16 by Krzysztof R. Apt, Apt, Krzysztof R., Francesca Rossi +4
Computer Science · #Artificial Intelligence (cs.AI) #Computer Science and Game Theory (cs.GT) #Constraint Satisfaction and Optimization #D.3.3 #Data Management and Algorithms #FOS: Computer and information sciences #I.2.11 #Logic, Reasoning, and Knowledge #cs.AI #cs.GT
paper · pdf · doi:10.48550/arxiv.0810.2861
18 pages. To appear in Recent Advances in Constraints, (F. Fages, S. Soliman and F. Rossi, eds.) Springer Lecture Notes in Artificial Intelligence 5129, 2008
arxiv created 2008/10/16 · openalex publication_date 2008/10/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.