Matching

Data Science Matching

  • Prof. Diego d'Andria

  • Hochschule Schmalkalden

  • WS 2024-2025

  • University of Applied Sciences

Matching

Definition

Matching refers to the techniques used to pair two observational units based on similarity or propensity to experience a specific effect (often termed as treatment). These techniques have various practical applications, such as:

  • Providing alternatives to experimental settings for studying causal effects when randomization for treatment and control groups is impractical.

  • Identifying the best match from a sample (for example, on dating apps).

  • Searching for an exact ID or string of text from a list.

Applications of Matching Techniques

  1. Experimental Alternatives: Used to study causal effects without randomization.

  2. Sample Matching: Utilized in scenarios like dating apps to find suitable partners.

  3. Search Algorithms: Used for locating specific data in tables, like names in a database.

Search Algorithms

Definition

Matching techniques that locate specific values in a list are known as search algorithms.

Example

For instance, in a relational database with a list of names, a user may want to find a specific name such as "John Smith." A search algorithm would scan the column of names to retrieve the corresponding row related to "John Smith."

Proper Matching Algorithms

Purpose

Proper matching algorithms generate pairs of observational units that are either identical or sufficiently similar based on specific criteria.

  • These methods can be viewed as specialized forms of cluster analysis, focusing on creating pairs of individuals.

  • A distance measure is minimized to form these pairs.

Matching Techniques and Methods

Types of Matching

  1. Without Replacement: Once a subject is matched, they cannot be selected again for matching with other subjects.

  2. With Replacement: A subject can match with multiple other subjects.

Optimal Matching Algorithms

  • These form pairs to minimize total within-pair difference, offering a global solution to a minimization problem.

  • Optimal matching closely resembles clustering algorithms, particularly partitioning algorithms like K-Means.

Greedy Matching

  • Greedy matching starts with a randomly selected subject and continually selects the most similar subject for matching, regardless of future matches' potential.

Comparison of Matching Methods

Optimal vs. Greedy Algorithms

  • Greedy methods are computationally cheaper, making them preferable when balancing time and CPU usage.

  • Optimal algorithms yield the best matching with minimized dissimilarity, often seen as superior.

  • Evidence from Gu and Rosenbaum (1993) indicates that optimal matching does not significantly outperform greedy methods for matched sample production.

Nearest Neighbor Matching

Explanation

  • This method pairs subjects based on the proximity of their scores.

  • Without Caliper Distance: It selects the nearest subject without restrictions.

  • With Caliper Distance: This method only accepts subjects within a specified distance, ensuring matches are close enough based on predetermined thresholds.

Matching Distinct Subject Types

  • In some instances, matching may occur between two differing groups (e.g., employers and employees).

  • The Gale-Shapley algorithm is suitable for these cases, matching individuals based on preferences.

The Gale-Shapley Algorithm

Overview

  • Designed to address the stable matching problem with two equally-sized subject sets that have preference orderings.

  • Produces a stable matching, ensuring no matched subjects would prefer to be matched with someone else than their current partners.

Iterative Process

For example, in a job market scenario:

  1. Employers with open positions extend offers to preferred candidates.

  2. Candidates evaluate offers, and the best offer, or the only one for unemployed candidates, is accepted.

  3. This process repeats until all positions are filled, demonstrating the effectiveness of the Gale-Shapley algorithm.

R Packages for Matching

  • In R, various packages are available for performing matching tasks:

    • Matching

    • Matchlt

    • Optmatch

    • Gale-Shapley algorithm can be executed using MatchingR and matchingMarkets.

Experiments and Propensity Score Matching

Experimental Settings

  • Treatment effects are assessed by comparing scores from treated and untreated groups.

  • Ensuring both groups are similar usually involves random selection or measuring the same subjects before and after treatment.

Challenges

  • Sometimes random selection is infeasible, such as when evaluating the impact of an R&D subsidy.

  • Due to self-selection bias, treated and untreated group differences can complicate analysis without adjustments.

Propensity Score Matching

Methodology

  • PSM involves forming matched sets of treated and untreated subjects based on their likelihood of receiving treatment (the propensity score).

  • This is accomplished by ensuring that subjects in matched pairs share similar propensity scores, allowing outcome comparisons akin to random assignments.

Variable Selection

  • Variables influencing treatment assignment must be utilized to measure similarity during PSM.

  • Some researchers advocate including all relevant variables, while others argue for a narrower focus.

Implementing PSM

  • Upon selecting appropriate variables, various matching algorithms can be applied.

  • The propensity score is defined as the probability of treatment assignment, based on observed characteristics.

Logistic Regression Model

Application

  • For example, in R&D subsidies analysis, using firm size, past investments, and financial leverage as predictors.

  • By running a Logit model, the corresponding propensity scores can be calculated and subsequently used to form matched pairs of firms.

References

  • Austin, P.C. (2011). An Introduction to Propensity Score Methods for Reducing the Effects of Confounding in Observational Studies, Multivariate Behavioral Research.

  • Gale, D. and Shapley, L. S. (1962). College Admissions and the Stability of Marriage, American Mathematical Monthly.

  • Gu X.S. and Rosenbaum P.R. (1993). Comparison of multivariate matching methods: Structures, distances, and algorithms, Journal of Computational and Graphical Statistics.