Nash-Bargaining-Based Models for Matching Markets: One-Sided and Two-Sided; Fisher and Arrow-Debreu
summary
Paper proposes Nash-bargaining-based matching models (one-sided and two-sided; Fisher and Arrow-Debreu) with explicit convex programs for linear, separable and non-separable piecewise-linear-concave utilities, and a disagreement-point treatment. Two solver families are developed: a central cutting-plane method with several practical enhancements, and a Frank–Wolfe approach that reduces iterations to max-weight-matchings. Experiments scale to 200–2,000 agents: Frank–Wolfe wins on binary sparse instances, cutting-plane wins on dense and nonlinear cases and solves large separable instances in minutes and harder non-separable cases within an hour. 1LF and 2LF models are provided.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:23Talk Outline
- 1:01Matching-Based Market Design
- 3:42The Nash Bargaining Game
- 7:10Connection between HZ and NBB Models
- 9:59Nash-Bargaining-Based Models One Sided Matching Markets
- 11:25One-Sided Matching Markets: 1SAD
- 16:38Two-Sided Matching Markets: 2LF Linear Fisher Nash bargaining two-sided watching market
- 18:06Solution Methods
- 20:22Central Cutting-Plane Algorithm
- 21:13Enhancement Techniques
- 24:05Frank-Wolfe Algorithm
- 25:21Computational Experiments (ILAD, 1LF, 2LF)
- 27:35Computational Experiments (1SAD & INAD)
related talks
04mOn gradient-based methods for finding game-theoretic equilibria
01h 10mMulti-Dimensional and Non-Linear Mechanism Design and Approximation II
43mLearning about Auctions
01h 07mMulti-Dimensional and Non-Linear Mechanism Design and Approximation I
01h 14mCompetitive Analysis Meets Stochastic Input: Secretary Problems And Prophet Inequalities
42mLearning What Works Best When
46mEliciting and Enforcing Subjective Individual Fairness
45mAGT and Machine Learning