Are Large Random Graphs Always Safe to Hide?
By: Sourav Chakraborty, Sujata Ghosh, Smiha Samanta
Potential Business Impact:
Predicts game winners using math logic.
We discuss winning possibilities of players in various variants of cops and robber game played on large random graphs, a testbed for various kinds of network queries, search problems in particular. We explore the use of logic frameworks to investigate such results; in particular, we show that whenever a winning condition for either player can be expressed as a certain kind of formula in first-order logic, that player almost always wins. In the process, we obtain more insight into the logic-game connection from the zero-one law perspective.
Similar Papers
Reasoning under uncertainty in the game of Cops and Robbers
Logic in Computer Science
Tracks how players learn in guessing games.
A Game-Theoretic Framework for Network Formation in Large Populations
Optimization and Control
Helps people build better online groups.
Attacking and Securing Community Detection: A Game-Theoretic Framework
Machine Learning (CS)
Hides people in online groups from trackers.