Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch: 04/01 Yeganeh Ali Mohammadi

David Wajc wajc at
Tue Mar 30 14:25:41 PDT 2021

Hi all,

Welcome back from Spring break!
As a reminder, there are still open slots for talks this quarter.
Let me know if you want to give a talk!

The first theory lunch of the quarter will take place Thursday at noon
(PDT), at our gather space: (*password:*
Yeganeh will tell us about*:* *Raising Supply vs Improving Matching: A
Random Walk Down Spatial Markets*

We study dynamic matching in a spatial setting: there are $n$ riders and
$m$ drivers placed uniformly at random on the interval $[0,1]^2$. The
location of the drivers is known. The riders arrive in some (possibly
adversarial) order and they have to be matched irrevocably to a driver at
the time of arrival. The cost of matching a driver to a rider is equal to
the $l_1$-norm of their distance on the interval. The question we consider
is which strategy is better: to boost supply by attracting more drivers to
the platform, or to have a perfect forecast and design an optimal matching

We prove that if $m\geq (1+\epsilon)n$ for some $\epsilon>0$, the cost of
matching returned by a simple greedy algorithm that pairs each arriving
rider to the closest available driver is $\tilde{O}(1)$. On the other hand,
when $n=m$, even an omniscient algorithm with perfect knowledge about the
positions of riders cannot find a matching with cost better than
$C\sqrt{n}$. Our results shed light on the important role of supply in
spatial matching markets: No level of sophistication in the matching
algorithm and no amount of data to predict times and locations of future
demand in a balanced market can beat a myopic greedy algorithm with a small
excess supply.

*This is joint work with Mohammad Akbarpour, Shengwu Li and Amin Saberi.*

*Cheers,DavidPSPro tip: To join the talk (at 12:30):(1) go to the lecture
hall, (2) grab a seat, and (3) press X to join the zoom lecture*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list