Přepis řeči - SOCIAL NORM AND LONG-RUN LEARNING IN PEER-TO-PEER NETWORKS

0:00:23	sure
0:00:35	a
0:00:36	you
0:00:37	i
0:00:39	um
0:00:41	for
0:00:42	yeah
0:00:43	i
0:00:44	why
0:00:45	um
0:00:46	i
0:00:49	a
0:00:50	we
0:00:51	oh
0:00:53	okay
0:00:53	oh
0:00:54	right
0:00:55	and
0:00:56	a
0:00:57	uh
0:00:58	you
0:00:59	no
0:01:00	i
0:01:01	no
0:01:03	a
0:01:03	yeah
0:01:04	i
0:01:06	i
0:01:07	and
0:01:09	oh
0:01:12	oh
0:01:15	a
0:01:16	you
0:01:18	a
0:01:18	and
0:01:20	uh
0:01:22	i
0:01:24	oh well
0:01:27	i
0:01:28	oh
0:01:29	oh
0:01:31	a
0:01:31	was
0:01:34	i
0:01:35	oh
0:01:35	i
0:01:36	i
0:01:38	and
0:01:39	two
0:01:40	and
0:01:40	i
0:01:41	i
0:01:43	and
0:01:46	ah a
0:01:48	i
0:01:48	oh
0:01:49	right
0:01:51	a
0:01:52	yeah
0:01:53	uh
0:01:55	oh
0:02:01	where
0:02:02	uh
0:02:04	i
0:02:05	a
0:02:06	a
0:02:08	yeah
0:02:09	like that
0:02:10	yeah
0:02:12	one
0:02:13	i
0:02:15	for
0:02:17	a
0:02:18	but
0:02:20	right
0:02:21	i
0:02:22	i
0:02:23	right
0:02:25	the moment i
0:02:26	so
0:02:27	oh
0:02:28	a
0:02:29	thank Q
0:02:30	um and hands and use was that can be enforced and then any moment in time
0:02:35	as both the server as a klein
0:02:37	i'm going to model this in the following way i'm going to assume that i have a client which can
0:02:41	quest a file of some form of service a server
0:02:44	which are is an upload quest
0:02:47	and and i'm going to assume that
0:02:49	um i can model this
0:02:51	as shown in here
0:02:52	and i going to call is a gift giving game
0:02:55	so i'm going to assume that the client has no action
0:02:58	he just a request at some content
0:03:00	and the set that has
0:03:02	an action he can choose to serve and
0:03:06	i'd
0:03:06	thus that of is to the client
0:03:08	or not to serve
0:03:10	i'm going to assume that it the step but decided to set the clan to get the if you don't
0:03:14	be and
0:03:15	otherwise is this that but it and i to serve you to get the benefit of zero
0:03:19	so clearly thus client has the benefit
0:03:22	from
0:03:22	being served by the server
0:03:24	a set on the other hand in the cost of C so has a to do would be minus C
0:03:29	and
0:03:30	the um in the case of doesn't
0:03:31	serve
0:03:32	the cost will be zero
0:03:34	so that a yeah why actually can action a one prime in that action there would be no incentive for
0:03:39	the server to a
0:03:41	to to to two to of and hands she would like to not serve and fear
0:03:47	so what is important in this context is to try to bring some form of incentives
0:03:51	to can is the users
0:03:52	to serve each other
0:03:53	and that is the goal of the proper design of let's call or than that design
0:03:58	yeah are many ways to implement incentives to not lex
0:04:01	the most studied within the out of engineering a a see propagation for example in P two P a was
0:04:06	people assume of his study of past see propagation out that users
0:04:11	how about in the current and vitamin we can see that that is not a good model because i may
0:04:15	not have a his study of past see propagation of the particular person
0:04:19	so i know a couple of you in the audience but moment ready to of you i don't know
0:04:22	however i may be interested in getting some content from you and you might be interested in getting some content
0:04:27	from somebody else
0:04:29	but because of that fast see the of interest
0:04:32	as as well as the that of being dynamic can use of starting and going i may not be able
0:04:36	to have a he story of few are particular
0:04:39	um
0:04:39	a
0:04:40	personal his story of reciprocation
0:04:43	has in such situations
0:04:45	we use social of
0:04:46	um
0:04:47	if C propagation
0:04:48	and this also reciprocation skins so a from based on reputation and going to discuss that in know to do
0:04:53	that
0:04:54	so like a like less you will is you are going to implement this
0:04:57	source show
0:04:58	all if you provocation in a rigorous way as follows
0:05:01	i'm going to assume that the of code design or would try to design a social norm
0:05:07	and he's going to do that the by introducing the following elements for he's going to a to and you
0:05:13	here were every agent
0:05:15	a set of imputation labels L
0:05:17	but number of L would be part of the design
0:05:20	um then a peer cannot but the a G
0:05:24	a web are given a particular reputation a label for the
0:05:28	so that for the client with from seen that that he be can decide to starve not this
0:05:34	uh
0:05:34	that the protocol designer can
0:05:37	design a social norm as follows
0:05:39	she can sell like the set of reputation label
0:05:43	she can determine i mean the social strategy what you would like to see it in that actions and merging
0:05:48	so given the reputation of the sort of a and the reputation of the client be if i'd upon be
0:05:54	a at the G to start models that or
0:05:57	and if the agent was a P D and
0:06:00	he's its reputation would be increased
0:06:02	otherwise it would be decrease
0:06:05	not to though that we deal with that of fish agent here so they may decide that it's not in
0:06:09	the set of interest
0:06:10	to form of this also
0:06:13	um so i'm with don't you one more thing and went to assume that you can though maybe somebody comply
0:06:19	with the social norm
0:06:20	that maybe be a
0:06:22	i the reporting errors
0:06:23	or
0:06:24	something has happened and i i'm a not product the update this reputation
0:06:30	um let give an example of a source of i'm going to use in the talk
0:06:34	um
0:06:36	i'm having to san ninety as i'm going to have a and a to you are going to consider a
0:06:39	for base or shows that they G
0:06:41	which has a service to old age
0:06:44	if the server has a class hold below age
0:06:48	and the kind and has a reputation of by of age i'm going to assume always
0:06:53	that
0:06:53	that was that of so we've one condition or not that happened that would serve
0:06:57	well yeah at hand
0:06:59	they are not going to serve if the server has a reputation that is higher than that of the plot
0:07:06	uh yeah
0:07:07	you and this type of test whole base also of the G
0:07:10	uh i i can have much more sophisticated social that i give a talk earlier today day which can that's
0:07:15	a more sophisticated strategies
0:07:17	but that makes a noise is more difficult
0:07:19	so here and once the ring just a simple they G
0:07:22	if they you was that's are going to follow the social strategy that put patient is going to increase
0:07:28	an and went to assume a marketing a passionate stations
0:07:31	if at any moment in find somebody body all bay
0:07:34	it's going to be punished
0:07:36	or the way the reputation
0:07:39	um so
0:07:40	they the use that have on the ability to decide that you want to solve all this type of
0:07:46	um
0:07:48	that's for based scheme
0:07:50	so what if you doing kids optimization one
0:07:53	so the not would be its own reputation label
0:07:56	um
0:07:57	reputation
0:07:58	distribution of the community which i'm going to consider consider
0:08:01	i'm going to call let's community configuration
0:08:04	and also the a one and a quotation you may want how that all this information is known
0:08:09	well this information could be no maybe there is a track
0:08:12	you can come up with distributed versions of the but they are more complicated
0:08:15	to
0:08:16	to really formal lies and and come up with a eighty percent you
0:08:22	oh or going to introduce a simple belief that users are going to hold
0:08:25	so the use that's are going to assume that
0:08:28	use as that are at a reputation zero
0:08:31	um
0:08:32	will
0:08:34	higher than zero will follow the social more
0:08:36	and you data reputation zero they do not provide them
0:08:40	now in in order to determine whether a user should for this sort of thought that are not i need
0:08:44	to determine not only the for kind a D V D of the user
0:08:48	but also the long-term utility of
0:08:50	are we use a given the community configuration and the specify social norm you can this actually i yet or
0:08:56	not and keep data is that based on its performance in the long term
0:09:00	in that you could would be just one shot did you need to go to T decided nobody will comply
0:09:04	everybody will feel i
0:09:07	so this is the
0:09:08	um
0:09:09	a problem of that values use that needs to solve
0:09:11	so you can use to decide actually what be its best response at every period in time that maximise is
0:09:18	it's a long time at that it is a can used to select this at signal which is to leading
0:09:22	to the optimal long term that data
0:09:25	no that's not from a system point of view what they would like to her
0:09:28	so from a system point of view what they would like to have
0:09:31	is he would like to have an a me go back to to this first setting with like to have
0:09:35	a problem was that
0:09:37	is
0:09:38	source should the optimal
0:09:40	so that we would like is that is not a code design of cell X that's also one
0:09:43	that's so long as form on what time by the set of degradation label
0:09:48	the reputation update scheme
0:09:50	and the social strategy
0:09:53	so is to send that this and i mean that
0:09:55	such that
0:09:56	the community are rice at the unique stochastic a stable like will there is i want to have something like
0:10:02	that is if i don't have a unique a key
0:10:06	the community make over to different and it different um
0:10:10	types of configurations some of which may be efficient
0:10:14	and in part because can that i would like that this unique
0:10:17	a Q blue which i'm going to define in just one second
0:10:20	is corporate
0:10:21	so in this unique i Q label everybody will cooperate with the job
0:10:25	what you talk i speak at least a be like in meets up quite complicated concept you why there no
0:10:29	with already you word this would be kind of a very small somebody you of it
0:10:33	but the idea here is is that um
0:10:35	i have a strategy at you provide sick to get together with a comedy configuration you
0:10:40	and this should be a stochastic a least table like you do if and only if when the at
0:10:45	is update errors
0:10:46	of excitation go to zero
0:10:48	seek my is that that's this response of the use as against
0:10:51	the overall population
0:10:53	configuration
0:10:55	and use new is time-invariant then is that points than i make in do by this particular signal
0:11:01	and more than that that the community stay set me with a positive for about
0:11:05	okay
0:11:06	now that you look so this is a protocol design a problem i'm going to
0:11:10	go back to it all the way the end for now let me concentrate on the use
0:11:15	and you know what that for this again to be a stochastic a least like you leave room
0:11:19	the best is one dynamic when need to ended cold first to decision able actually
0:11:24	i for this that to sort is best response then i mean in to solve an in P yeah or
0:11:29	finding me with and P the only thing i want to point out here is that we can see that
0:11:32	in this and D that this state
0:11:34	is the reputation of the user
0:11:36	and the configuration of the components
0:11:39	given that at additional of they was
0:11:41	so best on this
0:11:43	big for lies the of a to functions such that we can do that best response than i mean
0:11:48	and we want to now look at a given that this and and
0:11:51	what that the structural properties of these test is point by not
0:11:55	and if is that we have which is very important is that the solution of the previous and be problem
0:12:00	in this type of social norm governed
0:12:02	all um
0:12:03	community is that that's all they the G
0:12:06	this is the optimal strategy selected what it means is actually
0:12:09	that given the configuration of the client which which i mean that acting
0:12:13	i'm going to have a a S for age
0:12:15	a that as for than going to start the users and below and not
0:12:20	therefore in order to determine the optimal point see we can
0:12:24	only it's sufficient to determine the optimal test hold at at very
0:12:29	um
0:12:30	state
0:12:30	yeah so the optimal set service test for that age
0:12:34	yeah i can be formulate
0:12:36	this and D
0:12:39	and and if i do that
0:12:40	based on this information is structured is desired
0:12:43	i can come up with one more
0:12:44	or out
0:12:45	also also some form of structure
0:12:47	which is that this that's for of remote point
0:12:50	has the following property i will now a one two
0:12:54	of
0:12:55	some body
0:12:56	a but have the source norm so the source norm that is me go to so that of people have
0:13:00	a bad reputation five
0:13:02	i would never go and set some by they shall for
0:13:06	that's a first thing
0:13:07	a not that is that the service is user provides one one only increases with a but
0:13:12	you can think about that as some to think it'd the above a certain and that's about but as the
0:13:17	reputation increase is you don't want to get in the start this you have in the system it becomes increasingly
0:13:22	that you meant for you
0:13:23	to to cheap
0:13:26	no that's a look
0:13:27	do you this type of structure properties how as the community of or
0:13:31	because you would like to solve this from a proper code design a point of view
0:13:35	so for thing is we can prove that the community of all following a markov of chain
0:13:39	and that is that's these phones and i'm mean of the user
0:13:42	in each state of the markov chain is a community configuration
0:13:46	more of what we can show is that is not of jane P as the following properties
0:13:51	that exist actually is T you are shown we have stability and a D
0:13:55	and i in a some of that just to be able to define a early meeting configuration is if you
0:14:00	are shown which i'm going to court it all make a hat
0:14:03	to which the community will
0:14:05	oh four to as this at all
0:14:08	oh reputation errors
0:14:09	then the words your
0:14:11	so that has a configuration is stochastic least stable when it's probability in on that data
0:14:17	star or or make a on had well my um
0:14:20	bar should say
0:14:21	is a larger than zero
0:14:22	that's one i'm going to say that the configuration is to classical state
0:14:28	you that what i can can in terms of gorgeous of the community the following first is that the limit
0:14:33	in configuration distribution diffusion unique
0:14:36	has the comedy converges to early make it's a top of the degradations in the long down so i just
0:14:41	i want give a small set of configuration
0:14:44	and this is very good because otherwise the design space will explode
0:14:47	a second the and says that the set of stochastic least able configuration and the set of configuration be long
0:14:53	it to this stochastic take a like people are the fame
0:14:56	what does that really mean
0:14:58	it means that we can and otherwise
0:15:00	only the stochastic or stable like you be a
0:15:03	we can use yeah like the stochastic least able it can either by analysing think the that of stochastic least
0:15:08	stable configuration quotations
0:15:11	okay so i can have a weight to
0:15:13	conduct that i Z school version of the community
0:15:16	what i want to do
0:15:17	about
0:15:17	when they want to do the design no
0:15:20	for we can cut that i've barely meetings set
0:15:23	all of this
0:15:24	stochastic stable configuration and if we do that we have a first you're that which says
0:15:29	well as anything in this network will converge i that two
0:15:32	zero which means never cooperate operate everybody here writing
0:15:36	or or always corpora
0:15:38	and thing in the middle of from one to a minus one
0:15:41	it's not going to get a present
0:15:43	so i that everybody serves
0:15:45	or nobody sir
0:15:47	yeah the question becomes of the proper up design of or
0:15:50	how what he design
0:15:52	this type of interaction between users how should he determined the social strategy the G that it could station
0:15:58	a a data would and the set of excitation
0:16:01	to let use that as she as the competitive out
0:16:04	other then the defect about
0:16:07	for that what he is to do is to set that that's hold in the also at
0:16:12	depending on the pot i'm it that's of the form
0:16:15	and is to set it in such a weighting which
0:16:18	depending on the cost of the benefit ratio
0:16:21	as well as the discount factor of the
0:16:23	on utility of the users
0:16:25	this test is smaller than is about
0:16:28	so the design becomes
0:16:30	mainly focus on the H
0:16:32	well as that really em you know what that is by as
0:16:34	let's look at that in in state of result
0:16:37	what actually in here is the following thing first i show that
0:16:41	how the social well if there very is for a community as the cost increase as the cost of service
0:16:47	okay
0:16:48	that as increases
0:16:49	i assume a i peak the network
0:16:52	with the following parameters
0:16:54	and what i want to show with the following first let's look at the blue lines
0:16:58	what used the blue as is you optimal corporation this is something like a network utility maximization of do if
0:17:05	i have self less use that's for be the end user
0:17:09	they would always but it they were always feel a protocol
0:17:12	and this is the best i can do
0:17:13	that is in is goes down is because the cost increase so
0:17:17	even we user corporate
0:17:18	the cost increases as well
0:17:21	hence
0:17:22	what i want to show here is
0:17:24	if you have a B D and is that everything goes fine
0:17:27	one yeah hand if i need to determine the optimal
0:17:32	um um
0:17:33	talk
0:17:34	which is sustainable
0:17:36	meaning the optimal protocol which is
0:17:39	oh bait by D set interested users is what i'm getting is this to be an bar see here
0:17:45	so what is see that to be a design
0:17:47	two things happen
0:17:48	for is the cost becomes too high
0:17:50	but one want to out that it that a will collapse you cannot apply to that interested users to in
0:17:55	is high cost
0:17:56	relative to the band
0:17:58	i se
0:17:59	a thing is you can see a as the cost increases
0:18:02	you are starting to have gap
0:18:04	then if you have this gap with as opposed to the optimal cooperation is because you have a trade
0:18:10	between one hand optimality
0:18:12	the that was incentive
0:18:14	so in order to make this protocols protocol sustainable about you need to give a something in terms of form
0:18:19	that we say well this optimization is that in ask and that it difficult what with i why would i
0:18:23	go out that of this very difficult
0:18:25	um
0:18:26	a complicated optimization problem can and not just to was a particular fixed
0:18:29	so shows that they using the particular that's for which makes sense
0:18:33	if you do that to see that is that in red
0:18:36	so what you would see is first the network community will collapse much faster
0:18:40	because of the cost
0:18:42	increasing and this stuff that you being chosen randomly
0:18:45	well so you we see that as the cost increases is that gap to the optimal corporation
0:18:50	a what we take away from here is to messages and this would be the last thing and not even
0:18:54	going to show the crucial
0:18:56	the that's the thing i like to to see is that
0:18:59	you can not talk yet about a network to delete the optimization need to talk about sustainable that the direct
0:19:04	optimization
0:19:05	because the one
0:19:07	type
0:19:08	problems cannot piece
0:19:10	really a really for forty used in this type of environment that is that a selfish
0:19:14	and secondly if you want to go well
0:19:16	a head and just to something a hall
0:19:18	like a lot of the literature are currently in engineering is trying to do to cut people up
0:19:23	social strategies and policies is for that but they up the that that ad hoc
0:19:29	you performance with for a lot
0:19:31	thank you that
0:19:41	yeah
0:19:45	no
0:19:45	i i have every bite your bus has some
0:19:48	information some knowledge let's say and we change with each other
0:19:52	so i mean change it with you you make change it that on a make change changes if you can
0:19:56	and so on
0:20:01	no so what happens in here is because we don't have the few story of fife the see location what
0:20:06	i had is i have a blob his study
0:20:09	you're are study in the that
0:20:10	so you don't have a for his study will need that i in the beauty of this work
0:20:14	so in an that that it which i that i with the all the time
0:20:16	this will not be that i model
0:20:18	but an an use dynamic users coming go in the use of have been in different things
0:20:23	i would not have the P and to necessarily have met to before
0:20:27	and and
0:20:27	be a the his study with you
0:20:30	so it is a they she's a global level of reputation after it in that action
0:20:34	you will have a different excitation
0:20:36	of course you can come up with a reputation scheme or maybe be are part of a club of the
0:20:39	signal processing a and we should behave in a signal processing cost but there we moved to the information that
0:20:44	the club we only to behave was we don't meet these people very often
0:20:47	that would be extended
0:20:49	i

SOCIAL NORM AND LONG-RUN LEARNING IN PEER-TO-PEER NETWORKS

Bio-inspired Information Processing and Networks

Přednášející: Mihaela van der Schaar, Autoři: Yu Zhang, Mihaela van der Schaar, University of California Los Angeles, United States