On October 27, 2020, Jeong Ok Choi (최정옥) from IBS Discrete Mathematics Group / GIST gave a talk on some game-theoretic problems on graphs, more specifically on the contagion game and the network creation game. The title of her talk was “Various game-theoretic models on graphs“.
We introduce some of well-known game-theoretic graph models and related problems.
A contagion game model explains how an innovation diffuses over a given network structure and focuses on finding conditions on which structure an innovation becomes epidemic. Regular infinite graphs are interesting examples to explore. We show that regular infinite trees make an innovation least advantageous to be epidemic considering the whole class of infinite regular graphs.
A network creation game model, on the other hand, tries to explain the dynamics on forming a network structure when each vertex plays independently and selfishly. An important question is how costly a formation can be made without any central coordination, and the concept of Price of Anarchy (PoA) is introduced. In the model originally suggested by Fabrikant et al., PoA measures how bad the forming cost can be at Nash equilibria compared to absolute minimum, and they conjectured that this inefficiency can happen only when some tree structures are formed (Tree Conjecture). We will introduce recent progress on this tree conjecture, remaining open problems, and possible variations.
This talk includes part of joint work with Unjong Yu.
The IBS Discrete Mathematics Group welcomes Prof. Jeong Ok Choi (최정옥) from GIST, Gwangju, Korea. She will visit the IBS Discrete Mathematics Group for 1 year until August 31, 2021 during her sabbatical leave from GIST. She received her Ph.D. from University of Illinois at Urbana-Champaign under the supervision of Prof. Douglas West. She was a visiting assistant professor at Furman University and Trinity College. In 2011, she moved to GIST (Gwangju Institute of Science and Technology) in Gwangju, Korea as an assistant professor and she is currently an associate professor.