TY - GEN
T1 - Privacy-preserving public information for sequential games
AU - Blum, Avrim
AU - Morgensterny, Jamie
AU - Sharma, Ankit
AU - Smith, Adam
PY - 2015/1/11
Y1 - 2015/1/11
N2 - 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 confidentiality 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.
AB - 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 confidentiality 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.
UR - http://www.scopus.com/inward/record.url?scp=84922115813&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84922115813&partnerID=8YFLogxK
U2 - 10.1145/2688073.2688100
DO - 10.1145/2688073.2688100
M3 - Conference contribution
AN - SCOPUS:84922115813
T3 - ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science
SP - 173
EP - 180
BT - ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science
PB - Association for Computing Machinery, Inc
T2 - 6th Conference on Innovations in Theoretical Computer Science, ITCS 2015
Y2 - 11 January 2015 through 13 January 2015
ER -