Showing posts with label trust. Show all posts
Showing posts with label trust. Show all posts
Wednesday, 3 March 2010
Signalling and Signalling Games
Just did a bit of reading on the class of Game Theory games termed 'Signalling Games' and the Economics and Evolutionary Biology theories of 'Signalling'.
Friday, 23 March 2007
12, The Evolution of Cooperation
Notes taken from ‘The Evolution of Co-operation’, by Robert Axelrod (1984)
The Prisoner’s Dilemma – a two-player game of choice; the choice to cooperate or defect at each move, with individual player payoffs depending on what both players (independently) choose, as follows:
(R’s move, C’s move, R’s payoff, C’s payoff)
Cooperate, Cooperate, R=3, R=3 (reward for mutual cooperation)
Cooperate, Defect, S=0, T=5 (sucker’s payoff and temptation to defect)
Defect, Cooperate, T=5, S=0, (temptation to defect and sucker’s payoff)
Defect, Defect, P=1, P=1 (punishment for mutual defection)
Strategy (or decision rule): A specification of what to do in any situation that might arise.
TIT FOR TAT, the strategy of starting with co-operation, and thereafter doing what the other player did on the previous move.
w is the ‘weight’ (or importance) of the next move relative to the current move. It is a ‘discount parameter’ that represents the degree to which the payoff of each move is discounted relative to the previous move.
1 + w + (w^2) + (w^3)… The sum of this infinite series for any w greater than zero and less than one is simply 1/(1-w).
(Proposition 1) If the discount parameter, w, is sufficiently high, there is no best strategy independent of the strategy used by the other player.
A strategy is ‘collectively stable’ if no strategy can invade it.
(Proposition 2) TIT FOR TAT is collectively stable iff w is large enough. This critical value of w is a function of the four payoff parameters; T, R, P and S.
(Proposition 3) Any strategy which may be the first to cooperate can be collectively stable only when w is sufficiently large.
A ‘nice’ strategy is one, such as TIT FOR TAT, which will never be the first to defect.
(Proposition 4) For a ‘nice’ strategy to be collectively stable, it must be ‘provoked’ by the first defection of the other player.
(Proposition 5) ALL D (i.e. always defect) is always collectively stable.
A strategy is ‘maximally discriminating’ if it will eventually cooperate even if the other has never cooperated yet, and once it cooperates will never cooperate again with ALL D but will always cooperate with another player using the same strategy as it uses.
p is the proportion of interactions by someone using the new strategy with another individual using the new strategy.
(Proposition 6) The strategies which can invade ALL D in a cluster with the smallest value of p are those which are maximally discriminating, such as TIT FOR TAT.
(Proposition 7) If a nice strategy cannot be invaded by a single individual, it cannot be invaded by any cluster of individuals.
How to do well in a durable iterated Prisoner’s Dilemma:
1. Don’t be envious.
2. Don’t be the first to defect.
3. Reciprocate both cooperation and defection. (Extracting more than one defection for each defection of the other risks escalation. On the other hand, extracting less than one-for-one risks exploitation.)
4. Don’t be too clever.
How to promote cooperation:
1. Enlarge the shadow of the future.
2. Change the payoffs.
3. Teach people to care about each other.
4. Teach reciprocity.
5. Improve recognition abilities.
Four factors which can give rise to interesting types of social structure:
- Labels, a fixed characteristic of a player, such as sex or skin colour, which can be observed by the other player.
- Reputation, malleable and comes into being when another player has information about the strategy that the first one has employed with other players.
- Regulation, a relationship between a government and the governed… Gives rise to the problems of just how stringent the rules and enforcement procedures should be.
- Territoriality, occurs when players interact with their neighbours rather than with just anyone.
A new strategy is introduced into one of the neighbourhoods of a population where everyone else is using a native strategy. The new strategy territorially invades the neighbourhood if every location in the territory will eventually convert to the new strategy.
A native strategy is territorially stable if no strategy can territorially invade it.
(Proposition 8) If a rule is collectively stable, it is territorially stable.
TIT FOR TAT’s robust success is due to being nice, provocable, forgiving and clear:
- Nice – it is never the first to defect, preventing it from getting into unnecessary trouble.
- Retaliation – discourages the other side from persisting whenever defection is tried.
- Forgiveness – helps restore mutual cooperation.
- Clarity – makes its behavioural pattern easy to recognise, and once recognised, it is easy to perceive that the best way of dealing with TIT FOR TAT is to cooperate with it.
The Prisoner’s Dilemma – a two-player game of choice; the choice to cooperate or defect at each move, with individual player payoffs depending on what both players (independently) choose, as follows:
(R’s move, C’s move, R’s payoff, C’s payoff)
Cooperate, Cooperate, R=3, R=3 (reward for mutual cooperation)
Cooperate, Defect, S=0, T=5 (sucker’s payoff and temptation to defect)
Defect, Cooperate, T=5, S=0, (temptation to defect and sucker’s payoff)
Defect, Defect, P=1, P=1 (punishment for mutual defection)
Strategy (or decision rule): A specification of what to do in any situation that might arise.
TIT FOR TAT, the strategy of starting with co-operation, and thereafter doing what the other player did on the previous move.
w is the ‘weight’ (or importance) of the next move relative to the current move. It is a ‘discount parameter’ that represents the degree to which the payoff of each move is discounted relative to the previous move.
1 + w + (w^2) + (w^3)… The sum of this infinite series for any w greater than zero and less than one is simply 1/(1-w).
(Proposition 1) If the discount parameter, w, is sufficiently high, there is no best strategy independent of the strategy used by the other player.
A strategy is ‘collectively stable’ if no strategy can invade it.
(Proposition 2) TIT FOR TAT is collectively stable iff w is large enough. This critical value of w is a function of the four payoff parameters; T, R, P and S.
(Proposition 3) Any strategy which may be the first to cooperate can be collectively stable only when w is sufficiently large.
A ‘nice’ strategy is one, such as TIT FOR TAT, which will never be the first to defect.
(Proposition 4) For a ‘nice’ strategy to be collectively stable, it must be ‘provoked’ by the first defection of the other player.
(Proposition 5) ALL D (i.e. always defect) is always collectively stable.
A strategy is ‘maximally discriminating’ if it will eventually cooperate even if the other has never cooperated yet, and once it cooperates will never cooperate again with ALL D but will always cooperate with another player using the same strategy as it uses.
p is the proportion of interactions by someone using the new strategy with another individual using the new strategy.
(Proposition 6) The strategies which can invade ALL D in a cluster with the smallest value of p are those which are maximally discriminating, such as TIT FOR TAT.
(Proposition 7) If a nice strategy cannot be invaded by a single individual, it cannot be invaded by any cluster of individuals.
How to do well in a durable iterated Prisoner’s Dilemma:
1. Don’t be envious.
2. Don’t be the first to defect.
3. Reciprocate both cooperation and defection. (Extracting more than one defection for each defection of the other risks escalation. On the other hand, extracting less than one-for-one risks exploitation.)
4. Don’t be too clever.
How to promote cooperation:
1. Enlarge the shadow of the future.
2. Change the payoffs.
3. Teach people to care about each other.
4. Teach reciprocity.
5. Improve recognition abilities.
Four factors which can give rise to interesting types of social structure:
- Labels, a fixed characteristic of a player, such as sex or skin colour, which can be observed by the other player.
- Reputation, malleable and comes into being when another player has information about the strategy that the first one has employed with other players.
- Regulation, a relationship between a government and the governed… Gives rise to the problems of just how stringent the rules and enforcement procedures should be.
- Territoriality, occurs when players interact with their neighbours rather than with just anyone.
A new strategy is introduced into one of the neighbourhoods of a population where everyone else is using a native strategy. The new strategy territorially invades the neighbourhood if every location in the territory will eventually convert to the new strategy.
A native strategy is territorially stable if no strategy can territorially invade it.
(Proposition 8) If a rule is collectively stable, it is territorially stable.
TIT FOR TAT’s robust success is due to being nice, provocable, forgiving and clear:
- Nice – it is never the first to defect, preventing it from getting into unnecessary trouble.
- Retaliation – discourages the other side from persisting whenever defection is tried.
- Forgiveness – helps restore mutual cooperation.
- Clarity – makes its behavioural pattern easy to recognise, and once recognised, it is easy to perceive that the best way of dealing with TIT FOR TAT is to cooperate with it.
Thursday, 11 January 2007
3, Trust in Multi-Agent Systems
Notes taken from 'Trust in Multi-Agent Systems' (2004), by Sarvapali D. Ramchurn et al.
1, Introduction
Trust - a belief that the other party will do what it says it will (being honest and reliable) or reciprocate (being reciprocative for the common good of both), given an oppurtunity to defect to get higher payoffs.
Individual-Level Trust - whereby an agent has some beliefs about the honesty or reciprocative nature of its interaction partners.
System-Level Trust - whereby the actors in the system are forced to be trustworthy by the rules of encounter (i.e. protocols and mechanisms) that regulate the system.
2, Individual-Level Trust
Trust-Models at the Individual Level - classified as either learning (and evolution) based, reputation based, or socio-cognitive based.
Learning and Evolving Trust - an emergent property of direct interactions between self-interested agents. We assume that agents will interact many times rather than through one-shot interactions.
Reputation Models - the opinion or view of someone about something, mainly derived from an aggregation of opinion of members of the community about one of them.
Socio-Cognitive Models of Trust - forming beliefs according to the assessment of the environment and the opponent's characteristics which could also include an analysis of past interactions.
3, System-Level Trust
Open Multi-Agent Systems - agents interact via a number of mechanisms or protocols that dictate the rules of encounter, e.g., auctions, voting, contract-nets, bargaining, market mechanisms etc.
System-Level Trust - subdivided in terms of:
i, devising truth-eliciting interaction protocols.
ii, developing reputation mechanisms that foster trustworthy behaviour.
iii, developing security mechanisms that ensure new entrants can be trusted.
4, Discussion and Conclusion
A classification of approaches to trust in multi-agent systems:
Individual-Level (Socio-cognitive/Reputation/Evolutionary-and-Learning models) -> Reasoning -> TRUST <- Actions <- System-Level (Trustworthy-Interaction/Reputation/Distributed-Security mechanisms)
1, Introduction
Trust - a belief that the other party will do what it says it will (being honest and reliable) or reciprocate (being reciprocative for the common good of both), given an oppurtunity to defect to get higher payoffs.
Individual-Level Trust - whereby an agent has some beliefs about the honesty or reciprocative nature of its interaction partners.
System-Level Trust - whereby the actors in the system are forced to be trustworthy by the rules of encounter (i.e. protocols and mechanisms) that regulate the system.
2, Individual-Level Trust
Trust-Models at the Individual Level - classified as either learning (and evolution) based, reputation based, or socio-cognitive based.
Learning and Evolving Trust - an emergent property of direct interactions between self-interested agents. We assume that agents will interact many times rather than through one-shot interactions.
Reputation Models - the opinion or view of someone about something, mainly derived from an aggregation of opinion of members of the community about one of them.
Socio-Cognitive Models of Trust - forming beliefs according to the assessment of the environment and the opponent's characteristics which could also include an analysis of past interactions.
3, System-Level Trust
Open Multi-Agent Systems - agents interact via a number of mechanisms or protocols that dictate the rules of encounter, e.g., auctions, voting, contract-nets, bargaining, market mechanisms etc.
System-Level Trust - subdivided in terms of:
i, devising truth-eliciting interaction protocols.
ii, developing reputation mechanisms that foster trustworthy behaviour.
iii, developing security mechanisms that ensure new entrants can be trusted.
4, Discussion and Conclusion
A classification of approaches to trust in multi-agent systems:
Individual-Level (Socio-cognitive/Reputation/Evolutionary-and-Learning models) -> Reasoning -> TRUST <- Actions <- System-Level (Trustworthy-Interaction/Reputation/Distributed-Security mechanisms)
Subscribe to:
Comments (Atom)