The Snowball Effect of Uncertainty
Feb 22, 2012
ABSTRACT:
Uncertainty is present in different guises in many settings, in particular in environments with strategic interactions. However, most game-theoretic models assume that players can accurately observe interactions and their own costs. We quantify the effect on social costs of two different types of uncertainty: adversarial perturbations of small magnitude to costs (effect called the Price of Uncertainty (PoU)) and the presence of several players with Byzantine, i.e. arbitrary, behavior (effect we call the Price of Byzantine behavior (PoB)).
In this talk, we provide lower and upper bounds on the PoU and PoB in two well-studied classes of potential games: consensus games and set-covering games. For consensus games, we are able to prove tight bounds on the PoB for any number of Byzantine players.
Joint work with Nina Balcan and Florin Constantin.
Uncertainty is present in different guises in many settings, in particular in environments with strategic interactions. However, most game-theoretic models assume that players can accurately observe interactions and their own costs. We quantify the effect on social costs of two different types of uncertainty: adversarial perturbations of small magnitude to costs (effect called the Price of Uncertainty (PoU)) and the presence of several players with Byzantine, i.e. arbitrary, behavior (effect we call the Price of Byzantine behavior (PoB)).
In this talk, we provide lower and upper bounds on the PoU and PoB in two well-studied classes of potential games: consensus games and set-covering games. For consensus games, we are able to prove tight bounds on the PoB for any number of Byzantine players.
Joint work with Nina Balcan and Florin Constantin.