Algorithmic Issues in Non-helpful (i.e., vital) Appropriated Frameworks.


124 views
Uploaded on:
Description
Algorithmic Issues in Non-helpful (i.e., vital) Disseminated Frameworks Two Examination Customs Hypothesis of Calculations: computational issues What can be practically registered? What amount does it take to process an answer? Which is the nature of a figured arrangement?
Transcripts
Slide 1

Algorithmic Issues in Non-helpful (i.e., key) Distributed Systems

Slide 2

Two Research Traditions Theory of Algorithms: computational issues What can be possibly figured? What amount of does it take to process an answer? Which is the nature of a processed arrangement? Brought together or dispersed computational models Game Theory: collaboration between self-intrigued people What is the connection\'s result? Which social objectives are perfect with self-centeredness?

Slide 3

Different Assumptions Theory of Algorithms (in circulated frameworks): Processors are dutiful , flawed , or ill-disposed Large frameworks, constrained computational assets Game Theory: Players are key (egotistical) Small frameworks, boundless computational assets

Slide 4

The Internet World Agents regularly self-ruling (clients) Users have their own individual objectives Network segments possessed by suppliers Often include “Internet” scales Massive frameworks Limited correspondence/computational assets  Both key and computational issues!

Slide 5

Fundamental Questions What are the computational parts of a diversion ? What does it intend to plan a calculation for a vital (i.e., non-agreeable) circulated framework? Algorithmic Game Theory of Algorithms Game Theory = +

Slide 6

Basics of Game Theory An amusement comprises of: An arrangement of players An arrangement of tenets of experience: Who ought to act when , and what are the conceivable activities ( procedures ) A detail of adjustments for every mix of systems An arrangement of results Game Theory endeavors to foresee the diversion\'s result ( arrangement ) by considering the individual conduct of the players ( operators )

Slide 7

Equilibrium Among the conceivable results of an amusement, equilibria assume a central part. Casually, a balance is a system mix in which people are not eager to change their state. At the point when a player would not like to change his state? In the Homo Economicus model, when he has chosen a method that augments his individual result, realizing that different players are likewise doing likewise.

Slide 8

Roadmap Nash Equilibria (NE) Does a NE dependably exist? Could a NE be plausibly processed, once it exists? Which is the “quality” of a NE? To what extent does it take to focalize to a NE? Algorithmic Mechanism Design Which social objectives can be (productively) executed in a non-agreeable narrow minded appropriated framework? VCG-instruments and one-parameter systems Mechanism outline for some essential system plan issues

Slide 9

FIRST PART: (Nash) Equilibria

Slide 10

Formal representation of an amusement: Normal Form N levelheaded players S i =Strategy set of player i The methodology mix (s 1 , s 2 , …, s N ) gives result (p 1 , p 2 , …, p N ) to the N players  S 1 ï‚\'S 2 ï‚\' … ï‚\' S N result framework

Slide 11

Types of diversions Cooperative versus non-helpful Symmetric versus lopsided Zero entirety versus non-zero whole Simultaneous versus successive Perfect data versus defective data One-shot versus rehashed

Slide 12

An acclaimed one-shot diversion: the Prisoner’s Dilemma …the story of two odd and perilous fellows…

Slide 13

A renowned one-shot diversion: the Prisoner’s Dilemma Strategy Set Payoffs Strategy Set

Slide 14

Prisoner I’s choice Prisoner I’s choice: If II picks Don’t Implicate then it is best to Implicate If II picks Implicate then it is best to Implicate It is best to Implicate for I, paying little mind to what II does: Dominant Strategy

Slide 15

Prisoner II’s choice Prisoner II’s choice: If I picks Don’t Implicate then it is best to Implicate If I picks Implicate then it is best to Implicate It is best to Implicate for II, paying little heed to what I does: Dominant Strategy

Slide 16

Hence… It is best for both to ensnare paying little respect to what the other one does Implicate is a Dominant Strategy for both ( Implicate , Implicate ) turns into the Dominant Strategy Equilibrium Note: If they may conspire, then it’s advantageous for both to Not Implicate , however it’s not a harmony as both have motivation to veer off

Slide 17

A system diversion C, S: peering focuses s1 two Internet Service Providers (ISP): ISP1 e ISP2 t2 C S ISP1 needs to send activity from s1 to t1 ISP2 needs to send movement from s2 to t2 (long) connections have taken a toll 1 (for ISP owning the connection) s2 Each ISPi can utilize two ways: the one going through C o the one going through S

Slide 18

A system diversion C, S: peering focuses s1 t2 Cost Matrix C S t1 ISP2 s2 ISP1

Slide 19

Dominant Strategy Equilibrium Dominant Strategy Equilibrium: is a technique blend s * = (s 1 * , s 2 * , …, s N * ), such that s i * is an overwhelming procedure for every i, specifically, for each s= (s 1 , s 2 , …, s i , …, s N ): p i (s 1 , s 2 , …, s i * , …, s N ) ≥ p i (s 1 , s 2 , …, s i , …, s N ) Dominant Strategy is the best reaction to any technique of different players It is useful for operators as it needs not to think about other agents’ methodologies obviously, not all recreations (just not very many in the practice!) have a prevailing technique balance

Slide 20

A more casual arrangement idea: Nash Equilibrium [1951] Nash Equilibrium: is a technique mix s * = (s 1 * , s 2 * , …, s N * ) such that for every i, s i * is a best reaction to (s 1 * , …,s i-1 * ,s i+1 * ,…, s N * ), to be specific, for any conceivable option procedure s i p i (s * ) ≥ p i (s 1 * , s 2 * , …, s i , …, s N * )

Slide 21

Nash Equilibrium In a NE no specialists can singularly go amiss from its method given others’ systems as altered Agent needs to consider about the procedures of alternate specialists If the diversion is played more than once and players focalize to an answer, then it must be a NE Dominant Strategy Equilibrium  Nash Equilibrium (yet the opposite is not genuine)

Slide 22

Nash Equilibrium: The Battle of the Sexes (coordination diversion) ( Stadium , Stadium ) is a NE: Best reactions to one another ( Cinema , Cinema ) is a NE: Best reactions to one another  yet they are not Dominant Strategy Equilibria … would we say we are truly certain they will in the long run go out together????

Slide 23

A comparable amusement: steering blockage diversion O two activity streams started at hub O should be directed to whatever is left of the system 1 2 5 6 A B Costs without clog: c(O,A)=1 c(O,B)=2 system Costs with blockage: c(O,A)=5 c(O,B)=6 Each stream can utilize two ways: the one going through An o the one going through B

Slide 24

A comparable diversion: directing clog diversion O 1 2 5 6 A B Cost Matrix system stream 2 stream 1

Slide 25

A defining moment theoretic issue: the presence of a NE Unfortunately, for immaculate methods recreations (as those seen in this way), it is anything but difficult to see that we can\'t have a general consequence of presence at the end of the day, there may be no , one , or numerous NE, contingent upon the diversion

Slide 26

A conflictual amusement: Head or Tail Player I (column) likes to do what Player II does, while Player II want to do the inverse of what Player I does!  In any setup, one of the players wants to change his system, thus on thus forth…thus, there are no NE!

Slide 27

On the presence of a NE (2) However, when a player can choose his methodology stochastically by utilizing a likelihood appropriation over his arrangement of conceivable systems ( blended technique ), then the accompanying general result holds: Theorem (Nash, 1951): Any diversion with a limited arrangement of players and a limited arrangement of methodologies has a NE of blended procedures ( i.e., the normal result can\'t be enhanced by changing singularly the chose likelihood conveyance). Head or Tail diversion : if every player sets p(Head)=p(Tail)=1/2, then the normal result of every player is 0, and this is a NE, since no player can enhance this by picking an alternate randomization!

Slide 28

Three major computational issues Finding a NE, once it does exist Establishing the nature of a NE, when contrasted with a helpful framework, i.e., a framework in which operators can participate (review the Prisoner’s Dilemma ) In a rehashed amusement, building up whether and in what number of steps the framework will in the long run merge to a NE (review the Sex\'s Battle )

Slide 29

On the processability of a NE for unadulterated methods By definition, it is anything but difficult to see that a passage (p 1 ,…,p N ) of the result grid is a NE if and if p i is the most extreme i th component of the line (p 1 ,…,p i-1 ,{p(s):s S i } ,p i+1 ,…,p N ) , for each i=1,…,N . Notice that, with N players, an unequivocal (i.e., in ordinary structure) representation of the result capacities is exponential in N  beast power hunt down immaculate NE is then exponential in the quantity of players (regardless of the possibility that it is still straight in the info size, yet the typical structure representation needs not be an insignificant space representation of the data!)  Alternative less expensive systems are looked for (we will see that for a few classes of recreations of our advantage, a NE can be found in poly-time w.r.t. to the quantity of players)

Slide 30

On the nature of a NE How wasteful is a NE in correlation to a romanticized circumstance in which the players would endeavor to work together sacrificially with the normal objective of augmenting the social welfare ? Review : in the Prisoner’s Dilemma amusement, the DSE  NE implies an aggregate of 8 years in prison for the players. Be that as it may, in the event that they would not involve corresp

Recommended
View more...