Two-Sided Manipulation Games in Stable Matching Markets Article Swipe
Seyed Hossein Hosseini
,
Grzegorz Lisowski
,
Shraddha Pathak
·
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2506.00554
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2506.00554
The Deferred Acceptance (DA) algorithm is an elegant procedure for finding a stable matching in two-sided matching markets. It ensures that no pair of agents prefers each other to their matched partners. In this work, we initiate the study of two-sided manipulations in matching markets as non-cooperative games. We introduce the accomplice manipulation game, where a man misreports to help a specific woman obtain a better partner, whenever possible. We provide a polynomial time algorithm for finding a pure strategy Nash equilibrium (NE) and show that our algorithm always yields a stable matching - although not every Nash equilibrium corresponds to a stable matching. Additionally, we show how our analytical techniques for the accomplice manipulation game can be applied to other manipulation games in matching markets, such as one-for-many and the standard self-manipulation games. We complement our theoretical findings with empirical evaluations of different properties of the resulting NE, such as the welfare of the agents.
Related Topics
Concepts
No concepts available.
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2506.00554
- https://arxiv.org/pdf/2506.00554
- OA Status
- green
- OpenAlex ID
- https://openalex.org/W4414891019
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4414891019Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2506.00554Digital Object Identifier
- Title
-
Two-Sided Manipulation Games in Stable Matching MarketsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2025Year of publication
- Publication date
-
2025-05-31Full publication date if available
- Authors
-
Seyed Hossein Hosseini, Grzegorz Lisowski, Shraddha PathakList of authors in order
- Landing page
-
https://arxiv.org/abs/2506.00554Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2506.00554Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2506.00554Direct OA link when available
- Cited by
-
0Total citation count in OpenAlex
Full payload
| id | https://openalex.org/W4414891019 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2506.00554 |
| ids.doi | https://doi.org/10.48550/arxiv.2506.00554 |
| ids.openalex | https://openalex.org/W4414891019 |
| fwci | |
| type | preprint |
| title | Two-Sided Manipulation Games in Stable Matching Markets |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11182 |
| topics[0].field.id | https://openalex.org/fields/18 |
| topics[0].field.display_name | Decision Sciences |
| topics[0].score | 0.9973999857902527 |
| topics[0].domain.id | https://openalex.org/domains/2 |
| topics[0].domain.display_name | Social Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1803 |
| topics[0].subfield.display_name | Management Science and Operations Research |
| topics[0].display_name | Auction Theory and Applications |
| topics[1].id | https://openalex.org/T10991 |
| topics[1].field.id | https://openalex.org/fields/20 |
| topics[1].field.display_name | Economics, Econometrics and Finance |
| topics[1].score | 0.9950000047683716 |
| topics[1].domain.id | https://openalex.org/domains/2 |
| topics[1].domain.display_name | Social Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/2002 |
| topics[1].subfield.display_name | Economics and Econometrics |
| topics[1].display_name | Game Theory and Voting Systems |
| topics[2].id | https://openalex.org/T11031 |
| topics[2].field.id | https://openalex.org/fields/18 |
| topics[2].field.display_name | Decision Sciences |
| topics[2].score | 0.9714999794960022 |
| topics[2].domain.id | https://openalex.org/domains/2 |
| topics[2].domain.display_name | Social Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1803 |
| topics[2].subfield.display_name | Management Science and Operations Research |
| topics[2].display_name | Game Theory and Applications |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2506.00554 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2506.00554 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2506.00554 |
| locations[1].id | doi:10.48550/arxiv.2506.00554 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2506.00554 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5041205664 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-5115-9332 |
| authorships[0].author.display_name | Seyed Hossein Hosseini |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Hosseini, Hadi |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5100493811 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Grzegorz Lisowski |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Lisowski, Grzegorz |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5105103096 |
| authorships[2].author.orcid | |
| authorships[2].author.display_name | Shraddha Pathak |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Pathak, Shraddha |
| authorships[2].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2506.00554 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Two-Sided Manipulation Games in Stable Matching Markets |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11182 |
| primary_topic.field.id | https://openalex.org/fields/18 |
| primary_topic.field.display_name | Decision Sciences |
| primary_topic.score | 0.9973999857902527 |
| primary_topic.domain.id | https://openalex.org/domains/2 |
| primary_topic.domain.display_name | Social Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1803 |
| primary_topic.subfield.display_name | Management Science and Operations Research |
| primary_topic.display_name | Auction Theory and Applications |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2506.00554 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2506.00554 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2506.00554 |
| primary_location.id | pmh:oai:arXiv.org:2506.00554 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2506.00554 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2506.00554 |
| publication_date | 2025-05-31 |
| publication_year | 2025 |
| referenced_works_count | 0 |
| abstract_inverted_index.- | 93 |
| abstract_inverted_index.a | 11, 55, 60, 64, 71, 77, 90, 101 |
| abstract_inverted_index.In | 32 |
| abstract_inverted_index.It | 18 |
| abstract_inverted_index.We | 48, 69, 134 |
| abstract_inverted_index.an | 6 |
| abstract_inverted_index.as | 45, 127, 150 |
| abstract_inverted_index.be | 117 |
| abstract_inverted_index.in | 14, 42, 123 |
| abstract_inverted_index.is | 5 |
| abstract_inverted_index.no | 21 |
| abstract_inverted_index.of | 23, 39, 142, 145, 153 |
| abstract_inverted_index.to | 28, 58, 100, 119 |
| abstract_inverted_index.we | 35, 105 |
| abstract_inverted_index.NE, | 148 |
| abstract_inverted_index.The | 0 |
| abstract_inverted_index.and | 83, 129 |
| abstract_inverted_index.can | 116 |
| abstract_inverted_index.for | 9, 75, 111 |
| abstract_inverted_index.how | 107 |
| abstract_inverted_index.man | 56 |
| abstract_inverted_index.not | 95 |
| abstract_inverted_index.our | 86, 108, 136 |
| abstract_inverted_index.the | 37, 50, 112, 130, 146, 151, 154 |
| abstract_inverted_index.(DA) | 3 |
| abstract_inverted_index.(NE) | 82 |
| abstract_inverted_index.Nash | 80, 97 |
| abstract_inverted_index.each | 26 |
| abstract_inverted_index.game | 115 |
| abstract_inverted_index.help | 59 |
| abstract_inverted_index.pair | 22 |
| abstract_inverted_index.pure | 78 |
| abstract_inverted_index.show | 84, 106 |
| abstract_inverted_index.such | 126, 149 |
| abstract_inverted_index.that | 20, 85 |
| abstract_inverted_index.this | 33 |
| abstract_inverted_index.time | 73 |
| abstract_inverted_index.with | 139 |
| abstract_inverted_index.every | 96 |
| abstract_inverted_index.game, | 53 |
| abstract_inverted_index.games | 122 |
| abstract_inverted_index.other | 27, 120 |
| abstract_inverted_index.study | 38 |
| abstract_inverted_index.their | 29 |
| abstract_inverted_index.where | 54 |
| abstract_inverted_index.woman | 62 |
| abstract_inverted_index.work, | 34 |
| abstract_inverted_index.agents | 24 |
| abstract_inverted_index.always | 88 |
| abstract_inverted_index.better | 65 |
| abstract_inverted_index.games. | 47, 133 |
| abstract_inverted_index.obtain | 63 |
| abstract_inverted_index.stable | 12, 91, 102 |
| abstract_inverted_index.yields | 89 |
| abstract_inverted_index.agents. | 155 |
| abstract_inverted_index.applied | 118 |
| abstract_inverted_index.elegant | 7 |
| abstract_inverted_index.ensures | 19 |
| abstract_inverted_index.finding | 10, 76 |
| abstract_inverted_index.markets | 44 |
| abstract_inverted_index.matched | 30 |
| abstract_inverted_index.prefers | 25 |
| abstract_inverted_index.provide | 70 |
| abstract_inverted_index.welfare | 152 |
| abstract_inverted_index.Deferred | 1 |
| abstract_inverted_index.although | 94 |
| abstract_inverted_index.findings | 138 |
| abstract_inverted_index.initiate | 36 |
| abstract_inverted_index.markets, | 125 |
| abstract_inverted_index.markets. | 17 |
| abstract_inverted_index.matching | 13, 16, 43, 92, 124 |
| abstract_inverted_index.partner, | 66 |
| abstract_inverted_index.specific | 61 |
| abstract_inverted_index.standard | 131 |
| abstract_inverted_index.strategy | 79 |
| abstract_inverted_index.whenever | 67 |
| abstract_inverted_index.algorithm | 4, 74, 87 |
| abstract_inverted_index.different | 143 |
| abstract_inverted_index.empirical | 140 |
| abstract_inverted_index.introduce | 49 |
| abstract_inverted_index.matching. | 103 |
| abstract_inverted_index.partners. | 31 |
| abstract_inverted_index.possible. | 68 |
| abstract_inverted_index.procedure | 8 |
| abstract_inverted_index.resulting | 147 |
| abstract_inverted_index.two-sided | 15, 40 |
| abstract_inverted_index.Acceptance | 2 |
| abstract_inverted_index.accomplice | 51, 113 |
| abstract_inverted_index.analytical | 109 |
| abstract_inverted_index.complement | 135 |
| abstract_inverted_index.misreports | 57 |
| abstract_inverted_index.polynomial | 72 |
| abstract_inverted_index.properties | 144 |
| abstract_inverted_index.techniques | 110 |
| abstract_inverted_index.corresponds | 99 |
| abstract_inverted_index.equilibrium | 81, 98 |
| abstract_inverted_index.evaluations | 141 |
| abstract_inverted_index.theoretical | 137 |
| abstract_inverted_index.manipulation | 52, 114, 121 |
| abstract_inverted_index.one-for-many | 128 |
| abstract_inverted_index.Additionally, | 104 |
| abstract_inverted_index.manipulations | 41 |
| abstract_inverted_index.non-cooperative | 46 |
| abstract_inverted_index.self-manipulation | 132 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile |