research-article

Matchings with externalities and attitudes

Authors:

Simina Brânzei,

Tomasz Michalak,

Nicholas R. JenningsAuthors Info & Claims

AAMAS '13: Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems

Pages 295 - 302

Published: 06 May 2013 Publication History

Abstract

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.

References

[1]

H. Aziz, F. Brandt, and H. G. Seedig. Stable partitions in additively separable hedonic games. In Proceedings of AAMAS, pages 183--190, 2011.

Digital Library

[2]

E. Bodine-Baron, C. Lee, A. Chong, B. Hassibi, and A. Wierman. Peer effects and stability in matching markets. In Proceedings of SAGT, 2011.

Digital Library

[3]

D. Braziunas and C. Boutilier. Preference elicitation and generalized additive utility. In Proceedings of AAAI, pages 1573--1576, 2006.

Digital Library

[4]

R. Burkard, M. Dell'Amico, and S. Martello. Assignment Problems. SIAM, 2009.

Digital Library

[5]

B. Dutta and J. Masso. Stability of Matchings when Individuals have Preferences over Colleagues. J. Econ. Theory, 75:464--475, 1997.

[6]

F. Echenique and J. Oviedo. A Theory of Stability in Many-to-Many Matching Markets. Theoretical Economics, 1(2):233--273, 2006.

[7]

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.

Digital Library

[8]

G. Gigerenzer and R. Selten, editors. Bounded rationality: The adaptive toolbox. MIT Press, 2001.

[9]

I. Hafalir. Stability of marriage with externalities. Int. J. Game Theory, 37:353--370, 2008.

Digital Library

[10]

M. O. Jackson. Social and Economic Networks. Princeton University Press, 2008.

Digital Library

[11]

B. Klaus and M. Walzl. Stable Many-to-Many Matchings with Contracts. J. Math. Econ., 45(7--8):422--434, 2009.

[12]

L. Koczy. A Recursive Core for Partition Function Form Games. Theor. Decis., 63:41--51, 2007.

[13]

L. Koczy. Sequential Coalition Formation and the Core in the Presence of Externalities. Game. Econ. Behav., 66(1):559--565, 2009.

[14]

A. E. Roth and M. O. Sotomayor. Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press, 1990.

[15]

H. Sasaki and M. Toda. Two-Sided Marriage Problems with Externalities. J. Econ. Theory, 70(1):93--108, 1996.

Cited By

Seddighin MSaleh HGhodsi M(2019)Externalities and FairnessThe World Wide Web Conference10.1145/3308558.3313670(538-548)Online publication date: 13-May-2019
https://dl.acm.org/doi/10.1145/3308558.3313670
Meir RParkes DAndre EKoenig SDastani MSukthankar G(2018)Playing the Wrong GameProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237403(86-94)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237403
Anshelevich EBhardwaj OHoefer M(2017)Stable Matching with Network ExternalitiesAlgorithmica10.1007/s00453-016-0197-978:3(1067-1106)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s00453-016-0197-9
Show More Cited By

Index Terms

Matchings with externalities and attitudes
1. Applied computing
  1. Law, social and behavioral sciences
    1. Economics
2. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Multi-agent systems

Recommendations

Combinatorial auctions with externalities
AAMAS '10: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 1

Although combinatorial auctions have received a great deal of attention from the computer science community over the past decade, research in this domain has focussed on settings in which a bidder only has preferences over the bundles of goods they ...
Expressive auctions for externalities in online advertising
WWW '10: Proceedings of the 19th international conference on World wide web

When online ads are shown together, they compete for user attention and conversions, imposing negative externalities on each other. While the competition for user attention in sponsored search can be captured via models of clickthrough rates, the post-...
Optimal auctions with positive network externalities
EC '11: Proceedings of the 12th ACM conference on Electronic commerce

We consider the problem of designing auctions in social networks for goods that exhibit single-parameter submodular network externalities in which a bidder's value for an outcome is a fixed private type times a known submodular function of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

AAMAS '13: Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems

May 2013

1500 pages

ISBN:9781450319935

General Chairs:
Maria Gini
University of Minnesota, USA
,
Onn Shehory
IBM Haifa Research Lab, Israel
,
Program Chairs:
Takayuki Ito
Nagoya Institute of Technology, Japan
,
Catholijn Jonker
Delft Institute of Technology, The Netherlands

Sponsors

IFAAMAS

In-Cooperation

SIGAI: ACM Special Interest Group on Artificial Intelligence

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 06 May 2013

Check for updates

Author Tags

Qualifiers

Research-article

Conference

AAMAS '13

Sponsor:

AAMAS '13: International conference on Autonomous Agents and Multi-Agent Systems

May 6 - 10, 2013

MN, St. Paul, USA

Acceptance Rates

AAMAS '13 Paper Acceptance Rate 140 of 599 submissions, 23%;

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
109
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Seddighin MSaleh HGhodsi M(2019)Externalities and FairnessThe World Wide Web Conference10.1145/3308558.3313670(538-548)Online publication date: 13-May-2019
https://dl.acm.org/doi/10.1145/3308558.3313670
Meir RParkes DAndre EKoenig SDastani MSukthankar G(2018)Playing the Wrong GameProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237403(86-94)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237403
Anshelevich EBhardwaj OHoefer M(2017)Stable Matching with Network ExternalitiesAlgorithmica10.1007/s00453-016-0197-978:3(1067-1106)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s00453-016-0197-9
Zick YElkind E(2014)Arbitration and stability in cooperative gamesACM SIGecom Exchanges10.1145/2692359.269236812:2(36-41)Online publication date: 25-Nov-2014
https://dl.acm.org/doi/10.1145/2692359.2692368

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents