蒼蠅拍打飛機的dynamic matching

Leshno， Jacob。 “Dynamic matching in overloaded waiting lists。” 2019， WP

T=1，2，。。。（finite）

每期t的時候產出一個object xt，同時有一堆新人過來排隊（隊伍裡也包含之前沒分配到還在的）

東西和人都有2種type： 東西為A or B，人為a or b————機率分別為p （1-p）和q （1-q）

（A，a） （B，b）就是match其他就是mismatch

人獲得東西的payoff為 1 （match） or v （mismatch） v<1

所有人風險中立線性效用：得到東西的payoff減去等待的cost，其中cost為c *w w為等待的period

Remark：這裡假設轉賣也有time cost所以永遠worse

p=q時稱為balanced

social planner只關心mismatch的程度（min），所以用以下定義的welfare loss function（WFL）

這裡I為set of agents

後面減個機率差是因為那東西是c逼近0時的mismatch rate

為了把問題reduce成經典的balk model，這裡用buffer-queues： 把佇列分成2組 A佇列專門等A type的object， B佇列專門等B的 （heter obejcts時候瞎排隊的確不好 見fig 1

https：//

arxiv。org/pdf/1901。0639

9。pdf

）

於是分析可以變為只分析某一個佇列就好了

排隊裡面的經典邏輯就是先到先得（first come first served FCFS）

這文章先分析了下FCFS，然後提出了一個randomization比FCFS好————這顯而易見，因為random之後每個agent的cost就不是佇列長度而是佇列的期望

這種randomization被叫做（K，Q）-buffer-queue policy，其中K是一個佇列能裝的agent的上限，Q是assignment

Q_k（n）即在一個長度為k的佇列裡排在第n個的agent獲得object的機率

顯然Q_k（1）=1就是FCFS

機制執行邏輯如下（此機制等價於一個direct mechanism 見footnote 21）：

有很多個agent （I）

放2批人進來分別組成A佇列和B佇列

假設現在t期，有B type的xt出來了

1）如果B佇列有人，那就按B的Q把東西分配給B佇列裡的人， end

2）如果B佇列沒人，就找個之前沒放進來的agent問他：

2-1） 如果此時A佇列滿了（達到K了） 就把B type的xt直接給這個新來的，end

2-2） 如果A佇列沒滿，就問新來的你要拿B還是要去A排隊——拿了B就像2-1） 一樣end，去A排隊了就不管這個新來的，再找下一個新來的問

當然A佇列和B佇列具體的parameter不一定一樣，所以這樣一個機制是2個pair

這個機制下SP（說真話）被定義成————每個agent都會按照自己的type去排隊（a去A佇列，b去B佇列）；但是如果他想去隊已經滿了，他就去接受一個mismatch的allocation了就像like 2-1）一樣，因為這個時候他排不進去了

Remark： 實際上是這個agent發現接受mismatched object的效用大於等待的cost，因為此時滿佇列帶來的成本太高，這個機制下的quota K其實就是等待時間的threshold value

這裡一個有趣的結果就是，只要佇列沒滿，那麼一個新agent加入A佇列的機率就等於q （B佇列就為1-q），不管這佇列前面排了多少個人

倒回去，給定說真話，agent的期望只關於這個機制（K，Q）和p，q

再倒回去，如果K，Q設的好，那麼所有人都會說真話

不出意外的，這個機制是給馬爾科夫鏈，state space

就是佇列人數（類似結論見

https：//

arxiv。org/pdf/1804。0186

1。pdf

）

後面主要就是比較了幾種機制

FCFS

LIEW （load independent expected wait）：這個機制下不管佇列長度多少，期望等待時間都一樣

SIRO （service in random order policy）： 這個機制下Q為均勻分佈