Abstract

We study the game modification problem, where a benevolent game designer or amalevolent adversary modifies the reward function of a zero-sum Markov game sothat a target deterministic or stochastic policy profile becomes the uniqueMarkov perfect Nash equilibrium and has a value within a target range, in a waythat minimizes the modification cost. We characterize the set of policyprofiles that can be installed as the unique equilibrium of some game, andestablish sufficient and necessary conditions for successful installation. Wepropose an efficient algorithm, which solves a convex optimization problem withlinear constraints and then performs random perturbation, to obtain amodification plan with a near-optimal cost.

 

Quick Read (beta)