| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | May 14, 2018 |
| Latest Amendment Date: | May 14, 2018 |
| Award Number: | 1815901 |
| Award Instrument: | Standard Grant |
| Program Manager: |
A. Funda Ergun
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | June 1, 2018 |
| End Date: | July 31, 2021 (Estimated) |
| Total Intended Award Amount: | $499,999.00 |
| Total Awarded Amount to Date: | $499,999.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
160 ALDRICH HALL IRVINE CA US 92697-0001 (949)824-7295 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
Donald Bren Hall, Room 4032 CA US 92617-3213 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
This project will develop new foundations for three fundamental problem areas. All three problem areas, matching, markets, and matching markets have deep and rich algorithmic theories. All three have found numerous applications; for instance, applications of matching markets go all the way from assigning interns to hospitals, to assigning query keywords to advertisers in the multi-billion dollar online ads markets of search engine companies. The investigator has made foundational contributions to all three problem areas in the past, and has identified several new problems for this project. At the same time the investigator, who recently moved to the University of California, Irvine, has the mandate of helping propel its Theory Group to the next level. Towards this end, he will be recruiting a postdoc and high quality graduate students to increase the level and quality of research activity and will help revamp graduate and undergrad theory courses.
On matching, the investigator recently solved a thirty-plus-year-old open problem by giving a fast parallel (NC) algorithm for finding a perfect matching in planar graphs, and has identified a number of important follow-up problems. Following up on his work giving complementary pivot equilibrium algorithms for several market models, he plans to analyze the smoothed complexity of this algorithm. Recent work of the investigator on the stable matching problem has yielded new structural results about relationships between the lattices of stable matchings of two "nearby" instances. This should help in developing efficient algorithms for finding solutions that are robust to errors introduced in the input.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
A fast parallel deterministic (NC) algorithm was discovered for finding a perfect matching in a planar graph, thereby settling a long-standing open problem.
A pseudo-determinsitic RNC algorithm was given for perfect matching in general graphs.
On the outstanding open question "Is matching in NC?" it was shown that the solution finding version NC-reduces to determining if a graph with polynomially bounded weights has a perfect matching of weight at most W, for a given weight W. This has substantially diminished the remaining open problem.
The classic Hylland-Zeckhauser mechanism for one-sided matching markets, found in 1979, was shown to be in PPAD, for the problem of computing an approximate equilibrium. Other researchers later showwed PPAD-hardness as well for this problem, thereby establishing intractability.
To deal with the intractability reported above, Nash-bargaining-based models were proposed for one-sided and two-sided matching markets.
NC algorithms were given for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs thereby settling a thirty-plus year-old open problem.
The classic 1971 paper of Shapley and shubik gave a characterization of the core of the assignment game. In contraast, it is well known that hte general graph matching game may have an empty core. Existence of a 2/3-approximate core was demonstrated for this game.
Last Modified: 10/05/2021
Modified by: Vijay V Vazirani
Please report errors in award information by writing to: awardsearch@nsf.gov.
