Aarhus University Seal / Aarhus Universitets segl

Matching Games with Additive Externalities

Research output: Working paper/Preprint Working paperResearch

  • Simina Branzei
  • Tomasz Michalak, Oxford Unviersity, United Kingdom
  • Talal Rahwan, University of Southampton, United Kingdom
  • Kate Larson, School of Computer Science, University of Waterloo, Canada
  • Nicholas R. Jennings, University of Southampton, United Kingdom
Two-sided matchings are an important theoretical tool used to model markets and social interactions. In many real life problems the utility of an agent is influenced not only by their own choices, but also by the choices that other agents make. Such an influence is called an externality. Whereas fully expressive representations of externalities in matchings require exponential space, in this paper we propose a compact model of externalities, in which the influence of a match on each agent is computed additively. In this framework, we analyze many-to-many and one-to-one matchings under neutral, optimistic, and pessimistic behaviour, and provide both computational hardness results and polynomial-time algorithms for computing stable outcomes.
Original languageEnglish
Number of pages14
Publication statusPublished - 2012

See relations at Aarhus University Citationformats

ID: 52502218