Games in Logic, Language and Computation 11Amsterdam, September 19 2005
| ||||||||||||||||||||||||||
About the workshopThis workshop is the eleventh episode in an irregular workshop series called Games in Logic, Language and Computation. These workshops have been organised at different locations in The Netherlands (see this page for an overview of previous episodes). These workshops are intended as a informal and lively discussion platform, where both senior researchers and promising young researchers from different backgrounds can share ideas. In this episode, attention is given to computational aspects such as complexity, to applications in social science, and to the uses of games inside logic.Attendance of this workshop is free. If you intend to visit, you are requested to send an email to Sieuwert van Otterloo (sieuwert _at_ bluering . nl). The workshop is generously sponsored by
| ||||||||||||||||||||||||||
Programme
| ||||||||||||||||||||||||||
LocationThe workshop takes place in room D.028, Nieuwe Achtergracht 129 in Amsterdam. To reach this building, take the metro to Weesperplein. | ||||||||||||||||||||||||||
Speakers and AbstractsUlle EndrissILLC, University of AmsterdamAs proposed in various places, a set of propositional formulas, each associated with a numerical weight, can be used to model the preferences of an agent in combinatorial domains. If the range of possible choices can be represented by the set of possible assignments of propositional symbols to truth values, then the utility of an assignment is given by the sum of the weights of the formulas it satisfies. In this talk, we are going to exemplify several correspondences between certain types of weighted formulas and well-known classes of utility functions (such as monotonic, concave or k-additive functions). We are also going to comment both on the comparative succinctness of different types of weighted formulas for representing the same class of utility functions and on some related complexity issues. Wilfrid HodgesQueen Mary University of LondonWe consider problems of the following kind. Objects are to be constructed on the basis of some data, and certain agents have intentions that these objects should have certain properties. How can we define a class of games (parametrised by the data) so that the agents are the players, and the games allow each agent to act out his or her intentions? For example, should the object emerge out of the play or out of players' winning strategies? What moves should be allowed to which players? My claim is that there are canons of rationality, not for the players but for the designers of such games, and in the academic community these canons could be observed more than they usually are. Johan van BenthemILLC, University of AmsterdamStatements made to us not only update our current knowledge, but can also have other dynamic effects. In particular, suggestions or commands may 'upgrade' our current preferences. So far, much work has been done on knowledge update, but little on explicit dynamic logics of preference upgrade. We propose a logic of knowledge update plus preference upgrade that works just like a dynamic-epistemic logic in having a complete set of reduction axioms, but with some new twists in changing the relevant relations. This system can model issues of changing obligations, conflicting commands, or 'regret'. Moreover, it has a product update version which allows for preferences between actions, in addition to those between worlds, a move which has also been proposed elsewhere in dynamic logic. At this stage, we also find it convenient to look at the issues from a second perspective, viz. upgrade of explicit utilities. We also propose a utility upgrade logic, on the analogy of product update systems for graded belief models. We show how this second system can deal with update logics for defaults. Some delicate differences come up when comparing our two kinds of preference upgrade, which we are still trying to resolve. But construed either way, given the ubiquity of preference relations in many settings (deontic logic, games, conditional logic), we think understanding the dynamics of preference is important. We conclude with some illustrations in deontic reasoning. (joint work with Fenrong Liu) Sieuwert van OtterlooSieuwert van Otterloo is a researcher at the University of Liverpool, and has been a visiting researcher at the ILLC in the last 10 months.Eric PacuitILLC, University of AmsterdamIn 1992, Moss and Parikh studied a bimodal logic of knowledge and effort called Topologic. We show how to extend Topologic to the case of many agents who are assumed to have some private information at the outset, but may refine their information by acquiring information possessed by other agents, possibly via yet other agents. We assume that the agents are connected by a communication graph. In the communication graph, an edge from agent i to agent j means that agent i can directly receive information from agent j. Agent i can then refine its own information by learning information that j has, including information acquired by j from another agent, k. We introduce a multi-agent modal logic with knowledge modalities and a modality representing communication among agents. Merlijn SevensterFrom the huge space of logical generalized quantifiers, what are the ones that occur in natural language and why so? This is the "basic question facing anyone who studies natural language quantification" (Westerstahl, 1989). In my presentation I show that model checking any sentence with a natural language determiner is of very low complexity, TC0. This means that verifying gossip like "Most boys fancy an odd number of girls" on a birthday party, can be done by a constant depth circuit, with only THRESHOLD and NOT gates. TC0 is of low complexity indeed: it is contained in log-space.I observe that well-known operations on quantifiers like iteration, cumulation, and resumption all yield quantifiers that can be verified in TC0. However, this does not hold for branching quantifiers, as introduced by Barwise (1979): Checking whether "Most boys and most girls fancy each other" is NP-complete! Assuming that humanly feasible problems have polynomial-time complexity and PTIME is not equal to NP, this means that in the worst case one may not know whether the rumor is true, when the host of the party has gone to bed (alone) long ago. Time permitting, I relate our investigations to abstract model theory and cognitive empirical research. Bernard WalliserB. Walliser (ENPC, Paris)(joint work with A. Billot (Paris 2), J.-C. Vergnaud (Paris 1)) A syntactical and a semantical framework are proposed for the modeling of a multiplayer belief revision rule that allows to study the impact of a message on the initial beliefs within a game structure. For that purpose, we introduce first various types of accuracy relations expressing that one knows more in a belief hierarchy than in another. Then, we define the status of a message especially in the case of a secret, private and public message, and we design a belief revision rule such that the accuracy property can be shown to be carried from the message to the final beliefs (for a given initial belief). Finally, we define a semantic game and we prove in this context that the information value of a message is positive
Michael WooldridgeUniversity of LiverpoolThe multi-agent systems field is primarily concerned with systems composed of multiple self-interested autonomous or semi-autonomous computational entities known as agents. Game theory has proved to be a useful tool for understanding the property of such systems; and yet standard game theoretic models of cooperative systems are typically not directly applicable to the problem of understanding and reasoning about computational multi-agent systems. In this seminar, we present a type of coalitional game in which agents are each assumed to have a goal to be achieved, and where the characteristic property of a coalition is a set of choices, with each choice denoting a set of goals that would be achieved if the choice was made. Such qualitative coalitional games (QCGs) are a natural tool for modelling goal-oriented multiagent systems. After introducing and formally defining QCGs, we systematically formulate a range natural solution concepts and associated decision problems for QCGS, and investigate the computational complexity of these problems. For example, we formulate a notion of coalitional stability inspired by that of the core from conventional coalitional games, and prove that the problem of showing that the core of a QCG is non-empty is Dp-complete. We conclude by discussing the relationship of our work to other research on coalitional reasoning in multiagent systems, and present some avenues for future research. (This talk will include joint work with Paul E. Dunne.) Audrey YapStanford UniversityThe motivation behind this paper is to look at temporal information in models of BMS product update. That is, it may be useful to look at models produced through taking products with action models, as being structurally similar to game trees. So a state in a product can be seen as encoding a history of actions, along with an original world. Given that, it seems useful to add the ability to express information about past states. For this purpose, we can combine a temporal modality with product update. This involves adding a new modality to the language allowing us to form statements similar to, "Before you did c, I did not know whether phi was true, but now I know that phi is false." | ||||||||||||||||||||||||||
Links
|