| Social Software |
Article Index for Social |
Website Links For Social |
Information AboutSocial Software |
| CATEGORIES ABOUT SOCIAL SOFTWARE | |
| collaboration | |
| internet culture | |
| online social networking | |
| technology in society | |
| on-line chat | |
|
Social Software is an emerging field of research that studies formal tools such as formal models of knowledge and beliefs, the dynamics of information in a multi-agent setting, the foundations of game theory, and logics etc that may be used to prove correctness of certain Social Procedure s. INTRODUCTION We are all used to Computer Software , but what is Social Software? Actually, Social Software is both a new and an old idea. It is new in the sense that we have become aware of the idea of software only very recently. But it is also old since Social Engineering is quite well established. Institutions like elections, governments, postal systems, Robert’s Rules of Order, etc are all meant to organize social activity in a beneficial way – and here the key idea is ''organize''. The first third of the XXth century saw two important developments. One of these was Frank P. Ramsey ’s tracing of personal probabilities to an agent’s choices. This was a precursor to the work of de Bruno De Finetti , John Von Neumann and Morgenstern, and Savage. The other one was Turing’s invention of the Turing Machine and the formulation of the Church-Turing thesis according to which all computable functions on natural numbers were recursive or Turing computable. Game Theory – which is part of social software – has depended heavily on the first of these developments, since of course von Neumann and Morgenstern can be regarded as the fathers of Game theory. But the other development has received too little attention. This development led to the development and design of computers and also to fields like logic of programs, complexity theory and analysis of algorithms. It also resulted in much deeper understanding of algorithms, but only computer algorithms. Social algorithms remain largely unanalyzed except in special subfields like social choice theory or fair division Steven Brams and Alan Taylor, The Win-Win Solution: guaranteeing fair shares to everybody, Norton 1999.. These fields do not tend to analyze complex social algorithms as is done in computer science. A later development, going back to the work of Hintikka, Lewis and a little later Aumann Jaakko Hintikka, Knowledge and Belief: an introduction to the logic of the two notions, Cornell University press, 1962.R. Aumann, “Agreeing to disagree”, Annals of Statistics, 4 (1976) 1236-1239.D. Lewis, Convention, a Philosophical Study, Harvard U. Press, 1969., brought in the issue of knowledge. The notion of common knowledge is of course very important for Aumann as common knowledge of rationality can be seen as a justification for backward induction arguments. Some fact is common knowledge to Ann and Bob if Ann knows it, Bob knows it, Ann knows that Bob knows it, and so on. But knowledge too has received less attention than it might. We all know that the Plame affair had something to do with someone knowing something which they should not have, and someone revealing something which they should not have. But why should they not? Clearly because of certain possible consequences. Knowledge and knowledge transfer are ubiquitous in how social algorithms work. The goal of this article is to bring attention to the importance of the two issues of knowledge and logical structure of algorithms, and show the way to a broader arena in which social scientists and game theorists might want to play. Hopefully, in fact almost certainly, there is a rich general theory to be developed. An important early paper in this area is R. Parikh, “Social Software,” Synthese, 132, Sep 2002, 187-211.. This paper proposed studying social algorithms or social software in a serious way. It was followed by two doctoral dissertations, Marc Pauly, Logic for Social Software, Ph.D. Thesis, University of Amsterdam. ILLC Dissertation Series 2001-10, ISBN: 90-6196-510-1.Eric Pacuit, Topics in Social Software: Information in Strategic Situations Doctoral dissertaion, City University of New York (2005)., and four conferences devoted wholly or partly to social software. These took place in Copenhagen 2004, London, Utrecht and most recently at the City University of New York in May 2007. The notion of algorithm is implicit in so many things which happen in everyday life. We humans are tool-making creatures (as are chimps to a somewhat smaller extent) and both individual and social life is over-run with routines, from cooking recipes (Savage’s celebrated eggs to omelette example) to elections – a subject of much discussion going back to Con-dorcet. STRUCTURE Normally, a piece of social software or social algorithm has a logical structure. As was argued in R. Parikh, “Social Software,” Synthese, 132, Sep 2002, 187-211., this structure must address three important aspects, namely incentives, knowledge, and logical structure. For normally, an algorithm has logical structure, “A happens before B, which is succeeded by action C if condition X holds and by action D if X does not hold.” But quite often, the logical structure of the algorithm is parasitic on logical (or algorithmic) properties of existing physical or social structures. Clearly a prison needs a certain ''physical structure'' in order to be able to confine people, and a classroom needs a blackboard or a lectern in order for it to be usable as the venue of a lecture. Thus the teacher can now perform actions like write ”No class tomorrow” on the blackboard and the students can read what she wrote or copy it in their notebooks. The physical properties of the blackboard enable certain actions with their own algorithmic properties. A ''cultural structure'' with certain logical properties is a queue. The queue is a very popular institution which occurs both in daily life and in computer programs. In a computer program, a queue is a FIFO structure, where FIFO means, “First in, first out.” There are two operations, one by which an element is deleted from the front of the queue, and a second one where an element is added to the back of the queue. In real life, the queue could consist of people waiting at a bank to be served. The person deleted is the one who was at the front of the queue but is no longer in the queue, and who receives service from a teller. The element which is added is a new customer who has just arrived and who goes to the back of the queue. Clearly the queue implements our notions of fairness, (which can be proved rigorously as a theorem) that someone who came earlier gets service earlier, and in a bank this typically does happen. If someone in a bank tries to rush to the head of the line, people will stop him. We also have queues at bus stops and quite often the queue breaks down, there is a rush for seats at the last moment. I suspect the difference arises because things happen much faster in a bus queue than they do in a bank. At a bus stop, when the bus arrives, everything happens very fast and people are more interested in getting on the bus than in enforcing the rules. Consider now, by comparison, the problem of parking, which is a similar problem. A scarce resource needs to be allocated on the basis of some sort of priority, which, however, is difficult to determine. When people are looking for parking in a busy area, they tend to cruise around until they find a space. There is no queue as such, but in general we do want that someone who arrives first should find a parking space and someone who arrives later may not. This is much more likely in a university or company parking lot, which is compact, rather than on the street, where parking is distributed, and priority does play some role but it is a probabilistic role. This phenomenon has unfortunate consequences as Shoup {Link without Title} points out. ''When my students and I studied cruising for parking in a 15-block business district in Los Angeles, we found the average cruising time was 3.3 minutes, and the average cruising distance half a mile (about 2.5 times around the block). This may not sound like much, but with 470 parking meters in the district, and a turnover rate for curb parking of 17 cars per space per day, 8,000 cars park at the curb each weekday. Even a small amount of cruising time for each car adds up to a lot of traffic.'' ''Over the course of a year, the search for curb parking in this 15-block district created about 950,000 excess vehicle miles of travel – equivalent to 38 trips around the earth, or four trips to the moon. And here’s another inconvenient truth about underpriced curb parking: cruising those 950,000 miles wastes 47,000 gallons of gas and produces 730 tons of the greenhouse gas carbon dioxide. If all this happens in one small business district, imagine the cumulative effect of all cruising in the United States.'' Shoup regards this problem as one of incentive and suggests that parking fees be raised so that occupancy of street parking spaces is only 85%. But clearly this will penalize the less affluent drivers. The new fees will likely be still less than garage parking, affluent drivers will abandon garage parking for street parking, and the less affluent drivers will be priced out. “Well,” one might say, “they ''should'' be priced out, why don’t they take the bus?” But note that we do not need to charge people for standing in a queue. Surely queues would also be shorter if people had to pay to stand in them, but this has not occurred to anyone as a solution to the ‘standing in line problem.’ Ultimately, the difference between queues and searching for parking is structural. In one case there is an easy algorithmic solution which respects priority (more or less) and in the other case such solutions are harder to find – except when we are dealing with parking lots. An algorithmic solution would in fact be possible using something like a GPS system. If information about empty parking spaces was available to a central computer which could also accept requests from cars for parking spaces, and allocate spaces to arriving cars, then a solution could in fact be implemented. The information transfer and the allocation system would in effect convert the physically distributed parking spaces into the algorithmic equivalent of a compact parking lot. Here is another example. When you rent an apartment, you receive a key from the landlord. The key serves two purposes. Its possession is proof of a right, the right to enter the apartment. But its possession is also a physical enabler. The two are not the same of course, since if you lose your key, you still have the right but are not enabled. If some stranger finds the key, then he is enabled, but does not have the right. Thus the two properties of a key do not coincide perfectly. But normally the two do coincide. There are other analogs of a key which perform similar functions to a key. A password to a computer account is like a key, but does not need to be carried in your pocket. An ID card establishes your right to enter, but typically you need a guard to be present and to see your card and let you into the building. If the building is locked and the guard is not present, you are out of luck. In any case, these various generalized keys differ in some crucial ways. Stealing someone’s identity was at one time very difficult. You had to look like that person, know some personal facts, and you had to stay away from that person’s dog who knew perfectly well that you had a different smell. You needed a different ‘ID’ for the dog than you needed for people. But now identity theft is extremely easy. Lots of Social Security numbers, and mothers’ maiden names are out there for the taking, and people who do not look like you at all can make use of them. Personal appearance or brass keys which originally provided proof of “right to entry,” have been replaced by electronic items which are very easy to steal. Let x be an individual, and let R(x) mean that x has a right to use the key and E(x) mean that x is enabled by the key. Then we have two important conditions.
Clearly, safety is more important than liveness. If you lose your key and someone finds it, you are in trouble. But liveness also matters. A good notion of key must provide for both properties. In any case the structural problem (of safety) can be addressed at the incentive level, for instance by instituting heavy penalties for stealing identities. But we could also look for a structural solution without seeking to penalize anyone. Toddlers are apt to run away and into trouble, but we do not solve the problem by punishing them – we solve it by creating barriers to such escape, e.g., safety gates. Another interesting example is a fence. A farmer may have a fence to keep his sheep in, and the fence prevents certain kinds of movement – namely sheep running away. But sometimes on a university campus we will see a very low fence around a grassy area. Almost anyone can walk over the fence, so the fence is no longer a physical obstacle. Rather the value of the fence is now informational, it says, ''Thou shalt not cross''! With the yellow tape which the police sometimes put up, perhaps around a crime scene, or perhaps simply to block off some intersection, the ''Thou shalt not cross'' acquires quite a bit of punch. KNOWLEDGE ''Distributed Algorithms'' are much studied by computer scientists. A lot of commercial activity which goes on on the web has the property of being a distributed algorithm with many players. And of course the market is itself a very old distributed algorithm. In such algorithms, it is crucial to make sure that when agents have to act, they have the requisite knowledge. And models for calculating such knowledge have existed for some time; we ourselves have participated in constructing such models Parikh, R. and Ramanujam, R., A knowledge based semantics of messages, in J. Logic, Language, and Information, 12, pp. 453 - 467, 2003.R. Parikh and R. Ramanujam “Distributed Processing and the Logic of Knowledge,” in Logics of Programs Proceedings of a Conference at Brooklyn College, June 1985, Springer Lecture Notes in Computer Science #193, pp. 256-268.. See also Fagin, R., J. Halpern, Y. Moses and M. Vardi, Reasoning about Knowledge, MIT Press 1995.. The notion of ''common knowledge'' as the route to consensus was introduced by Aumann in R. Aumann, “Agreeing to disagree”, Annals of Statistics, 4 (1976) 1236-1239.. There is subsequent work by various people, including Geanakoplos and Polemarchakis Issues about how knowledge enters into social algorithms are discussed in Eric Pacuit and Rohit Parikh, “Reasoning about Communication Graphs,” Presented at Augustus de Morgan Workshop: Interactive Logic: Games and Social Software, 2006 (ADMW 2006). To appear in the proceedings of ADMW. Eric Pacuit, Rohit Parikh and Eva Cogan, “The Logic of Knowledge Based Obligation,” Knowledge, Rationality and Action, a subjournal of Synthese, 149(2), 311 – 341, 2006.Parikh, R. and Ramanujam, R., A knowledge based semantics of messages, in J. Logic, Language, and Information, 12, pp. 453 - 467, 2003.. Parikh, R. and Ramanujam, R., A knowledge based semantics of messages, in J. Logic, Language, and Information, 12, pp. 453 - 467, 2003. actually ddiscusses how a framework for defining knowledge can be developed. A finite number of agents have some private information to start with, and they exchange messages. Each exchange of messages reveals something about the situation, or, in technical terms, it reduces the size of the relevant Kripke structure or Aumann structure. An agent who has seen some events but not others can make guesses as to what other events ''could'' have taken place and it knows some fact ''phi'' iff ''phi'' would be true ''regardless'' of how the unseen events went. This framework is used in both Eric Pacuit, Rohit Parikh and Eva Cogan, “The Logic of Knowledge Based Obligation,” Knowledge, Rationality and Action, a subjournal of Synthese, 149(2), 311 – 341, 2006.Eric Pacuit and Rohit Parikh, “Reasoning about Communication Graphs,” Presented at Augustus de Morgan Workshop: Interactive Logic: Games and Social Software, 2006 (ADMW 2006). To appear in the proceedings of ADMW.. Eric Pacuit and Rohit Parikh, “Reasoning about Communication Graphs,” Presented at Augustus de Morgan Workshop: Interactive Logic: Games and Social Software, 2006 (ADMW 2006). To appear in the proceedings of ADMW. discusses agents who are connected along some graph, and knowledge can move only along the edges of a graph. Thus if agent ''i'' is not connected to agent ''j'', then ''i'' cannot directly obtain information from ''j'', but might get such information via a third agent ''k'', as in fact Novak got some information from Judith Miller. Such edges may be approved or disapproved, and if information transfer took place along a disapproved edge, then that could be cause for legal sanctions, not because harm had occurred, but because harm ''could'' occur and the algorithm was no longer secure. It is shown in Eric Pacuit and Rohit Parikh, “Reasoning about Communication Graphs,” Presented at Augustus de Morgan Workshop: Interactive Logic: Games and Social Software, 2006 (ADMW 2006). To appear in the proceedings of ADMW. that the graph completely determines the logical properties of possible states of knowledge, and vice versa. An early version of this paper already discussed the Plame case before it hit the headlines. In Eric Pacuit, Rohit Parikh and Eva Cogan, “The Logic of Knowledge Based Obligation,” Knowledge, Rationality and Action, a subjournal of Synthese, 149(2), 311 – 341, 2006. we consider how obligations arise from knowledge. We consider the following examples: Example 1: Uma is a physician whose neighbour is ill. Uma does not know and has not been informed. Uma has no obligation (as yet) to treat the neighbour. Example 2: Uma is a physician whose neighbour Sam is ill. The neighbour’s daughter Ann comes to Uma’s house and tells her. Now Uma does have an obligation to treat Sam, or perhaps call in an ambulance or a specialist. Example 3: Mary is a patient in St. Gibson’s hospital. Mary is having a heart attack. The caveat which applied in case a) does not apply here. The hospital has an obligation to be ''aware'' of Mary’s condition at all times and to provide emergency treatment as appropriate. In such cases, when an agent cannot herself take a requisite action, it is incumbent upon her to provide such information to the agent who can take such action. Or, as in the case of the hospital, the agent has an obligation not only to act, but also to gather knowledge so as to be ''able to act'' when the occasion arises. A milder example of such situations consists of requiring homeowners to install fire alarms. Again the semantics from Parikh, R. and Ramanujam, R., A knowledge based semantics of messages, in J. Logic, Language, and Information, 12, pp. 453 - 467, 2003. is used. Various possible sequences of events are possible, depending on the actions taken by the agents. Some of these sequences are better than others, and some, indeed are disastrous, as when a patient is not treated for lack of information. It is shown how ''having information'' creates obligations on the agents, and also how the need to ''convey information'' arises, when one knows that an agent who could carry out some required action lacks the requisite information. REFERENCES SEE ALSO EXTERNAL LINKS |
|
|