Approximating Correlated Equilibria using Relaxations on the Marginal Polytope

摘要: In game theory, a Correlated Equilibrium (CE) is an equilibrium concept that generalizes the more well-known Nash Equilibrium. If represented as graphical game, computational complexity of computing optimum CE exponential in tree-width graph. settings where this exact computation not feasible, it desirable to approximate properties CE, such its expected social utility and marginal probabilities. We study outer relaxations problem yield strategies for players under variety functions. Results on simulated games real involving drug design indicate our approximations can be highly accurate successfully used when infeasible.