cut
Department of Computer and Information Science
作文话题University of Pennsylvania
1Introduction
Inspired by events ranging from9/11to the collap of the accountingfirm Arthur Ander-n,economists Kunreuther and Heal[5]recently introduced an interesting game-theoretic model for problems of interdependent curity(IDS),in which a large number of players must make individual investment decisions related to curity—whether physical,finan-cial,medical,or some other type—but in which the ultimate safety of each participant may depend in a complex way on the actions of the entire population.A simple example is the choice of whether to install afire sprinkler system in an individual condominium in a large building.While such a system might greatly reduce the chances of the owner’s prop-erty being destroyed by afire originating within their own unit,it might do little or nothing to reduce the chances of damage caud byfires originating in other units(since sprinklers can usually only dou smallfires early).If“enough”other unit owners have not made the investment in sprinklers,it may be not cost-effective for any individual to do so. Kunreuther and Heal[5]obrve that a great variety of natural problems share this basic in-terdependent structure,including investment decisions in airline ba
ggage curity(in which investments in new screening procedures may reduce the risk of directly checking suspi-cious cargo,but nearly all airlines accept transferred bags with no additional screening1); risk management in corporations(in which individual business units have an incentive to avoid high-risk or illegal activities only if enough other units are similarly well-behaved); vaccination against infectious dia(where the fraction of the population choosing vac-cination determines the need for or effectiveness of vaccination);certain problems in com-puter network curity;and many others.All the problems share the following important properties:
There is a“bad event”(condominiumfire,airline explosion,corporate bankruptcy,
infection,etc.)to be avoided,and the opportunity to reduce the risk of it via some
kind of investment.
The cost-effectiveness of the curity investment for the individual is a function
of the investment decisions made by the others in the population.
The original work by Kunreuther and Heal[5]propod a parametric game-theoretic model for such problems,but left the interesting question of computing the equilibria of model largely untouched.In th
is paper we examine such computational issues.
2Definitions
In an IDS game,each player must decide whether or not to invest in some abstract curity mechanism or procedure that can reduce their risk of experiencing some abstract bad event. The cost of the investment to is,while the cost of experiencing the bad event is; the interesting ca is when.Thus,player has two choices for his action: means the player makes the investment,while means he does not.It turns out that the important parameter is the ratio of the two costs,so we define.
For each player,there is a parameter,which is the probability that player will expe-rience the bad event due to internal contamination if—for example,this is the probability of the condominium owner’s unit burning down due to afire originating in his own unit.We can also think of as a measure of the direct risk to player—as we shall e,it is that portion of his risk under his direct control.
To model sources of indirect risk,for each pair of players,let be the proba-bility that player experiences the bad event as a result of a transfer from player—for example,this is the probability that the condominium of player burns down due to afire originating in the unit of player.Note the impli
cit constraint that.
An IDS game is thus given by the parameters,,,for each player,and the expected cost to player under the model is defined to be
(1)
Let us take a moment to par and motivate this definition,which is the sum of three terms. Thefirst term reprents the amount invested in curity by player,and is either0(if )or(if).The cond term is the expected cost to due to internal or direct risk of the bad event,and is either(which is the expected cost of internally generated bad events in the ca),or is0(in the ca of investment,).Thus,there is a natural tension between thefirst two terms:players can either invest in curity,which costs money but reduces risk,or gamble by not investing.Note that here we have assumed that curity investment perfectly eradicates direct risk(but not indirect risk);generalizations are obviously possible,but have no qualitative effect on the model.
It is the third term of Equation(1)that express the interdependent nature of the problem. This term encodes the assumption that there are sources of risk to player—his own internal risk,and a specific transfer risk from each of the other players—and that all the sources are statistically independent.
The prefactor is simply the probability that player does not experience the bad event due to direct risk.The bracketed expression is the probability that player experiences a bad event due to transferred risk: each factor in the product is the probability that a bad event does not befall player due to player(and the product express the assumption that all of the possible transfer events are independent).Thus1minus this product is the probability of transferred contamination,and of cour the product of the various risk probabilities is also multiplied by the cost of the bad event.
The model parameters and Equation(1)define a compact reprentation for a multiplayer game in which each player’s goal is to minimize their cost.Our interest is in the efficient computation of Nash equilibria(NE)of such games2.
word up3Algorithms
We begin with the obrvation that it is in fact computationally straightforward tofind a
single pure NE of any IDS game.To e this,it is easily verified that if there are any con-
ditions under which player prefers investing()to not investing()according to the expected costs given by Equation(1),then it is certainly the ca that will prefer to
invest when all the other players are doing so.Similarly,the most favorable condi-
tions for not investing occur when no other players are investing.Thus,tofind a pure NE, we canfirst check whether either all players investing,or no players investing,forms a NE. If so,we arefinished.If neither of the extremes are a NE,then there are some players for whom investing or not investing is a dominant strategy(a best respon independent of the behavior of others).If we then“clamp”such players to their dominant strategies,we obtain a new IDS game with fewer players(only tho without dominant strategies in the original game),and can again e if this modified game has any players with dominant strategies. At each stage of this iterative process we maintain the invariant that clamped players are playing a best respon to any possible tting of the unclamped players.
Theorem1A pure NE for any-player IDS game can be computed in time.
scrambleIn a n,the argument above demonstrates the fact that in most“interesting”IDS games (tho in which each player is a true participant,and can have their behavior swayed by that of the overall population),there are two trivial pure NE(all invest and none invest). However,we are also interested infinding NE in which some players are choosing to invest and others not to(even though no player has a dominant strategy).A primary motivation forfinding such NE is the appearance of such behavio
r in“real world”IDS ttings,where individual parties do truly em to make differing curity investment choices(such as with sprinkler systems in large apartment buildings).Conceptually,the most straightforward way to discover such NE would be to compute all NE of the IDS game.As we shall eventually e,for computational efficiency such a demand requires restrictions on the parameters of the game,one natural example of which we now investigate.
3.1Uniform Transfer IDS Games
A uniform transfer IDS game is one in which the transfer risks emanating from a given player are independent of the transfer destination.Thus,for any player,we have that for all,for some value.Note that the risk level prented to the population by different players may still vary with—but each player spreads their risk indiscriminately across the rest of the population.An example would be the assumption that each airline transferred bags with equal probability to all other airlines.
In this ction,we describe two different approaches for computing NE in uniform trans-fer IDS games.Thefirst approach views a uniform transfer IDS game as a special type of summarization game,a class recently investigated by Kearns and Mansour[4].In an -player summarization game,the payoff of each player is a function of the actions
of all the other players,but only through the value of a global and common real-valued summarization function.The main result of[4]gives an algorithm for computing approximate NE of summarization games,in which the quality of the approximation de-pends on the influence of the summarization function.A well-known notion in discrete functional analysis,the influence of is the maximum change in that any input(player) can unilaterally cau.(See[4]for detailed definitions.)
It can be shown(details omitted)that any uniform transfer IDS game is in fact a summa-
rization game under the choice
(2) and that the influence of this function is bounded by the largest.We note that in many natural uniform transfer IDS ttings,we expect this influence to diminish like with the number of players.(This would be the ca if the risk transfer comes about through physical objects like airline baggage,where each transfer event can have only a single destination.)Combined with the results of[4],the above discussion can be shown to yield the following result.
Theorem2There is an algorithm that takes as input any uniform transfer IDS game,and any,and computes an-NE,where and .The running time of the algorithm is polynomial in,,and.
We note that in typical IDS ttings we expect both the and to be small(the bad event is relatively rare,regardless of its source),in which ca may be viewed as a constant. Furthermore,it can be verified that this algorithm will in fact be able to compute approxi-mate NE in which some players choo to invest and others not to,even in the abnce of any dominant strategies.
While viewing uniform transfer IDS games as bounded influence summarization games relates them to a standard class and yields a natural approximation algorithm,an improved approach is possible.We now prent an algorithm(Algorithm UniformTransferIDSNash in Figure3.1)that efficiently computes all NE for uniform transfer IDS games.The algo-rithm(indeed,even the reprentation of certain NE)requires the ability to compute th roots.
We may assume without loss of generality that for all players,,and. For a joint mixed strategy vector,denote the t of(fully)investing players as the t of(fully)non-investing players as and the t of partially investing players as
The correctness of algorithm UniformTransferIDSNash follows immediately from two lemmas that we now state without proof due to space considerations.Thefirst lemma is a generalization of Proposition2of[2],and esntially establishes that the values and determine a two-level ordering of th
e players’willingness to invest.This dou-ble ordering generates the outer and inner loops of algorithm UniformTransferIDSNash. Note that a player with small has a combination of relatively low cost of investing compared to the loss of a bad event(recall),and relatively high direct risk, and thus intuitively should be more willing to invest than players with large.The lemma makes this intuition preci.
dictionariesLemma3(Ordering Lemma)Let be a NE for a uniform transfer IDS game .Then for any(an investing player),any(a partially investing player),and any(a non-investing player),the following conditions hold:
The cond lemma establishes that if a NE contains some partially investing players,the values for their mixed strategies is in fact uniquely determined.The equations for the mixed strategies is exploited in the subroutine TestNash.
Algorithm UniformTransferIDSNash
Input:An-player uniform transfer IDS game with direct risk parameters,transfer risk parameters,and cost parameters,where.
Output:A t of all exact connected ts of NE for.
去英国要考什么
1.Initialize a partition of the players into three ts(the investing,not investing,
and partially investing players,respectively)and test if everybody investing is a NE:
TestNash
2.Let be an ordering of the players satisfying
.Call this the outer ordering.
3.for
(a)Move the next player in the outer ordering from the investing to the partially-
investing ts:
(b)Let be an ordering of the players in satisfying
.Call this the inner ordering.quintus
(c)Consider a strategy with no not-investing players:
TestNash
(d)for
i.Move the next player in the inner ordering from the partially-investing to
non-investing ts,and test if there is a NE consistent with the partition:
TestNash
Subroutine TestNash
Inputs:An-player uniform transfer IDS game;a partition of the players(as above); ,the current discovered t of connected ts of NE for
Output:with possibly one additional connected t of NE of consistent with,and (assuming unit-time computation of-roots of rational numbers)
1.Set pure strategies for not-investing and investing players,respectively:
,.
2.if(Lemma4,part(a)applies)
(a)Let,as in Equation3and
(b),player is indifferent)and,then return
3.el(Lemma4,part(b)applies)
(a)Compute mixed strategies as in Equation4
(b)if or,return
(c)if is a NE for then return
Figure1:Algorithm UniformTransferIDSNash
If is an interval of with endpoints and,and then we define
.
exceed
Lemma4(Partial Investment Lemma)Let be a mixed strategy for a uniform transfer IDS game,and let be the t of partially investing players in. Then(a)if,then letting,
工程管理系统and
(3) it holds that is a NE if and only ,player is indifferent)and player mixed strategy satisfies el,(b)if,and is a NE,then for all
,
(4) where
The next theorem summarizes our cond algorithmic result on uniform transfer IDS games.The omitted proof follows from Lemmas3and4.
Theorem5Algorithm UniformTransferIDSNash computes all exact(connected ts of) NE for uniform transfer IDS games in time polynomial in the size of the model.
We note that it follows immediately from the description and correctness of the algorithm that any-player uniform transfer IDS game has at most connected ts of NE.In addition,each connected t
of NE in a uniform transfer IDS game is either a singleton or a simple interval where of the players play pure strategies and the remaining player has a simple interval in of probability values from which to choo its strategy.At most of the connected ts of NE in a uniform transfer IDS game are simple intervals.
3.2Hardness of General IDS Games
In light of the results of the preceding ction,it is of cour natural to consider the com-putational difficulty of unrestricted IDS.We now show that even a slight generalization of uniform transfer IDS games,in which we allow the to assume twofixed values instead of one,leads to the intractabilty of computing at least some of the NE.
A graphical uniform transfer IDS game,so named becau it can be viewed as a marriage between uniform transfer IDS games and the graphical games introduced in[3],is an IDS game with the restriction that for all players,,for some.Let
be the t of players that can be directly affected by player’s behavior.In other words,the transfer risk parameter of player with respect to player is either zero,in which ca the player has no direct effect on player’s behavior;or it is constant,in which ca,the public safety of player with respect to player i
s the same as for any other player in.
The pure Nash extension problem for an-player game with binary actions takes as input a description of the game and a partial assignment.The output may be any complete assignment(joint action)that agrees with on all its0and1ttings, and is a(pure)NE for the game;or“none”if no such NE exists.Clearly the problem of computing all the NE is at least as difficult as the pure Nash extension problem. Theorem6The pure Nash extension problem for graphical uniform transfer IDS games is NP-complete,even if for all,and is somefixed value for all.
The reduction(omitted)is from Monotone One-in-Three SAT[1].
口语话题
4Experimental Study:Airline Baggage Security
As an empirical demonstration of IDS games,we constructed and conducted experiments on an IDS game for airline curity that is bad on real industry data.We have access to a data t consisting of35,362records of actual civilian commercialflight rervations, both domestic and international,made on August26,2002.Since the records contain completeflight itineraries,they include pasnger transfers between the122reprented commercial air carriers.As described below,we ud this data t to construct an IDS
