Edge Rewrite
everything Source code View original
// HTMLRewriter · presentation

This page was redesigned at the edge.

Cloudflare fetched the original article and streamed it through HTMLRewriter to apply an entirely new visual system without rebuilding the source page.

// request.cf · coarse context

A page that knows where it met you.

Only coarse request metadata is shown. This demo does not display or persist visitor IP addresses.

Country
US
Cloudflare location
CMH
Connection
HTTP/2
Language
Not provided

Ray ID: a22c7c491a864afc

Jump to content

// Workers AI · dad joke modeWhat did popular matching data say to its friend? "You match my criteria.

Add links
From Wikipedia, the free encyclopedia

In the theory of matching markets, a popular matching is a matching that at least half of the agents prefer over any other matching. In other words, it is a (weak) Condorcet winner in the elections where the candidates are all possible matchings. The notion was invented in 1975 by Peter Gardenfors.[1]

Popularity vs. stability

[edit]

A stable matching is a matching that is not "blocked" by any pair of agents. That is, no two agents prefer to be matched to each other than to be matched to their present partners.

Every stable matching is popular.[1] This is because, for every other matching, in every pair of matched agents, at least one member of the pair prefers the original matching. But the opposite is not true: there may be popular matchings that are not stable. As an example,[2] suppose there are two men: David and Palti, and two women: Michal and Abigail. The preferences are:

  • David prefers Michal to Abigail;
  • Palti can only be matched to Michal.
  • Michal prefers David to Palti;
  • Abigail can only be matched to David.

The only stable matching is David-Michal, as in any other matching, David and Michal form a blocking pair. Note that the size of this matching is 1, as Abigail and Palti cannot be matched to each other.

The matching David-Abigail and Michal-Palti is not stable, but it is "popular". Specifically, in the vote between the stable matching (David-Michal) and the non-stable matching, two agents (namely David and Michal) vote for the stable matching, and the other two agents vote for the non-stable matching. So both matchings are popular, but only one of them is stable.

Popularity and matching size

[edit]

The above example shows that relaxing the requirement of stability to popularity might enable larger matching, which is an important requirement in many applications.[2] In fact, in two-sided matching markets:

  • Stable matchings have the smallest size among all popular matchings.[3]
  • There always exists a popular matching with size at least 2/3 of the maximum cardinality matching, and this is tight.[4]
  • There always exists a popular matching with size at least 1/2 of the maximum cardinality matching, and this is tight, as shown by the above example.
[edit]

In some cases, it is required to have a matching of maximum cardinality. Hence, it makes sense to compute the popularity of a matching only among the set of maximum-cardinality matching. A popular max-matching is a (weak) Condorcet winner among the maximum-cardinality matching.

In two-sided matching markets, a popular max-matching always exists, and can be found in time O(n m), where n is the number of agents and m the number of edges.[4] The algorithm is a variant of the Gale–Shapley algorithm and it is called "|A|-level Gale-Shapley". It is equivalent to finding a stable matching in an auxiliary instance.[2]

[edit]

A quasi-popular matching is a matching with "unpopularity factor" of at most 2, that is, the number of agents who weakly prefer it to another matching is at least half the number of agents who prefer the other matching.[5]

Popularity vs. Pareto-efficiency

[edit]

Every popular matching is Pareto-efficient, as if there were a Pareto improvement, at least one agent would vote only for the Pareto improvement, whereas the others would vote for both.

Hence, popularity is between stability and efficiency:

Stable → Popular → Efficient

[edit]

In some cases, each pairing between a man and a woman has a cost, and it is required to find a popular matching of minimum total cost (this problem is analogous to the problem of optimal stable matching, where the goal is to find a stable matching of miniumum cost). The following holds in two-sided matching markets:

  • Finding a maximum-cardinality matching among all popular matchings can be done in polytime.[3]
  • Finding a min-cost popular matching is NP-hard.[6]
  • Finding a min-cost popular max-matching can be done in polynomial time. The algorithm uses a compact representation of the polytope of popular max-matchings.[2]
  • Finding a min-cost Parete-efficient max-matching in NP-hard, and hard to approximate to any constant factor. This holds even when all edge costs are in {0,1} and all rankings are strict.[2]
  • Finding a min-cost quasi-popular matching is NP-hard.[5]
[edit]

Popular matchings were also studied in one-sided matching markets, where only agents in one side of the market have preferences, as in the house allocation problem and the fair random assignment problem. In that context, the term used is popular assignment.

  • Finding a min-cost popular assignment can be done in polynomial time.[7]
  • A popular max-assignment does not always exist. Existence can be decided in polynomial time.[8]
  • Finding a min-cost popular max-assignment is NP-hard.[8]

So the situation in one-sided markets is the opposite of the situation in two-sided markets:[2]

One-sided markets ("assignment") Two-sided markets ("marriage")
Min-cost popular matching P[7] NP-hard[6]
Min-cost popular max-matching NP-hard[8] P[2]

Additional reading

[edit]
  • A survey paper on computational aspects of popular matchings.[9]

References

[edit]
  1. 1 2 Gärdenfors, Peter (May 1975). "Match making: Assignments based on bilateral preferences". Behavioral Science. 20 (3): 166–173. doi:10.1002/bs.3830200304. ISSN 0005-7940.
  2. 1 2 3 4 5 6 7 Kavitha, Telikepalli (2024-04-04). "Maximum Matchings and Popularity". SIAM Journal on Discrete Mathematics. 38 (2): 1202–1221. doi:10.1137/22m1523248. ISSN 0895-4801.
  3. 1 2 Huang, Chien-Chung; Kavitha, Telikepalli (January 2013). "Popular matchings in the stable marriage problem". Information and Computation. 222: 180–194. doi:10.1016/j.ic.2012.10.012. ISSN 0890-5401.
  4. 1 2 Kavitha, Telikepalli (January 2014). "A Size-Popularity Tradeoff in the Stable Marriage Problem". SIAM Journal on Computing. 43 (1): 52–71. doi:10.1137/120902562. ISSN 0097-5397.
  5. 1 2 Faenza, Yuri; Kavitha, Telikepalli (February 2022). "Quasi-Popular Matchings, Optimality, and Extended Formulations". Mathematics of Operations Research. 47 (1): 427–457. doi:10.1287/moor.2021.1139. ISSN 0364-765X.
  6. 1 2 Faenza, Yuri; Kavitha, Telikepalli; Powers, Vladlena; Zhang, Xingyu (January 2019), "Popular Matchings and Limits to Tractability", Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA: Society for Industrial and Applied Mathematics, pp. 2790–2809, ISBN 978-1-61197-548-2, retrieved 2026-05-20
  7. 1 2 Abraham, David J.; Irving, Robert W.; Kavitha, Telikepalli; Mehlhorn, Kurt (January 2007). "Popular Matchings". SIAM Journal on Computing. 37 (4): 1030–1045. doi:10.1137/06067328x. ISSN 0097-5397.
  8. 1 2 3 Kavitha, Telikepalli; Király, Tamás; Matuschke, Jannik; Schlotter, Ildikó; Schmidt-Kraepelin, Ulrike (January 2022), "The popular assignment problem: when cardinality is more important than popularity", Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Philadelphia, PA: Society for Industrial and Applied Mathematics, pp. 103–123, ISBN 978-1-61197-707-3, retrieved 2026-05-20
  9. ↑ Cseh, Agnes (2017). Popular Matchings. In: Trends in Computational Social Choice. Lulu.com. pp. 105–122. ISBN 978-1-326-91209-3.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Popular_matching&oldid=1360729490"