Search
Results
-
Stabilization Bounds for Influence Propagation from a Random Initial State
(2021)Leibniz International Proceedings in Informatics (LIPIcs) ~ 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)We study the stabilization time of two common types of influence propagation. In majority processes, nodes in a graph want to switch to the most frequent state in their neighborhood, while in minority processes, nodes want to switch to the least frequent state in their neighborhood. We consider the sequential model of these processes, and assume that every node starts out from a uniform random state. We first show that if nodes change ...Conference Paper -
Network-Aware Strategies in Financial Systems
(2020)Leibniz International Proceedings in Informatics (LIPIcs) ~ 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)We study the incentives of banks in a financial network, where the network consists of debt contracts and credit default swaps (CDSs) between banks. One of the most important questions in such a system is the problem of deciding which of the banks are in default, and how much of their liabilities these banks can pay. We study the payoff and preferences of the banks in the different solutions to this problem. We also introduce a more refined ...Conference Paper -
A General Stabilization Bound for Influence Propagation in Graphs
(2020)Leibniz International Proceedings in Informatics (LIPIcs) ~ 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)We study the stabilization time of a wide class of processes on graphs, in which each node can only switch its state if it is motivated to do so by at least a (1+λ)/2 fraction of its neighbors, for some 0 < λ < 1. Two examples of such processes are well-studied dynamically changing colorings in graphs: in majority processes, nodes switch to the most frequent color in their neighborhood, while in minority processes, nodes switch to the ...Conference Paper