Approximating One-Sided and Two-Sided Nash Social Welfare With Capacities
Salil Gokhale
IIT Delhi
Rohit Vaish
IIT Delhi
Harshul Sagar
IIT Delhi
Jatin Yadav
IIT Delhi
Joint work with:
One-sided Model
Valuation function
One-sided Model with Capacities
Two-sided Model
Valuation function
Valuation function
Two-sided Model with Capacities
Classes of Valuation Functions
Previous Results
1. Jugal Garg, Edin Husi´c, Wenzheng Li, László A Végh, and Jan Vondrák. Approximating Nash Social Welfare by Matching and Local Search. STOC, 2023
2. Pallavi Jain and Rohit Vaish. Maximizing Nash Social Welfare under Two-Sided Preferences. AAAI, 2024
Hardness
Algorithm
e/(e-1)
One-sided Model
Without
Capacities
[Garg et al.,2023]
With
Capacities
Hardness
Algorithm
Two-sided Model
Without
Capacities
[Jain and Vaish, 2024]
With
Capacities
4
[Garg et al.,2023]
Submodular
Additive
Our Results
1. Jugal Garg, Edin Husi´c, Wenzheng Li, László A Végh, and Jan Vondrák. Approximating Nash Social Welfare by Matching and Local Search. STOC, 2023
Hardness
Algorithm
6
One-sided Model
Without
Capacities
With
Capacities
Hardness
Algorithm
Two-sided Model
Without
Capacities
With
Capacities
1.0000759
(even for additive)
1.33
e/(e-1)
[Garg et al.,2023]
4
[Garg et al.,2023]
Submodular
Subadditive
4-Approximate Algorithm for One-sided NSW without Capacities
[Garg et al.,2023]
6-Approximate Algorithm for One-sided NSW with Capacities
Cardinality preserving!
Assign the remaining items using
a local search with two-way swaps
Algorithm for Two-sided NSW without Capacities
Phase 1: Find a Nash optimal one to one matching.
Phase 2: Assign each remaining worker to their favourite firm.
A 1.33-approximation!
Algorithm for Two-sided NSW with Capacities
MIN-COST-FLOW does Phase 1 and Phase 2 together.
Open Questions
Open Questions
Thank You! Questions?