Capacity Modification

in the Stable Matching Problem

Salil Gokhale

IIT Delhi

Samarth Singla

IIT Delhi

Shivika Narang

UNSW

Rohit Vaish

IIT Delhi

Stable Matchings

​

Many-to-one stable matching mechanisms are everywhere.

​

​

​

​

Stable matching mechanisms are well studied.

​

Capacity Modification is Ubiquitous

The Model

___

___ ___

is a blocking pair

Responsive, strict preferences over all subsets of workers

Strict preferences

The Model

___

___ ___

Stable Matching

Strict preferences

WPDA: Worker-proposing deferred acceptance algorithm

FPDA: Firm-proposing deferred acceptance algorithm

Responsive, strict preferences over all subsets of workers

Modifying Capacity: An Example

___

___ ___

___

___

Decrease capacity of f₂

Technical Contribution

1. Who benefits by increasing capacity?

​

​

2. Can we use capacity modification to get desired outcomes in polynomial time?

​

​

3. Preference Manipulation v/s Capacity Modification

1. Effect of Capacity Increase

^{1. Tayfun Sönmez. Manipulation via Capacities in Two-Sided Matching Markets. Journal of Economic Theory, 1997}

^{2. David Gale and Marilda Sotomayor. Some Remarks on the Stable Matching Problem. Discrete Applied Mathematics, 1985}

^{3. Alvin E Roth and Marilda Sotomayor. Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, 1990}

FPDA

WPDA

Yes

[Sönmez, 1997]

Yes

[Sönmez, 1997]

Can the firm

improve?

Yes

Yes

Can the firm

worsen?

Yes

Yes

Can all workers

improve?

No

[Gale and Sotomayor, 1985]

[Roth and Sotomayor, 1990]

No

[Gale and Sotomayor, 1985]

[Roth and Sotomayor, 1990]

Can some worker

worsen?

Increasing Capacity can worsen a firm in WPDA�

^{1. Tayfun Sönmez. Manipulation via Capacities in Two-Sided Matching Markets. Journal of Economic Theory, 1997}

Increase capacity of

___ ___

___

___

___

2. Achieving Goals using Capacity Modification

Goals:

1. Match a given firm-worker pair
2. Stabilize a given matching

Adding/Deleting Capacity

Achieved by:

Constraints:

Global Budget/Individual Budget on capacity change

Summary of Computational Results

Several results via canonical reduction to one-to-one setting. Some one-to-one control problems previously solved by Boehmer et al.

^{1. Niclas Boehmer, Robert Bredereck, Klaus Heeger, and Rolf Niedermeier. Bribery and Control in Stable Marriage. Journal of Artificial Intelligence Research, 2021}

Delete Capacity

Add Capacity

Delete Capacity

Add Capacity

Poly Time

Poly Time

Poly Time

Poly Time

Global Budget

Poly Time

Poly Time

NP

-

hard

NP

-

hard

Individual Budget

Delete Capacity To Stabilize Matching under Global Budget

Input:

Question:

Step 1: Reducing to one-to-one instance

Input:

Question:

Input:

Question:

Step 2: Algorithm for the one-to-one problem

Idea: To resolve a blocking pair, we necessarily need to delete an agent participating in the blocking pair.

​

Algorithm: Keep deleting men in blocking pairs until we either run out of budget or no blocking pairs are left.

3. Preference Manipulation v/s Capacity Modification�

Introducing Peak

:= Peak of a firm is the maximum number of workers that can be matched to it under any capacity with the preferences kept fixed.

Observations

• As you increase capacity of a firm, size of the matched set for the firm keeps increasing by 1 till it reaches peak, and then plateaus.

​

​

• Above peak, all stable matchings match the firm to the same set of workers as those obtained by WPDA.

​

​

• Above peak, preference manipulation is useless, under any stable matching mechanism.

Comparison of Manipulation Actions via Peak

Add

Pref

Del

Del

Pref

Add

Del

Pref

Add

Above Peak

Add

Pref

Del

At Peak

Add

Pref

Del

Below Peak

WPDA

FPDA

An arrow from action X to action Y denotes the existence of an instance where X is strictly more beneficial for the firm than Y. Each missing arrow denotes that there is (provably) no instance where X is more beneficial than Y.

Future Directions

• Analyse capacity modification with simultaneous Add and Delete actions.

​

​

• Experiments on synthetic or real-world data to evaluate the frequency of goal completion in control problems.

THANK YOU