MatchXplain: Analyzing Preferences, Explaining Outcomes, and Simplifying Decisions

1 Introduction

Matching markets are fundamental for facilitating pairings between two distinct groups based on ranked preferences. These markets play a central role in various real-world applications such as college admission and medical residency, and led to development of seminal algorithms to ensure their stability [Gale and Shapley, 1962]. Since their introduction, matching markets have became essential in a variety of fields beyond college admissions, including job placement [Roth and Peranson, 1999], school admissions [Abdulkadiro˘glu et al., 2005a; Abdulkadiro˘glu et al., 2005b], recommender systems [Eskandanian and Mobasher, 2020], electric vehicle charging [Gerding et al., 2013], and ride sharing [Banerjee and Johari, 2019]. The effectiveness and longterm success of these markets hinges on several key properties including stability, economic efficiency, and their fairness guarantees. Each of these properties is critical in ensuring fairness and avoiding conflict in the market. Among the algorithms designed to address these challenges, perhaps the most-recognized mechanism is the Deferred Acceptance (DA) algorithm. Given a set of ordinal preferences, the DA algorithm is guaranteed to find a stable matching [Gale and Shapley, 1962], i.e., a solution wherein no pair of agents prefer each other to their matched partners.

The theoretical guarantees of DA hold under strict and complete linear preferences. However, when preferences include ties or are incomplete, challenges arise regarding matching size, efficiency, stability type, and fairness. While various algorithms have been developed to address specific aspects of these challenges [Gusfield, 1987], no single solution satisfies all desirable properties across all problem instances. Moreover, inherent trade-offs-such as the incompatibility between Pareto optimality and stability [Abdulkadiroˇglu et al., 2020]-as well as computational complexity issues [Manlove et al., 2002] make a universal, one-size-fitsall solution unattainable.

MatchXplain (www.matchxplain.org) aims to inform and guide the decisions of social planners and policymakers. To this end, it offers a menu of recommended solutions-derived from input preferences-that satisfy different sets of properties, allowing decision-makers to explore, adjust, and better understand potential outcomes. Effective explanation of an outcome requires a deep understanding of the nuances within the input data. MatchXplain bridges the gap between inputs and outputs by providing a comprehensive set of analytics and visualizations on the input preferences in a layered approach, enhancing interpretablity of decisions.

Related Platforms. With the recent wide-spread attention to algorithmic AI solutions, several platforms now offer provable and accessible algorithms for collective decisionmaking. For example, MatchU.ai [Ferris and Hosseini, 2020] emphasizes interactive visualization for pedagogical purposes; MATWA [Glitzner and Manlove, 2024] provides a web toolkit of matching algorithms. Broader platforms like Spliddit.org [Goldman and Procaccia, 2015] address fair resource allocation; Panelot.org [Flanigan et al., 2021] focuses on fair civic lotteries-all related to matching problems under preferences. Our platform distinguishes itself by emphasizing preference mapping and visualization, solution explanation, and interactive tools for understanding desired properties.

2 Model and Properties

Matching Model. A two-sided matching market consists of two disjoint sets, often denoted by A and B, where each agent i has a preference list over the members of the other side. The preference list of agent i is a weak and potentially partial order, and is denoted by ⪰i. We use b1 ≻a b2 to denote that agent a prefers b1 to b2. We additionally use b1 ⪰a b2 to denote that agent a weakly prefers b1 to b2 (a may prefer b1 and b2 equally). In the case of incomplete preferences, we use ϕ ≻a b1 to denote that b1 does not appear in a's preference list. A preference profile is simply the collection of all preferences lists of agents in both sides of the market, and is denoted by ≻= (≻a1 , . . . , ≻am , ≻b1 , . . . , ≻bn ), where m = |A| and n = |B|.

A matching is a mapping µ : A ∪ B → A ∪ B such that |µ(a)| ≤ 1 and µ(a) ⊆ B for all a ∈ A, |µ(b)| ≤ cb (where cb is the maximum number of agents that b can be matched with) and µ(b) ⊆ A for all b ∈ B, and b ∈ µ(a) if and only if a ∈ µ(b). For now, we focus on the special case of one-toone matchings, where capacities cb for all agents b ∈ B are set to 1.

Properties. Given a matching µ, a blocking pair is a pair (a, b) who prefer each other over their assigned match, i.e., b ≻a µ(a) and a ≻b µ(b). A matching is said to be stable if it does not have any blocking pairs. Stability is often seen as a fairness notion under the name of 'justified envy-freeness'. It states that any envy that agent a1 may feel for a2's match, say b1, is "justified" by agent b1 preferring a2 to a1, that is, a2 ≻b1 a1. Amatching is non-wasteful if no unmatched ai ∈ A can be matched without changing the partner of at least one aj ∈ A (same condition applies for the set B). In the one-to-many setting, a stable solution is defined as one which satisfies both justified envy-freeness and non-wastefulness.

A matching µ is Pareto-optimal relative to set A if no ai ∈ A can strictly improve their assigned match without rematching at least one aj ∈ A with a strictly less-preferred partner (same condition applies for set B). The size of a matching µ is the number of individuals pairs (a, b) in the matching, where µ(a) = {b} and µ(b) = {a}.

3 General Framework

The MatchXplain platform is comprised of three distinct but related components: MatchXplain's preference analysis, MatchXplain's matching engine to process two-sided market problems, and MatchXplain's mechanism selection and comparison system. Each of these components adopt a multilayered and scaffolded structure when presenting the results.

3.1 Preference Analysis

Preference mapping and analysis is critical to understanding the dynamics between agents in elections [Szufa et al., 2020] and matching markets [Boehmer et al., 2024]. MatchXplain introduces a comprehensive framework designed to analyze input preference profiles across three dimensions: popularity, similarity, and ties. This approach employs established algorithms and visualization techniques to illustrate the dynamics of two-sided matching markets.

Popularity Analysis

To quantitatively describe the desirability of agents in a given preference profile, MatchXplain utilizes the Borda count method, a well-studied positional voting mechanism that aggregates individual rankings into a collective preference order [Saari, 2023]. This method is well-suited for extracting numerical scores from ranked preferences, which are then used to determine the overall popularity of each agent in the market.

Borda Count. MatchXplain adapts the traditional Borda Count metric, typically used for complete and strict preferences, to handle ties and incomplete preferences. This is done through Averaged and Pessimistic Borda adjustments [Terzopoulou and Endriss, 2021]. The Averaged Borda approach calculates scores for incomplete preferences by averaging points for unranked agents, effectively assuming they are tied in rank. The Pessimistic Borda approach assigns the lowest possible scores to unranked alternatives, assuming these agents are strictly unwanted.

Similarity Analysis

To evaluate the similarity between agents' preferences, MatchXplain employs the Kendall tau distance, another wellstudied metric to compute statistical correlation [Kendall, 1938].

Kendall tau distance. The Kendall tau distance quantifies the similarity between two sets of rankings by identifying and counting pairs that are in a different order between the two rankings (these are called discordant pairs) [Kendall, 1938]. To handle weak and/or incomplete preferences, MatchXplain considers unranked agents as being tied at the bottom of preference lists, and ties between pairs of agents are counted as half the value of a discordant pair. The platform additionally integrates principal component analysis (PCA) [Jolliffe, 1986] and hierarchical clustering [Johnson, 1967] to describe how agent preferences are clustered.

Tie Analysis

To identify and classify ties in preference profiles, MatchXplain employs two mechanisms: the Louvain algorithm for community detection, and the Tie Ratio metric developed specifically for MatchXplain to quantify and visualize the extent of ties.

Louvain Algorithm. The Louvain algorithm [Blondel et al., 2008] detects community structures in large networks. MatchXplain applies this by representing preference ties as an adjacency matrix, which is used by the algorithm to cluster agents based on shared ties. This approach groups agents with similar desirability, reflecting their relative appeal.

Tie Ratio Method. MatchXplain additionally quantifies the extent of ties using a newly-developed tie ratio method. For each agent ai ∈ A, the individual tie score Si, is calculated as Si = Aties,i - Ti, where Aties,i is the sum of alternatives in ai's preference list that are involved in ties (possibly different ties), and Ti is the number of ties in ai's preference list. The total tie score is the summation of individual tie scores across all agents, Stotal = ∑n+m i=1 Si, where m = |A| and n = |B|. The maximum possible individual tie score is m-1 for agents in A (n-1 for agents in B), occurring when all agents in a preference list are tied, leading to a maximum possible total tie score of m(n-1)+n(m-1). The tie ratio, R, is then defined as R = Stotal m(n-1)+n(m-1) , providing a normalized measure of the prevalence of ties within a preference profile.

3.2 Matching Engine

The platform's matching engine currently employs five algorithms (with more under development) to compute solutions based on preference data. These solutions satisfy a range of economic properties.

Stable Matching

When the goal is to achieve stability, the platform selects different algorithms based on the nature of the preference data (e.g., strict or weak, complete or incomplete preferences). Each algorithm satisfies a specific variation of stability and addresses different aspects of efficiency, such as the size of the matching

Deferred Acceptance. The most seminal mechanismproposed by Gale and Shapley [Gale and Shapley, 1962]- is the deferred acceptance (DA) algorithm. MatchXplain's stable marriage algorithm is an implementation of the algorithms developed for weak preferences (those with ties) [Irving, 1994]. In the presence of ties, different variants of stability-weak, strong, and super stability-are computed using their respective algorithms.

Stable Marriage with Incomplete Preferences MatchXplain also generates solutions for incomplete preference profiles. Because the problem of finding a maximum size stable solution under incomplete preferences containing ties is APX-Hard [McDermid, 2009], MatchXplain employs an algorithm developed by Kir`aly to approximate the maximum size stable solution [Kir´aly, 2013]. The implementation achieves 3/2 approximation in this setting. Kir`aly further introduces an approximation algorithm to find stable one-to-many solutions with weak and incomplete preferences [Kir´aly, 2013].

Top Trading Cycles

To find a Pareto optimal solution (for one side), MatchXplain implements the Top Trading Cycles (TTC) algorithm

[Shapley and Scarf, 1974]. The resulting matching is guaranteed to be Pareto optimal but may not be stable [Shapley and Scarf, 1974]. Since TTC is a one-sided allocation mechanism, only one side of agents' preferences are considered, and an efficient allocation is found based on these preferences. This algorithm is only applied when preference profiles are complete. Fixed tie-breaking strategies can the applied when working with weak preference profiles [Ehlers, 2014].

3.3 Mechanism Selection and Comparison

Matchxplain compares potential matchings generated by the matching engine by displaying key properties (such as matching size, number of blocking pairs, and number of envious agents) on radar charts for easy interpretation of trade-offs between the solutions. The use of interactive bipartite graphs further presents individual matchings by displaying matched pairs, blocking pairs, exchange cycles, and even envy between agents in a multi-layered manner. These interactive graphs enable the visual exploration and comparison of the recommended solutions.

4 Implementation Details and Data Format

MatchXplain is a web application developed with React, with a backend REST API developed with Flask and Python. All algorithms described in Sections 3.1 & 3.2 are implemented in Python. Users upload preference data to MatchXplain as plain text. These preference profiles follow a similar format to that of the Preflib preference library [Mattei and Walsh, 2013]. MatchXplain currently accepts four types of two-sided ordinal preference profiles: SOC: Complete strict preferences without ties; TOC: Complete preferences with permissible ties; SOI: Incomplete strict preferences without ties; TOI: Incomplete preferences with permissible ties.

5 Concluding Remarks

MatchXplain offers detailed preference analysis and diverse matching algorithms for a variety of objectives and preference types, presenting information in a scaffolded, digestible manner. The components such as the matching engine are currently focused on two-sided matching markets. Yet, its preference analysis tools and layered recommendations can be utilized within other relevant computational social choice problems (e.g. voting theory [Szufa et al., 2020], hedonic games [Kerkmann et al., 2020], fair division [Igarashi et al., 2024], etc.) that deal with ordinal preference data.

Future work includes integrating additional algorithms (one-to-many matchings for weak and incomplete preferences [Irving, 1994; Kir´aly, 2013] and a TTC algorithm for weak preferences [Ehlers, 2014]), adding abstraction layers for deeper analysis, and introducing meta-analysis techniques to allow users to adjust or constrain the output to modify matching outcomes. Additionally, there are future plans to enable the platform to suggest modifications to the initially input preferences. Suggestions could include modifying ties in preference profiles, or modifying matching quotas in many-to-one matchings. These problems pose computational challenges.

Acknowledgments

This research was supported in part by NSF Awards IIS2144413 and IIS-2107173.