Emmanouil Pountourakis

Ali Khodabakhsh, Ger Yang, Soumya Basu et al.

Distribution network reconfiguration (DNR) is a tool used by operators to balance line load flows and mitigate losses. As distributed generation and flexible load adoption increases, the impact of DNR on the security, efficiency, and reliability of the grid will increase as well. Today, heuristic-based actions like branch exchange are routinely taken, with no theoretical guarantee of their optimality. This paper considers loss minimization via DNR, which changes the on/off status of switches in the network. The goal is to ensure a radial final configuration (called a spanning tree in the algorithms literature) that spans all network buses and connects them to the substation (called the root of the tree) through a single path. We prove that the associated combinatorial optimization problem is strongly NP-hard and thus likely cannot be solved efficiently. We formulate the loss minimization problem as a supermodular function minimization under a single matroid basis constraint, and use existing algorithms to propose a polynomial time local search algorithm for the DNR problem at hand and derive performance bounds. We show that our algorithm is equivalent to the extensively used branch exchange algorithm, for which, to the best of our knowledge, we pioneer in proposing a theoretical performance bound. Finally, we use a 33-bus network to compare our algorithm's performance to several algorithms published in the literature.

Erick Galinkin, Emmanouil Pountourakis, John Carter et al.

In the cybersecurity setting, defenders are often at the mercy of their detection technologies and subject to the information and experiences that individual analysts have. In order to give defenders an advantage, it is important to understand an attacker's motivation and their likely next best action. As a first step in modeling this behavior, we introduce a security game framework that simulates interplay between attackers and defenders in a noisy environment, focusing on the factors that drive decision making for attackers and defenders in the variants of the game with full knowledge and observability, knowledge of the parameters but no observability of the state (``partial knowledge''), and zero knowledge or observability (``zero knowledge''). We demonstrate the importance of making the right assumptions about attackers, given significant differences in outcomes. Furthermore, there is a measurable trade-off between false-positives and true-positives in terms of attacker outcomes, suggesting that a more false-positive prone environment may be acceptable under conditions where true-positives are also higher.

Erick Galinkin, Emmanouil Pountourakis, Spiros Mancoridis

The well-worn George Box aphorism ``all models are wrong, but some are useful'' is particularly salient in the cybersecurity domain, where the assumptions built into a model can have substantial financial or even national security impacts. Computer scientists are often asked to optimize for worst-case outcomes, and since security is largely focused on risk mitigation, preparing for the worst-case scenario appears rational. In this work, we demonstrate that preparing for the worst case rather than the most probable case may yield suboptimal outcomes for learning agents. Through the lens of stochastic Bayesian games, we first explore different attacker knowledge modeling assumptions that impact the usefulness of models to cybersecurity practitioners. By considering different models of attacker knowledge about the state of the game and a defender's hidden information, we find that there is a cost to the defender for optimizing against the worst case.

Yutong Wu, Ali Khodabakhsh, Bo Li et al.

We consider a repeated game where a player self-reports her usage of a service and is charged a payment accordingly by a center. The center observes a partial signal, representing part of the player's true consumption, which is generated from a publicly known distribution. The player can report any value that does not contradict the signal and the center issues a payment based on the reported information. Such problems find application in net metering billing in the electricity market, where a customer's actual consumption of the electricity network is masked and complete verification is impractical. When the underlying true value is relatively constant, we propose a penalty mechanism that elicits truthful self-reports. Namely, besides charging the player the reported value, the mechanism charges a penalty proportional to her inconsistent reports. We show how fear of the uncertainty in the future incentivizes the player to be truthful today. For Bernoulli distributions, we give the complete analysis and optimal strategies given any penalty. Since complete truthfulness is not possible for continuous distributions, we give approximate truthful results by a reduction from Bernoulli distributions. We also extend our mechanism to a multi-player cost sharing setting and give equilibrium results.