Boolean Games: Inferring Agents' Goals Using Taxation Queries

In Boolean games, each agent controls a set of Boolean variables and has a goal represented by a propositional formula. We initiate a study of inference in Boolean games assuming the presence of a Principal who has the ability to control the agents and impose taxation schemes. Previous work used taxation schemes to guide a game towards certain equilibria. We show how taxation schemes can also be used to infer agents' goals. In our formulation, agents' goals are assumed to be unknown and the objective of the Principal is to infer the goals of all the agents using appropriate taxation queries. Using an undirected graph (called the goal overlap graph) associated with a Boolean game, we establish necessary and sufficient conditions for the existence of a Nash equilibrium for any taxation query. Using these conditions, we develop an algorithm that uses taxation queries to learn agents' goals. Using a valid node coloring of the goal overlap graph, we show that goals of many agents can be inferred simultaneously. We also present more efficient (in terms of number of queries) goal inference algorithms for two special classes of Boolean functions, namely threshold and symmetric functions.