Interdependent Security Games and NetworksGame Theory: Whirlwind ReviewGames on NetworksThe Airline Security ProblemThe IDS Model [Kunreuther and Heal]Abstract Features of the GameOther IDS SettingsAn Experimental Study [Kearns and Ortiz]Network VisualizationSlide 10Slide 11Slide 12Some Obvious QuestionsInterdependent Security Gamesand NetworksNetworked LifeCSE 112Spring 2006Prof. Michael KearnsGame Theory: Whirlwind Review•Matrix (normal form) games, mixed strategies, Nash equil.–the basic objects of vanilla game theory–the power of private randomization•Repeated matrix games–the power of shared history–new equilibria may result•Correlated equilibria–the power of shared randomization–new equilibria may result–the result of adaptation and learning by playersGames on Networks•Matrix game “networks”•Vertices are the players•Keeping the normal (tabular) form–is expensive (exponential in N)–misses the point•Most strategic/economic settings have much more structure –asymmetry in connections–local and global structure–special properties of payoffs•Two broad types of structure:–special structure of the network•e.g. geographically local connections–special global payoff functions•e.g. financial marketsThe Airline Security Problem•Imagine an expensive new bomb-screening technology–large cost C to invest in new technology–cost of a mid-air explosion: L >> C•There are two sources of explosion risk to an airline:–risk from directly checked baggage: new technology can reduce this–risk from transferred baggage: new technology does nothing–transferred baggage not re-screened (except for El Al airlines)•This is a “game”…–each player (airline) must choose between I(nvesting) or N(ot)•partial investment ~ mixed strategy–(negative) payoff to player (cost of action) depends on all others•…on a network–the network of transfers between air carriers–not the complete graph–best thought of as a weighted networkThe IDS Model[Kunreuther and Heal]•Let x_i be the fraction of the investment C airline i makes•Define the cost of this decision x_i as: - (x_i C + (1 – x_i)p_i L + S_i L)•S_i: probability of “catching” a bomb from someone else–a straightforward function of all the “neighboring” airlines j–incorporates both their investment decision j and their probability or rate of transfer to airline i•Analysis of terms:–x_i C = C at x_i = 1 (full investment); = 0 at x_i = 0 (no investment)–(1-x_i)p_i L = 0 at full investment; = p_i L at no investment–S_i L: has no dependence on x_i•What are the Nash equilibria?–fully connected network with uniform transfer rates: full investment or no investment by all parties!Abstract Features of the Game•Direct and indirect sources of risk•Investment reduces/eliminates direct risk only•Risk is of a catastrophic event (L >> C)–can effectively occur only once•May only have incentive to invest if enough others do!•Note: much more involved network interaction than info transmittal, message forwarding, search, etc.Other IDS Settings•Fire prevention–catastrophic event: destruction of condo–investment decision: fire sprinkler in unit•Corporate malfeasance (Arthur Anderson)–catastrophic event: bankruptcy–“investment” decision: risk management/ethics practice•Computer security–catastrophic event: erasure of shared disk–investment decision: upgrade of anti-virus software•Vaccination–catastrophic event: contraction of disease–investment decision: vaccination–incentives are reversed in this settingAn Experimental Study[Kearns and Ortiz]•Data:–35K N. American civilian flight itineraries reserved on 8/26/02–each indicates full itinerary: airports, carriers, flight numbers–assume all direct risk probabilities p_i are small and equal–carrier-to-carrier xfer rates used for risk xfer probabilities•The simulation:–carrier i begins at random investment level x_i in [0,1]–at each time step, for every carrier i:•carrier i computes costs of full and no investment unilaterally•adjusts investment level x_i in direction of improvement (gradient)Network VisualizationAirport to airportCarrier to carrierleast busymost busylevel of investmentsimulationtimeThe Price of Anarchy is HighTipping and CascadingNecessary Conditions for TippingSome Obvious Questions•Does the carrier transfer network obey the “universals” of social network theory?–small diameter, local clustering, heavy tails, etc.•I don’t know, but probably.•What generally happens with IDS games on such networks?–Do “connectors” invest or not invest at equilibrium?–Do such networks lead to investing or non-investing equilibria?–Does subsidization of a couple of connectors make everyone invest?•I don’t know… but it’s just a matter of time.•For standard economic market models, we’ll give