Strategic multiway cut and multicut games

DOI10.1007/s00224-011-9380-1zbMath1260.90046MaRDI QIDQ1946494

Ameya Hate, Bugra Caskurlu, Elliot Anshelevich

Publication date: 15 April 2013

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-011-9380-1

zbMATH Keywords

price of stability; network formation games; multiway cut; approximate Nash equilibrium; multi-cut

Mathematics Subject Classification ID

91A80: Applications of game theory

90B15: Stochastic network models in operations research

Related Items

Resource buying games

Cites Work

• Unnamed Item
• Unnamed Item
• Price of stability in survivable network design
• Exact and approximate equilibria for optimal group network formation
• Network design with weighted players
• Strong equilibrium in cost sharing connection games
• Non-cooperative facility location and covering games
• Non-cooperative tree creation
• Interdependent security
• An improved approximation algorithm of MULTIWAY CUT.
• Potential games
• Strategic cooperation in cost sharing games
• Cut problems in graphs with a budget constraint
• Inoculation strategies for victims of viruses and the sum-of-squares partition problem
• Rounding algorithms for a geometric embedding of minimum multiway cut
• On a network creation game
• The Price of Stability for Network Design with Fair Cost Allocation
• The complexity of pure Nash equilibria
• On nash equilibria for a network creation game
• On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations
• Convergence and Approximation in Potential Games
• Computing and Combinatorics
• The Price of Defense