Don’t Let the Bad Guys Win: 2 Problems in Multi Agent Systems
In this talk I will present two problems which we modeled using disciplines from game-theory and social choice, and then analyzed their computational aspects. In the first part of the talk, I will deal with the problem of security of flows on networks. In many exciting multi-agent applications - including future battlefields, law enforcement and commerce - agents must communicate in inherently or potentially hostile environments in which an adversary disrupts or intercepts the communication between agents for malicious purposes. Intelligent agents must balance network performance with possible harm suffered from an adversary's attack, while accounting for the broadcast nature of their communication and the heterogeneous vulnerabilities of communication links. I will show our network-flow-based approach for compactly representing this problem, and the polynomial time algorithms that we provided to find the equilibrium. In addition, I will present the definition of the inducible Stackelberg equilibrium, which was motivated by our settings.
In the second part of my talk I will present our computational complexity results regarding the model of "safe manipulation", which is a new model of coalitional manipulation that was recently put forward by Slinko and White. I will also describe two ways to extend the original notion of safe-manipulation, in order to capture some of the scenarios that may occur in practice.