Waiting time vs. mismatch in the online assignment game

We examine a class of online assignment games where heterogeneous market participants -- clients and providers -- arrive stochastically to a two-sided market. The cost of matching may vary markedly between agents, so a social planner is faced with two contending objectives: a) to reduce the coexistence of clients and providers, that is, to reduce the agents' waiting time; and b) to match clients with providers in the most productive manner, i.e., to reduce matching cost. Our first result is that there is no `free lunch' in this setting, i.e., there exists no clearing schedule that is optimal along both objectives. We then proceed to identify optimal clearing schedules that interpolate between matching cost and waiting time minimization, illustrating how different social planners can cut this trade-off. Finally, we show there exists a unique optimal schedule when committing to a family of utility functions weighing waiting time and matching cost.

 

Joint work with Panayotis Mertikopoulos and Heinrich Nax