Assignment games with conflicts: robust price of anarchy and convergence results via semi-smoothness

DOI10.1007/S00224-015-9646-0zbMATH Open1354.91011arXiv1304.5149OpenAlexW1245519188MaRDI QIDQ503458FDOQ503458

Authors: Elliot Anshelevich, John Postl, Tom Wexler 

Publication date: 12 January 2017

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

Abstract: We study assignment games in which jobs select machines, and in which certain pairs of jobs may conflict, which is to say they may incur an additional cost when they are both assigned to the same machine, beyond that associated with the increase in load. Questions regarding such interactions apply beyond allocating jobs to machines: when people in a social network choose to align themselves with a group or party, they typically do so based upon not only the inherent quality of that group, but also who amongst their friends (or enemies) choose that group as well. We show how semi-smoothness, a recently introduced generalization of smoothness, is necessary to find tight or near-tight bounds on the price of total anarchy, and thus on the quality of correlated and Nash equilibria, for several natural job-assignment games with interacting jobs. For most cases, our bounds on the price of total anarchy are either exactly 2 or approach 2. We also prove new convergence results implied by semi-smoothness for our games. Finally we consider coalitional deviations, and prove results about the existence and quality of Strong equilibrium.

Full work available at URL: https://arxiv.org/abs/1304.5149

Recommendations

• Intrinsic robustness of the price of anarchy
• Strong price of anarchy
• Intrinsic robustness of the price of anarchy
• Strong price of anarchy
• Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy

zbMATH Keywords

price of anarchycongestion gamesgroup formationcut gamesgames in networkssmooth games

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Applications of game theory (91A80) Noncooperative games (91A10) Games involving graphs (91A43)

Cites Work

• Algorithmic Game Theory
• Worst-case equilibria
• Potential games
• Title not available (Why is that?)
• Selfish load balancing
• The price of anarchy of finite congestion games
• Tight Bounds for Selfish and Greedy Load Balancing
• Intrinsic robustness of the price of anarchy
• On best response dynamics in weighted congestion games with polynomial delays
• Strong price of anarchy, utility games and coalitional dynamics
• Cascading behavior in networks: algorithmic and economic issues
• Bounding the inefficiency of outcomes in generalized second price auctions
• Local smoothness and the price of anarchy in atomic splittable congestion games
• Title not available (Why is that?)
• Contagion
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Selfish load balancing and atomic congestion games
• The Speed of Convergence in Congestion Games under Best-Response Dynamics
• Convergence and Approximation in Potential Games
• The max \(k\)-cut game and its strong equilibria

Cited In (2)

• On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games
• The price of anarchy for utilitarian scheduling games on related machines

This page was built for publication: Assignment games with conflicts: robust price of anarchy and convergence results via semi-smoothness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q503458)