Note: This is a work in progress. Its purpose is twofold: as a mechanism for organizing my own thoughts on some of my current research, and as an informal means of making those thoughts accessible to others that might be interested. Some parts of it are derivative from others' work; I will try to keep a current list of sources. If anyone would like to use or refer to any part of this in their own work, or would like to comment on it, please contact me.
Currently I am working with Steve Fickas of the Computer and Information Science Department of the University of Oregon on a project for which he, Holly Arrow of the Psychology Department, and John Orbell of the Political Science Department, are the principal investigators. The essential motivation of the project is to study the self-organization of people into groups to achieve tasks; groups that form in this way are called clubs in the theory of political science. In particular, we are interested in the processes of negotiation that are involved both in club formation, and in the distribution of whatever good that the club derives through achieving its task.
The experimental metaphor that is being used to study these phenomena is a game called social poker. In social poker, no one player has enough cards to comprise a complete poker hand. Thus, the players must organize themselves into groups (such that each group has a set of cards from which a valid poker hand may be created) and then informally decide how to distribute the payoff associated with that hand. Then each player makes a private claim on that payoff, which may bear no relation to the amount which they agreed to claim; if the sum of the claims is greater than the size of the payoff, then each player is penalized. Thus, each player has an incentive to identify those players who contribute to overclaiming, so that he/she may avoid forming a group with them in a subsequent round.
My connection to, and interest in, this endeavor is:
Agents (in this context, 'entities that are capable of action') do not generally have available all the information that would allow them to completely predict the behavior of other agents. In particular, often two agents will interact that have never interacted before. Thus, when two or more agents engage in a transaction, they tend to rely on information about each others' reputations as an aid to guide their actions in the transaction. Agents in a computer-mediated (CM) environment must rely on reputation even more than must those in a face-to-face (FTF) environment, because CM-environment agents do not have available such information as facial expression, tone of voice, style of dress, etc. as are available to FTF-environment agents.
There are essentially two distinct types of models for managing reputation information: the central authority model and the distributed model.
In the central authority model, a single server is responsible for storing all reputation information, according to the evaluations that participating agents submit after each transaction. The weaknesses of this approach are:
In the distributed model, each agent maintains its own reputation information. At first, this seems to be a terrible waste of space--and would be, if each agent were to store all of the information that would have been stored by the central authority. However, it seems reasonable to suppose that:
Reputation is comprised of the recorded judgements of agents on the quality of their interaction with other agents. After agent X and agent Y interact, then X and Y each rate their interaction based on whether their respective outcomes of the interaction were satisfactory. These ratings are then incorporated into X's reputation for Y and Y's reputation for X.
Some important qualities that reputation should have are:
(Alternate definition: X has a belief that Y provides accurate information about Z's performance on tasks in domain D; this belief would then be Y's credibility with respect to Z's performance in domain D for X.)
I am interested in exploring the questions of how to represent reputation information for each agent, how to share it among agents, and how to incorporate one agent's reputation information into the reputation information of another. To that end, I have compiled the following list of parameters whose values we may need to determine.
There are (at least) two major ways of approaching this research.
One is to attempt to reproduce the complex of mechanisms that humans use in collecting and using reputation information; if successful, this might tell us some interesting and perhaps useful things about human psychology and decision- making.
The other is to attempt to design agents that have their own criteria for assembling reputation information, whose purpose is to assist human beings in making decisions about transactions. My personal inclination, at the moment, is to pursue this latter course.
An active query is an (unprompted) request for information from X of other agents that X trusts. Such queries fall into two categories:
Passive exchange of information can most readily take place around a transaction (either before or after it), in which an agent may request its counterpart to reveal the contents of its recommendation/evaluation database (or offer to reveal its own). Intuitively, this is "gossip". The user may place restrictions on the kinds of information that they wish their agent to passively collect from other agents in general.
Of course, the extent to which the user's agent will incorporate this information into its database will depend on the credibility of its counterpart agent in the various domains in which information was received.
It seems prudent to assume that there will be some agents that will provide false information. Obviously, if such agents comprise too much of the population, then the system becomes useless (and society probably falls apart, too, so no one will care or even notice). However, agents must be prepared to cope with deliberately falsified information. Another (perhaps less depressing) way to put this is that other users will not necessarily evaluate on the same set of priorities
Fortunately, the answer is inherent in the distributed model of reputation information: don't trust any given individual too much, i.e., one shouldn't let information from a single source have too great an effect on one's own reputation evaluations.
When I first started to consider issues of reputation, it seemed obvious to me that reputation ought to represented directly as an expectation, e.g., if Y has a "good" reputation in domain D for X, then X believes that there is a 85% probability (perhaps with some confidence interval) that Y will perform satisfactorily in a given transaction. This formulation would have had the advantage of enabling us to use various existing tools and techniques in probability and in graph theory
Partially as a result of reading Abdul-Rahman's papers, I have decided that probabilities are probably not the best representations of reputations. The basic reason for this is that probabilities do have convenient mathematical properties...not all of which are properly used in this context. In particular, consider transitivity. If Y has a credibility of 80% in domain D for X, and Z has a credibility of 90% in D for Y, probability theory would seem to imply that Z has, or should have, a credibility of 72% (.9 * .8) in D for X. I strongly doubt that this is the most reasonable conclusion, and it is for this reason that I suggest that probabilities be used sparingly, if at all, in this context.
Evaluations are subjective, based on X's level of satisfaction with the outcome of a transaction in which X has participated. However, it might be useful to consider the following: there are characteristics that X possesses that inform these evaluations--perhaps we should try to represent some of these as well. It was pointed out by Towle and Quinn (in their paper entitled Knowledge Based Recommender Systems Using Explicit User Models, presented in the 2000 Austin, TX workshop on Knowledge-Based Markets) that people make evaluations for different reasons, and (by implication) that conflating two ratings of "good" may therefore be misleading. (Towle and Quinn also pointed out that some make decisions on basis of preference, and some on basis of need. Should we try to capture this? It doesn't necessarily seem apropos in terms of evaluations (as opposed to purchase decisions, which is what they're talking about), but it may be worth looking into some more.)
Evaluations should be multidimensional: X should be able to evaluate a transaction based on several different factors. To combine this with the note above, perhaps X should also specify, as global characteristics, how important each of these factors tend to be. This could also be represented as annotations to each evaluation, or (best?) there could be global defaults, which could be modified ad hoc as necessary. (Because, of course, one's priorities are not always the same.)
Making prioritizations public knowledge is a two-edged sword. In some sense the ideal outcome is that everyone else makes theirs public, but mine remain secret. The reason is this: if I know someone else's prioritizations, that gives me a valuable context in which to interpret their recommendations. However, other people knowing my prioritizations doesn't help me...and it may hurt me, because if my prioritizations are known, then other agents (of deception) may represent themselves as having the same (or highly similar, to reduce suspicion) set of prioritizations for purposes of increasing their influence on me when I ask them for recommendations.
Concept for prioritizations: don't list order of priority for factors; imposing a total ordering is not always apropos (two factors may have equal priority) and does not tell the whole story in any case. Instead list their relative importance in terms of fractions of a whole (e.g., factor A comprises 15%, B comprises 10%, C comprises 30%, and so on).
How, in most circumstances, is a reputation agent to know that its user should be prompted to give an evaluation, or that it should provide reputation/recommendation info? (The second one is a priori easier, since the easy way to deal with this is to "speak when spoken to".)
The best papers that I have seen on this subject--in terms of a detailed discussion of reputation and recommendations--have been authored by Alfarez Abdul-Rahman and Stephen Hailes. They are available on Abdul-Rahman's webpage at http://www.cs.ucl.ac.uk/staff/F.AbdulRahman/docs/.
Jay Schneider, formerly a member of the Wearable Computing group of the U of Oregon CIS department, got me into this in the first place with a paper that he co-authored, entitled "Disseminating Trust Information in Wearable Communities". His papers are available at http://photobooks.com/~j/publications.html.
I have not (yet) specified how these beliefs are represented.
note that this is all exclusive of risk, utility, and other concepts related to payoff...
add hyperlinks to definitions