comparing the notions of optimality in cp-nets, strategic：比较了战略的最优性概念精品.pdfVIP

Comparing the notions of optimality in CP-nets, strategic games and soft constraints 1,2 3 3 Krzysztof R. Apt , Francesca Rossi , and Kristen Brent Venable 1 CWI Amsterdam, Kruislaan 413 1098 SJ, Amsterdam, the Netherlands E-mail: apt@cwi.nl 2University of Amsterdam, Plantage Muidergracht 24 1018 TV, Amsterdam, the Netherlands 3Department of Pure and Applied Mathematics, University of Padova, Via Trieste, 63 - 35121, Padova, Italy E-mails:{frossi,kvenable}@math.unipd.it Keywords: Strategic games, pure Nash equilibria, preferences, CP nets, soft constraints AMS MOS Classification: 91B10, 91B50, 68T01, 68T30 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 three formalisms used for different purposes in reasoning about multi-agent systems: strategic games, CP-nets, and soft constraints. To relate the notions of optimal- ity in these formalisms we introduce a natural qualitative modification of the notion of a strategic game. We show then that the optimal out- comes of a CP-net are exactly the Nash equilibria of such games. This allows us to use the techniques of game theory to search for optimal outcomes of CP-nets and vice-versa, to use techniques developed for CP-nets to search for Nash equilibria of the considered games. Then, we relate the notion of optimality used in the area of soft constraints