Matchings with Externalities and Attitudes

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Simina Branzei
  • Tomasz Michalak, University of Warsaw, Poland
  • Talal Rahwan, University of Southampton, United Kingdom
  • Kate Larson, University of Waterloo, Canada
  • Nicholas 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. Under this framework, we analyze many-to-many matchings and one-to-one matchings where agents take different attitudes when reasoning about the actions of others. In particular, we study optimistic, neutral and pessimistic attitudes and provide both computational hardness results and polynomial-time algorithms for computing stable outcomes.
Original languageEnglish
Title of host publicationInternational Conference on Autonomous Agents and Multi-agent Systems, AAMAS '13
EditorsMaria Gina, Onn Shehory
Number of pages8
PublisherAssociation for Computing Machinery
Publication year1 May 2013
ISBN (print)978-1-4503-1993-5
Publication statusPublished - 1 May 2013
EventInternational Conference on Autonomous Agents and Multiagent Systems - St Paul, United States
Duration: 6 May 201310 May 2013


ConferenceInternational Conference on Autonomous Agents and Multiagent Systems
LandUnited States
BySt Paul

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 54561040