Incentive-basedSchemes激励方案

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Incentive-based Schemes,Smita Rai,ECS289L,Outline,Incentives for Co-operation in Peer-to-Peer Networks.,Aimed at applications like file sharing.,Priority Forwarding in Ad hoc Networks with Self-Interested Parties.,Layered Incentive-based model for Ad hoc networks.,“Provide incentives to self-interested users to co-operate,Incentives for Co-operation in Peer-to-Peer Networks,Kevin Lai,Visiting Post-doctoral Researcher,UCB.,PhD Stanford.,Part of MosquitoNet group.,Developed tools like Nettimer etc.,Ion Stoica,Assistant Professor,UCB.,PhD CMU.,Worked on a wide range of topics,one of them Incentives.,Incentives for Co-operation in Peer-to-Peer Networks,Michal Feldman,PhD Student,UCB.,John Chuang,Assistant Professor,UCB.,PhD CMU.,All of them work on the OATH Project Providing Incentives for Co-operation in P2P Systems.,Contents,Model of co-operation in P2P systems.,Framework in terms of Evolutionary Prisoners Dilemma(EPD).,Design space for possible incentive strategies.,Comparison using simulation.,Conclusions.,Motivation,Many peer-to-peer systems rely on co-operation among self-interested users.,When non-cooperative users benefit from free riding on others resources “Tragedy of the Commons.,Incentives for co-operation needed to avoid this problem.,Tragedy of the Commons,Coined by Garrett Hardin in Science,1968.,Pasture open to all.,Herdsmen keeping cattle.,Rational herdsman wants to maximize his gains.,Add more cattle to his herd.,Positive component The owner will get the gain.,Negative component The effects of overgrazing will be shared by all.,Result “Freedom in a commons brings ruin to all,Model of Co-operation,Features of a model of co-operation in P2P systems.,Universal co-operation leads to optimal overall utility.,Individual incentive to defect.,Rational behavior.,All these provide the essential tension that results in the tragedy of the commons.,Authors look at incentive techniques to avoid this problem.,The specific application they look at is a file sharing system.,The approach is to model the problem of co-operation in this system in terms of“Prisoners Dilemma.,Prisoners Dilemma,Two suspects in a major crime are held in separate cells.,There is enough evidence to convict each of them of a minor offense.,Not enough evidence to convict either of them of the major crime.,If one of them acts as an informer against the other(finks),then the other can be convicted of the major crime.,If they both stay quiet,each will be convicted of the minor offense and spend one year in prison.,If one and only one of them finks,she will be freed,the other will spend four years in prison.,If they both fink,each will spend three years in prison.,Quiet,Fink,Quiet,1,1,4,0,Fink,0,4,3,3,Suspect 2,Suspect 1,Evolutionary Prisoners Dilemma(EPD),Enhancements,Repetition.,Reputation.,Symmetric,the authors generalize it to include asymmetric transactions(client server).,Asymmetric EPD,AEPD consists of players who meet for games.,A player can be a client in one game and a server in another.,The server has a choice between co-operation and defection.,Players decide depending on a strategy.,They may maintain histories of other players actions.,As a result of client and servers actions,the payoffs from a payoff matrix are added to their scores.,Asymmetric EPD,General form of a Payoff Matrix,Asymmetric EPD,Round consists of one game by each player in the system as a client and a server.,A generation consist of r rounds.,After a generation,all history is cleared.,Players evolve from their current strategies to higher scoring strategies in proportion to the difference between the average scores of the two strategies,after a generation.,Design Space,Reciprocative Decision function,P(co-operation with X)=Min,(Co-op X gave/co-operation X received),1,Private vs.Shared History,Private history does not scale to large population sizes.,Repeat games become less likely with increase in population size.,However,decentralized implementation straightforward.,Design Space,Policy with strangers,Legitimate newcomer.,Whitewasher.,Authors assume that the P2P systems they model,have zero cost identities,Objective vs.Subjective reputation,Objective reputation may be subverted by collusion.,Subjective reputation can avoid this problem.,Simulation results,Varying,Population sizes.,Number of rounds.,Payoff Matrix,Allow Download,Ignore Request,Request File,7,-1,0,0,Dont request file,0,0,0,0,Server,Client,Results,Private vs.Shared History,Results,Private vs.Shared History,Convergence of Reciprocative using private history varies depending on,Population size.,Initial mix of population.,Rate at which players are making transactions.,In any case,fails at some point as the population increases.,Since it is less likely that you have repeat games with the same player.,So,a player using private history is taken advantage of by a defector.,Results,Stranger