Whenever the outcome of some social choice process depends on the information collected from a number of self-interested agents, strategic issues come into play and mechanism design techniques have to be used in order to motivate all agents to truthfully report the relevant information they own as their private knowledge. The talk illustrates some general background on these techniques and specific methods that can be applied when some kind of verification on the declarations of the agents is possible. In particular, attention is focused on analysing a class of mechanisms that naturally arise in the context of allocation problems, by proposing to interpret them in terms of well-known solution concepts for coalitional games. Complexity issues arising in this setting are also discussed, and structural requirements are investigated which can be used to identify islands of tractability.
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.