Slightly less relevant stuff

This research is taking me places I never thought I'd go.

Today that meant the "IT business" section of The Australian as well as the other sections. It was somewhat intriguing to note that the suggestions of changing economy I mentioned just previously were more or less agreed with by the articles there - the way businesses are changing thier structure, and the rise of social networking companies, etc. This may also be coloured by previously listening to the Value Networks lecture given by Verna Allee as a podcast from a Berkeley course, on similar topics.

Another article I spotted was about quantum computers calculating the solution to problems without actually running at all. This was somewhat intriguing but sort of made sense given a very slight background learning about such things. On returning to my office I found this post over at Shtetl-Optimized, which explained it much more convincingly.

Some thoughts on group selection

Rather than the usual pseudo paper review, I have some thoughts written during an otherwise uninspiring talk that ran overtime by 30 mins.

Group selection is a highly useful concept which makes a lot of evolutionary sense. In this way groups with cooperative tendencies can outcompete groups with a tendency to defect. While the individual group member isn't doing the optimal thing, the group as a whole performs much better.

One thing I feel is vital in an agent society is that agents should be able to change their groups and their behaviour as they (or their creator/potential human controller) see fit.

Tags as described in some earlier entries create implicit group selection, where groups are not explicitly formed but come about by the agents effectively distrusting anyone with sufficiently different "genes". Maybe looking at explicit group selection would be a good idea as an agent trying to cheat can probably abuse such an implicit group selection criteria if they want to anyway.

One reason I like the idea of group selection is that everyone wants groups to exist. Cooperators want groups to exist so that they can prosper peacefully with other cooperators and try to keep the defectors out. Defectors want groups so that they can try to invade the groups - without groups or some similar notion everyone will end up defecting, which nobody ever wants. So this is something that should be a popular choice for everyone. I have ignored any other "impure" strategy here, for completeness something more should be discussed.

An important question I need to ask is if there are other theories which compete with group selection. I have a feeling there is because from at least earlier papers/books on the topic of group selection it sounds like it's deemed to be a controversial view. Note to self is to look this sort of thing up more thoroughly.

There are some problems I have with group selection though, before discussing its value or implementation in different arenas any further. One problem is that in many cases it just doesn't matter whether everyone cooperates, so there isn't a strong need for this. An example given in Beenen et al 2004 (though they cite earlier sources for each figure) is that of the Gnutella file sharing network, where 10% of users share 87% of the files, while 2/3 of users don't share any files. Yet it is still considered successful for all concerned, if the freeloaders were driven off it would be far less successful at achieving its goals, in my opinion. The freeloaders don't intend to share files regardless, for reasons external to benefits gained from the network. The work on group selection in this area by Hales 2004 might still be effective though, despite the holes I mentioned previously.

In other cases, group selection isn't such a great idea because the whole point of the system is that everyone is contributing to a whole, and it's the number of participants that makes the system work. Moving to a group based selection would somewhat devalue the usefulness of the system, potentially. In this category I put such systems as eBay or recommender sites that use social networking to get reviews and data on every movie ever made or similar. Here cooperation is very imporgant, but so is participation and everyone being available as a potential trading partner. Reputation based systems for keeping defectors at bay seem more applicable in these areas.

Where does that leave group selection in my mind as a motivator for good behaviour in an agent society? It's probably most useful in a situation where there's competition for resources - the kinds of situations where an evolutionary model makes the most sense in the first place, I suppose.


Gerard Beenen, Kimberly Ling, Xiaoqing Wang, Klarissa Chang, Dan Frankowski, Paul Resnick, Robert E. Kraut - Using Social Psychology to Motivate Contributions to Online Communities
Proceedings of ACM CSCW 2004 Conference on Computer Supported Cooperative Work

David Hales - From Selfish Nodes to Cooperative Networks - Emergent Link-based incentives in Peer-to-Peer Networks
Proceedings of the Fourth International Conference on Peer-to-Peer Computing, 2004

Economics and Agent Society

I've been reading a couple of papers which suggest a paradigm shift in business strategy will surely be upon us soon. While these sorts of papers seem more like they're trying to sell copies of the "forthcoming new book" more than anything and are full of buzzwords, something in them resonates with how I think an agent society should be able to operate.

The idea according to Hagel & Brown (2005) is that we are increasingly moving from a "push" model to a "pull" model.

Push models treat people as passive consumers (even when they are producers like workers on an assembly line) whose needs can be anticipated and shaped by centralized decision-makers. Pull models treat people as networked creators (even when they are customers purchasing goods and services) who are uniquely positioned to transform uncertainty from a problem into an opportunity. Pull models are ultimately designed to accelerate capability building by participants, helping them to learn as well as innovate, by pursuing trajectories of learning that are tailored to their specific needs.

If one reads between the economist-speak it sounds like a good idea but without a lot of substance. Some of that substance is filled out in the rest of the paper. The immediate example that came to mind of this transition is the increasing use of "just in time" manufacture whereby manufacturers move away from the old model of making a whole lot of stuff and putting it in warehouses and then trying to sell it, towards producing items only as they are needed (or ideally just before). The point is that they aren't keeping a large inventory on hand, so that if the market changes they can quickly react.

One point stressed by Hagel and Brown is that the reason this works well in practice for some large companies is partly because they have a vast number of subcontractors with different specialties, but also because they do take into account the social factors involved by sticking with the same subcontractors but switching around exactly who manufactures different parts and how they go together according to the needs of a product. Again, the Granovetter paper I mentioned last time is relevant to this.

Internally within companies this idea is being used as well. Within Cisco apparently there's a system whereby the salespeople have training courses relevant to the client they're about to see given to them on a just-in-time basis. The demand here is coming from the client side - they're pulling the employee into learning what they need to know, as opposed to the sales rep turning up and trying to sell whatever they usually sell. It sounds very efficient - for a big business that can afford to have all those training courses sitting around waiting to be used at least.

I think the main point of all this is that consumers do have options now, and businesses are in a position where they can tailor their products and their services far more individually while still on a massive scale. Examples of pull platforms are rife on the Internet - social networking programs are one example. The consumers are also the creators, the business just enables it. Google ads are another example, they aren't very sophisticated, but they're starting to go in that direction by only supplying ads that seem relevant to the viewer based on the page they're already viewing, leading to a much greater "hit rate" than ads that are just globally broadcast to all and sundry.

I think an agent society should certainly incorporate aspects of this. Every agent should be a creator not just work within the system. Quite possibly this means that an OS-agent relays data about the user on the computer it resides on and between the agent society and machine learning type techniques the user gets better service. In a trading arena it's less obvious, but the agents should evolve to form a structure which discourages cheating - as this kind of idea is really "eBay with agents" it's pretty much covered already anyway.

It's pretty much about the end user and tailored service enabled by greater flexibility and communication. There might be some efficiency lost as it's harder to have such a flexible product line (whatever the product is), but there are greater rewards for everyone when it works.

Having written this, the reasons this model should work within an agent society seem obvious - an agent society is already using something like this by definition. Nevertheless, it's still interesting to see this being suggested as a business model not just for the Internet businesses but for manufacturers and all all other businesses as well.


John Hagel, John Seely Brown - From Push to Pull - Emerging Models for Mobilizing Resources
Working Paper, 2005

Mark Granovetter - Economic Action and Social Structure: The problem of Embeddedness, 1985

A different version of "Social Capital"

From: Impersonal Sociotechnical Capital, ICTs, and Collective Action Among Strangers
Paul Resnick, 2004

Economic Action and Social Structure: The problem of Embeddedness
Mark Granovetter, 1985

Resnick defines social capital differently to Kanazawa. His definition, taken from Coleman (1988), is that social capital is "productive resources that inhere in social relations". It's not exactly contradictory, but it places the emphasis on general social benefit rather than individual genetic benefit.

Aside from the usual tragedy of the commons that develops without such social capital, there's other examples of social mobilisation given, such as starting a labour strike or the dancing at a party - beneficial for all if everyone does it, but to the detriment of an individual if they're the only one. Further, social relationships can be vital in business and dramatically affect how businesses operate. This is the idea flowing throughout Granovetter's paper, that the situations predicted by classical economic theory don't occur in reality because of the relationships formed between businesses and individuals.

"It's not what you know, it's who you know."

The title of the Resnick paper mentions "sociotechnical capital". This refers to "productive resources that inhere in patterns of social relations that are maintained with the support of information and communication technologies". The suggestion is that these can support impersonal social capital, where closer ties are not needed. The benefits include such things as matching systems for geographically disparate users, or behaviour monitoring through reputation systems to weed out defectors.

Resnick mentions that people are increasingly turning to what he alarmingly calls "word of mouse" from strangers as well as recommendations from sources they know. What he doesn't mention is that there is an increasing danger of social manipulation by "shills" who surreptitiously advertise a product as if it was an impartial review. This is already reality, as guerrilla marketing firms employ people to do this - it's along the same lines as "googlebombing" to make your site appear first in a search for a particular type of product (by making a large number of fake websites linking to yours as if it's the best authority on a topic or producer of a product). It's hard to say if these kinds of tactics will erode social trust in social systems. My answer is probably not enough to drag them down entirely, but it deserves a mention. It may be worth a further mention that this kind of tactic has been used outside of the online world as well, although I'm not sure how successfully.

Likewise, news services can be filtered through what the most people read or what the most bloggers are talking about. Apparently in some cities in the US commuters have developed an informal system called "slugging" in which people wanting a lift wait at certain spots and get a lift with people so that they can take advantage of the special lanes for high occupancy vehicles. This benefits everyone except the bus system, even though the system is essentially anonymous. There is personal safety risks with this though, as well as the danger of avocados. Resnick suggests ways in which this system could develop given technology, and the ideas are very impressive - incorporating a review based system (for safety or hygiene reasons) and origin and destination data could lead to a truly efficient semi-public transport system. That still sounds like something that has inherent dangers and discomforts, but it gives an idea of the kinds of potential developments that could occur in the not too distant future with these kinds of technologies and with sufficient social capital. Other examples are given of collective action amongst strangers who share a common goal (such as political activities).

I haven't mentioned much of the paper by Granovetter, and I don't want to go into that one in depth, but I'll just finish this with a somewhat unrelated quote from that paper that may be worth remembering:

The notion that rational choice is derailed by social influences has long discouraged detailed sociological analysis of economic life and led revisionist economists to reform economic theory by focussing on its naive psychology. My claim here is that however naive that psychology may be, this is not where the main difficulty lies - it is rather in the neglect of social structure.

Coleman - Social Capital in the Creation of Human Capital, American Journal of Sociology, 1988

The Savanna Principle

I already talked about this back in my livejournal but I've read further on the topic now, so I'll add some more comments.

From: The Savanna Principle
Satoshi Kanazawa, Managerial and Decision Economics, 2004

Social Capital and the Human Psyche: Why Is Social Life "Capital"?
Joanne Savage, Satoshi Kanazawa, Sociological Theory, 2004

Social Sciences are branches of biology
Satoshi Kanazawa, Socio-Economic Review, 2004

Quoting myself summarising what I say are the key points of Kanazawa:

I've been reading about the Savanna Principle, which is the idea that the human brain is inherently biased towards not comprehending concepts that didn't exist back in the hunter-gatherer days in the African Savanna, known as the Environment of Evolutionary Adaptiveness (EEA).

Fundamentally, the human body hasn't changed in the last 10 000 years, so the idea is that the brain remains in pretty much the same state. This is one explanation for why children take a reasonably long time to learn to distinguish people in real life from people on TV, and indeed, studies have shown that people never really do - those who watch certain types of TV shows (soaps and similar, I expect), rate themselves as having greater satisfaction with their social lives, as if they have those people as actual friends.

This is the theme that appears to run through all Kanazawa's papers, although he tackles a few different things with this idea.

He describes the approach as avoiding "hydrogenology" - the study of hydrogen separate from the rest of the elements, or considering humans as separate from the animal kingdom. We can note how advanced we are, but we should acknowledge the impact of our animal origins on our current society. The papers seem a little repetitive in that respect to be honest.

In Social Sciences Are Branches Of Biology, the question the question asked is why there is a wage penalty for motherhood, as opposed to a wage reward for fatherhood? What Kanazawa's answer boils down to is that evolutionary pressure compels mothers to want to spend more time looking after children, and fathers to want to spend more time working to provide for them to increase their survival rate. Additionally (and perhaps more persuasively), studies have shown that fathers of male children earn more - this fits in with the theory because historically female children would do as well as they could on their looks regardless, while male children would need status and power to attract the ladies. Apparently couples with sons are less likely to divorce than couples with daughters, also.

I think there's some equally persuasive arguments against this, but the case he has made is still well put. These evolutionary biases of course, are not always appropriate in the modern day and age.

The third paper I read was Social Capital and the Human Psyche: Why Is Social Life "Capital"?. Here's their definition:

Social Capital from the evolutionary psychological perspective is any feature of a social relationship that, directly or indirectly, confers reproductive benefits to a participant in that relationship.

Reproductive success here includes that of close kin (i.e. success of genes).

When prodded with a stick, the point that falls out of this paper is really just claiming that there are innate differences in what social capital constitutes between genders, based on the idea of what kinds of social structure is likely to have been evolutionary important for men and women. It's really just justifying that women form fewer closer social relationships and more often with kin, while men should be better at cooperating but more competitive with each other. So cooperation happens under a dominance heirarchy for men, by and large. This would also explain the consistently better verbal skills for girls, for instance.

I think there's some more I could talk about here, but it's 6pm on a Friday, so I'll just leave it as a summary so I can remember what they're about at some later point.

Another Quick Paper About Tags

From: Change Your Tags Fast!–A necessary condition for cooperation?
David Hales, 2004

I think this paper was on my "to read" pile as something which other papers were referring to. A quick glance over suggests that this is the study which tried to establish what the optimal ratio of mutations of tags vs strategies is for agents in a tag based system, such that they achieve optimal cooperation.

There is a benefit for tags to mutate much more often than strategies, it seems. This allows agents to form cooperative groups relatively easily by mutating into a group which then becomes successful. If the strategy mutation rate is too high by comparison, then cooperative groups will quickly be ripped apart by some of the cooperative members becoming defectors.

The outcome of this study seems to suggest the ratio should be about 10 to 1. As they note, this was actually an implicit assumption in earlier papers that didn't appear to be deliberate because of the way mutations were applied.

I've been spending some time over the last couple of days trying to add the papers I've been reading to my library at CiteULike to possibly make my life easier at a later date.

Agents Tags in Peer-to-Peer Applications

From: From Selfish Nodes to Cooperative Networks - Emergent Link-based incentives in Peer-to-Peer Networks
David Hales, Proceedings of the Fourth International Conference on Peer-to-Peer Computing, 2004

It doesn't come as a great shock to hear that in most peer-to-peer (P2P) systems the majority of users are freeloaders, while a minority shares a great deal of files. This is good news, of course, for the law enforcement world which only has to take out the ringleaders for the whole thing to fall apart. Let's assume that we're talking about entirely legal file sharing from here on in though.

Generally speaking, for a P2P application to be as useful as possible, it should encourage as many as possible to share. Ideally this should be done without having to resort to any centralised server or third party solutions, so as to maintain the greatest benefits from having the most open network possible. One can also assume that everyone wants to act as selfishly as possible individually.

The algorithm the agents use is called SLAC (which as a grad student, I heartily approve of) - Selfish Link and behaviour Adaption to produce Cooperation. Yeah, choosey with the letters. This algorithm doesn't really use tags as such, but is closer in spirit to the ideas suggested in Riolo et al 2001 but which they didn't really look at closely.

Each agent has to choose whether to spend its time answering other queries, or whether to spend its time making queries (and thus getting more responses most likely), there is the same kind of tragedy of the commons situation here. It's optimal for the individual agents not to help others but it's no good if everyone does that.

The agents have links to other agents (as in a P2P situation) in some random fashion to start with, and they ask other agents they have links to whether they will trade with them (or play a game of the Prisoner's Dilemma, the algorithm works either way). The agents gain some utility if they are able to source files from another agent. Every so often each agent will randomly select an agent from the population as a whole and compare their utility with that agent. Whoever has the lower utility drops all of their previous links and adopts a link with each of the other agent’s links, as well as the other agent itself. Importantly, the agent with a lower utility also adopts the strategy of the agent with the higher utility.

Because of this system, it turns out that those that don't ever cooperate have their links leave them for more cooperative groups, and thus suffer from a certain amount of ostracisation. This works well in theory, at least according to the pretty pictures, but I do have some issues with this, many of which they themselves admit require further research (which they may well have done by now, I shall soon check). The reason these are problems is that the idea of this sort of system is that anyone should be able to connect to it with a varying strategy and not control the system too much. If you force people to abide by the rules properly, then fine, but that's not easy!

1. I wonder if falsely reporting utility might be a good idea for an agent. As I think about it, I guess it never is. Either way they will have a link to the agent they compare utilities with, and after that they might as well have a link to the other agents "friends" if they are indeed more cooperative. Likewise it wouldn't be worth underreporting utility. It seems like there would be other ways to cheat the system, but they would be more security than algorithmic issues.

2. How do they choose a node at random from the whole network? Actually I'm not entirely sure how the completely decentralised P2P networks work in this manner; I guess everyone has to connect somewhere. Can anyone else tell me before I get around to learning it myself?

3. While each agent will always want to move into groups which are more eager to share, I'm not sure that for the agent changing their strategy is necessarily a good move when they do so. The authors mention that checking the effect of "whitewashers" like this is important future work. They mention Lai et al 2003 in this respect.

4. Every so often an agent mutates to either change its behaviour or "reset" its links to be to just one random other agent. I guess this could be viewed as being disconnected from the network and reconnecting or something, rather than something an agent does deliberately. Changing strategy could be changing to some new client version, apparently.

5. Why do agents have to draw from the same pool of resources to answer queries as well as make queries? This seems to be creating a different problem because it's one that's more convenient to solve with the technique! Otherwise it's just users being lazy or choosing not to share for a different reason than limited resources, and that isn't a convenient problem to solve with any technique from computer science.

6. They assume that each agent is equally capable of sharing files. This will never be so in a P2P situation, even when everyone does share. They may not have done so in all their tests though, it may have just been for the particular graphs shown. Equally, even if we assume resources for answering and making queries are drawn from the same pool, different agents will have different sized pools depending on computer and connection speeds. This may confuse the issue.

Conclusion: It does seem to be a good incentives mechanism for a P2P application, but I think it still offers a lot of opportunities for exploitation, and is likely to discriminate against even the most cooperative user who just doesn't have a lot to share. But maybe that's fair, depending on how you look at it. It is very nice in that the structure of encouraging sharing is purely emergent from agents being selfish so long as they follow the rules. It's also reasonable to assume that even though at least some will exploit any loopholes in the system, sufficiently many will not, so it will work. The system should certainly cope with a few freeloaders.

Riolo, Cohen, Axelrod - Evolution of Cooperation Without Reciprocity, Nature, 2001

Lai, Feldman, Stoica, Chuang - Incentives for Cooperation in Peer-to-Peer Networks, Workshop on Economics of Peer-to-Peer Systems, 2003

More on Agents with Tags

From: Using Tags to Evolve Trust and Cooperation Between Groups
Zohar, Rosenschien 2005

This very short paper seems to have taken me up on some of the thoughts I had on extensions to the ideas in the previous paper I talked about. Or at least where I might have gotten with my thoughts had I spent a bit longer working out what I was trying to say.

In Zohar and Rosenschein's work the procedure for agent evolution is a little different. This time the agents don't get to pick their opponents, they are just able to observe the tag of their randomly selected opponent and can base their strategy (cooperating or defecting) on that agent's tag. Each agent also has a memory of what their opponents with each tag have played against them in the past.

Once again the tags of an agent have no relation to what their strategy will actually be. However, as the well-performing agents reproduce asexually (with a small chance of mutation), a correlation between the tag and the behaviour of an agent is to be expected.

There are some interesting parallels to this situation that come to mind. Firstly it seems like each round is in essence an example of Newcomb's Paradox (a.k.a. the Predictor Paradox) for the agents involved. It's not really, as they're dumb creatures following a simple strategy, but it does look like that. The other agent can predict with a certain amount of accuracy what they'll do, based on what they or other agents with the same tag (i.e. the same genetic material) have done in the past. I guess all instances of the Prisoner's Dilemma in which the agents are basing their decision on what they guess their opponents will do is an instance of Newcomb's Paradox. It comes down to a coordination problem if you have no desire to defect if you don't think your opponent will defect.

The other parallel that comes to mind is again something from the real world, where people do feel free to judge people with genetic material that has thrown up "defectors". According to the results in this paper that sort of judgemental attitude actually strongly leads to a more cooperative society. Controversial.

The results seem reasonably convincing to me. It seems (or they claim) that a lot of variants on tit-for-tat and forgiving versions of it seem to be developed. Just how effective this evolutionary process is depends on four factors they discuss.

1. How many rounds are played before each new generation is created. You need a decent number so the co-operators can learn not to trust the defectors each time.

2. How many memory states the agents have. They need to actually remember that a particular tag defected against them last time, and more states allow more complex strategies to be developed. It doesn't matter much beyond about 3 according to the pretty picture.

3. How high is the mutation rate? With no mutations a tag that was trustworthy to start with will always stay that way, so eventually everyone cooperates. With higher rates it deteriorates slowly as there is a loss of correlation. There is a large dip when there's a very small mutation rate as the "safe" tag groups will eventually become invaded, but there isn't so much chance that another co-operator group will form and expand anytime soon. Or that's my take on it.

4. How large is the tag space? More tags means better social utility, it seems. There isn't that much extra effort associated with a larger tag space in terms of complexity of the system, as long a sensible system is used for memory, it just has the effect that defecting agents are less likely to mutate to have the same tag as co-operators, so only the mutations within a tag effect the trustworthiness of that tag.

It looks like things haven't gone much further than this as yet in this particular direction. This was only published July of last year. It seems like I'm slowly getting to the present.