FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 |

«Abstract. We consider the solution concept of stochastic stability, and propose the price of stochastic anarchy as an alternative to the price of ...»

-- [ Page 1 ] --

The Price of Stochastic Anarchy

Christine Chung1, Katrina Ligett2, Kirk Pruhs1, and Aaron Roth2


Department of Computer Science

University of Pittsburgh



Department of Computer Science

Carnegie Mellon University


Abstract. We consider the solution concept of stochastic stability, and propose

the price of stochastic anarchy as an alternative to the price of (Nash) anarchy

for quantifying the cost of selfishness and lack of coordination in games. As a solution concept, the Nash equilibrium has disadvantages that the set of stochas- tically stable states of a game avoid: unlike Nash equilibria, stochastically stable states are the result of natural dynamics of computationally bounded and decen- tralized agents, and are resilient to small perturbations from ideal play. The price of stochastic anarchy can be viewed as a smoothed analysis of the price of an- archy, distinguishing equilibria that are resilient to noise from those that are not.

To illustrate the utility of stochastic stability, we study the load balancing game on unrelated machines. This game has an unboundedly large price of Nash anar- chy even when restricted to two players and two machines. We show that in the two player case, the price of stochastic anarchy is 2, and that even in the general case, the price of stochastic anarchy is bounded. We conjecture that the price of stochastic anarchy is O(m), matching the price of strong Nash anarchy without requiring player coordination. We expect that stochastic stability will be useful in understanding the relative stability of Nash equilibria in other games where the worst equilibria seem to be inherently brittle.

Partially supported by an AT&T Labs Graduate Fellowship and an NSF Graduate Research Fellowship.

Supported in part by NSF grants CNS-0325353, CCF-0448196, CCF-0514058 and IIS- 0534531.

1 Introduction Quantifying the price of (Nash) anarchy is one of the major lines of research in algorith- mic game theory. Indeed, one fourth of the authoritative algorithmic game theory text edited by Nisan et al. [20] is wholly dedicated to this topic. But the Nash equilibrium solution concept has been widely criticized [15, 4, 9, 10]. First, it is a solution charac- terization without a road map for how players might arrive at such a solution. Second, at Nash equilibria, players are unrealistically assumed to be perfectly rational, fully informed, and infallible. Third, computing Nash equilibria is PPAD-hard for even 2- player, n-action games [6], and it is therefore considered very unlikely that there exists a polynomial time algorithm to compute a Nash equilibrium even in a centralized manner. Thus, it is unrealistic to assume that selfish agents in general games will converge precisely to the Nash equilibria of the game, or that they will necessarily converge to anything at all. In addition, the price of Nash anarchy metric comes with its own weaknesses; it blindly uses the worst case over all Nash equilibria, despite the fact that some equilibria are more resilient than others to perturbations in play.

Considering these drawbacks, computer scientists have paid relatively little attention to if or how Nash equilibria will in fact be reached, and even less to the question of which Nash equilibria are more likely to be played in the event players do converge to Nash equilibria. To address these issues, we employ the stochastic stability framework from evolutionary game theory to study simple dynamics of computationally efficient, imperfect agents. Rather than defining a-priori states such as Nash equilibria, which might not be reachable by natural dynamics, the stochastic stability framework allows us to define a natural dynamic, and from it derive the stable states. We define the price of stochastic anarchy to be the ratio of the worst stochastically stable solution to the optimal solution. The stochastically stable states of a game may, but do not necessarily, contain all Nash equilibria of the game, and so the price of stochastic anarchy may be strictly better than the price of Nash anarchy. In games for which the stochastically stable states are a subset of the Nash equilibria, studying the ratio of the worst stochastically stable state to the optimal state can be viewed as a smoothed analysis of the price of anarchy, distinguishing Nash equilibria that are brittle to small perturbations in perfect play from those that are resilient to noise.

The evolutionary game theory literature on stochastic stability studies n-player games that are played repeatedly. In each round, each player observes her action and its outcome, and then uses simple rules to select her action for the next round based only on her size-restricted memory of the past rounds. In any round, players have a small probability of deviating from their prescribed decision rules. The state of the game is the contents of the memories of all the players. The stochastically stable states in such a game are the states with non-zero probability in the limit of this random process, as the probability of error approaches zero. The play dynamics we employ in this paper are the imitation dynamics studied by Josephson and Matros [16]. Under these dynamics, each player imitates the strategy that was most successful for her in recent memory.

To illustrate the utility of stochastic stability, we study the price of stochastic anarchy of the unrelated load balancing game [2, 1, 11]. To our knowledge, we are the first to quantify the loss of efficiency in any system when the players are in stochastically stable equilibria. In the load balancing game on unrelated machines, even with only two players and two machines, there are Nash equilibria with arbitrarily high cost, and so the price of Nash anarchy is unbounded. We show that these equilibria are inherently 1 brittle, and that for two players and two machines, the price of stochastic anarchy is

2. This result matches the strong price of anarchy [1] without requiring coordination (at strong Nash equilibria, players have the ability to coordinate by forming coalitions).

We further show that in the general n-player, m-machine game, the price of stochastic anarchy is bounded. More precisely the price of stochastic anarchy is upper bounded by the nmth n-step Fibonacci number. We also show that the price of stochastic anarchy is at least m + 1.

Our work provides new insight into the equilibria of the load balancing game. Unlike some previous work on dynamics for games, our work does not seek to propose practical dynamics with fast convergence; rather, we use simple dynamics as a tool for understanding the inherent relative stability of equilibria. Instead of relying on player coordination to avoid the Nash equilibria with unbounded cost (as is done in the study of strong equilibria), we show that these bad equilibria are inherently unstable in the face of occasional uncoordinated mistakes. We conjecture that the price of stochastic anarchy is closer to the linear lower bound, paralleling the price of strong anarchy.

In light of our results, we believe the techniques in this paper will be useful for understanding the relative stability of Nash equilibria in other games for which the worst equilibria are brittle. Indeed, for a variety of games in the price of anarchy literature, the worst Nash equilibria of the lower bound instances are not stochastically stable.

1.1 Related Work

We give a brief survey of related work in three areas: alternatives to Nash equilibria as a solution concept, stochastic stability, and the unrelated load balancing game.

Recently, several papers have noted that the Nash equilibrium is not always a suitable solution concept for computationally bounded agents playing in a repeated game, and have proposed alternatives. Goemans et al. [15] study players who sequentially play myopic best responses, and quantify the price of sinking that results from such play. Fabrikant and Papadimitriou [9] propose a model in which agents play restricted finite automata. Blum et al. [4, 3] assume only that players’ action histories satisfy a property called no regret, and show that for many games, the resulting social costs are no worse than those guaranteed by price of anarchy results.

Although we believe this to be the first work studying stochastic stability in the computer science literature, computer scientists have recently employed other tools from evolutionary game theory. Fisher and V¨ cking [13] show that under replicator o dynamics in the routing game studied by Roughgarden and Tardos [22], players converge to Nash. Fisher et al. [12] went on to show that using a simultaneous adaptive sampling method, play converges quickly to a Nash equilibrium. For a thorough survey of algorithmic results that have employed or studied other evolutionary game theory techniques and concepts, see Suri [23].

Stochastic stability and its adaptive learning model as studied in this paper were first defined by Foster and Young [14], and differ from the standard game theory solution concept of evolutionarily stable strategies (ESS). ESS are a refinement of Nash equilibria, and so do not always exist, and are not necessarily associated with a natural play dynamic. In contrast, a game always has stochastically stable states that result (by construction) from natural dynamics. In addition, ESS are resilient only to single shocks, whereas stochastically stable states are resilient to persistent noise.

2 Stochastic stability has been widely studied in the economics literature (see, for example, [24, 17, 19, 5, 7, 21, 16]). We discuss in Sect. 2 concepts from this body of literature that are relevant to our results. We recommend Young [25] for an informative and readable introduction to stochastic stability, its adaptive learning model, and some related results. Our work differs from prior work in stochastic stability in that it is the first to quantify the social utility of stochastically stable states, the price of stochastic anarchy.

We also note a connection between the stochastically stable states of the game and the sinks of a game, recently introduced by Goemans et al. as another way of studying the dynamics of computationally bounded agents. In particular, the stochastically stable states of a game under the play dynamics we consider correspond to a subset of the sink equilibria, and so provide a framework for identifying the stable sink equilibria.

In potential games, the stochastically stable states of the play dynamics we consider correspond to a subset of the Nash equilibria, thus providing a method for identifying which of these equilibria are stable.

In this paper, we study the price of stochastic anarchy in load balancing. Even-Dar et al. [1] show that when playing the load balancing game on unrelated machines, any turn-taking improvement dynamics converge to Nash. Andelman et al. [1] observe that the price of Nash anarchy in this game is unbounded and they show that the strong price of anarchy is linear in the number of machines. Fiat et al. [11] tighten their upper bound to match their lower bound at a strong price of anarchy of exactly m.

2 Model and Background We now formalize (from Young [24]) the adaptive play model and the definition of stochastic stability. We then formalize the play dynamics that we consider. We also provide in this section the results from the stochastic stability literature that we will later use for our results.

–  –  –

putationally efficient agents, and so we imagine that each agent has some finite memory of size z, and that after time step t, all players remember a history consisting of a sequence of play profiles ht = (S t−z+1, S t−z+2,..., S t ) ∈ (X)z.

We assume that each player i has some efficiently computable function pi : (X)z × Xi → R that, given a particular history, induces a sampleable probability distribution over actions (for all players i and histories h, a∈Xi pi (h, a) = 1). We write p for i pi. We wish to model imperfect agents who make mistakes, and so we imagine that at time t each player i plays according to pi with probability 1 −, and with probability plays some action in Xi uniformly at random.3 That is, for all players i, for all actions 3 The mistake probabilities need not be uniform random—all that we require is that the distribution has support on all actions in Xi.

–  –  –

We will refer to P 0 as the unperturbed Markov process. Note that for 0, ph,h 0 for every history h and successor h, and that for any two histories h and ˆ h not necessarily a successor of h, there is a series of z histories h1,..., hz such that ˆ h1 = h, hz = h, and for all 1 i ≤ z, hi is a successor of hi−1. Thus there is positive ˆ probability of moving between any h and any h in z steps, and so P is irreducible.

ˆ Similarly, there is a positive probability of moving between any h and any h in z + 1 steps, and so P is aperiodic. Therefore, P has a unique stationary distribution µ.

The stochastically stable states of a particular game and player dynamics are the states with nonzero probability in the limit of the stationary distribution.

Definition 2.2 (Foster and Young [14]). A state h is stochastically stable relative to P if lim →0 µ (h) 0.

Intuitively, we should expect a process P to spend almost all of its time at its stochastically stable states when is small.

When a player i plays at random rather than according to pi, we call this a mistake.

Definition 2.3 (Young [24]). Suppose h = (S t−z+1,..., S t ) is a successor of h. A t t mistake in the transition between h and h is any element Si such that pi (h, Si ) = 0.

Note that mistakes occur with probability ≤.

We can characterize the number of mistakes required to get from one history to another.

Definition 2.4 (Young [24]). For any two states h, h, the resistance r(h, h ) is the minimum total number of mistakes involved in the transition h → h if h is a successor of h. If h is not a successor of h, then r(h, h ) = ∞.

Note that the transitions of zero resistance are exactly those that occur with positive probability in the unperturbed Markov process P 0.

Definition 2.5. We refer to the sinks of P 0 as recurrent classes. In other words, a recurrent class of P 0 is a set of states C ⊆ H such that any state in C is reachable from any other state in C and no state outside C is accessible from any state inside C.

Pages:   || 2 | 3 |

Similar works:

«Study of the Effect of a Flu Pandemic on Insured Mortality Using the Delphi Method Project Oversight Group Tom Edwalds, Chair Scott Cochran Robert Gleeson Max Rudolph Bill Sayre Jan Schuh, SOA staff Ronora Stryker, SOA staff, Principal Investigator May 2007 Please direct questions and comments to: Ronora Stryker SOA Research Actuary rstryker@soa.org ©2007 Society of Actuaries TABLE OF CONTENTS Introduction 1 Summary of Individual Responses 2 Question 1 2 Question 2 4 Question 3 5 Question 4 6...»

«Community Mining from Multi-relational Networks⋆ Deng Cai1, Zheng Shao1, Xiaofei He2, Xifeng Yan1, and Jiawei Han1 1 Computer Science Department, University of Illinois at Urbana Champaign (dengcai2, zshao1, xyan, hanj)@cs.uiuc.edu 2 Computer Science Department, University of Chicago xiaofei@cs.uchicago.edu Abstract. Social network analysis has attracted much attention in recent years. Community mining is one of the major directions in social network analysis. Most of the existing methods...»

«INTRODUCTION Dear parents, We at Alger Pediatrics are pleased to be entrusted with the care of your children. As nurses and physicians, we wish to assist you in maintaining the wellness of your family through regular check-ups and immunizations. However, illnesses and mishaps are inevitable. You will readily manage most of these events in the home setting. We have developed this book to help you with these problems. When an event occurs, we ask that you refer to this booklet. We are more than...»

«JESUS: MAGICIAN OR MIRACLE WORKER? BY DONALD HOWARD BROMLEY 1124 GRANT STREET YPSILANTI, MI 48197 don@annarborvineyard.org A THESIS PRESENTED TO THE FACULTY OF ASHLAND THEOLOGICAL SEMINARY IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF ARTS AUGUST 28, 2004 Accepted by the faculty of Ashland Theological Seminary Ashland, Ohio In partial fulfillment of the requirements For the degree of Master of Arts Director of Thesis _ Academic Dean ii INTRODUCTION Our understanding of...»

«Best Practices: Thames Water Adopts BPMS Solution to Streamline Its Customer Services, with Wipro as Systems Integrator IDC Energy Insights: European Utility IT Strategies BEST PRACTICES #EIOS05T www.idc -ei.com Roberta Bigliani Daniella Muallem IDC ENERGY INSIGHTS OPINION F.508.988.7881 This IDC Energy Insights report details Thames Water's journey to implement an advanced business process management system in its Customer Services business unit, for eight months from 2010–2011. This...»

«MODELING PACKAGED HEAT PUMPS IN A QUASI-STEADY STATE ENERGY SIMULATION PROGRAM By TANG, CHIH CHIEN Bachelor of Science Oklahoma State University, Stillwater, Oklahoma 2003 Submitted to the Faculty of the Graduate College of the Oklahoma State University in partial fulfillment of the requirements for the Degree of MASTER OF SCIENCE May, 2005 MODELING PACKAGED HEAT PUMPS IN A QUASI-STEADY STATE ENERGY SIMULATION PROGRAM Thesis Approved: Dr. Daniel Fisher Thesis Adviser Dr. Jeffrey Spitler Dr. Ron...»

«For Accepted Students Handbook Brown Environmental Leadership Lab: Alaska 1 BROWN UNIVERSITY PRE-COLLEGE PROGRAMS BELL: Alaska | July 31 – August 13, 2016 Table of Contents I. A Note to Parents, Guardians, and Students II. Next Steps for BELL: Alaska III. What to Bring IV. Arrival and Departure Day Details V. Program Information (FAQ) VI. Policies I. A Note to Parents, Guardians, and Students Congratulations! We are looking forward to your participation in this unique and engaging...»

«MEMORIAL DISCOURSE Trinity College Dublin Trinity Monday 13th June 1949 Jospeh Sheridan Le Fanu (1814-1873) By T. S. C. Dagg, M.A. Joseph Sheridan Le Fanu, whose memory we honour to-day, was described on his father’s side from a distinguished and ennobled Huguenot family, the Le Fanus of Caen, in Normandy, who, on the revocation of the Edict of Nantes, had been deprived of their estates and had settled in England. It is estimated that 600,000 Huguenots fled from France to escape the...»

«Material Safety Data Sheet Bromine MSDS Section 1: Chemical Product and Company Identification Product Name: Bromine Contact Information: Sciencelab.com, Inc. Catalog Codes: SLB4777 14025 Smith Rd. Houston, Texas 77396 CAS#: 7726-95-6 US Sales: 1-800-901-7247 RTECS: EF9100000 International Sales: 1-281-441-4400 TSCA: TSCA 8(b) inventory: Bromine Order Online: ScienceLab.com CI#: Not available. CHEMTREC (24HR Emergency Telephone), call: 1-800-424-9300 Synonym: International CHEMTREC, call:...»

«Minion Documentation Release 0.4 Mozilla September 22, 2015 Contents 1 Installing Minion 3 1.1 Prerequisites............................................... 3 1.2 Install using Minion VM......................................... 3 1.3 Manual Installation............................................ 4 2 Configuring Minion 9 2.1 Configure Minion Frontend..........»

«Dystopian Love: A Look at Romance in Young Adult Dystopian Novels An Honors Thesis (HONR 499) by Kaleah Wolf Thesis Advisor Susanna Be~~?u.-­ ~l'~~ Ball State University Muncie, Indiana May 2013 Expected Date of Graduation May 4, 2013 r C I' Uhde y3r c, c:! 1 h J L 2 ~J1gq, ). J.j I~ Abstract n J',. 1_. yv.-,.­ Research in young adult literature lacks a specific focus on romance within the increasingly popular genre of young adult dystopian novels. This paper provides an analysis of four...»

«Distribution Agreement In presenting this thesis or dissertation as a partial fulfillment of the requirements for an advanced degree from Emory University, I hereby grant to Emory University and its agents the non-exclusive license to archive, make accessible, and display my thesis or dissertation in whole or in part in all forms of media, now or hereafter known, including display on the world wide web. I understand that I may select some access restrictions as part of the online submission of...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.