Abstract: Motivated by the control theoretic distinction between controllable and uncontrollable events, we distinguish between two types of agents within a multi-agent system: controllable agents, which are directly controlled by the system's designer, and uncontrollable agents, which are not under the designer's direct control. We refer to such systems as partially controlled multi-agent systems, and we investigate how one might influence the behavior of the uncontrolled agents through appropriate design of the controlled agents. In particular, we wish to understand which problems are naturally described in these terms, what methods can be applied to influence the uncontrollable agents, the effectiveness of such methods, and whether similar methods work across different domains. Using a game-theoretic framework, this paper studies the design of partially controlled multi-agent systems in two contexts: in one context, the uncontrollable agents are expected utility maximizers, while in the other they are reinforcement learners. We suggest different techniques for controlling agents' behavior in each domain, assess their success, and examine their relationship.
Introduction
In traditional multi-agent systems (MAS) research, designers often assume either total control over all agents or that all agents will naturally follow a set of "social laws" (like traffic rules). However, in the real world—and in open digital environments—agents are often "uncontrollable." They might be rational utility-maximizers looking for an edge, or simple learners who don't yet know the "right" way to behave.
This 1996 paper by Brafman and Tennenholtz bridges the gap between control theory and AI by introducing Partially Controlled Multi-Agent Systems (PCMAS). In a PCMAS, a designer controls a subset of agents to influence the behavior of the remaining, autonomous agents. The core challenge is vulnerability: if a system relies on everyone following the rules, a single "malicious" or "selfish" agent can exploit the law-abiding ones. This research asks: How can we design our own agents so that even the agents we don't control find it in their best interest to behave?
Methods
The authors tackle this problem through two distinct lenses: game theory for rational agents and Markov Decision Processes (MDPs) for learning agents.
1. Enforcement of Social Laws (Game Theory)
The authors model interactions as iterative games. To keep uncontrollable agents in line, they propose a punishment mechanism. They use "projected games"—transforming a standard game into a zero-sum game—to find the Nash equilibrium strategy that minimizes the maximum payoff a deviating agent can receive. If the controllable agents are "hard-wired" to execute this punishment, the threat becomes common knowledge, making deviation irrational for the uncontrollable agent.
2. Embedded Teaching (Markov Decision Processes)
When the uncontrollable agent is a reinforcement learner (specifically, a Q-learner), the controllable agent acts as a "teacher." The authors frame the teaching process as an MDP. By modeling the student's internal state (their Q-values), the teacher can use value iteration to find an optimal policy that "nudges" the student toward a desired behavior, such as cooperation in a Prisoner's Dilemma.
Key Insights and Results
- The Power of the Unexecuted Threat: In the social law context, a well-designed punishment mechanism is never actually used. Because the rational agent knows they will be punished, they never deviate. The "control" is achieved through the existence of the strategy, not its execution.
- Teaching as Optimization: The paper demonstrates that if you have a model of how an agent learns, you can treat their learning process as a dynamic system to be optimized. In simulations with "Blind Q-learners," the MDP-based optimal teaching policy significantly outperformed naive strategies.
- Tit-For-Tat (TFT) as a Teacher: One of the most interesting findings is that the classic "Tit-For-Tat" strategy is an incredibly effective "teaching" tool for Q-learners. It provides immediate, consistent feedback (reward for cooperation, punishment for defection) that aligns perfectly with how reinforcement learners update their values.
- The "DIF" Metric: The authors proposed a mathematical condition (DIF) to predict whether a Tit-For-Tat strategy will successfully teach a student to cooperate based on the specific payoffs of the game matrix.
- Efficiency Gains: In a block-pushing coordination task, a knowledgeable "teacher" agent was able to coax a learning agent into a high-effort state, resulting in much better system performance than if two learners were paired together.
Limitations and Future Work
The experiments are primarily limited to small 2x2 game matrices, and scaling this to complex, high-dimensional environments remains a major challenge. Furthermore, the "optimal teaching" model assumes the teacher can directly observe the student's internal Q-values. In reality, a teacher would likely have to estimate these from observed actions, necessitating a Partially Observable MDP (POMDP) approach. Future directions include exploring how these techniques work when multiple uncontrollable agents form "teams" to counter the controller.
Summary updated