1 of 69

STOCHASTIC MATCHING NETWORKS�Theory and Applications�

SIVA THEJA MAGULURI AND SUSHIL VARMA��SCHOOL OF INDUSTRIAL AND SYSTEMS ENGINEERING�GEORGIA INSTITUTE OF TECHNOLOGY

1

2 of 69

A CLASSICAL QUEUE

2

3 of 69

A MATCHING QUEUE

3

4 of 69

A MATCHING QUEUE

TRANSIENT

NULL RECURRENT

TRANSIENT

4

Unstable in all three cases

5 of 69

STABILITY IN A MATCHING QUEUE

External Control is needed for stability
Finite waiting Space

Abandonment of customers or drivers

Dynamic Arrivals – using pricing

5

6 of 69

CLASSICAL QUEUE AS A MATCHING QUEUE

6

M/M/1/K QUEUE AS A MATCHING QUEUE

7 of 69

M/M/K QUEUE AS A BIPARTITE MATCHING QUEUE

7

8 of 69

A PRODUCTION SYSTEM AS A MATCHING QUEUE

8

Outstanding Demand

Surplus Product

9 of 69

OUTLINE OF THE TUTORIAL

PART I
Introduction

Heavy-Traffic in a single Matching Queue

Matching and Pricing in Online Market Places

PART II

Multipartite Matching Queues in a Quantum Switch

Literature Survey on Stochastic Matching Networks

9

10 of 69

OUTLINE OF THE TUTORIAL

PART I
Introduction

Heavy-Traffic in a single Matching Queue

Matching and Pricing in Online Market Places

PART II

Multipartite Matching Queues in a Quantum Switch

Literature Survey on Stochastic Matching Networks

10

11 of 69

Heavy Traffic Theory

RESULTS

11

12 of 69

CLASSICAL SINGLE SERVER QUEUE

12

13 of 69

MATCHING QUEUE

13

What is Heavy-Traffic here?

For the purpose of this talk, we are working with a discrete time system. However, everything works in a continuous time Markovian system also.

-----

Since this is null-recurrent, we use pricing to make the arrival rate state dependant. We work with the setting when the dynamic arrivals are such that we have positive recurrence.

Ph1, ph2, psi1, psi2 can be positive or negative.

-------

Since only one of q1 or q2 are nonempty. Z is complete state descriptor

Discrete-time System, Number of exogenous arrivals in each time is a random variable with same mean but possibly different variance.

We have a price that depends on the state, z. Some agents accept the price and enter. Others may leave. The random variable of arrivals is a(z), and the corresponding means and variances. WLOG, we can write in this additive form

For Bernouolli arrivals and general control, since it is a birth-death process, conditions for stability and expressions for stationary distribution are known. But they can potentially be very messy.

Assuming both exogenous arrival rates are same is WLOG and is only for ease of exposition. This is because we can assume that the prices are set such that this is attained.

14 of 69

MATCHING QUEUE: HEAVY-TRAFFIC

14

15 of 69

HEAVY-TRAFFIC: BERNOULLI CASE

Bernoulli Arrivals and Threshold control

Closed form expression for stationary distribution

15

Theorem [Varma, M 21]: 𝜖→0 or 𝜏→∞ (or both)

The limiting distribution depends on the relative manner in which epsilon and tau go to their limits. (Can think of epsilon and tau to be functions of another parameter \eta or can think of tau as a function of \epsilon.

Firstly, if 𝜖𝜏→0, epsilon goes to zero faster than tau going to zero (think of tau being fixed). Then, it is a two-sided analog of the classical queue result. So, firstly, we get that z is like /1epsilon, and eps z goes to two-sided exponential

If 𝜖𝜏→∞, tau goes to infty faster than epsilon going to zero (think of eps as fixed). Here, z is O(tau), and z/tau is Uniform.

Hybrid just means that it is a stitched version of uniform and Laplace. 𝐻𝑦𝑏𝑟𝑖𝑑((𝜎_1^2+𝜎_2^2)/2, 𝑙) is a Laplace that is plateaued between –l and l and renormalized

------

In Bernoulli case, actually, sigma_1^2 = sigma_2^2= lambda(1-lambda)

16 of 69

16

HEAVY-TRAFFIC: BERNOULLI CASE

17 of 69

HEAVY-TRAFFIC: GENERAL CASE

General Arrivals and General control – Stationary distribution unknown

Control ensures stability

17

While the previous result illustrated the pahase-transition phenomenon, the proof is not interesting. Due to simplicity of the system, one can get exact stationary distribution and so can study any regime. The main motivation to study asymptotic regimes is to accommodate for general arrivals. Here, we look at a general system, and illustrate a similar phase transition. This is the main theorem in this section.

Gibbs – family of distributions. If g(x)=x, we get Gaussian. If g(x)=1, we get exponential. If g(.) has a step function structure, we get the Hybrid from previous slide

When the policy is threshold policy, it reduces to the previous result. The fact that this is general arrival doesn’t change the asymptotic result, but the pricing policy changes it.

Taking the middle one and letting l go to 0, we get the left side. Letting l to infty, we get the right one

Left regimes depend only on mean and vairances. But in the middle regime and right regime depends on the whole control function

-------------------------

Right result – Uniform within a set. The set comes from the assumptions we make on phi1 and phi2.

Assumptions:

18 of 69

CLASSICAL QUEUE WITH DYNAMIC ARRIVALS

Classical single server queue is usually studied under static arrivals. Now consider dynamic arrivals

18

Bernoulli Arrivals and Threshold control

We also have a result for general arrivals and control

19 of 69

Heavy Traffic Theory

PROOF OUTLINE

19

20 of 69

CLASSICAL QUEUE: TRANSFORM METHOD

20


Two-Sided Laplace Transform MGF	One-sided Laplace transform	Fourier Transform Characteristic Function

21 of 69

MATCHING QUEUE – HYBRID REGIME

21

Among the three regimes, we will focus on the hybrid regime for the proof.

There are several issues here. In the classical queue, we got an explicit expression for the transform of the limit, which immediately implies convergence in distribution. Here, since we only have an implicit formula, we need to also show that the limit exists.

The solution of Stein equation is known to be Gaussian. Thus, generalizing to a generic g(.), we get Gibbs distribution. Note that Gaussian is special case of Gibbs when g(x)=x

Based on this, we can guess Gibbs and substitute and check that it works establishing it is a solution. We will focus on showing uniqueness, which also gives the solution in our case. Tightness is again established using drift arguments.

----------------

We actually use tightness (existence of a limit along a subsequence) to get the implicit equation.

22 of 69

UNIQUENESS: INVERSE FOURIER TRANSFORM

22

23 of 69

PROOF OUTLINE

23

24 of 69

HEAVY-TRAFFIC: GENERAL CASE

24



Characteristic Function Method	Inverse Fourier Transform Method	Characteristic Function Method
	Tightness Transform method – Implicit equation Solve using Inverse Fourier Transforms	Show Uniform within the thresholds – using Transform Method Show that the probability outside the thresholds goes to zero

25 of 69

OUTLINE OF THE TUTORIAL

PART I
Introduction

Heavy-Traffic in a single Matching Queue

Matching and Pricing in Online Market Places

PART II

Multipartite Matching Queues in a Quantum Switch

Literature Survey on Stochastic Matching Networks

25

26 of 69

OUTLINE OF THE TUTORIAL

PART I
Introduction

Heavy-Traffic in a single Matching Queue

Matching and Pricing in Online Market Places

PART II

Multipartite Matching Queues in a Quantum Switch

Literature Survey on Stochastic Matching Networks

26

27 of 69

Online Marketplaces

REVENUE MAXIMIZATION

SINGLE MATCHING QUEUE

27

28 of 69

REVENUE

28

29 of 69

FLUID REVENUE

29

30 of 69

CAN WE ACHIEVE FLUID REVENUE?

30

Small Perturbations:

Small Loss in Revenue ☺

Large Queue Length (Heavy-Traffic result) ☹

What is the trade-off?

31 of 69

31

32 of 69

ASYMPTOTIC VIEWPOINT

32

33 of 69

33

34 of 69

Online Marketplaces

REVENUE MAXIMIZATION

BIPARTITE PLATFORM

34

35 of 69

CLASSICAL QUEUE AS A MATCHING QUEUE

35

36 of 69

BIPARTITE MATCHING PLATFORM

36

BipartiteMatching Platform

Parallel Server System

37 of 69

MATCHING PLATFORMS

37

Successful operation of these platforms involves several control and decision problems: How to match customers and service providers? How to mange congestion in the platform? How should the services be priced? How should these prices be adjusted dynamically to match constantly changing supply and demand?

We study these systems from a queueing or stochastic networks perspective. The basic building block of these systems is a two sided queue

----------------------

Over the last several years, wireless, mobile and cloud technologies have become ubiquitous, and consequently, most of the economic and societal activity has moved online, and platforms facilitate these activities. Examples include Amazon and ebay that act as platforms to match sellers and buyers, Ride hailing and Meal delivery platforms such as Uber, Lyft and Doordash that match riders and drivers. In this talk, we focus on the latter. Lets consider the example of a ride hailing system on a city

The whole city can be divided into several regions. Riders and Drivers arrive in each region and wait in their queues. A rider in a region can be served by drivers within that region or nearby regions. This can be modeled using a bipartite graph as follows, where the edges denote the compatibility or closeness constraints.

38 of 69

MATCHING PLATFORM

MaxWeight Matching

38

We want Joint Pricing and Matching Policy

39 of 69

LARGE MARKET REGIME

39

n independent matching queues

40 of 69

COMPLETE RESOURCE POOLING

40

CRP Condition

Related to Hall’s condition. Ensures

Graph is connected

Fluid solution is in the interior of the “stability region”

Key Ingredient: State Space Collapse!

41 of 69

INCORPORATING STRATEGIC SERVERS

Incentive-compatible, near-optimal, pricing and matching policies for a wide variety of utility functions

Result [Varma, Castro, M 2021]

Set a Driver Destination

When one sets a Driver Destination in your app, riders going towards that destination will be matched.

Area Preferences

Surge Pricing

What if I lie and join another queue

Model

42 of 69

STOCHASTIC MATCHING NETWORKS

BEYOND BIPARTITE SETTING

42

43 of 69

MATCHING QUEUE AND BIPARTITE MATCHING PLATFORM

Matching Platform

44 of 69

PAYMENT CHANNEL NETWORKS

44

Matching Network

Classical Communication Network

45 of 69

OUTLINE OF THE TUTORIAL

PART I
Introduction

Heavy-Traffic in a single Matching Queue

Matching and Pricing in Online Market Places

PART II

Multipartite Matching Queues in a Quantum Switch

Literature Survey on Stochastic Matching Networks

45

46 of 69

Thank You

BREAK

46

47 of 69

Backup Slides

47

48 of 69

EXTENSIONS FOR ONLINE MARKETPLACES

48

49 of 69

POWER OF MAX-WEIGHT FOR LARGE SYSTEMS

49

Analogous to the operating point being in the interior of a facet of capacity region

50 of 69

STRATEGIC SERVERS

50

Queue 3, 4 offers better price

Queue 2,4 share neighbors with Queue 1

What if I Lie and Join Another Queue?

51 of 69

STRATEGIC SERVERS

51

Utility Function depending on the price, detour cost, and expected matching rates

Each Driver will maximize its Utility (Equilibrium (EQ))

52 of 69

RELATED WORK

52

53 of 69

CONCLUSIONS

53

54 of 69

Other Applications

54

55 of 69

ASSEMBLE TO ORDER MANUFACTURING SYSTEMS

55

56 of 69

ASSUMPTIONS FOR HEAVY-TRAFFIC

For stability (needed in both regimes):

Laplace Regime (To retain symmetry in the limiting distribution):

Hybrid Regime (To use Fourier transform theory):

56

57 of 69

GENERAL CASE (SINGLE SERVER QUEUE)

General Arrivals and General control – Stationary distribution unknown

57

58 of 69

TWO-SIDED QUEUE

58

59 of 69

…

MGF METHOD [Hurtado-Lange, Maguluri 19]

60 of 69

…

MGF METHOD

61 of 69

TRANSFORM TECHNIQUES

62 of 69

ASSUMPTIONS [VARMA, CASTRO, M ‘21]

62

63 of 69

ASSUMPTIONS [VARMA, PORNPAWEE, WANG, M ‘20]

63

64 of 69

64

65 of 69

JOINT WORK WITH

65

Sushil Varma

OR PhD candidate

ISyE, GaTech

Pornpawee Bumpensanti

OR PhD Candidate

ISyE, GaTech

He Wang

ISyE, GaTech

Francisco Castro

Anderson School of Management

UCLA

66 of 69

OUTLINE

PART I

Heavy-Traffic in a Single Matching Queue

Recap: Heavy-Traffic in a Classical Queue
Proof Sketch

Matching and Pricing in an Online Marketplace

A Two-Sided Queue
A Matching Platform

66

67 of 69

OUTLINE

PART I

Heavy-Traffic in a Single Matching Queue

Recap: Heavy-Traffic in a Classical Queue
Proof Sketch

Matching and Pricing in an Online Marketplace

A Two-Sided Queue
A Matching Platform

67

68 of 69

RELATED WORK

Transient Analysis or Discounted MDP

[Plambeck, Ward ‘06], [Gurvich, Ward ‘14], [Lu, Song, Zhang ‘14], [Hu, Zhou ‘18], [Ozkan, Ward ‘20], [Ozkan ‘20] [Chen, Hu ‘20]

Dynamic Matching Models

[Caldentey, Kaplan, Weiss ‘09], [Adan, Weiss ‘12], [Busic, Meyn ‘15], [Adan et. al. ‘18], [Cadas et. al. ‘20]
A single pair of demand and supply arrive at each time slot – Ensures Stability

Other models

Organ matching: [Anderson, Ashlagi, Gamarnik, Kanoria ‘17], [Akbarpour, Li, Gharan ’20]
Stochastic Programming: [Dogru, Reiman, Wang, ‘10], [Reiman, Wang ‘13]

Our focus

Steady-state analysis
Ensuring stability challenging
[Nguyen, Stolyar ‘17] use dynamic arrivals and abandonment for stability, but focus on fluid model
Heavy-Traffic

68

69 of 69

Two-Sided Queues

INTRODUCTION

69