Project Number 001907 DELIS Dynamically Evolving, Large-scale Information Systems Integrate

Project Number001907

DELIS

Dynamically Evolving,Large-scale Information Systems

Integrated Project

Member of the FET Proactive Initiative Complex Systems

Deliverable D4.1.2

A preliminary set of methods and tools for computing or approximating net equilibria,net ?ows and the core,price of anarchy,for

restricted agent rationality

Start date of the project:January2004

Duration:48months

Project Coordinator:Prof.Dr.math.Friedhelm Meyer auf der Heide

Heinz Nixdorf Institute,University of Paderborn,Germany

Due date of deliverable:December2005

Actual submission date:January2006

Dissemination level:PU–public

Work Package4.1:Game theoretic approaches to cooperation and competition in

dynamic large nets

Participants:University of Cyprus(UCY),Cyprus

University of Paderborn(UPB),Germany

Research Academic Computer Science Institute(CTI),Greece

Universita di Roma,“La Sapienza”(UDRLS),Italy

Rheinisch-Westf¨a lische Technische Hochschule Aachen(RWTH),Germany

University of Cambridge(UCAM-DAE),United Kingdom

Contributing researchers:Martin Gairing(gairing@upb.de)

Spyros Kontogiannis(kontog@cti.gr)

Stefano Leonardi(leon@dis.uniroma1.it)

Berthold V¨o cking(voecking@cs.rwth-aachen.de)

Authors of deliverable:Marios Mavronicolas(mavronic@ucy.ac.cy)

Vicky Papadopoulou(viki@ucy.ac.cy)

Contents

1Introduction2 2Congestion Games4

2.1The General Framework (4)

2.1.1Congestion Games (4)

2.1.2Price of Anarchy (5)

2.2Algorithms and Complexity (6)

2.2.1Sel?sh Unsplittable Flows (6)

2.2.2Worst-Case Equilibria (7)

2.2.3Symmetric Congestion Games (7)

2.2.4Exact Price of Anarchy (7)

3Sel?sh Routing with Incomplete Information8

3.1Bayesian Routing Games (8)

3.2Player-Speci?c Latency Functions (9)

3.3Network Uncertainty in Sel?sh Routing (9)

3.4Restricted Sel?sh Scheduling (10)

3.5Adaptive Routing with Stale Information (11)

4Game-Theoretic Analysis of Internet Switching11

4.1A Game-Theoretic Model (11)

5Algorithmic Mechanism Design13

5.1Stackelberg Games (14)

5.1.1Stackelberg Equilibria (14)

5.1.2The Price of Optimum (15)

5.2Cost Sharing Mechanisms (15)

6Network Security Games16

6.1A Graph-Theoretic Model (17)

6.2A Generalized Model (18)

7The Core19 8Complexity of Computing Equilibria19

8.1Pure Nash Equilibria in Mupli-players Games (19)

8.2Games with at Least Four Players (20)

8.3Games with Three Players (20)

8.4Games with Two players (21)

8.5Correlated Equilibria (21)

9Discussion22

1Introduction

Most of the existing,such as the Internet,and foreseen complex networks are operated and built by thousands of large and small entities(autonomous agents),collaborating with admirable e?ectiveness to process and deliver end-to-end?ows originating and terminating in any of them.The distributed nature of the Internet has as a consequence a lack of co-ordination among its users.Instead,each user attempts to obtain maximum performance according to his own parameters.

Methods from Game Theory and Mechanism Design are proved to be a powerful math-ematical tool in order to understand,control and e?ciently design such dynamic,complex networks.Game theory can provide a good starting point for Computer Scientists in order to understand sel?sh rational behavior of complex nets of many agents(players).Such a scenario is readily modeled using Game Theory techniques in which players with poten-tially di?erent goals participate under a common setting with well prescribed interactions (in this case,TCP/IP protocols).

Nash Equilibrium[Nas50,Nas51]stands out as the predominant concept of rationality in non-cooperative settings.Thus,Game Theory and its notions of equilibria provide a rich framework for modelling the behavior of sel?sh agents in these kinds of distributed or networked environments and ofter mechanisms to achieve e?cient and desirable global outcomes in spite of the sel?sh behavior.

Mechanism Design asks how one can design systems so that agents’sel?sh behavior results in desired system-wide goals.Algorithmic Mechanism Design additionally considers computational tractability to the set of concerns.Work in Algorithmic Mechanism Design classically focuses on the complexity of centralized implementations of game-theoretic mechanisms for distributed optimization problems.Moreover,in such a huge network each player does not have access to and may not process complete information.The notion of bounded rationality for network agents and the design of distributed algorithms have been successfully utilized to capture the aspect of incomplete information.

In the context of this research framework,within Subproject“Game Theoretic and Organizational Economics Inspired Approaches”we have been dwelving into a sequence of related?elds.Deliverable D4.1.1[D4104]contained a comprehensive catalog of open problems in Game Theory https://www.wendangku.net/doc/522666230.html,putational e?ciency as recorded in the beginning of the project.In this second deliverable,we present some of the most important ad-vances observed during the last years towards answering some of the quite important open problems indicated in[D4104].For the?elds addressed,not only we have absorbed the existing worldwide knowledge but,for some of them,we have also contributed towards their progress.The areas addressed are the followings:

Congestion Games A central problem arising in the management of large-scale commu-nication networks like the Internet is that of routing tra?c through the network.Due to the large size of these networks,however,it is often impossible to employ a centralized tra?c management.A natural assumption to justify the absence of central regulation is that network users behave sel?shly and aim at optimizing their own individual wel-fare.One way to address this problem,proved to be much powerful,is to model it as a non-cooperative multi-player game and formalize it as a(un-)weighted congestion game; this is a sel?sh routing game with splittable or unsplittable?ows.In this document,we later provide a set of methods and tools for computing Nash equilibria for such network settings.

Price of Anarchy We survey precise and approximate computations of the Price of An-archy;this is the cost of sel?sh cooperation in dynamic,large-scale nets,compared to centralized hypothetical solutions.We consider the Price of Anarchy for some of the most important network problems,modeled by non-cooperative games;for example,we consider routing and security problems.

Sel?sh Routing with Incomplete Information The notion of bounded rationality in net-works with incomplete information can be addressed by Bayesian games and also by congestion games with player speci?c payo?functions.We will survey methods and tools for approximating net equilibria and net?ows for restricted agent rationality.

Game Theoretic Analysis of Internet Switching We survey the problem of Internet switching,where tra?c is generated by sel?sh users concentrated on packetized(TCP-like)tra?c models;this is more realistic than the widely used?uid model.We survey a game-theoretic model and analysis of the Internet switching problem.

Mechanism design Mechanism design is a sub?eld of Game Theory and Microeconomics which deals with the design of protocols for rational agents.Generally,a Mechanism Design problem can be described as the task of selecting from a collection of feasible games,a game which will yield desirable results for the designer.The routing problem in large-scale networks,where users are instinctively sel?sh,can be modeled by a non-cooperative game.Such a game could impose strategies that might induce an equilibrium closer to the overall optimum.These strategies are enforced through pricing mechanisms [FCHPSS00],algorithmic mechanisms[NR99]and network design[KLO95,Rou01a]. Stackelberg Games We will consider network routing games from the network designer’s point of view.In particular,the network administrator or designer can de?ne prices and rules,or even construct the network,in a way that induces near-optimal performance when the users act sel?shly to the system.Particularly interesting is the approach where the network manager takes part in the non-cooperative game.The manager has the ability to control centrally a part of the system resources,while the rest resources are used by the sel?sh users.This approach has been studied through Stackelberg or Leader-Follower games[BO99,KLO97,CDR03].The advantage of this approach is that it might be easier to be deployed in large-scale networks.This is so since there is no need to add extra components to the network or to exchange information between the users of the network. In a Stackelberg game,one player acts as a leader(here,the centralized authority interested in optimizing system performance)and the rest as followers(here,the sel?sh users).The problem is then to compute a strategy for the leader(a Stackelberg strategy)that induces the followers to react in a way that(at least approximately)minimizes the total latency in the system.

Sel?sh routing games can be modeled as a Stackelberg game.We will survey issues related to how the manager should assign the?ow under his control into the system so as to induce optimal cost incurred by the sel?sh users.

Pricing mechanisms Pricing mechanisms in resource allocation problems aim to allocate resources in such a way that those users who derive greater utility from the network are not denied access due to other users who place a lower value on it.In other words,pricing mechanisms are designed to guarantee economic e?ciency.We will discuss cost-sharing mechanisms for pricing the competitive usage of a collection of resources by a collection of sel?sh agents,each coming with an individual demand.

Network Security Games We will also consider security problems in dynamic,large-scale,distributed networks.This problem can be modeled as a concise,non-cooperative multi-player game played on a graph.We will investigate associated Nash equilibria in such network security games.

The Core The nucleolus is a solution concept for coalitional form games with transferable utility that was?rst introduced by Schmeidler[Sch69].Osborne and Rubinstein[OR94] proposed a new but equivalent de?nition of the nucleolus in terms of objections and counter-objections in negotiations.The nucleolus is a payo?division such that for every objection to it,there is a counter-objection.In recent years,there has been an increased interest in computational complexity aspects of solution concepts in cooperative game theory,such as the nucleolus of a game.Here,we will investigate issues related to the nucleolus of games with an emphasis on?ow games.

Complexity of Computing Equilibria The investigation of the complexity of?nding a Nash equilibrium in a general game is de?nitely a fundamental task for the development of Algorithmic Game Theory.Answers to such questions are expected to have great prac-tical impact on both the analysis of the behavior of antagonistic networks and the network designers directions.Finding a Nash equilibrium in a game with two players could poten-tially be easier than for many players for several reasons.First,the zero-sum version of the game can be solved in polynomial time by linear programming.Secondly,it admits a polynomial size rational number solution,while games with three or more players may only have solutions in irrational numbers.This reasoning justi?ed the identi?cation of the problem of?nding Nash equilibria for a2-player game as one of the most important open questions in the?eld of Algorithmic Game Theory.The complexity of this problem was very recently settled in a perhaps surprising way in a series of breakthrough papers.Here, we will survey the worldwide literature related to this problem and the recent progress to it. The scienti?c background related to this document can be found in deliverable D4.2.1 [D4204].That document provides a comprehensive evaluation of?tness of the currently known mechanisms with respect to sel?sh cooperation in networks.

2Congestion Games

2.1The General Framework

2.1.1Congestion Games

Rosenthal[Ros73]introduced a special class of strategic games,now widely known as congestion games.Here,the strategy set of each player is a subset of the power set of a set of resources.The players share a private objective function,de?ned as the sum(over their chosen resources)of functions in the number of players sharing this resource.In his seminal work,Rosenthal showed with the help of a potential function that congestion games(in sharp contrast to general strategic games)always admit at least one pure Nash equilibrium.An extension to congestion games are weighted congestion games,in which the players have weights and thus di?erent in?uence on the congestion of the resources.In (weighted)network congestion games,the strategy sets of the players correspond to paths in a network.

2.1.2Price of Anarchy

In order to measure the degradation of social welfare due to the sel?sh behavior of the players,Koutsoupias and Papadimitriou[KCHP99]introduced in their seminar work a global objective function,usually coined as Social Cost.They de?ned the Price of Anarchy, also called Coordination Ratio,as the worst-case ratio between the value of Social Cost in a Nash equilibrium and that of some Social Optimum.Thus,the Coordination Ratio measures the extent to which non-cooperation approximates cooperation.

As a starting point for studying the Coordination Ratio,Koutsoupias and Papadimitriou considered a very simple weighted network congestion game,now known as KP-model. Here,the network consists of a single source and a single destination(single-commodity network)which are connected by parallel links.The load on a link is the total weight of players assigned to this link.Associated with each link is a capacity representing the rate at which the link processes load.Each of the players sel?shly routes from the source to the destination by using a probability distribution over the links.The private objective function of a player is de?ned as its expected latency.In the KP-model,the Social Cost is de?ned as the expected maximum latency on a link,where the expectation is taken over all random choices of the players.

Mavronicolas and Spirakis[MS01]introduced the notion of a fully mixed Nash equilib-rium,in which each player chooses every link with positive probability.Gairing et al. [GTLM+03]conjectured that,in case of its existence,the fully mixed Nash equilibrium is the worst Nash equilibrium with respect to Social Cost.This so-called Fully Mixed Nash Equilibrium Conjecture is simultaneously intuitive and signi?cant.It is intuitive because the fully mixed Nash equilibrium favors collisions between di?erent players(since each player assigns its item with positive probability to every link).This increased probability of collisions should favors an increase to Social Cost.The conjecture is also signi?cant since it identi?es the worst-case Nash equilibrium over all instances.

Recently,the KP-model was extended to restricted strategy sets[GTLMM04a],where the strategy set of each player is a subset of the links.Furthermore,the KP-model was extended to general latency functions and studied with respect to di?erent de?nitions of Social Cost[AAE05].Inspired by the arisen interest in the Price of Anarchy,the much older Wardrop-model was reinvestigated in[RT02].In this weighted network congestion game,weights can be split into arbitrary pieces.The social welfare of the system is de?ned as the sum of the edge latencies(Sum or Total Social Cost).An equilibrium in the Wardrop model can be interpreted as a Nash equilibrium in a game with in?nitely many players, each carrying an in?nitesimal amount of weight.

In[KCHP99],the authors consider the objective of(expected)maximum latency(also called Maximum Social Cost)for a weighted congestion game in uniformly related parallel links.The Price of Anarchy for this game is shown to beΘ(log m

log log m

)if either the users or

the links are identical[CV02,KMS03]andΘ(log m

log log log m )for weighted users and uniformly

related links[CV02].On the other hand,[CKV02]shows that the Price of Anarchy is far worse and can be even unbounded for arbitrary latency functions.For uniformly related parallel links,identical users,and the objective of total latency,the Price of Anarchy is 1?o(1)for the general case of mixed equilibria and4/3for pure equilibria[LMMR04, GTLM+04].For identical users and polynomial latency functions of degree d,the Price of Anarchy is dΘ(d)[GTLMM04b,GTLM+04].

Christodoulou and Koutsoupias in[CK05]consider the Price of Anarchy of pure Nash equilibria in congestion games with linear latency functions.They showed that for general (asymmetric)games,the Price of Anarchy of Maximum Social Cost isΘ(

√N),where N

is the number of players.For all other cases of symmetric or asymmetric games and for

both Maximum and Average Social Cost,the Price of Anarchy is shown to be5/2.

2.2Algorithms and Complexity

A comprehensive survey of some of the most important recent advances in the literature for

atomic congestion games is contained in[KS05].That work is an overview of the extensive

expertise on(mainly network)congestion games and the closely related potential games,

that has been developed in various disciplines(e.g.,Economics,Computer Science and

Operations Research)under a common formalization and modeling.In particular,the

survey is not only an exposition of known results,but goes deep into the details of some of

the most characteristic results in the area in order to compile a useful toolbox that Game

Theory provides in order to study antagonistic behavior due to congestion phenomena in

real-life problems.

2.2.1Sel?sh Unsplittable Flows

In[FKS05a],Fotakis et al.study congestion games in which sel?sh users with varying

service demands for the system resources may request a joint service from arbitrary subsets

of resources.Each user’s demand has to be served unsplittably from a speci?c subset of

resources.In that work,it is proved that the weighted congestion games are no longer

isomorphic to the well known potential games,although this was true for the case of users

with identical service demands.The authors also demonstrate the power of the network

structure,when users of varying demands request service.For very simple networks,they

show that there may not exist a pure Nash equilibria,which is not true for the case of

parallel links network or for the case of in?nitely splittable service demands.Furthermore,

the authors propose a family of networks(called layered networks)for which they show

the existence of at least one pure Nash equilibria when each resource(that is,link)charges

its users with delay identical to its load.Finally,the same work considers the Price of

Anarchy in the family of layered networks in the case when each resource delay equals its load.It is shown that the Price of Anarchy for this case isΘ log m log log m .That is,within constant factors,the worst network is the simplest one(the parallel links network).This

implies that in this family of networks,the network structure does not essentially a?ect

the quality of the congestion games played on the network.

[PS05]considers sel?sh routing in single-commodity networks,where sel?sh users select

paths to route their loads(represented by arbitrary integer weights).It considers identical

delay functions for the links of the network.That work focuses also on the algorithm

suggested in[FKS05a];this is a potential-based method for?nding pure Nash equilibria

in such networks.The analysis of this algorithm in[FKS05a]gives an upper bound on

its running time,which is polynomial in n(the number of users)and the sum W of their

weights.This bound can be exponential in n when some weights are superpolynomial.

Therefore,the algorithm was indeed proved to be pseudo–polynomial.[PS05]provides

strong experimental evidence that this algorithm actually converges to a pure Nash equi-

libria in strong polynomial time in n(independent of the weights values).In addition,

the authors propose an initial allocation of users to paths that dramatically accelerates

this algorithm,as opposed to an arbitrary initial allocation.A byproduct of that work

is the discovery of a weighted potential function when link loads are exponential to their

loads.This guarantees the existence of pure Nash equilibria for these delay functions and

extends the result of[FKS05a].

2.2.2Worst-Case Equilibria

In [FV05b],S.Fischer and B.V¨o cking studied the sel?sh routing game associated with the KP-model [KCHP99],where n weighted jobs are allocated to m identical machines.Gairing et al.[GTLM +03]had conjectured that the fully mixed Nash equilibrium is the worst Nash equilibrium for this game with respect to the expected maximum load over all machines.The known algorithms for approximating the Price of Anarchy relied on proved cases of that conjecture.In [FV05b],the authors interestingly present a counter-example to the conjecture showing that fully mixed equilibria cannot be generally used to approximate the Price of Anarchy within reasonable factors.In addition,they present an algorithm that constructs the so-called concentrated equilibria that approximate the worst-case Nash equilibrium within constant factors.

2.2.3Symmetric Congestion Games

[FKS05b]continues the work of [FKS05a]and study computational and coordination issues of Nash equilibria in symmetric network congestion games.A game is symmetric if all users have the same strategy set and users costs are given by identical symmetric functions of other users’strategies.In congestions games,the users are identical,so that a common strategy set implies symmetry.This work proposed a simple and natural greedy method (which is called the Greedy Best Response –GBR ),that computes a pure Nash equilibria.In this algorithm,each user plays only once and allocates his tra?c to a path selected via a shortest path computation.Then,it is shown that this algorithm works for series-parallel networks ,when users are identical,or when users are of varying demands but have the same best response strategy for any initial network tra?c (this is called the Common Best Response property).The authors also give constructions where the algorithm fails if either the above condition is violated (even for series-parallel networks),or the network is not series-parallel (even for identical users).Thus,they essentially indicate the limits of the applicability of this greedy approach.

The same work [FKS05b]studies also the Price of Anarchy for the objective of maximum latency.It is proved that for any network of m uniformly related links and for identical

users,the Price of Anarchy is Θ log m log log m .This result is complementary (and somewhat

orthogonal)to a similar result provided in [FKS05a]for the case of players of varying weights to be routed in a layered network.

2.2.4Exact Price of Anarchy

Exact bounds on the Price of Anarchy or unweighted and weighted congestion games with polynomial latency functions are provided in [ADGaFS06].The authors use the total latency as the Social Cost measure.This improves on results by Awerbuch et al.[AAE05]and Christodoulou and Koutsoupias [CK05],where non-matching upper and lower bounds were are given.

For the case of unweighted congestion games ,in the same work [ADGaFS06]it is shown that the price of anarchy (PoA )is exactly

PoA =(k +1)2d +1?k d +1(k +2)d (k +1)d +1?(k +2)d +(k +1)d ?k d +1

,where k =?Φd ?and Φd is a natural generalization of the golden ratio to larger dimensions such that Φd is the solution to (Φd +1)d =Φd +1d .Prior to that paper,the best known upper and lower bounds were shown to be of the form d d (1?o (1))[CK05].However,the term o (1)still hide a signi?cant gap between the upper and the lower bound.

For weighted congestion games,the authors show that the Price of Anarchy(PoA)is exactly

PoA=Φd+1

d

.

This result closes the gap between the so far best upper and lower bounds of O(2d d d+1) and?(d d/2)from[AAE05].

The authors show that the above values on the Price of Anarchy also hold for the subclasses of unweighted and weighted network congestion games.For the upper bounds, the authors use a similar analysis as in[CK05].The core of their analysis is to determine parameters c1and c2such that

y·f(x+1)≤c1·x·f(x)+c2·y·f(y)(1) for all polynomial latency functions of maximum degree d and for all reals l x,y≥0. For the case of unweighted demands,it su?ces to show(1)for all pairs of integers x and y.In order to prove their upper bound,Christodoulou and Koutsoupias[CK05]looked

at(1)with c1=1

2and gave an asymptotic estimate for c2.In the analysis presented in

[ADGaFS06]both parameters c1and c2are optimized.This optimization process required new mathematical ideas and is non-trivial.

3Sel?sh Routing with Incomplete Information

In his seminal work,Harsanyi[Har67]introduced an elegant approach to study non-cooperative games with incomplete information,where the players are uncertain about some parameters.To model such games,he introduced the Harsanyi transformation, which converts a game with incomplete information to a strategic game where players may have di?erent types.In the resulting Bayesian game,the players’uncertainty about each other’s types is described by a probability distribution over all possible type pro?les. The problem of sel?sh routing with incomplete information has recently been faced via the introduction of new suitable models and the development of new methodologies that help to analyze such network settings.In particular,new sel?sh routing games with incomplete information have been introduced,called Bayesian routing games[GaKT05]. Furthermore,the same problem can be viewed as a congestion game where latency func-tions are player-speci?c[GMT05],or a congestion game under the restriction that the link for each user must be chosen from a certain set of allowed links for the user[EGTL+05].

A relevant,also important,problem is that of adaptive routing in networks by sel?sh users that lack central control.This important problem has not yet been addressed.

3.1Bayesian Routing Games

In[GaKT05],a particular sel?sh routing game with incomplete information,called Bayesian routing game is introduced.Here,n sel?sh users wish to assign their tra?c to one of m parallel https://www.wendangku.net/doc/522666230.html,ers do not know each other’s tra?c.Following Harsanyi’s approach,the authors introduce for each user a set of possible types.This work contains a comprehensive collection of results for this Bayesian routing game.

In[GaKT05],with respect to the problem of the existence and computational complexity of pure Bayesian Nash equilibria,it is proved with the help of a potential function,that every Bayesian routing game has a pure Bayesian Nash equilibrium.This result can also be generalized to a larger class of games,called weighted Bayesian congestion games.For the case of identical links and independent type distributions,it is shown that a pure Bayesian Nash equilibrium can be computed in polynomial time.(A probability distribution over all

possible type pro?les is independent if it can be expressed as the product of independent

probability distributions,one for each type.)

In the same work the authors study structural properties of fully mixed Bayesian Nash

equilibria for the case of identical links and show that they maximize Individual Cost.In

general,there exists more than one fully mixed Bayesian Nash equilibrium.The authors

provide a characterization of the class of fully mixed Bayesian Nash equilibria for the case

of independent type distribution;the characterization determines in turn the dimension

of the space of fully mixed Nash equilibria.

Finally,then authors in[GaKT05]consider the Price of Anarchy for the model of iden-

tical links for three Social Cost measures;that is,Social Cost as expected maximum

congestion,Sum of Individual Costs and Maximum Individual Cost.For the latter two,

(asymptotic)tight bounds using the proven structural properties of fully mixed Bayesian

Nash equilibria were provided.

3.2Player-Speci?c Latency Functions

[GMT05]studies(weighted)network congestion games under the aspect of incomplete

knowledge also about the system.As shown there,such Bayesian routing games can be

transformed into routing games where the latency functions are player-speci?c.There,n

sel?sh players wish to route their tra?c through a shared network.This work considers

both the case of splittable and unsplittable tra?cs.

In this perspective,the proposed models generalize the two famous models of sel?sh rout-

ing,namely weighted(network)congestion games and the Wardrop model to accommo-

date player-speci?c latency https://www.wendangku.net/doc/522666230.html,tency functions may be arbitrary non-decreasing

functions;however,many of their results assume that the latency function for player i on

resource j is a linear function f ij(x)=a ij x+b ij where a ij≥0and b ij≥0.They use the term player-speci?c capacities to denote a game where b ij=0in all latency functions.

They derive several interesting results on the existence and computational complexity

of(pure)Nash equilibria and the Price of Anarchy.For routing games on parallel links

with player-speci?c capacities,they introduce two new(potential)functions,one for un-

splittable and one for splittable tra?cs.The?rst potential function is used to prove,

for the case of unsplittable tra?cs,that games with unweighted players possess the?nite

improvement property.It is also shown that games with weighted players do not possess

the?nite improvement property in general,even if n=3.The second function is a con-

vex function that plays the role of a potential function for the case of splittable tra?cs.

This convex function is minimized if and only if the corresponding assignment is a Nash

equilibrium.This result implies that a Nash equilibrium can be computed in polynomial

time.

The same work proves upper and lower bounds on the Price of Anarchy under a certain

restriction on the linear latency functions.For the case of unsplittable tra?cs the upper

and lower bounds are asymptotically tight.All results on the Price of Anarchy translate

to general congestion games.

3.3Network Uncertainty in Sel?sh Routing

The problem of sel?sh routing in the presence of incomplete network information is also

studied in[GTPP06].This work proposes a new model for sel?sh routing in the presence of

incomplete network information.The proposed model captures situations where the users

have incomplete information regarding the link capacities.Such uncertainty may be caused

if the network links are complex paths created by routers which are constructed di?erently

on separate occasions and according to the presence of congestion or link failures.

The new,extremely interesting model presented in[GTPP06]consists of a number of users who wish to route their tra?c on a network of m parallel links with the objective of minimizing their latency.In order to capture the lack of precise information on the capacity of the network links,it is assumed that links may present a number of di?erent capacities.Each user’s uncertainty about the capacity of the links is modeled via a prob-ability distribution over all possibilities.Furthermore,it is assumed that users may have di?erent sources of information regarding the network and,therefore,take their prob-ability distributions to be distinct from each another.This gives rise to a model with user-speci?c payo?functions,where each user uses its distinct probability distribution to take decisions as to how to route its tra?c.

The authors propose polynomial-time algorithms for computing some special cases of pure Nash equilibria and demonstrate that the counter-example presented in[Mil96],show-ing that pure Nash equilibria may not exist in the general case,does not apply in their model.Thus,they identify an interesting open problem in this area,that of existence of pure Nash equilibria in the general case.Also,two di?erent expressions for the Social Cost and the associated Price of Anarchy are identi?ed and employed.For the latter,the authors obtain upper bounds in the general case and improved upper bounds for several special cases.

In the same work,the authors show how to compute the fully mixed Nash equilibrium, and show that when it exists it is unique.Also,it is shown that for certain instances of the game,fully mixed Nash equilibria assign all links to all users equiprobably.Finally, it veri?es the Fully-Mixed Nash Equilibrium conjecture,by proving that the fully mixed Nash equilibrium maximizes the social welfare.

3.4Restricted Sel?sh Scheduling

The paper[EGTL+05]considers sel?sh routing problems in networks under the restriction that the link for each user must be chosen from a certain set of allowed links for the user. It is assumed that each user has access(that is,?nite cost)to only two machines;its cost on other machines is in?nitely large,giving it no incentive to switch there.The(expected) cost of a user is the(expected)load of the machine it chooses.Interaction with just a few neighbors is a basic design principle to guarantee e?cient use of resources in a distributed system.Restricting the number of interacting neighbors to just two is then a natural starting point for the theoretical study of the impact of sel?sh behavior in a distributed system with local interactions.

In that work,a simple,graph-theoretic model for sel?sh scheduling among m non-cooperative users over a collection of n machines was introduced and studied.There,each user is restricted to assign its unsplittable load to one from a pair of machines that are allowed for the user.The authors model these bounded interactions using an interaction graph,whose vertices and edges are the machines and the users,respectively.They also study the impact of the modeling assumptions on the properties of Nash equilibria in their new model.

In that same work,it is proved that the parallel links graph is the best-case interaction graph–the one that minimizes expected makespan of the standard fully mixed Nash equilibrium–among all3-regular interaction graphs.The proof employs a graph-theoretic lemma about orientations in3-regular graphs,which may be of independent interest.

A lower bound on Coordination Ratio[KCHP99]is also provided.In particular,it is proved that there is an interaction graph incurring Coordination Ratio? log n log log n .This bound is shown for pure Nash equilibria.Finally,the authors present counterexample interaction graphs to prove that a fully mixed Nash equilibrium may sometimes not exist

at all.Moreover,they prove existence and uniqueness properties of the fully mixed Nash equilibrium for complete bipartite graphs and hypercube graphs.

3.5Adaptive Routing with Stale Information

The work[FV05a]considers the problem of adaptive routing in networks by sel?sh users that lack central control.The main focus of this work is on simple adaption policies,or dynamics,that make use of possibly stale load information.The analysis provided covers a wide class of dynamics encompassing the well-known replicator dynamics and other dynamics known from Evolutionary Game Theory.As a well known problem,it has been often pointed out,that always choosing the best option based on out-of-date information can lead to undesirable oscillation e?ects and poor overall performance.

In that work,it is shown that it is possible to cope with this problem,and guarantee convergence towards an equilibrium state,for all of this broad class of dynamics,if the function describing the cost of an edge depending on its load is not too steep.Therefore, it turns out that whether or not convergence can be guaranteed depends solely on the size of a single parameter describing the greediness of the agents.

While the best response dynamics,corresponding to always choosing the best option, performs well if information is always up-to-date,it is clear from the results in[FV05a] that this policy fails when information is stale.The authors present a dynamics which approaches the global optimal solution in networks of parallel links with linear latency functions as fast as the best response dynamics does,but which does not su?er from poor performance when information is out-of-date.

4Game-Theoretic Analysis of Internet Switching

If all Internet users voluntarily deploy a congestion-responsive transport protocol(e.g. TCP[Jac88]),one can design this protocol so that the resulting network would achieve certain performance goals such as high utilization or low delay.However,with the fast growth of the Internet users population,the assumption about cooperative behavior may not remain valid,and in fact it is https://www.wendangku.net/doc/522666230.html,ers are likely to behave sel?shly,that is,each user makes decisions so as to optimize its own utility,without coordination with the other users. Bu?er sharing and bandwidth allocation problems are prime candidates for investigating the e?ect of such a sel?sh behavior.

If a user does not reduce its sending rate upon congestion detection,it can get a better share of the network bandwidth.On the other hand,all users su?er during congestion collapse,since the network delay and the packet loss increase drastically.Therefore,it is important to understand the nature of congestion resulting from sel?sh behavior.A natural framework to analyze this class of problems is that of non-cooperative games,and an appropriate solution concept is that of Nash equilibrium[Nas51].Strategies of the users are at a Nash equilibrium if no user can gain by unilaterally deviating from its current policy.

4.1A Game-Theoretic Model

The problem of Internet switching,where tra?c is generated by sel?sh users,has been considered in[KSLB05].That work concentrates on a packetized(TCP-like)tra?c model which is more realistic than the widely used?uid model.There,it is assumed that routers have First-In-First-Out(FIFO)bu?ers of bounded capacity managed by the drop-tail policy.The utility of each user depends on its transmission rate and the congestion level.

Since sel?sh users try to maximize their own utility and disregard the system objectives, Nash equilibria that correspond to a steady state of the system are studied.

[KSLB05]presents a game-theoretic model,called switching model,and an analysis of the Internet switching problem,assuming a FIFO bu?er shared by many users.The users compete for the bu?er share in order to maximize their throughput,but they su?er from the created congestion.It is assumed that each user knows its bu?er usage,the queue length and the bu?er size.The goal of a user is to maximize its utility.It is assumed that the utility function of a user increases when its throughput increases and decreases when the network congestion increases.

The model assumes that there are n users and the bu?er capacity is B,where B?n. In the model presented,all packets have a constant size.Time is slotted.Every time step each user may or may not send a packet to the bu?er.These packets arrive in an arbitrary order and are processed to the bu?er management policy one by one.Then,the ?rst packet in the FIFO order is transmitted on the output link.

The drop policy has to decide at each time step which of the packets to drop and which to accept.It can also preempt(drop)accepted packets from the bu?er.Under the drop-tail policy,all arriving packets are accepted if the bu?er is not full and dropped otherwise (when the bu?er is full).

Here,w t i denotes the number of packets of user i in the bu?er at the beginning of time step t.It is called the bu?er usage of user i.W t= i w t i denotes the queue length at time t.W t?i denotes the bu?er usage of all users but user i,i.e.,W t?i=W t?w t i.It is assumed that the users are greedy,that is,i.e.,they always have data to send and the queue is never empty.r t i=w t i/W t denotes the instant transmission rate of user i at time t.We say that the system is in a steady state if the queue length remains constant.Intuitively, when a packet of user i is transmitted at time step t,at time step t+1,user i will send a new packet to the queue.In a steady state,the average transmission rate of user i is r i=w i/W,where w i is the average bu?er usage of user i and W is the average queue length.Note that in this model,transmission rate is essentially equal to the throughput of the user.

A utility function,which falls into a general family of utility functions increasing in the sending rate and decreasing in the network congestion(see[DM87,She95]),is then de?ned.However,the rate and the delay(congestion)are rather incomparable values and thus it is natural to normalize one of these parameters.[KSLB05]introduces a novel

notion of congestion level,that is the congestion level at time t is L t=W t

B .Note that the

congestion level is zero when the bu?er is empty and one when the bu?er is full.

The utility of user i at time t is u i(w t i,W t?i)=r t i·(1?L t);so,it is proportional to the throughput while decreasing in the congestion level.It is assumed that user i sends a packet to the bu?er at time t if its utility increases(that is,u i(w t i+1,W t?i)>u i(w t i,W t?i)). Note that users maximize their instantaneous utility,and not the long-term one adapting to the current network conditions.In a steady state,the utility of user i is u i(w i,W?i)= r i·(1?L),where L=W/B.Observe that when the bu?er is almost empty,the utility of each user approximately equals its throughput.On the other hand,when the bu?er is nearly full,all users have utility close to zero.The latter situation can be viewed as congestion collapse.The strategy of each user is its bu?er usage while the strategies of the other users de?ne the background bu?er backlog.

The total utility of the users in a Nash equilibrium is n i=1u i(w i,W?i).Observe that under an optimal fair centralized policy,all users have equal sending rates of1/n and experience zero delay,which results to a total utility of1.

For example,users may send one packet in turn every time step and in this case the link would be fully utilized with zero congestion level.The Price of Anarchy in a Nash

equilibrium is de?ned to be1/ n i=1u i(w i,W?i).The fairness of a Nash equilibrium is also of concern.A Nash equilibrium is said to be fair if all users have the same bu?er usage.A Nash equilibrium in a networking environment is interesting only if it can be reached e?ciently(in polynomial time).The convergence time to a Nash equilibrium is de?ned to be the maximum number of time steps required to reach a Nash equilibrium starting from an arbitrary state of the bu?er.

In[KSLB05],it is demonstrated that the drop-tail bu?ering policy imposes a fair Nash equilibrium.However,the Price of Anarchy is proportional to the number of users.It is also shown that the system converges to a Nash equilibrium in polynomial time,namely after O(B2)time steps.Then,the authors propose a simple modi?cation of the Random Early Detection(RED)policy[FJ93]called Preemptive RED(PRED)that achieves a constant Price of Anarchy.It is also demonstrated that a Nash Equilibrium can be reached if all users deploy TCP Vegas as their transport protocol.

Finally,some natural extensions of the model including the case of multiple QoS re-quirements,routing on parallel links and general networks with multiple bottlenecks,are considered in[KSLB05].It is shown that if users have di?erent QoS requirements,the bu?er usage of each user in a Nash equilibrium depends on the requested QoS.In the case m identical links,the Price of Anarchy is shown to drop to n/m.It is also established that a max-min fair rate allocation is a Nash Equilibrium for general networks(under some restricting assumptions).The theoretical analysis of the equilibria is also complemented with simulations.

5Algorithmic Mechanism Design

Mechanism Design is a sub?eld of Game Theory and Microeconomics which deals with the design of protocols for rational agents.Generally,a Mechanism Design problem can be described as the task of selecting from a collection of feasible games,a game which will yield desirable results for the designer.Speci?cally,the theory of Mechanism Design has focused on problems where the goal is to satisfactorily aggregate privately known preferences of several agents towards a social choice.Intuitively,a Mechanism Design problem has two components:the usual algorithmic output speci?cation,and descriptions of what the participating agents want,formally given as utility functions over the set of possible outputs(outcomes).

A mechanism solves a given problem by assuring that the required outcome occurs,when agents choose their strategies as to maximize their own sel?sh utilities.A mechanism needs thus to ensure that players’utilities(which it can in?uence by handing out payments)are compatible with the algorithm.

As mentioned earlier in this deliverable,the routing problem in large-scale networks, where users are instinctively sel?sh,can be modeled as a non-cooperative game.Such a game could impose strategies that might induce an equilibrium closer to the overall optimum.These strategies are formulated through pricing mechanisms[FCHPSS00],al-gorithmic mechanisms[NR99]and network design[KLO95,Rou01a].The network admin-istrator(or designer)can de?ne prices or rules,or even construct the network in a way that induces near optimal performance when the users act sel?shly.

In the network design approach,the network manager takes part in the noncooperative game.The manager has the ability to control centrally a part of the system resources, while the rest of the resources are used by the sel?sh users.This approach has been studied through Stackelberg or Leader-Follower games[BO99,KLO97,CDR03].A sel?sh routing game can be also modeled as a Stackelberg game[Rou01b].We here overview some issues related to how should the manager assign the?ow he controls into the system,with the

objective to induce optimal cost due to the behavior of the sel?sh users.

5.1Stackelberg Games

In[Rou01b],Roughgarden studies the problem of optimizing the performance of a system shared by sel?sh,noncooperative users assigned to shared machines with load-dependent latency functions.Roughgarden measures system performance by the total latency of the system.Assigning jobs according to the sel?sh interests of individual users typically results in suboptimal system performance.However,in many systems of this type there is a mixture of sel?shly controlled and centrally controlled jobs;as the assignment of centrally controlled jobs will in?uence the subsequent actions by sel?sh users,the degradation in system performance due to sel?sh behavior can be reduced by scheduling the centrally controlled jobs in the best possible way.

[Rou01b]formulates this goal as an optimization problem via Stackelberg games,games in which one player acts a leader(here,the centralized authority interested in optimizing system performance)and the rest as followers(here,the sel?sh users).The problem is then to compute a strategy for the leader(a Stackelberg strategy)that induces the followers to react in a way that(at least approximately)minimizes the total latency in the system.Roughgarden[Rou01b]proves that it is NP-hard to compute the optimal Stackelberg strategy and present simple strategies with provable performance guarantees. More precisely,Roughgarden gives a simple algorithm that computes a strategy inducing a job assignment with total latency no more than a constant times that of the optimal assignment of all of the jobs;in the absence of centrally controlled jobs and a Stackelberg strategy,no result of this type is possible.Roughgarden also proves stronger performance guarantees in the special case where every machine latency function is linear in the machine load.

5.1.1Stackelberg Equilibria

In[KKPS05],a sel?sh routing games is viewed as a Stackelberg game.The authors investigate issues related to how the manager assign the?ow he controls into the system so as to induce optimal cost by the sel?sh users.In particular,they consider random tuples of machines,with either linear or M/M/1latency functions,and Price of Anarchy at least a tuning parameter c when there is no interference of the network designer(whom they call the Leader).

A variant(NLS)of the Largest Latency First(LLF)Leader’s strategy on tuples with Price of Anarchy≥c is evaluated.It is discovered that NLS experimentally improves on LLF for systems with inherently high Price of Anarchy,where the Leader is constrained to control a low portion a of jobs.This suggests even better performance for systems with arbitrary Price of Anarchy.Also,the least Leader’s portion a0needed to induce optimum cost is bounded experimentally.Unexpectedly,as the parameter c increases the corresponding a0decreases,for M/M/1latency functions.All these are implemented in an extensive Matlab toolbox.

Assume now that we have a system M of parallel machines with load dependent latency functions shared by an in?nite number of users,each scheduling its in?nitesimal small portion of total?ow r to machines in M of currently minimum delay.This may yield a Nash assignment of?ow with cost arbitrarily larger than the optimum one,increasing the Price of Anarchy on M.A Leader can decrease the Coordination Ratio on the price of the?ow he controls.He wisely acts?rst,assigning?ow ar on M,and then all Followers react sel?shly,assigning(1?a)r?ow on M.This is a Stackelberg Scheduling Instance (M,r,a),0≤a≤1.The NP-hard problem1

3?23Partition was reduced to deciding if

an instance(M,r,a),restricted to linear latencies,admits a Leader’s strategy inducing a given cost.Thus,computing the optimal Leader’s strategy is NP-hard.

For systems with arbitrary latencies the Coordination Ratio has been shown to be at

most1

a ,or at most4

3+a

for linear latencies,or even better.For any system M with

arbitrary strictly increasing latencies,in[KKPS05]the authors e?ciently compute the minimum portionβM of?ow r needed for a Leader to induce M s optimum cost,and the Leader’s optimal strategy as well.Then,it is proved that computing the optimal Leader’s strategy on instances(M,r,A≥βM)can be solved in polynomial time,and the Coordination Ratio is then1.The really hard instances are(M,r,a<βM),where and no Leader’s strategy can induce the optimum cost(so the Coordination Ratio is greater than 1).

Finally,the same work investigated instances with special latencies,where,the optimal Leader’s strategy can be computed in polynomial time.(This had been shown in the literature for M/M/1latencies.)It is shown there that the same holds if each M i∈M incurs latency?i(x)=a i x+b i,with b1≤···≤b m and a1=···=a m.

5.1.2The Price of Optimum

In[KPS05],a system M of parallel machines,each with a strictly increasing and di?er-entiable load dependent latency function is considered.The users of such a system are of in?nite number and act sel?shly,routing their in?nitesimally small portion of the total ?ow r they control,to machines of currently minimum delay.In that work such a system is modeled as a Stackelberg or Leader-Followers game motivated by[RT02].

In[Rou01b],Roughgarden presented the LLF Stackelberg strategy for a Leader,on a noncooperative game with an in?nite number of Followers,each routing its in?nitesimal ?ow through machines of currently minimum delay(this is the Flow Model from[Rou01b]). An important question possed there was the computation of the least portionβM that a Leader must control in order to enforce the overall Optimum Cost on a system M.In [KPS05],an algorithm that computesβM was presented and its optimality was also shown. Most importantly,it was proved that the algorithm presented is optimal for any system M with any class of latency functions for which Nash and optimum assignments can be e?ciently computed.

5.2Cost Sharing Mechanisms

A simple and intuitive cost mechanism which assigns costs for the competitive usage of m resources by n sel?sh agents was proposed in[MPS05a].Each agent has an individual demand;demands are drawn according to some probability distribution.The cost paid by an agent for a resource he chooses is the total demand put on the resource divided by the number of agents who chose that same resource.So,resources charge costs in an equitable,fair way,while each resource makes no pro?t out of the agents.This simple model was called Fair Pricing model by the authors of[MPS05a].Its fair cost mechanism induces a non-cooperative strategic game,which is called FairPricingGame,whose players and strategies are the agents and resources,respectively.

In[MPS05a],the authors analyzed the Nash equilibria(both pure and mixed)for Fair-PricingGame;roughly speaking,these are stable states from which no agent has an incentive to unilaterally deviate.In particular,they consider the fully mixed Nash equilibrium where each agent selects each resource with non-zero probability.While o?ering in addition an advantage with respect to convenience in handling,the fully mixed Nash equilibrium is suitable for that economic framework under the very natural assumption that each resource o?ers usage to all agents without imposing any access restrictions.

To evaluate the Nash equilibria of this game,they introduced the Di?use Price of Anarchy,as an extension of the Price of Anarchy that takes into account the probability distribution on the demands.Roughly speaking,the Di?use Price of Anarchy is the worst-case,over all allowed probability distributions,of the expectation(according to each speci?c probability distribution)of the ratio of Social Cost over Optimum in the worst-case Nash equilibrium.

The Fair Pricing model,introduced by[MPS05a],was originally motivated by the stan-dard KP-model for sel?sh routing;it departs from it by encompassing some stochastic assumptions on user demands,and notions of pricing and fairness as well.

In the same work,it was proved that pure Nash equilibria may not exist,unless all chosen demands are identical;in contrast,a fully mixed Nash equilibrium exists for all possible choices of the demands.Further on,it was proved that the fully mixed Nash equilibrium is the unique Nash equilibrium in case there are only two agents.It was also shown that,in the worst-case choice of demands,the Price of Anarchy isΘ(n);for

the special case of two agents,the Price of Anarchy is less than2?1

m .Assume now

that demands are drawn from a bounded,independent probability distribution,where all demands are identically distributed and each is at most a(universal for the class)constant times its expectation.Then,it is proved in[MPS05a]that the Di?use Price of Anarchy is at most that same constant,which is just2when each demand is distributed symmetrically around its expectation.

In a subsequent work[MPS05b],the authors consider two other cost sharing mechanisms which are closely related to the Fair Pricing model,namely the Average Cost Pricing and the Serial Cost Sharing models.There,it is proved that pure Nash equilibria do exist for both of these cost sharing mechanisms.

The Fair Pricing model in[MPS05a,MPS05b]provides a concrete?rst step toward a systematic way of treating such cost mechanisms for pricing the competitive usage of multiple resources in large-scale networks like the Internet.

6Network Security Games

The recent huge growth of public networks(such as the Internet)has given to Network Security great importance and an even more critical role[Sta03].The highly dynamic, distributed nature and the huge size of public networks and future networks impose the need of new advances,methods and tools for the e?cient management of network security issues.Most current and future networks may not be considered to be absolutely secured. The system security software can no longer be assumed to have a global access to the network;rather,at any time,insecure network entities may join the network causing a possible viruses infection.

[ACY05]and[KO04]studied network security problems modeling them as Interdepen-dent Security games.In such a game,a large number of players must make individual investment decisions related to security,in which the ultimate safety of each participant may depend in a complex way on the actions of the entire population.In[ACY05],the authors establish connections of the game considered with variants of a Graph Partition https://www.wendangku.net/doc/522666230.html,ing them they provide polynomial-time computable Nash equilibria and prove NP-hardness of?nding the best equilibria(with respect to a suitable Social Cost they de?ned).

The work of[FGY00]studies the feasibility and computational complexity of two privacy tasks in distributed environments with mobile eavesdroppers:those of distributed database maintenance and message transmission.A mobile eavesdropper is a computationally un-bounded adversary that move its bugging equipment within the system.However,this

work does not utilize Graph-Theoretic tools.In contrast,[AKPW95]employs Graph-Theoretic tools to study a two-player game on a graph.It establishes connections of the problem with the k-server problem and provides an approximate solution for a simple as-sociated network design problem.However,this study does not concern network security problems.

[MPPS05b]considers a security problem on a distributed network modeling it as a multi-player non-cooperative game with attackers(e.g.,viruses)and a defender(e.g.,a security software)entities.The authors exploit both game-theoretic and graph-theoretic tools for studying the associated Nash equilibria.

6.1A Graph-Theoretic Model

[MPPS05b],considers a distributed network whose nodes are insecure and vulnerable to infection by harmful entities(e.g.,viruses,worms,trojan horses,eavesdroppers[FGY00]), called the attackers.A system security software,the defender,is available in the system. However,due to the network size and for economic and performance reasons,it is capable to provide safety(that is,clean nodes from the possible presence of attackers)only in a limited part of the network(e.g.,a small set of edges).

At any time,attackers and the defender take individual decisions,based on limited information due to the distributed nature of the system,for their placement in the network, seeking to maximize their(opposite)objectives.In particular,each attacker targets a location(i.e.,a node)of the network via a probability distribution;the node is damaged unless it is cleaned by the defender.The defender is able to clean a link or a set of links, which it may choose using a probability distribution.Such limitations are due to?nancial costs,such as the cost of purchasing a global security software,or due to performance reasons,such as the reduced e?ciency or usability of the protected network part.The selection of the defender seeks to protect the network as much as possible,while the harmful entities wish to avoid being caught so as to be able to damage the network.Thus, it is reasonable to view the problem as a non-cooperative game with players of con?icting interests.

[MPPS05b]assumes the most basic case of the problem scenario,where the defender is able to clean only a single edge of the network.Then,the problem is modeled as a non-cooperative,multi-player strategic game played on a graph.The game is played on a graph with two kinds of players:the vertex players,which can choose a node of the network, represent the attackers,and the defender,called the edge player,which can choose a single edge of the network and represent the system security software.The defender seeks to maximize the expected number of vertex players it catches,while each vertex player seeks to maximize the probability of escaping the defender.The resulting game is called the Edge model.

Such a modeling captures the simplest case of the problem.At the same time,its simplicity enables a relative ease for exploring the problem using graph-theoretic tools. For this game,the associated Nash equilibria,where no network entity can unilaterally improve its local objective are of interest.

For the edge model in[MPPS05b],it is proved that no instance of the game has a pure Nash equilibrium.The authors then proceed to study mixed Nash equilibria.A graph-theoretic characterization of mixed Nash equilibria is provided.Roughly speaking,the characterization implies that the support of the edge player and the vertex players are an edge cover and a vertex cover of the graph.Given the supports,the characterization provides a system of equalities and inequalities to be satis?ed by the probabilities of the players.Unfortunately,this characterization only implies an exponential time algorithm

for the general case.

The same work introduced a subclass of Nash equilibria,called matching Nash equilibria, which are a natural subclass of mixed Nash equilibria with a graph-theoretic de?nition. Roughly speaking,the supports of vertex players in a matching Nash equilibrium form together an independent set of the graph,while each vertex in the union of supports of the vertex players is incident to only one edge from the support of the edge player.

A characterization of graphs admitting a matching Nash equilibrium is then provided. It is proved that a matching Nash equilibrium can be computed in linear time for any graph satisfying the characterization once a suitable independent set is given for the graph. The authors proceed to consider bipartite graphs for which they show that they satisfy the characterization of matching Nash equilibria;hence,they always have one.More importantly,it is proved that a matching Nash equilibrium can be computed in polynomial time for bipartite graphs.

In a subsequent work[MPPS05a],the authors proceed to studying the same problem on other graph families.Utilizing graph-theoretic arguments and the characterization of mixed Nash equilibria proved in their earlier work,they show how to compute in poly-nomial time mixed Nash equilibria on corresponding graph instances.The graph families considered are regular graphs,graphs with polynomial time computable r-regular factors, and graphs with perfect matchings.

In the same work,the Social Cost of the game is de?ned to be the expected number of attackers caught by the protector.It is proved that the corresponding Price of Anarchy in any mixed Nash equilibria of the Edge model is upper and lower bounded by a linear function of the number of vertices of the graph.Finally,[MPPS05a]considers a more generalized variation of the problem,captured by the Path model.It is there proved that the problem of existence of a pure Nash equilibrium is NP-complete for this model.

6.2A Generalized Model

[GMP+05]introduced and studied a generalized version of the network security problem considered in[MPPS05b].In more detail,the authors in[GMP+05]consider a more general case of the Edge model where the defender is able to scan a set of k links of the network;this generalization is called the Tuple model.It is natural to expect that this increased power of the defender should result in a better quality of protection for the network.Ideally,this would be achieved at little expense on the existence and complexity of Nash equilibria.

In that work,it is proved that the existence problem for pure Nash equilibria is solvable in polynomial time.Then,the authors provide a graph-theoretic characterization of mixed Nash equilibria.

Inspired by matching Nash equilibria,the authors of[MPPS05b]introduce k-matching con?gurations that generalize matching con?gurations.They provide a polynomial-time reduction for transforming any matching Nash equilibrium of any instance of the Edge model to a k-matching Nash equilibrium on a corresponding instance of the Tuple model, and vice https://www.wendangku.net/doc/522666230.html,ing the polynomial-time reduction,they provide a characterization of graphs admitting k-matching Nash equilibria.Furthermore,a polynomial-time algorithm for computing k-matching Nash equilibria on graphs satisfying the characterization is provided.The applicability of the algorithm is demonstrated for the case of bipartite graphs.

In the same work,it is established that the increased power of the defender results in an improved quality of protection of the network.In particular,for the case of k-matching Nash equilibria,it is proved that the gain of the defender,which amounts to the expected

北大青鸟：详细设计说明书

招聘网站设计项目详细设计 第一部分、引言 1.1编写目的 本说明在概要设计的基础上，对招聘网站设计项目的各模块、页面、脚本分别进行了实现层面上的要求和说明。 软件开发小组的产品实现成员应该阅读和参考本说明进行代码的编写、测试。 1.2背景 说明： A、软件系统的名称：招聘网站设计项目 B、任务提出者：668Job在线科技发展有限公司 开发者：北大青鸟Aptech产品开发部 本项目将实现668Job的原型部分，并且在该原型的基础上进行功能的扩展和需求的界定，最终完成的版本将在https://www.wendangku.net/doc/522666230.html,网站上使用。提供互联网上的求职、招聘登记和搜索服务。 C、本系统将存储用户信息，668Job将与其他的系统共享这些注册信息，共享的系统可能是 668Job电子邮件系统、668Job电子杂志分发系统。 这些系统之间不提供应用程序级别的接口，数据共享通过SQL Server数据库表的公共访问来实现。 本系统将使用SQL Server 2000作为数据库存储系统，SQL Server 2000企业版将由668Job自行购买。 1.3定义 IPO图——输入/处理/输出图，一般用来描述一个程序的功能和机制；

1.4参考资料 相关的文件包括： A、湖人诊所的内部文件《核准招聘网站设计项目》； B、《招聘网站设计项目需求说明》； C、《招聘网站设计项目项目开发计划》； D、《招聘网站设计项目概要设计》； 参考资料： A、北大青鸟Aptech ACCP3.0 Sem2《基于软件开发项目的毕业设计》； B、北大青鸟Aptech ACCP3.0 Sem2《ASP程序设计》； C、国家标准《详细设计说明书（GB8567——88）》； D、莱克公司的人力资源管理项目的详细设计说明； 合同： A、《招聘网站设计项目合同20031102 - 54》； （说明：不同的文档都有第一部分类似的引言部分，这样是为了文档能够在独立使用的时候，能够提供足够的背景信息。）

软件工程项目管理计划书 完整版

储蓄业务项目管理计划书 1．简介 项目概述 本项目要开发一个银行系统，系统一共分为储蓄业务、贷款业务、外汇交易、网上银行、信用卡业务和系统管理六个子系统。本团队负责其中的有关储蓄业务 的子系统。通过团队合作开发整个子系统，使团队成员获得软件工程开发的实际训练。本系统采用目前主流的B/S开发架构，将与整个银行系统一起发布。不单独发布。交付的产品包括可执行的文件、源代码、技术文档与用户使用手册等。本系统的开发过程中的主要工作是子系统需求分析、系统总体设计、子系统源代码开发、子系统测试、交付团长进行最后的集成、整个系统的测试。关键里程碑是制定项目管理计划书、制定需求设计规格说明书初稿、制定系统设计报告的初稿、进行子系统运行情况的检查与测试、进行系统集成后的运行情况的检查与测试。项目所需工具是个人电脑和开发工具。进度为11周，工程量为3人/天。 项目范围说明 （1）提交文档：项目管理计划、需求规格说明，设计报告、测试报告、用户使用手册和项目个人总结。其中项目总结为每人一份，每个小组所有成员的总结装订在一起；其余文档每组提交一份。每个团队可将各小组的文档综合到一起，各小组也可自行分开提交，具体方式由团队内部协商确定。所有文档需要提交电子版和打印稿。 （2）源程序检查：一共两次。第一次检查每个小组的子系统运行情况。第二次检查每个团队内六个小组集成后完整的银行系统运行情况，检查完成后需要提交程序源文件和可执行的系统。程序检查安排在上机时间进行。 软件项目计划书的演化 软件项目计划书在第三周周末前经由小组讨论、共同撰写、汇总整合三步骤形成初稿，第四周以后根据项目的进展可以对其进行修改，需要有组员提出修改意，在全体会上讨论通过，并由组长整理修改意见并作出相应的修改。其余组员同步获得更新稿。 2．项目组织管理 过程模型 表1.过程模型表 团队的分工与合作

小学语文课文《唯一的听众》

小学语文课文《唯一的听众》 用父亲和妹妹的话来说，我在音乐方面简直是一个白痴。这是他们在经受了我数次"折磨";之后下的结论。在他们听来，我拉小夜曲就像在锯床腿。这些话使我感到十分沮丧，我不敢在家里练琴了。我发现了一个练琴的好地方，楼区后面的小山上有一片树林，地上铺满了落叶。 一天早晨，我蹑（niè）手蹑脚地走出家门，心里充满了神圣感，仿佛要去干一件非常伟大的事情。林子里静极了。沙沙的足音，听起来像一曲悠悠的小令。我在一棵树下站好，庄重地架起小提琴，像举行一个隆重的仪式，拉响了第一支曲子。但我很快又沮丧起来，我觉得自己似乎又把锯子带到了树林里。 我感觉到背后有人，转过身时，吓了一跳：一位极瘦极瘦的老妇人静静地坐在木椅上，平静地望着我。我的脸顿时烧起来，心想，这么难听的声音一定破坏了这林中的和谐，一定破坏了这位老人正独享的幽静。 我抱歉地冲老人笑了笑，准备溜走。老人叫住了我，说："是我打扰了你吗，小伙子？不过，我每天早晨都在这儿坐一会儿。";一束阳光透过叶缝照在她的满头银丝上，"我想你一定拉得非常好，可惜我的耳朵聋了。如果不介意我在场，请继续吧。"; 我指了指琴，摇了摇头。意思是说我拉不好。 "也许我会用心去感受这音乐。我能做你的听众吗，每天早晨？"; 我被老人诗一般的语言打动了。我羞愧起来，同时有了几分兴奋。嘿，毕竟有人夸我了，尽管她是一个聋子。我拉了起来。以后，每天清晨，我都到小树林去练琴，面对我唯一的听众，一位耳聋的老人。她一直很平静地望着我。我停下来时，她总不忘说上一句："真不错。我的心已经感受到了。谢谢你，小伙子。";我心里洋溢着一种从未有过的感觉。

很快我就发觉自己变了。我又开始在家里练琴了。从我紧闭门窗的房间里，常常传出基本练习曲的乐声。我站得很直，两臂累得又酸又痛，汗水湿透了衬衣。以前我是坐在木椅上练琴的。同时，每天清晨，我要面对一位耳聋的老人尽心尽力地演奏；而我唯一的听众总是早早地坐在木椅上等我。有一次，她说我的琴声能给她带来快乐和幸福。我也常常忘记她是聋子，只看见老人微笑着靠在木椅上，手指悄悄打着节奏。她慈祥的眼神平静地望着我，像深深的潭水 我一直珍藏着这个秘密，直到有一天，我的一曲《月光》奏鸣曲让专修音乐的妹妹大吃一惊。妹妹追问我得到了哪位名师的指点。我告诉她："是一位老太太，就住在12号楼，非常瘦，满头白发，不过--她是个聋子。"; "聋子？";妹妹惊叫起来，"聋子！多么荒唐！她是音乐学院最有声望的教授，曾是乐团的首席小提琴手！你竟说她是聋子！"; 后来，拉小提琴成了我无法割舍的爱好，我能熟练地拉许多曲子。在各种文艺晚会上，我有机会面对成百上千的观众演奏小提琴曲。那时，我总是不由得想起那位"耳聋";的老人，那清晨里我唯一的听众

北大青鸟软件开发课程

学软件开发，找软件工程师培训学校，北京哪家较好？学软件开发已经受到了广大初高中毕业生的青睐，作为北京地区的学生，选择在哪个学校学习软件开发已经成为广大考生迷惑的问题。而众所周知的北大青鸟软件开发课程是最好的，自然学软件开发去北京北大青鸟佳音校区！ 20世纪90年代以来，全球软件行业作为新兴产业，每年以平均13%的发展速度增长，中国处于价值链低端，产业态需要，国际软件行业的发展，迫使中国软件产品发展迫在眉睫。我国软件产品的整体技术含量和价值含量都比较低，需要培养高素质软件开发人员。国际化产业的需求，国家人才的缺乏导致软件开发成为近年来年较热门的IT专业。 那么我们为什么要选择北京北大青鸟佳音校区软件开发专业呢？其优势如下： 第一、课程系统，全面 北京北大青鸟佳音校区提供的不是单科的培训，而是系统的，全面的软件开发技术的培训，所有课程结构循序渐进。 第二、课程轻重分明 本课程重点是培养Java高级工程师和.net高级工程师，北京北大青鸟佳音校区的宗旨是“让学精一门语言，然后培养学生融会贯通的思想，学活其他语言”，因为软件的发展日新月异，学生只有学

活了程序设计语言，毕业后才能适应软件开发工作，才能在这领域里有所突破。 第三、采用“产学元方式教学” 北京北大青鸟佳音校区在平常的教学过程中，尽可能的将教学内容和企业发展相结合，学生时常可以去企业实践、用课本上的知识来为企业服务，用企业的先进技术带动学校的发展。真正做到学有所长、学有所用。 第四、培养扎实的理论基础 北京北大青鸟佳音校区不仅提供专业编程知识，同时，为了锻炼学生逻辑思维，还设置其他相应课程，比如：高数等，为了让学生全面掌握计算机软件，我们还开设了数据结构、操作系统等课程，为学生的进一步的学习。 第五、实践性强，针对性强 北京北大青鸟佳音校区的课程是与企业完全同步的，每个实践例子都是经过行业专家长期研讨开发出来的，因此在内容组织上，授课方式上都有成熟而先进的经验，确保学员“能够学会”，“学会了能够就业”。 第六、我们重视理论+实践，也注重职业素养的培养。 北京北大青鸟佳音校区的课程关注企业所注重的职业素养的培训，在班级管理，就业训练上都有专门的人员进行负责，保证项目经

《软件项目管理计划书》最佳模板

软件项目管理计划书 项目名称： 时间：年月日

目录 1.简介 (3) 1.1.项目概述 (3) 1.2.项目主要功能及性能 (3) 1.3.项目交付产品 (3) 1.4.参考资料 (3) 2.项目组织 (3) 2.1.过程模型 (3) 2.2.团队的分工与合作 (4) 3.管理过程 (4) 3.1.管理目标及优先级 (4) 3.2.风险管理 (5) 3.3.监督及控制机制 (5) 3.4.人员计划 (5) 3.5.培训计划 (6) 3.6.风险管理计划 (6) 3.7.项目配置计划 (7) 3.8.计划更新策略 (7) 3.9.项目沟通计划 (8) 3.9.1.项目组会议 (8) 3.9.2.项目报告机制 (8) 3.10.项目的重用计划 (9) 3.11.质量保证活动 (9) 3.11.1.内部审核 (9) 3.11.2.阶段审核 (10) 4.技术过程 (10) 4.1.开发工具、方法和技术 (10) 4.2.软件需交付的文档 (10) 5.开发进度安排及预算 (11) 5.1.进度表格描述 (11) 5.2.开发过程中的资源需求 (11) 5.3.软件管理过程中预算及资源分配 (12) 5.4.项目进度及关键工期设置 (12)

1.简介 1.1.项目概述 1.2.项目主要功能及性能 1.3.项目交付产品 （1）提交文档：项目管理计划、需求规格说明，设计报告、测试报告、用户使用手册和项目个人总结。其中项目总结为每人一份，每个小组所有成员的总结装订在一起；其余文档每组提交一份。每个团队可将各小组的文档综合到一起，各小组也可自行分开提交，具体方式由团队内部协商确定。所有文档需要提交电子版和打印稿。 （2）源程序检查：一共 1.4.参考资料 2.项目组织 2.1.过程模型

项目管理计划书-经典模板

XX Project Plan XX工程计划 Prepared by 拟制Date 日期 yyyy-mm-dd Reviewed by 审核Date 日期 yyyy-mm-dd Approved by 批准Date 日期 yyyy-mm-dd

Revision record 修订记录 Distribution LIST 分发记录

Catalog目录 7 1 1 Introduction 简介 7 .1目的 7 .2范围 7 .3参考资料 7 22Resource Summary资源概述 8 33Project specific software Processes 工程特定的软件过程 8 4 4 Project Scope工程范围 8 5 5 Deliverables交付件 8 .4 Customer Deliverables给客户的交付件 8 .5 Internal Deliverables内部交付件 8 6 6 Organization and Responsibilities组织和职责 10 77 Estimated Size /Effort/schedule规模/工作量/进度的估计 10 .6 size估计的规模 10 .7 effort估计的工作量 11 .8 schedule估计的进度 11 88 Project resource required 工程所需资源 11 .9 Requirement 设备需求 11 .10 tools 软件工具 12 .11文档资料 12 .12 Supplied Products 需要客户提供的产品 12 .13人员需求 12 .14差旅

项目管理年度计划模板(规范版)3篇

项目管理年度计划模板(规范版)3篇Annual project management plan template (normative version) 汇报人：JinTai College

项目管理年度计划模板(规范版)3篇 前言：工作计划是对一定时期的工作预先作出安排和打算时制定工作计划，有了工作计划，工作就有了明确的目标和具体的步骤，大家协调行动，使工作有条不紊地进行。工作计划对工作既有指导作用，又有推动作用，是提高工作效率的重要手段。本文档根据工作计划的书写内容要求，带有规划性、设想性、计划性、方案和安排的特点展开说明，具有实践指导意义。便于学习和使用，本文档下载后内容可按需编辑修改及打印。 本文简要目录如下：【下载该文档后使用Word打开，按住键盘Ctrl键且鼠标单击目录内容即可跳转到对应篇章】 1、篇章1：项目管理年度计划样本标准版 2、篇章2：项目管理年度计划例文(通用版) 3、篇章3：项目管理年度计划范文标准版 篇章1:项目管理年度计划样本标准版 一、工程项目管理部人员工作计划 1.制定工程部门制度及岗位责任制，明确各岗位职责。 2.参与施工图纸会审工作。 3.主持施工方案、总进度计划、质量控制计划的编制工作，以及工程项目划分、见证计划的审批工作。

对各项质量目标进行细化、量化分析，有针对性编制各 个工程项目的质量控制计划并监督实施。 4.工程项目管理部人员自身要认真学习GB/T 19001标准、公司质量管理手册内容及各相关施工质量规范，严格现场管理，对重要部位、关键技术、控制难度大、影响大、经验欠缺的施工内容及新材料、新工艺、新技术、新设备列为质量控制点，实行重点控制，发现偏差及时纠偏。 5.定期对项目部的质量、安全、进度等情况进行检查。 二、对项目部的检查工作计划 1、质量管理方面 （1）检查项目部质检员、实验员、资料员、测量员等技 术人员的持证上岗情况及对该岗位工作的熟悉情况，无证从事质量管理岗位的人员进行取证学习，尽量杜绝无证上岗;对于 持证人员进行在岗培训，不断更新知识以适应现在越来越的工程采用新工艺、新技术、新材料的技术要求。 （2）人员培训计划，为提高工程中质量管理水平，必须 使质量管理岗位人员具备相应的质量管理能力，首先要求无证从事质量管理岗位的人员进行取证学习，尽量杜绝无证上岗;

软件项目管理项目计划书

湖南文理学院实验报告 时间：2013年12月3日 课程名称：软件项目管理 实验名称：xx学院毕业生就业信息管理系统项目计划书 班级：姓名：同组人： 指导教师评定：签名： 一、实验目的 掌握项目计划书的格式和写作要求，会结合具体项目写作项目计划书。 二、实验要求 1、结合模拟项目写出项目计划书。 2、提交项目计划书一份。 三、实验环境 1．硬件：计算机 2．操作系统：windows平台。 3．相关软件：Microsoft office软件。 四、实验内容 1 引言 1.1 编写目的 为了保证项目团队按时保质地完成项目目标，便于项目团队成员更好地了解项目情况，使项目工作开展的各个过程合理有序，因此以文件化的形式，把对于在项目生命周期内的工作任务范围、各项工作的任务分解、项目团队组织结构、各团队成员的工作责任、团队内外沟通协作方式、开发进度、经费预算、项目内外环境条件、风险对策等内容做出的安排以书面的方式，作为项目团队成员以及项目干系人之间的共识与约定，项目生命周期内的所有项目活动的行动基础，项目团队开展和检查项目工作的依据。 1.2 背景 项目的名称：xx学院毕业生就业信息管理系统。

项目的委托单位：xx学院计算机科学与技术学院软件开发部。 项目的用户（单位）：xx学院各届毕业生。 项目的任务提出者：xx学院计算机科学与技术学院软件开发部。 项目的主要承担部门：xx学院计算机科学与技术学院软件开发部。 项目建设背景：通过本系统可以使xx学院毕业生就业信息管理工作更加合理化、科学化，提高工作的效率，从根本上改变就业管理工作的方式，通过Internet，各院系和学生利用网络的便利，可以直接查询和提交就业信息。在这种系统平台下，可以快速、有效、全面的反映最新的用人单位信息、毕业生基本信息和就业趋势，及时提供高校学生工作管理人员对历届用人单位需求信息的分析统计，及时有效地调查分析大学毕业生的择业趋势和引发的心理问题并进行及时有效的就业指导。可以做到信息的规范管理、科学统计和快速查询，从而减少管理方面的工作量。 1.3定义 Microsoft SQL Server2008：数据库开发环境 Visual Studio 2010：程序开发环境 1.4参考资料 [1]朱少民.软件过程管理.北京：清华大学出版社，2007 [2]朱少民.软件质量保证和管理.北京：清华大学出版社，2007 [3]韩万江，姜立新.软件开发项目管理.北京：机械工业出版社，2004 [4]Harold Kerzner,杨爱华，等.项目管理—计划、进度和控制的系统方法.第9版.北京： 电子工业出版社，2006. 1.5标准、条约和约定 《计算机科学与技术学院毕业生就业信息管理系统立项建议书》 《计算机科学与技术学院毕业生就业信息管理系统项目任务书》 《计算机科学与技术学院毕业生就业信息管理系统项目履行合同》 2、项目概述

六年级上册《唯一的听众》课文内容

六年级上册《唯一的听众》课文内容 用父亲和妹妹的话来说，我在音乐方面简直是一个白痴。这是他们在经受了我数次“折磨”之后下的结论。在他们听来，我拉小夜曲就像在锯床腿。这些话使我感到十分沮丧，我不敢在家里练琴了。我发现了一个练琴的好地方，楼区后面的小山上有一片树林，地上铺满了落叶。 一天早晨，我蹑（niè）手蹑脚地走出家门，心里充满了神圣感，仿佛要去干一件非常伟大的事情。林子里静极了。沙沙的足音，听起来像一曲悠悠的小令。我在一棵树下站好，庄重地架起小提琴，像举行一个隆重的仪式，拉响了第一支曲子。但我很快又沮丧起来，我觉得自己似乎又把锯子带到了树林里。 我感觉到背后有人，转过身时，吓了一跳：一位极瘦极瘦的老妇人静静地坐在木椅上，平静地望着我。我的脸顿时烧起来，心想，这么难听的声音一定破坏了这林中的和谐，一定破坏了这位老人正独享的幽静。 我抱歉地冲老人笑了笑，准备溜走。老人叫住了我，说：“是我打扰了你吗，小伙子？不过，我每天早晨都在这儿坐一会儿。”一束阳光透过叶缝照在她的满头银丝上，“我想你一定拉得非常好，可惜我的耳朵聋了。如果不介意我在场，请继续吧。”

我指了指琴，摇了摇头。意思是说我拉不好。 “也许我会用心去感受这音乐。我能做你的听众吗，每天早晨？” 我被老人诗一般的语言打动了。我羞愧起来，同时有了几分兴奋。嘿，毕竟有人夸我了，尽管她是一个聋子。我拉了起来。以后，每天清晨，我都到小树林去练琴，面对我唯一的听众，一位耳聋的老人。她一直很平静地望着我。我停下来时，她总不忘说上一句：“真不错。我的心已经感受到了。谢谢你，小伙子。”我心里洋溢着一种从未有过的感觉。 很快我就发觉自己变了。我又开始在家里练琴了。从我紧闭门窗的房间里，常常传出基本练习曲的乐声。我站得很直，两臂累得又酸又痛，汗水湿透了衬衣。以前我是坐在木椅上练琴的。同时，每天清晨，我要面对一位耳聋的老人尽心尽力地演奏；而我唯一的听众总是早早地坐在木椅上等我。有一次，她说我的琴声能给她带来快乐和幸福。我也常常忘记她是聋子，只看见老人微笑着靠在木椅上，手指悄悄打着节奏。她慈祥的眼神平静地望着我，像深深的潭水…… 我一直珍藏着这个秘密，直到有一天，我的一曲《月光》奏鸣曲让专修音乐的妹妹大吃一惊。妹妹追问我得到了哪位名师的指点。我告诉她：“是一位老太太，就住在12号楼，非常瘦，满头白发，不过——她是个聋子。”

北大青鸟网上商城项目开发计划

北大青鸟网上商城系统项目开发计划

J2EE第三小组 目录 1．引言 (2) 1.1编写目的 (2) 1.2项目背景 (3) 1.3定义 (3) 1.4参考资料 (3) 2．项目概述 (5) 2.1工作内容 (5) 2.2条件与限制 (5) 2.3产品 (5) 2.4运行环境 (5) 2.5服务 (6) 2.6验收标准 (6) 3．实施计划 (7) 3.1任务分解 (7) 3.2进度 (7) 3.3预算 ...................................................................................... 错误！未定义书签。 3.4关键问题 ............................................................................... 错误！未定义书签。4．人员组织及分工. (7) 5．交付期限 (8) 6．专题计划要点 (8) 1．引言 1.1编写目的 本计划提供一份合理的项目开发进程表,使所有的开发人员任务明确,步调一致,最终共同准时的完成项目.软件工程的目标是提高软件质量,本计划也是从软件的正确性,性能,易用性,灵活性,可重复性,可理解性等各个方面出发,以提高软件质量为最终目的而制定.读者为参与开发的所有相关人员.

1.2项目背景 说明： A、软件系统的名称：北大青鸟网上商城系统 B、任务提出者：北大青鸟J2EE九月班第三小组 C、开发者：北大青鸟J2EE九月班第三小组 实现完成的系统将作为北大青鸟珠在线销售系统使用，所应用的网络为Internet网络。 D、本系统将是独立的系统，所产生的输出独立。 本系统将使用Oracle9i作为数据库存储系统. 1.3定义 1.4参考资料 相关的文件包括： A、内部文件《北大青鸟网上商城电子商务系统案例研究项目》； B、北大青鸟网上商城电子商务系统案例研究项目分析会议备忘录； C、《北大青鸟网上商城电子商务系统案例研究项目可行性分析》； 参考资料： A、北大青鸟Aptech ACCP3.0 Y2《基于软件开发项目的毕业设计》； B、国家标准《软件需求说明书（GB856T——88）》； C、亚马逊网站的软件需求说明； 合同： A、《北大青鸟网上商城电子商务系统案例研究项目合同20040510 - 2》；

软件项目管理计划模板

. 软件项目管理计划 Version 1.2专业资料word . Revision 专业资料word . 录目 1. 简介1 项目概述1.1 1.2 项目交付产品1 SPMP 的演化1.3 1 参考资料1.4 1 1.5

术语与缩写1 1 2. 项目组织 1 2.1 过程模型2. 2 组织结构1 2. 3 组织接口1 2.4 项目职责2 2 管理过程3. 3 3.1 管理目标和优先级3.2 假设、依赖关系和限制3 风险管理3.3 3 监督和控制机制3.4 3 3.5 人员计划3 3 4. 技术过程 4 方法、工具和技术4.1 软件文档4.2 4 用户文档4.3 4 4.4 项目支持功能4 4 工作包、进度表和预算5. 4 工作包5.1 依赖关系5.2 4 资源需求5.3 4 预算和资源分配5.4 4 5.5 进度表4 6. 其他索引 6.1 4 6.2 附录 4 专业资料word . 1. 简介 1.1 项目概述 说明：简要综述项目的目标、发布的产品、主要工作活动、主要工作制品、关键里程碑、所需资源、进［度和预算等。必要的情况下，还应描述该项目与其他项目的关系。］ 1.2 项目交付产品

说明：列出主要的可交付产品、交付日期、交付地点和满足项目协议条款所需的质量。］［的演化SPMP1.3 说明：描述如何以及由谁负责维护本文档，应指明更新内容的传播方式以及在变更控制下更新文档版本[ 的机制。］ 1.4 参考资料 说明：提供项目计划中所引用的所有文档和其他信息资源的完整清单，包括标题、报告编号、日期、作[ 者以及发布机构。］ 1.5 术语与缩写 说明：定义SPMP 所应用的全部术语和缩写词。］［ 2. 项目组织 2.1 过程模型 说明：描述该项目所使用的软件过程模型，或者是所遵循的组织标准模型。过程模型需要指明［里程碑的时间、基线、评审、工作制品、项目交付产品、结束标志等。］ 2.2 组织结构 说明：描述项目的内部组织结构，可以参考如下的层次结构图形式。］［专业资料word .

《唯一的听众》教案.doc

《唯一的听众》教案 学习目标 1、学习本课生字、新词，摘录印象深刻的句子。2、有感情地朗读课文，把握课文内容。 3、体会老教授对“我”的鼓励、给“我”带来的变化，感受人与人之间真情的美好。4、环境描写、人物心理描写的作用。教学目标1．学会6个生字。正确读写“神圣、悠悠、庄重、仪式、抱歉、溜走、介意、追问、荒唐、声望、割舍、大吃一惊”等词语。2．有感情地朗读课文。提出不懂的问题与同学讨论。抄写印象深刻的句子。3．理解课文内容，引导学生从老教授的言行与“我”的心理、行动变化两方面感受人对“我”的爱护、鼓励，以及“我”对她的敬佩、感激之情。教学重点引导学生从老教授的言行与“我”的心理、行动变化两方面感受老人对“我”的爱护、鼓励，以及“我”对她的敬佩、感激之情。教学准备：课件。教学时间：两课时教学过程：第一课时一、导入1．播放《月光奏鸣曲》。同学们，刚才你们听的这首小提琴曲美吗？大家听得多认真、多投入呀！你们，就是这首曲子的──听众（板书）可是，曲子好听琴难拉。有一位小提琴的爱好者，刚开始，他拉出的小夜曲，被人当作是锯桌腿的声音，他感到十分沮丧和灰心，但是后来，他成功了，这都是得益于他的那位──唯一的听众。板书：唯一的（理解词

语）2．齐读课题，质疑：同学们，读了课题，你最想问什么？同学们可真会提问题，老师把大家的问题归纳一下，不外乎这两个：“唯一的听众”是指谁？ “唯一的听众”她做了什么事情？二、初读课文1．那么，你有什么好办法解决这两个问题呢？（好好地读读课文）。2．下面就请同学们自读课文，要求能够读准字音，读通课文，读的时候也不要忘记想想这两个问题的答案。学生自由朗读课文3．现在这两个问题，你能解决吗？（1）“唯一的听众”是指谁？相机板书：老妇人这是一个怎样的老妇人呢？请同学们快速 浏览课文，找出文中相关的句子。交流： （）的老妇人（一位极瘦极瘦的老妇人静静地坐在木椅上，平静地望着我。）（2）“唯一的听众”她做了什么事情？（父亲和妹妹说“我”在音乐方面是个白痴，使“我”十分沮丧，不敢在家中练琴。于是“我”到林中练琴，遇到一位自称耳聋的老妇人，她猜想“我”拉得很好，并愿意天天做“我”的听众。每次“我”停下练琴，她总是夸奖“真不错”。在她的鼓励下，“我”找回了自信，又回到家中练琴。最后写“我”从妹妹那儿知道了老妇人的真实身份，心灵受到震撼。后来拉小提琴成了“我”无法割舍的爱好，每次演出时总会想起这位德高望重的老人。） 4、老师还要检查一下大家对字词的预习情况白痴荒唐声望沮丧绝望懊恼神圣

北大青鸟.网络工程师.2.0 【试题】2.20

1、在Red Hat Enterprise Linux 4.0系统中，下列提高工作效率的功能中，（）不是bash的功能。（选一项） A 命令行补齐 B 别名 C 使用鼠标复制和粘贴 D 命令历史 2、在Dreamweaver MX中，为了使站点内的页面风格统一，经常使用到模板，以下有关模板的说法正确的是（）。（选一项） A 模板就是库项目 B 模板保存后不能进行修改 C 在模板中可以包含图像、表格等对象 D 模板修改后，必须手动更新应用该模板的网页 3、公司网络采用Windows server 2003单域模式进行管理，要实现域用户user 在域中任意一台计算机上登录时都显示同样的桌面环境，应在用户属性的（）标签中设置。（选一项） A 常规 B 终端服务配置文件 C 环境 D 配置文件 4、在RHEL4系统中，要实现磁盘配额，必须在系统中安装quota软件包，要查询该软件包是否已在当前系统中安装，可以使用的命令是（）。（选一项） A rpm -q quota B rpm -ivh quota C rpm -e quota D rpm -U quota 5、为了确保自身的安全，计算机病毒会采取一些手段来伪装自身，逃避防病毒系统的检查，这体现了病毒的（）特点。（选一项） A 非授权执行性 B 传染性 C 隐蔽性 D 潜伏性 6、某公司网络采用Windows server 2003单域结构进行管理，文件资料分布在域中的多台服务器上，采用（）技术可以使所有文件资料看似存储在一台服务器上。（选一项） A DFS B DNS C DHCP D VPN

7、你是一个Windows server 2003域的管理员，现在你需要创建一个通用安全组帐号，则必须要求域的模式为（）。（选二项） A Windows 2000 混合模式 B Windows2000 纯模式 C Windows Server 2003 模式 D Windows 混杂模式 8、 IOS是Cisco网络设备上运行的操作系统，作为初学者，小王（）可以显示当前模式下支持的所有命令。（选一项） A 使用“show history”命令 B 在提示符下直接输入？ C 在提示符下直接按下Tab键 D 使用“help？”命令 9、对硬盘分区并完成格式化后，就可以开始安装软件了，正确的顺序是（）。（选一项） A 先安装操作系统，再安装应用软件，最后安装驱动程序 B 先安装操作系统，再安装驱动程序，最后安装应用软件 C 先安装驱动程序，再安装操作系统，最后安装应用软件 D 只需要安装操作系统，不需要安装驱动程序 10、你是一个Windows server 2003网络的管理员，网络中有10个用户，部分用户需要能读取和修改ＮＴＦＳ分区上的文件和文件夹，而另外的用户不能对这些文件和文件夹有任何权限，你需要为这些用户设置访问授权，采取以下（）措施能使管理负担最小。（选一项） Ａ在ＮＴＦＳ分区上分别为这些用户帐号设置访问授权 Ｂ创建一个组帐号，将所有用户加入到组帐号中，在ＮＴＦＳ分区上为组帐号设置访问授权 Ｃ创建多个组帐号，将需要具备同样权限的用户加入到同一个组帐号中，在ＮＴＦＳ分区上为这些组帐号设置访问授权 11、在Dreamweaver MX制作的网页中，表单常用来收集用户的信息，如果希望用户能输入自己的信息，而不是在备选项中进行选择，可以使用（）表单元素。（选一项） A 文本区域 B 列表 C 单选按钮 D 复选框 12、在综合布线系统的水平子系统中，从信息插座到配线架的线缆总长度不能超过（）米。 （选一项） A 5 B 12

项目管理计划模板

项目管理计划模板

1目的 ......................................................................................................................................................... 2项目摘要 ................................................................................................................................................. 2.1项目目标和范围 ............................................................................................................................. 2.2主要干系人 ..................................................................................................................................... 2.3里程碑和可交付成果...................................................................................................................... 2.4约束 ................................................................................................................................................. 2.5假设 ................................................................................................................................................. 2.6项目组织结构 ................................................................................................................................. 3项目计划 ................................................................................................................................................. 3.1项目生命周期 ................................................................................................................................. 3.1.1生命周期确认............................................................ 3.1.2制定项目过程及产物裁剪.................................................. 3.2工作分解结构 .................................................................................................................................

唯一的听众教案

唯一的听众教案 篇一：唯一的听众 教案 《唯一的听众》教学设计 学习目标 1、学习本课生字、新词，摘录印象深刻的句子。 2、有感情地朗读课文，把握课文内容。 3、体会老教授对“我”的鼓励、给“我”带来的变化，感受人与人之间真情的美好。 4、环境描写、人物心理描写的作用。 课前准备 有关课件。 教学过程 一、板书课题，导入新课 文中的“唯一的听众”指的是谁？为什么称她为“唯一”的听众？ 二、初读课文，解决疑问

1、带着问题初读课文。 2、汇报交流。 三、再读课文，整体感知 1、读一读课文的开头和结尾，说说我在音乐方面发生了什么变化。 2、再读全文，结合课文内容概括“我”发生变化的原因。 3、概括课文主要内容。 四、以点带面，品味全文 1、浏览课文，找出描写老人神态的关键词。（平静） 2、描写老人神态平静的句子，总共出现了几次，在文中画出来。 课件出示： 一位极瘦极瘦的老妇人静静地坐在木椅上，平静地望着我。 她一直很平静地望着我。 她慈祥的眼睛平静地望着我，像深深的潭水?? （1）第一次“平静地望着我”。 ①在什么情况下，老妇人“平静地望着我”？对我产生了什么影响？

再读课文，并画出描写“我”的心理活动的语句。读一读，体会我的心理变化。（沮丧──充满了神圣感──沮丧──羞愧、兴奋） 可以联系上下文体会人物心理。如， 沙沙的足音，听起来像一曲悠悠的小令。（环境描写，侧面反映人物心理活动。） ②是谁给了我动力，让我的心理产生这么大的变化？ 划出描写老教授的语言的词句，读一读。 “是我打搅了你吗，小伙子？不过，我每天早晨都在这儿坐一会儿。” “我想你一定拉得非常好，可惜我的耳朵聋了。如果不介意我在场，请继续吧。” “也许我会用心去感受这音乐。我能做你的听众吗，每天早晨？” a．谈谈体会：从老人的几句话中，可以体会到老人的良苦用心，她在消除“我”的心理障碍。 b．练习读好这三句话。 ③出示“一位极瘦极瘦的老妇人静静地坐在木椅上，平静地望着我”。读一读，谈谈自己的感受。（老人在默默地鼓励我，在给我信心和继续练琴的勇气） (2)第二次“平静地望着我”。

北大青鸟软件开发主要学什么

软件开发是IT行业里的高薪职业之一，由于目前就业市场软件开发的人才稀缺，加上高薪的诱惑，吸引了越来越多的人转向了软件开发职业，那么要做软件开发工程师，需要学什么呢？ 软件开发是一项技术性很强的专业，对于没有基础的人来说，分层次分阶段分维度的学习，这样的效果会更好。这里以北大青鸟的软件开发培训课程为例。 北大青鸟的软件开发课程每18个月更新一次，目的是为了紧跟互联网时代的步伐。课程总共分为三个分阶段。每个阶段的课程知识讲解都贯穿了项目，并且为了锻炼学员们的动手能力，每个课程都会有项目案例训练，每一个阶段都会有阶段项目训练。 第一阶段为了强化学员语法和逻辑思维能力训练，注重学习方法和学习习惯的养成，培养团队意识和沟通表达能力。主要有以下这些课程

内容： 1. 课程内容：使用Java理解程序逻辑、使用HTML语言和CSS开发商业站点、C#语言和数据库技术基础、使用C#语言开发数据库应用系统、职业素质导向训练； 2.课程讲解贯穿的项目：MyShopping、MyBank、学生成绩管理系统、MySchoolBase、MySchool; 3.学员动手训练制作的项目案例：MyDVD 、V+网站、QQ数据库管理、QQ用户信息管理、超市商品管理； 4.阶段训练项目：MyKETV 学完这些课程，可胜任的工作岗位有JAVA初级开发工程师、商业网站开发、网页开发人员、即时沟通工具开发人员、非IT专业信息部门的管理信息系统设计、开发、维护岗位等。 北大青鸟：软件开发需要学什么？ 第二阶段为了让学员具备面向对象思想，掌握自我解决问题的方法，掌握职业沟通技巧。主要有以下这些课程内容： 1.课程内容：优化MySchool数据库设计、深入.NET平台和C#编程、深入.NET平台的软件系统分层开发、使用Java实现面向对象编程、使用jQuery快速高效制作网页交互特效、使用JSP/Servlet技术开发新闻发布系统、职业素质导向训练； 2.课程讲解贯穿的项目：网络电视精灵、学生成绩管理系统、电子宠物、新闻发布系统； 3.学员动手训练制作的项目案例：影院售票系统、银行ATM取款机系

软件项目管理计划模板

软件项目管理计划 Version1.2

SoftwareProjectManagementPlanofQuartet(Team10) 版本： 软件项目管理计划日期： Quartet_SPMP.doc Revision Date Version Description Author

Page1

SoftwareProjectManagementPlanofQuartet 版本：软件项目管理计划日期：Quartet_SPMP.doc 目录 1.简介 1.1项目概述 1.2项目交付产品 1.3SPMP的演化 1.4参考资料 1.5术语与缩写 2.项目组织 2.1过程模型 2.2组织结构 2.3组织接口 2.4项目职责 3.管理过程 3.1管理目标和优先级 3.2假设、依赖关系和限制 3.3风险管理 3.4监督和控制机制 3.5人员计划 4.技术过程 4.1方法、工具和技术 4.2软件文档 4.3用户文档 4.4项目支持功能 5.工作包、进度表和预算 5.1工作包 5.2依赖关系 5.3资源需求 5.4预算和资源分配 5.5进度表 6.其他 6.1 索引 6.2 附录1 1 1 1 1 1 1 1 1 2 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4

Page2

SoftwareProjectManagementPlanofQuartet 版本： 软件项目管理计划日期： Quartet_SPMP.doc 1.简介 1.1项目概述 ［说明：简要综述项目的目标、发布的产品、主要工作活动、主要工作制品、关键里程碑、所需资源、进度和预算等。必要的情况下，还应描述该项目与其他项目的关系。］ 1.2项目交付产品 ［说明：列出主要的可交付产品、交付日期、交付地点和满足项目协议条款所需的质量。］ 1.3 SPMP的演化 [说明：描述如何以及由谁负责维护本文档，应指明更新内容的传播方式以及在变更控制下更新文 档版本的机制。］ 1.4参考资料 [说明：提供项目计划中所引用的所有文档和其他信息资源的完整清单，包括标题、报告编号、日 期、作者以及发布机构。］ 1.5术语与缩写 ［说明：定义 SPMP所应用的全部术语和缩写词。］ 2.项目组织 2.1过程模型 ［说明：描述该项目所使用的软件过程模型，或者是所遵循的组织标准模型。过程模型需要指明 里程碑的时间、基线、评审、工作制品、项目交付产品、结束标志等。］ 2.2组织结构 ［说明：描述项目的内部组织结构，可以参考如下的层次结构图形式。］

软件项目管理计划书案例完整

学生宿舍信息管理系统项目计划书

目录 第一章前言---------------------------------------------------------2 1.1项目开发背景-------------------------------------------------2 1.2项目开发目的-------------------------------------------------2 1.3项目开发意义-------------------------------------------------2 第二章范围计划-------------------------------------------------------3 2.1项目工作分解结构--------------------------------------------3 2.2软件生命周期模型---------------------------------------------5 2.2.1软件生命周期模型图示表示-----------------------------------6 2.2.2软件生命周期模型详细文档-----------------------------------6 （一）软件规划----------------------------------------------6 （二）需求开发----------------------------------------------7 （三）软件结构设计-------------------------------------------8 （四）数据库设计-------------------------------------------10 （五）实施-------------------------------------------------10 （六）系统集成----------------------------------------------10 （七）提交-------------------------------------------------11 （八）维护-------------------------------------------------11 第三章进度计划------------------------------------------------------11 3.1甘特图-----------------------------------------------------11 3.2网络图（单代号或双代号）-------------------------------------12