Abstract:
Introduced by Zhang, Chen, and Parkes, the environment design problem concerns an interested party that must decide how to make limited changes to an environment so that an agent placed in the environment will perform a desired target policy. In this standard design scenario, the agent is assumed to have fixed preferences and capabilities. However, in many instances, it may be conceivable that the agents are capable of learning; this learning effect can be captured by allowing the agent's preferences to change after each elicitation round. By adopting a simplifying model, I analyze how these changes transform the underlying design problem. I provide a general design strategy to efficiently induce the the target policy, and I discuss a series of scenarios with varied goals in which this general strategy succeeds. I then characterize a few instances in which this strategy is sub-optimal. These results have implications in policy teaching and in general settings in which incentives are provided to humans with the goal of eliciting desired behaviors.

Dylan Zhang, Parkes, and Chen introduced environment design as a systematic method for designing incentives to influence agent behavior, providing algorithms for the single-agent setting when the agent's preferences are known or unknown. Monderer and Tennonholtz describe the process of influencing agent behavior in a game setting with multiple agents and known agent utilities. Here I attempt to extend both of these works by providing algorithms to influence agent behavior in a normal form game when the utilities of the agents are initially unknown. The incentives are restricted to providing positive payoffs in certain states of the game, subject to some budget constraint. As a result, the proposed algorithms may be employed by any interested party wishing to influence the game toward any outcome. These ideas can be applied to numerous practical, multi-agent settings, such as contributions to Web 2.0 sites, social networking, or electronic commerce, where an interested party cares about the outcome of a multi-agent interaction.