Optimal Bilevel Lottery Design for Multiagent Systems

Entities in multiagent systems may seek conflicting subobjectives, and this leads to competition between them. To address performance degradation due to competition, we consider a bilevel lottery where a social planner at the high level selects a reward first and, sequentially, a set of players at the low level jointly determine a Nash equilibrium given the reward. The social planner is faced with efficiency losses where a Nash equilibrium of the lottery game may not coincide with the social optimum. We propose an optimal bilevel lottery design problem as finding the least reward and perturbations such that the induced Nash equilibrium produces the socially optimal payoff. We formally characterize the price of anarchy and the behavior of public goods and Nash equilibrium with respect to the reward and perturbations. We relax the optimal bilevel lottery design problem via a convex approximation and identify mild sufficient conditions under which the approximation is exact.