Preferences are ubiquitous and unavoidable when dealing with interacting agents. This workshop consists of five talks by researchers in preference representation, highlighting recent work. The workshop follows Joel Uckelman's PhD defense (thesis) at 10:00 in the Agnietenkapel, on the same day. No registration is required; all are welcome.
Room A1.04, Science Park 904
ILLC, University of Amsterdam
Amsterdam, 11 December 2009
| 14:00–14:35 | Stable marriages: manipulation properties and compact preference representation | Francesca Rossi |
|---|---|---|
| 14:35–15:10 | Reasoning about preferences and coalitions in modal logics: Towards a unifying viewpoint | Cédric Dégremont |
| 15:10–15:45 | Prof Kripke, let me introduce Prof Nash: Incentive compatible social law design | Michael Wooldridge |
| 15:45–16:15 | coffee break | |
| 16:15–16:50 | Proof-Nets for Modelling Combinatorial Auctions | Daniele Porello |
| 16:50–17:25 | Voting with incomplete information: communication and compilation issues | Jérôme Lang |
The stable marriage problem is a well-known preference-based problem of matching men to women so that no man and woman who are not married to each other both prefer each other. Such a problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals to matching students to schools. A well-known algorithm to solve this problem is the Gale-Shapley algorithm, which runs in quadratic time in the number of men/women.
It has been proven that stable marriage procedures can always be manipulated. Whilst the Gale-Shapley algorithm is computationally easy to manipulate, we prove that there exist stable marriage procedures which are NP-hard to manipulate. We also consider the relationship between voting theory and stable marriage procedures, showing that voting rules which are NP-hard to manipulate can be used to define stable marriage procedures which are themselves NP-hard to manipulate.
Most algorithms to find stable marriages assume that the participants explicitly express a preference ordering. This can be problematic when the number of options is large or has a combinatorial structure. We consider using soft constraints or CP-nets, two compact preference formalisms, to model preferences compactly in stable marriage problems, and we study the computational complexity to find the next preferred partner (a crucial operation in the Gale-Shapley algorithm) in such formalisms.
Abstract soon...
We formulate a model of social laws (aka normative systems) from the point of view of a designer who wishes to manage/coordinate/regulate a system that is modelled as a Kripke structure. We then consider the issue of non-compliance to the social law, and this leads us to consider the compliance problem from the point of view of mechanism design: we aim to design a social law so that compliance is a rational choice (a Nash equilibrium) for all participants.
We show that linear logic proof-nets, a graph-theoretic interpretation of linear logic proofs, can serve as an expressive framework in which to model a rich variety of combinatorial auction mechanisms. Due to its resource-sensitive nature, linear logic can easily represent agent preferences in combinatorial auctions in which goods may be sold in multiple units, and we show how it naturally generalises several bidding languages familiar from the literature. Moreover, the winner determination problem, i.e., the problem of computing an allocation of goods to bidders producing a certain amount of revenue for the auctioneer, can be modelled as the problem of finding a proof-net for a particular linear logic sequent. This is joint work with Ulle Endriss.
We develop a unified viewpoint on modal logics for cooperation of agents that have preferences.
We first consider different families of normal modal cooperation logics—one of them containing the normal simulation of Pauly's Coalition Logic—and prove embedding results that clarify the relations between them.
Then, we determine how demanding certain game theoretical and social choice theoretical notions are for modal logics in terms of expressive power and complexity. We show how these notions can be interpreted on three different classes of models, and identify via invariance results the expressive power required for these notions. Explicit definability results in extended modal languages are given for each notion and class of models. Complexity results for extended modal logics are then used to obtain upper bounds on the complexity (model checking and satisfiability) of modal logics expressing the notions. Our analysis shows how the choice of models (simple models with coalitional power as a primitive vs. more complex power based or action based models) effects the expressive power required to express the notions.
Finally we raise the question of how results from the computational choice literature could be relevant: 1. to obtain lower bounds and 2. to study the complexity effects of using modal logics with a more compact preference representation.
Sponsored by GLoRiClass, the Institute for Logic, Language and Computation, and NWO Vidi project 639.022.706.