Privacy-Preserving Public Information for Sequential Games

In settings with incomplete information, players can find it difficult to coordinate to find states with good social welfare. For instance, one of the main reasons behind the recent financial crisis was found to be the lack of market transparency, which made it difficult for financial firms to accurately measure the risks and returns of their investments. Although regulators may have access to firms' investment decisions, directly reporting all firms' actions raises confiden- tiality concerns for both individuals and institutions. The natural question, therefore, is whether it is possible for the regulatory agencies to publish some information that, on one hand, helps the financial firms understand the risks of their investments better, and, at the same time, preserves the privacy of their investment decisions. More generally, when can the publication of privacy-preserving information about the state of the game improve overall outcomes such as social welfare? In this paper, we explore this question in a sequential resource-sharing game where the value gained by a player on choosing a resource depends on the number of other players who have chosen that resource in the past. Without any knowledge of the actions of the past players, the social welfare attained in this game can be arbitrarily bad. We show, however, that it is possible for the players to achieve good social welfare with the help of privacy-preserving, publicly-announced information. We model the behavior of players in this imperfect information setting in two ways -- greedy and undominated strategic behaviours, and we prove guarantees about the social welfare that certain kinds of privacy-preserving information can help attain. To achieve the social welfare guarantees, we design a counter with improved privacy guarantees under continual observation. In addition to the resource-sharing game, we study the main question for other games including sequential versions of the cut, machine-scheduling and cost-sharing games, and games where the value attained by a player on a particular action is not only a function of the actions of the past players but also of the actions of the future players.