Towards an Agent Society

Another Place

2008-01-15T03:34:00.000+11:00

While it's not likely I'll update this with a legitimate update again any time soon, I now have a home page briefly describing my research here.

Just noting this here for completeness. :)

An Explanation

2006-04-04T14:32:00.000+10:00

It has been pointed out to me that one really oughtn't to post about one's actual reseach in the public domain so I haven't really been updating for a while. Once I settle down to figuring out exactly what that research is, then I shall go back to posting about other topical but non-secret things. Perhaps.

Social networking as a business tool

2006-03-07T14:49:00.000+11:00

The blog update for today from Many-to-Many caught my eye as it posts the strategy description from the front page of Socialtext, which describes the way a business should convince employees to use the wiki setup that Socialtext sells.

Basically what it boils down to is: you won't convince everyone to use it, but if you can convince just a small core of users to do nearly all of the work on it, then you'll be successful in implementing such a business wiki (and it will boost productivity a billion percent etc etc buy our product etc etc).

This supernode idea is exactly why nearly all the social networking programs work, and it's perhaps not surprising given that it's how most social organisation works outside of the online environment as well. I offer no specific evidence of this, but I'm sure someone must have done studies on this. Is the key to success not to encourage everyone to cooperate but to encourage a specific few to cooperate far more than their fair share?

In a loosely cooperative agent community where a (decentralised?) reputation system is in place (but where a tragedy of the commons is possible because the things that need doing require a small cost to cooperate with but are a public good) maybe being a supernode can be encouraged by the fact that as a supernode in a given task the agent becomes a supernode in the network with associated benefits from a good reputation. In which problem domain is this the case?

The other suggestion from Phil Kilby just earlier based on this kind of concept was that a way to encourage supernodes might be for the supernode agents to convince the agents in the second-tier of cooperation to cooperate further and so on instead of pushing the least cooperative agents to become slightly cooperative.

Slightly less relevant stuff

2006-02-28T14:55:00.000+11:00

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

2006-02-24T14:25:00.000+11:00

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

2006-02-21T11:54:00.000+11:00

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"

2006-02-15T20:14:00.000+11:00

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

2006-02-08T14:42:00.000+11:00

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

2006-02-06T14:04:00.000+11:00

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

2006-02-02T09:22:00.000+11:00

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

2006-02-01T14:26:00.000+11:00

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.

Agent Group Selection

2006-01-31T12:11:00.000+11:00

From: Evolving Social Rationality for MAS using "Tags"
Hales & Edmonds, 2003

This paper discusses adding "tags" to agents in a multi-agent system to help co-operation break out over a number of generations. Each agent has some strategy for playing a game (let's say the Prisoner's Dilemma, seeing as they do), and they also have some tag which is a number of bits which is not related to their strategy at all, but will be reproduced via the same evolutionary principles.

Each round of this iterated Prisoner's Dilemma game, the agents pair up in some way and play each other, with the best performing agents being represented more strongly in the next round. A low level of mutation is also included - all standard evolutionary stuff. With random pairing the system will quickly devolve into every agent defecting as this is individually optimal.

The twist comes in that the agents choose a partner with the same tag as them if there is one available. In this way the system essentially becomes group selection with each tag having an associated "group". This sounds a lot like what people have evolved to do such as in Carpenter et al, 2003. They don't talk about the idea of group selection in a general sense although they do explain that the reason positive trends develop is due to groups forming. This leaves me wondering whether they just don't know about all the work done in philosophy on group selection theories that would almost certainly help further this work, or whether they just chose not to address them as they're not strictly vital to what's being done in this paper.

Hales and Edmonds show some pretty pictures which show almost total co-operation breaking out over a few thousand generations. More significantly they show an inverse scaling phenomenon in terms of how long it takes given the number of agents - with more agents there are more chances for co-operative groups to form early and influence the evolution in their direction. Of course, given the occasional mutations, every so often a co-operative group will be invaded by a defector who will quickly rip them apart by getting the highest payoff every time. But overall the trend will be towards co-operation.

More impressive is their final section which shows that a bunch of robots using these tags can outperform a group of robots using the obvious co-operative strategy. While impressive at first glance, as they admit the results look very preliminary.

This is applicable stuff for areas where you want a robust system designed to learn the most efficient way to deal with a problem over time. On the other hand, it doesn't really look useful in a society kind of sense, because a manipulator can easily insert a defecting agent to join co-operative groups and feed off each until they die out before moving onto the next. One way around that would be to allow agents to have more detailed strategies and force a newly created agent to "pay his dues" to other agents with the same tag. Again, various techniques for this are in Friedman, Resnick, 1999.

I think I'll find myself referencing that paper by Friedman and Resnick a lot, so I should probably find more papers in the same area that are more recent, if nothing else.

Of course, such techniques add many layers of complexity to what the agents have to know about instead of just "help or don't help" kinds of decisions. It might be interesting to think about what happens when the agents are free to deliberately change groups and remember other agents, in a persistent rather than evolutionary setting. To get anywhere this would require a paying your dues kind of strategy to be allowed or a defector could always try to invade other groups.

Once one goes down that path though, it's not long before one arrives at the point where the groups are irrelevant, and the agents are left choosing based on individual evaluations of their opponents in some way. Then it becomes something more like a reputation based system. So for the situation where you want co-operative agents or robots to do a good job without having to design a strategy each time, maybe we'll leave it as is.

Carpenter, Mathewws, Ong'ong'a - Why Punish? Social Reciprocity and the Enforcement of Prosocial Norms, 2003

Friedman, Resnick - The Social Cost of Cheap Pseudonyms, 1999

Thought Experiments

2006-01-30T13:00:00.000+11:00

I was thinking about an agent society (as one in my position should) and I wondered whether one could describe a "SocietyBot" which represented in some way the wishes of society, and had a certain amount of power over the other agents.

How would such a creature operate? I guess the idea is that every other agent can remonstrate with SocietyBot, but in such a way as to not allow manipulation by any single agent. SocietyBot can penalise agents as it feels appropriate and should probably use machine learning techniques or such to improve how it does these things to increase overall "happiness" over time.

Why am I even thinking about this? Surely the point of an agent society is that society evolves from the agent, rather than enforcing this single agent representing a government in some way. I don't really have an answer for this. It's just something that seemed worth thinking about. If nothing else we can consider it to be jumping straight to the point where the agents elect the most trusted of their number to make decisions for everyone. But let us keep running with the idea.

An obvious problem is that the agents report on their happiness to SocietyBot, so a strictly dominant strategy would be to always be unhappy with the current situation and want more. So then everyone in society is always unhappy and poor SocietyBot can't do anything right. This is pretty reminiscent of focus groups in the real world whose job it is to just be relentlessly unhappy at the government to get further concessions for their pet issue.

One way around this is to have happiness be rewarded in some way. So a "happy" agent is always given better deals etc by its contemporaries, and stops hassling SocietyBot. I kind of think this is where human society has evolved to. People who don't complain constantly are much better regarded. Smiling people are considered consistently more attractive, and those who are cheerful are often given better deals than surly people. If I searched, I could probably find some scientific studies that claim these results in a slightly more formal way. But this is a thought experiment; I don't need that sort of justification.

The other way is to penalise the remonstrations. If it costs an agent to complain then they better have a genuinely good reason.

Ways around both of these: In our agent world, the human manipulator on the outside can introduce bogus extra agents whose purpose is purely to manipulate the system. So the "real" agents keep their heads down and act sweet and nice to get good deals with their good reputations, whilst the "bogus" agents (and an arbitrary number thereof) just complain constantly to benefit the "real" agent. Even if the cost to complain is in terms of real money, it may well be of benefit to the manipulator to spend a lot of money in order to make a lot more money, by pumping money through these bogus agents. Still sounds a lot like focus groups to me. Even more so in fact.

How do we disallow these agents? Firstly, we can't rely on being able to identify such agents, as potentially every complaint could come from a new agent. One way is to only allow established agents to complain - i.e. those that have made a contribution to society by trading over time. There are problems with that too though. Probably this segues into the kind of thing discussed by Friedman and Resnick in The Social Cost of Cheap Pseudonyms. I don't really think human society has very satisfactory ways around this. Maybe there hasn't been enough time to really solve this?

Either way, I think the more interesting problems may be in the more egalitarian agent society. A SocietyBot is a fine idea if you have a centralised administration for the agent society (in fact it's just the embodiment of a more powerful administration), but peer-to-peer kinds of agents societies have a lot of advantages with interesting difficulties.

Socially Intelligent Agents

2006-01-27T15:03:00.000+11:00

Paper: Modelling Socially Intelligent Agents
Bruce Edmonds, 1997

The title of the paper under discussion for today is rather reminiscent of the heading for this blog. So it seemed worth a look. This is reasonably light stuff, and seems more like an introduction to something more impressive than a paper in itself, but anyway. Given it's a few years old I assume the research has continued since then and I intend to read some more.

The idea here is not to create something incredibly useful so much as to create agents that interact socially with each other in some kind of rational and believable (by which I mean human-like) way.

After some introductory comments, the bulk of the paper is devoted to the example of a bar which plays good Irish music on a Thursday night. The agents would like to go to this unless they think it's going to be crowded, in which case they'd rather just stay home. Each agent has its own model with which to make individual predictions. Left roughly to their own devices the number of agents attending hovers around 60%, the number at which the bar becomes too crowded.

When the model is extended with a very basic social structure such that the agents can communicate with each other then life gets more interesting. The agents have to choose whether to go and also whether they say they are going to go or not. There is also more benefit to going to the bar for an agent if its friends are going.

There is a modelling language that each of the agents uses to write its strategies in. This way they kind of design their own strategies based on the other agents and what they learn over time, and it's easyish for a human to read and see what they're doing. It seems that the agents are then left to their own devices over the course of a simulated year or two, with different strategies developing over this time.

The results would be more interesting, but there's only one case study mentioned, which only involves 5 agents. If the bar is crowded with only 3 people in it, it must be pretty darn small. My suspicion is that it's really just the closet where they keep their moonshine. In the end, some agents just learn to do their own thing rather than trusting anyone else, just choosing a mixed strategy to attend 60% of the time. Others become influenced positively or negatively by whether others say they'll attend.

To be honest, given the utility functions specified, it would seem that there would be an equilibrium of everyone going regardless of the crowdedness because their payoff would always be higher than staying at home that way. Only if someone goes while it's too crowded yet none of their friends are there is the payoff worse than staying at home. Given that it's a highly connected network this is only remotely possible for 3 of the agents, and given that it's strictly dominant for the other 2 to go regardless of who else is there (as those 2 are completely connected), I don't see why they don't just learn to always go.

I guess that's what they mean about learning to act as a society rather than act optimally. Or I've missed something in the text. I must read some more based on this soon to see if it does go anywhere.

Manipulating Elections

2006-01-23T14:08:00.000+11:00

How many candidates are needed to make elections hard to manipulate?
Conitzer, Lang, Sandholm (2003)

Seems to be heavily based on Conitzer and Sandholm's previous research in "Complexity of manipulating elections with few candidates", continuing the work therein to several other voting systems. Not bad stuff, but I've got some concerns.

The premise is that you have a few candidates (probably not many, as in most real decisions), and you want to know at what number of candidates manipulating the election becomes NP-complete with respect to the number of voters. There are a few assumptions that should be discussed.

1. This is the really controversial one as far as I'm concerned. They have assumed that the manipulators have absolute information about the actions of the other voters, and can base their decision on that. They have useful results given this assumption, it seems, but this isn't really an appropriate assumption for most real-world situations.

2. They assume that it is a coalition of voters conspiring to manipulate the election. That's fine, and they make a good case for it. Either way, it's a general case - so at least as good.

3. They assume that the voters are weighted. This apparently makes a difference because it's always easy for the unweighted case. This increasingly makes me question the usefulness of this, as in the vast majority of cases votes are unweighted. Or at worst case at least integer weighted. It's easy in the unweighted case as with only 4 candidates or so, then with strict orderings the voters can just be partitioned into 4! voting "vectors". Easy. I'm surprised that the weighted case can't be reduced to this in some way (i.e. take the greatest common divisor of all voter weights so you have integer weightings effectively. Then just assume that they are unweighted but there are groups that always vote together or something?). Anyway, it's not controversial, as again it's a general case.

4. They assume that the manipulators are either trying to make one candidate win, or trying to make sure one candidate doesn't win. Fair enough - they examine both cases.

The proofs are largely the usual sort of NP-complete fare, showing a polynomial conversion with the PARTITION problem.

In the end, they have the appropriate tables showing how many candidates are needed to make the elections "hard" to manipulate for 9 different voting systems. It's interesting to note that apparently it's far easy under most systems to make sure someone doesn't win than vice versa.

As noted, I think there's some flaws with the line of research, as usual with everything. Seems kind of interesting stuff though.

Ideas

2006-01-20T15:13:00.000+11:00

The heading for this blog is "Towards an agent society". Maybe I should justify this. It is, after all, a particularly pompous title.

1. I find the ways that humans maintain social norms kind of intriguing.

2. I think that online agent societies are more or less inevitable, once a few hurdles are overcome. I'm talking about societies in a very loose sense here.

3. My instincts insist that there should be some fundamentally simple mechanics underlying rules of social interaction that an agent should be able to learn or emulate. Note the "shoulds" dominating that sentence.

4. If agents can be convinced to interact in some sensible way with each other, then it opens up the way for a host of interesting applications. More realistic simulations of real societies, more fun examples of fake societies, and agents that people can trust to go online and interact with other agents and do something useful for them.

Under the heading of something useful, perhaps the most obvious thing is trading with other agents. So your agent talks to other agents, forms coalitions, trades money or whatever it is you want your agent to trade, and forms appropriate relationships with other agents in terms of trust, respect, etc.

There is a lot of big problems with this, at least some of which are obvious now, others of which are no doubt apparent with further inspection. I've written some of these down in my "working ideas document" to go through in more detail.

Inter-community Connections

2006-01-19T14:30:00.000+11:00

From: http://www.aip.org/pnu/2002/split/604-3.html
Number 604 #3, September 13, 2002 by Phil Schewe, James Riordon, and Ben Stein

"Eventually, the benefits of cooperating return the system to equilibrium, but the more long range connections in the network, the slower the system's recovery. Although the model is clearly a crude reflection of human interactions, it suggests that increasing numbers of long range connections between people may help destabilize communities. The result is in contrast to the general perception that connections across cultures and nations is exclusively beneficial to society."

That's not surprising at all, as per the introduction of "The Sociobiology of Conflict" by J.M.G. van der Dennen et al, "conflict serves to establish and maintain the identity and boundary lines of societies and groups" etc. So when a connection is made between different cultures, blurring the boundaries, and meaning that there isn't conflict where there ought to be between cultures, the identity of the cultural group is threatened, hence the destabilisation.

That's my rationalisation at least. The implication in the quote is interesting though, as it implies that the destabilisation of the communities is necessarily a bad thing.

Formal Game Theory

2006-01-18T15:40:00.000+11:00

My recent reading has been far more along the lines of sociology papers, so reading some more formal logic has been a bit of a stretch for me. Sadly I missed the talk based on this paper - the one time there's a game theory talk in my research school would be while I'm on holiday.

A Constructive Approach To Sequential Nash Equlibria, Rene Vestergaard, 2005

Abstract:

"We present a Coq-formalised proof that all non-cooperative, sequential games have a Nash equilibrium point. Our proof methodology follows the style advocated by LCF-style theorem provers, i.e., it is based on inductive definitions and is computational in nature. The proof i) uses simple computational means, only, ii) basically is by construction, and iii) reaches a constructively stronger conclusion than informal efforts. We believe the development is a first as far as formalised game theory goes."

Coq is a formal proof management system, and most of the results and description is given in terms of Coq code, which is thankfully reasonably easy on the eyes, even if it is functional.

This paper is concerned with Nash equilibria - the situation in a game where given the strategies of the other players no player would choose to change their individual strategy. Full marks for studying something that is useful. As usual though, the method for finding these equilibria (or at least proving their existance) is through finding a good solution and working backwards, which in many ways is not ideal. In complex games an agent wants to know what their next move is, one at a time, and a good guiess at that is a lot more useful than spending the lifetime of the universe finding a complete solution. Given that it's proving their existance in a formal logic way I'll assume that it does need doing and move on.

Basically it's mainly all about defining Games, Strategies, Plays, Payoffs etc in a functional manner, and because of how he's constructed them, the proofs are mainly trivial. Said proofs culminate with a theorem saying that there exists a function which sends any game to a Backwards Induction equlibrium for it. Without putting in a bit more time to go through the last part of the paper more thoroughly I'm not sure whether this "function" can be found easily and whether you could actually use it even so, but it's still a noteworthy result, I suppose.

Accompanying the paper is a bunch of Coq code I don't really want to read unless it seems like it will really be useful.

The Idea

2006-01-18T15:33:00.000+11:00

It seems that it would be convenient to have an online repository of my thoughts on the various papers I read. This is almost purely for my own benefit, so I entirely reserve the right to ignore major points of papers, to badmouth the perfectly valid results, and to not bother reading the details if I don't get around to doing so.