research
∙
04/05/2023
A Structural and Algorithmic Study of Stable Matching Lattices of Multiple Instances
Recently MV18a identified and initiated work on the new problem of under...
share
research
∙
02/15/2023
LP-Duality Theory and the Cores of Games
LP-duality theory has played a central role in the study of the core, ri...
research
∙
02/01/2023
The Investment Management Game: Extending the Scope of the Notion of Core
The core is a dominant solution concept in economics and game theory. In...
research
∙
09/11/2022
Cores of Games via Total Dual Integrality, with Applications to Perfect Graphs and Polymatroids
LP-duality theory has played a central role in the study of cores of gam...
research
∙
02/01/2022
Insights into the Core of the Assignment Game via Complementarity
The assignment game forms a paradigmatic setting for studying the core –...
research
∙
07/22/2021
Online Bipartite Matching and Adwords
A simple and optimal online algorithm for online bipartite matching, cal...
research
∙
06/03/2021
Combinatorial Algorithms for Matching Markets via Nash Bargaining: One-Sided, Two-Sided and Non-Bipartite
This paper is an attempt to deal with the recent realization (Vazirani, ...
research
∙
05/22/2021
Nash-Bargaining-Based Models for Matching Markets, with Implementations and Experimental Results
This paper addresses the paucity of models of matching markets, both one...
research
∙
01/19/2021
The General Graph Matching Game: Approximate Core
The classic paper of Shapley and Shubik <cit.> characterized the core of...
research
∙
12/07/2020
A Proof of the MV Matching Algorithm
The Micali-Vazirani (MV) algorithm for maximum cardinality matching in g...
research
∙
10/12/2020
An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs
We prove that a fractional perfect matching in a non-bipartite graph can...
research
∙
09/22/2020
An Arrow-Debreu Extension of the Hylland-Zeckhauser Scheme: Equilibrium Existence and Algorithms
The Arrow-Debreu extension of the classic Hylland-Zeckhauser scheme for ...
research
∙
04/03/2020
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets
In 1979, Hylland and Zeckhauser <cit.> gave a simple and general scheme ...
research
∙
03/19/2020
A Real Polynomial for Bipartite Graph Minimum Weight Perfect Matchings
In a recent paper, Beniamini and Nisan <cit.> gave a closed-form formula...
research
∙
06/27/2019
Further Results on Stability-Preserving Mechanisms for School Choice
We build on the stability-preserving school choice model introduced and ...
research
∙
04/09/2019
Stability-Preserving, Incentive-Compatible, Time-Efficient Mechanisms for Increasing School Capacity
We address the following dynamic version of the school choice question: ...
research
∙
01/29/2019
Matching is as Easy as the Decision Problem, in the NC Model
We give an NC reduction from search to decision for the problem of findi...
research
∙
01/29/2019
A Pseudo-Deterministic RNC Algorithm for General Graph Perfect Matching
The difficulty of obtaining an NC perfect matching algorithm has led res...
research
∙
03/30/2018
Finding Stable Matchings that are Robust to Errors in the Input
Given an instance A of stable matching, let B be the instance that resul...
research
∙
02/19/2018
A Natural Generalization of Stable Matching Solved via New Insights into Ideal Cuts
We study a natural generalization of stable matching to the maximum weig...
research
∙
01/31/2018
NC Algorithms for Perfect Matching and Maximum Flow in One-Crossing-Minor-Free Graphs
In 1988, Vazirani gave an NC algorithm for computing the number of perfe...
research
∙
10/30/2017
Rock-Paper-Scissors, Differential Games and Biological Diversity
We model a situation in which a collection of species derive their fitne...
research
∙
09/22/2017