Sanaz Rabinia

Ali Mohammadi, Sanaz Rabinia

Game theory is a powerful analytical tool for modeling decision makers strategies, behaviors and interactions. Act and decisions of a decision maker can benefit or negatively impact other decision makers interests. Game theory has been broadly used in economics, politics and engineering field. For example, game theory can model decision making procedure of different companies competing with each other to maximize their profit. Here, we present a brief introduction of game theory formulation and its applications. The focus of the chapter is non-cooperative Stackelberg game model and its applications in solving power system related problems. These applications include but not limited to; expanding transmission network, improving power system reliability, containing market power in the electricity market, solving power system dispatch, executing demand response and allocating resource in a wireless system. Finally, this chapter elaborates on solving a game theory problem through an example.

Akshar Chavan, Sanaz Rabinia, Daniel Grosu et al.

Reducing the running time of graph algorithms is vital for tackling real-world problems such as shortest paths and matching in large-scale graphs, where path information plays a crucial role. To address this critical challenge, this paper introduces a graph restructuring algorithm that identifies bipartite cliques and replaces them with tripartite graphs. This restructuring leads to fewer edges while preserving complete graph path information, enabling the direct application of algorithms like matching and all-pairs shortest paths to achieve significant runtime reductions, especially for large, dense graphs. The running time of the proposed algorithm for a graph $G(V,E)$, with $|V| = n$ and $|E| = m$ is~$O(mn^δ)$, which is better than $O(mn^δ\log^2 n)$, the running time of the best existing algorithm for speeding-up other graph algorithms (the Feder-Motwani (\textsf{FM}) algorithm), where $0 \leq δ\leq 1$. Both the \textsf{FM} algorithm and the proposed algorithm are originally formulated for bipartite graphs, but can also be applied to general directed or undirected graphs. Our extensive experimental analysis demonstrates that the proposed algorithm achieves up to 21.26\% higher reduction in the number of edges and runs up to 105.18$\times$ faster than the \textsf{FM} algorithm. On large synthetic graphs with up to 1.05 billion edges, it attains a reduction in the number of edges of up to 74.36\%. On real-world graphs, it achieves a reduction in the number of edges by up to 46.8\%. Furthermore, when used as a preprocessing step, our approach yields up to a 2.07$\times$ speedup for the matching algorithms on large synthetic graphs, and up to a 1.74$\times$ speedup for the All-Pairs Shortest Path algorithms on real-world graphs, when compared to using the given graph as input.