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

DOI10.1007/S00224-015-9646-0MaRDI QIDQ503458zbMATH OpenOpenAlexFDO

Authors Elliot Anshelevich, John Postl, Tom Wexler

Publication date 12 January 2017

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

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

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)

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.

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

Cites work

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