WP2: Communication

Coordinator: Jérôme Lang

This work package is dedicated to the study of the communication cost of the various mechanisms considered in this project (voting, resource allocation, coalition structure formation). We are interested in the following questions: what amount of information needs to be exchanged so as to find the winner(s), to determine an optimal allocation of resources, to find a stable coalition structure?

  • Incomplete preferences; ordinality vs. cardinality

Interesting collective decision mechanisms often require agents to specify a lot of information. To start with, voting rules require agents to rank all alternatives, which is often unpractical from a cognitive point of view, as soon as the number of alternatives is more than a small number (such as 4 or 5); a good trade-off is then to consider incomplete rankings on which variants or approximations of voting rules are applied. Even more problematic is the assumption, often required in fair division or coalition structure formation, that agents should rank all subsets of objects or all subsets of agents. In such a case, a good trade-off is to rank only singletons, and apply a preference extension principle to derive a preference over subsets. One of our goals is to evaluate the quality of the trade-off between the amount of information required and the quality of t solution obtained in these various settings.

  • Incremental elicitation

While computing a solution from a partial description of agents’ preferences can often be seen as a good trade-off between solution quality and communication costs, sometimes it can be improved by an interactive elicitation protocol, where agents first specify a small amount of information, and then receive more queries until a satisfactory solution is found. We focus on incremental elicitation protocols for various collective decision making problems.

  • Distributed mechanisms

While elicitation assumes that communication can take place between the agents and a central authority, in some other cases it can take place between the agents themselves, who interact in a decentralized way. Our focus is on designing distributed protocols for various collective decision making problems.

  • Domain restrictions and preference representation languages

Another way of helping agents to express their preferences is by provide them with a language for succinct preference representation. These languages generally come with a restriction on the preference relations they are able to express (and with an increase of computational complexity).