I am a third-year Ph.D. student in Computational Science and Engineering at MIT, advised by Saurabh Amin. My research interests are in the applications of optimization methods and game-theoretic tools for assessing and improving the survivability of infrastructure networks to disruptions. Currently, we are working on modeling a class of cyber-physical reliability and security problems in infrastructure networks that can result in component disruptions and loss of network functionality.
I received my B.S. in Fundamental and Applied Mathematics from the University of Paris XI-Sud, my B.Eng. and M.Eng. from the École Centrale Paris, and my M.S. in Computation for Design and Optimization from MIT. I expect to graduate from my Ph.D. in October 2018.
During the summer of 2016, I worked as a research scientist intern at Amazon.com (Seattle) in the Supply Chain Optimization Technologies team. Using Machine-Learning techniques, I worked on predicting the fulfillment cost and developing a prototype to grant a fast and accurate access to future shipping cost estimates.
This article considers a resource allocation problem for monitoring infrastructure networks facing strategic disruptions. The network operator is interested in determining the minimum number of sensors and a sensing strategy, to ensure a desired detection performance against simultaneous failures induced by a resource-constrained attacker. To address this problem, we formulate a mathematical program with constraints involving the mixed strategy Nash equilibria of an operator-attacker game. The set of player strategies in this game are determined by the network structure and players' resources, and grow combinatorially with the network size. Thus, well-known algorithms for computing equilibria in strategic games cannot be used to evaluate the constraints in our problem. We present a solution approach based on two combinatorial optimization problems, formulated as minimum set cover and maximum set packing problems. By using a combination of game-theoretic and combinatorial arguments, we show that the resulting solution has guarantees on the detection performance and admits a small optimality gap in practical settings. Importantly, this approach is scalable to large-scale networks. We also identify a sufficient condition on the network structure for this solution to be optimal. Finally, we demonstrate the scalability and optimality guarantee of our approach using a set of benchmark water networks.
We consider the problem of detecting security failures caused by a resource-constrained attacker using randomized sensing strategies. We propose a game-theoretic model in which the objective of the attacker (resp. defender) is to maximize the number of undetected attacks (resp. detections) on the network. Our game is strategically equivalent to a zero-sum game. Thus, the Nash Equilibria (NE) solution can be found by solving two linear programming (LP) problems. Still, characterization of equilibrium strategies is not tractable for large-scale networks. We assume that the defender's (resp. attacker's) detection (resp. attack) budget is limited relative to the size of the network. Under this assumption, we provide structural results on the equilibrium payoffs based on the players' resources and the size of the minimum set covers. We show that an equilibrium strategy of the defender is to choose a randomized sensing strategy that spans a minimum set cover. This result significantly improves the tractability of NE computation, and provides some practical insights on network sensing in adversarial environments.
Network optimization has widely been studied in the literature for a variety of design and operational problems. This has resulted in the development of computational algorithms for the study of classical operations research problems such as the maximum flow problem, the shortest path problem, and the network interdiction problem. However, in environments where network components are subject to adversarial failures, the network operator needs to strategically allocate at least some of her resources (e.g., link capacities, network flows, etc.) while accounting for the presence of a strategic adversary. This motivates the study of network security games. This thesis considers a class of network security games on flow networks, and focuses on utilizing well-known results in network optimization toward the characterization of Nash equilibria of this class of games.
Specifically, we consider a 2-player strategic game for network routing under link disruptions. Player 1 (defender) routes flow through a network to maximize her value of effective flow while facing transportation costs. Player 2 (attacker) simultaneously disrupts one or more links to maximize her value of lost flow but also faces cost of disrupting links. Linear programming duality and the Max-Flow Min-Cut Theorem are applied to obtain properties that are satisfied in any Nash equilibrium. Using graph theoretic arguments, we give a characterization of the support of the equilibrium strategies. Finally, we study the conditions under which these results extend to a revised version of the game where both players face budget constraints. Thus, our contribution can be viewed as a generalization of the classical minimum cost maximum flow problem and the minimum cut problem to adversarial environments.
This article considers a two-player strategic game for network routing under link disruptions. Player 1 (defender) routes flow through a network to maximize her value of effective flow while facing transportation costs. Player 2 (attacker) simultaneously disrupts one or more links to maximize her value of lost flow but also faces cost of disrupting links. Linear programming duality in zero-sum games and the Max-Flow Min-Cut Theorem are applied to obtain properties that are satisfied in any Nash equilibrium. A characterization of the support of the equilibrium strategies is provided using graph-theoretic arguments. Finally, conditions under which these results extend to budget-constrained environments are also studied. These results extend the classical minimum cost maximum flow problem and the minimum cut problem to a class of security games on flow networks.
This paper considers a 2-player strategic game for network routing under link disruptions. Player 1 (defender) routes flow through a network to maximize her value of effective flow while facing transportation costs. Player 2 (attacker) simultaneously disrupts one or more links to maximize her value of lost flow but also faces cost of disrupting links. This game is strategically equivalent to a zero-sum game. Linear programming duality and the max-flow min-cut theorem are applied to obtain properties that are satisfied in any mixed Nash equilibrium. In any equilibrium, both players achieve identical payoffs. While the defender's expected transportation cost decreases in attacker's marginal value of lost flow, the attacker's expected cost of attack increases in defender's marginal value of effective flow. Interestingly, the expected amount of effective flow decreases in both these parameters. These results can be viewed as a generalization of the classical max-flow with minimum transportation cost problem to adversarial environments.