Online Trading as a Secretary Problem Variant
針對「秘書問題交易變體（SPVT）」，研究團隊提出全新隨機演算法，將強競爭比極限精準推進至3.523，完美收斂了過往的理論邊界。
- 針對1賣家與n買家的SPVT模型，研究團隊將最佳強競爭比（Strong competitive ratio）極限精準鎖定在3.523。
- 揚棄過去將賣家視為虛擬買家的假設，新演算法細緻區分了「拒絕購買」與「錯過買家」的控制權限差異。
- 運用線性規劃對偶理論與無窮超圖拉姆齊定理，嚴格證明3.523為所有線上演算法無法跨越的絕對下界。
經典的「秘書問題」探討如何在未知的面試名單中選出最強候選人，這項最佳停止（Optimal stopping）理論如今被延伸到具備 1 個賣家與 n 個買家的線上交易市場中。由中國科學院與華東師範大學組成的研究團隊，針對「秘書問題交易變體（SPVT）」提出了全新的隨機演算法，成功將「強競爭比（Strong competitive ratio）」的理論極限精準鎖定在 3.523（確切數值為 4e²/(e²+1)），完美填補了過去界於 3.258 到 4.189 之間的學術空白。
1名賣家與n名買家的SPVT線上交易模型
在傳統的秘書問題中，決策者只需決定是否「錄取」依序出現的面試者；但在秘書問題交易變體（SPVT，Secretary Problem Variant Trading）中，情境轉換為一名居中協調的「中間商」。這個市場裡共有 n 名買家與 1 名手握單一商品的賣家（統稱為代理人），這些代理人會以完全隨機的順序依次與中間商接觸，並在會面當下揭露自己對該商品的估值（價格）。
中間商面臨的挑戰在於，每次接觸都必須立刻做出不可撤回的決定：如果是賣家，必須決定是否依其報價買入商品；如果是買家，且中間商手中已有商品，則必須決定是否將商品賣給對方。一旦錯過當前代理人，就無法再回頭交易。
這個模型的最佳化目標是「最大化社會福利（Social welfare）」，也就是確保最終持有該商品的人（無論是賣家自己保留，或是某個成功買到的買家）擁有最高的估值。如果賣家在第一順位出現且報價為 0，這個交易模型就會退化回最傳統的秘書問題。
評估效能的兩把量尺：強競爭比與弱競爭比
在線上演算法領域，我們通常無法預知未來，因此會將線上演算法獲得的結果，與擁有「全知視角」的離線最佳解（Offline optimum）進行比較，這個比值稱為「競爭比（Competitive ratio）」。針對 SPVT 模型，學界將這把量尺分為強與弱兩種維度。
「強競爭比」賦予離線最佳解極大的優勢：離線演算法不僅知道所有人的報價，還能任意更改代理人的出場順序，藉此保證商品絕對會落入全部 n+1 名代理人中出價最高者的手中。這是一個極為嚴苛的對照基準，過去針對單一賣家交易的強競爭比，學界僅證明其下界為 3.258，並提出過一個達到 4.189 上限的演算法。
相對而言，「弱競爭比」則限制離線最佳解必須遵守系統一開始給定的隨機出場順序。即便離線演算法事前知道完整名單與順序，也無法主動把出價最高的人挪到最有利的位置。針對弱競爭比的線上演算法設計，由於順序相依性的數學分析極為複雜，過去在文獻中甚少有具體突破。
經典秘書問題與預言家不等式的理論脈絡
要理解 SPVT 演算法的價值，必須先梳理其背後的兩大理論基石。最經典的秘書問題採用「先觀察、後決定」策略：決策者會先放過前 ⌊n/e⌋ 個面試者，接著只要遇到比觀察期內更優秀的對象就直接錄取。當 n 趨向無限大時，此策略可以保證獲得 1/e（約 37%）的最佳選擇機率，其競爭比即為 e。
另一個緊密相關的理論是「預言家不等式（Prophet inequality）」。預言家不等式的情境是：面試順序已經固定，但決策者事先知道每個面試者能力值的「機率分佈」。隨後學界又發展出混合兩者的「預言家秘書問題（Prophet secretary problem）」與「樣本驅動（Sample-driven）」的最佳停止問題。
Correa 等人曾在上述基礎上提出另一種線上交易變體，允許中間商在市場中低買高賣，並證明如果市場價格遵循獨立同分佈（i.i.d.），存在一個競爭比為 2 的最佳演算法。然而，本作探討的 SPVT 並未假設價格服從任何已知分佈，僅依賴到達順序的均勻隨機性，這讓演算法的設計更具挑戰性。
突破4.189天花板：達成3.523的強競爭比
在本篇研究中，團隊設計出一個名為 Algorithm 1 的全新隨機演算法，成功將 SPVT 的強競爭比上限壓縮至 4e²/(e²+1)，約等於 3.523。這個演算法最核心的突破，在於對待「賣家」的特殊邏輯。
在過去 Chen 等人的框架中，為了方便分析，往往將賣家視為一個「虛擬買家」。也就是把「中間商不跟賣家買」等同於「將慈善機構送的商品賣給賣家」。但在這篇論文中，團隊敏銳地抓出兩者的控制權差異：中間商對於「不買商品（讓賣家保留）」具有絕對控制權；但對於「把買到的商品賣給出價最高的買家」卻不具備絕對控制權（因為高價買家可能已經提早出現並被錯過）。
基於這個微小但關鍵的差異，Algorithm 1 透過複雜的雙重積分，計算出賣家到達時間 s 與最佳買家到達時間 t 的聯合機率。演算法會根據時間點 1/e 以及 (e-1)/e 作為動態閾值，決定是否收購賣家的商品。這個不把賣家當成一般買家看待的策略，成功收斂了社會福利的期望值，得出 3.523 的強競爭比。
引入線性規劃對偶理論：證明3.523下界
證明了 3.523 的上限後，團隊接著要證明這個數字也是所有演算法的「下界」——意味著這就是 SPVT 問題的理論極限。為了建構這個嚴謹的數學證明，研究人員先將問題簡化，假設賣家的報價永遠為 0，藉此收束代理人的價格向量。
接著，團隊引入了「值獨立（Value-independent）」的概念，證明我們可以將討論範圍縮小到「只看相對排名、不看絕對價格」的演算法，且不會影響最佳競爭比的推導。在這個過程中，研究團隊動用了無限超圖（Infinite hypergraphs）上的拉姆齊定理（Ramsey's theorem），排除掉雜亂的價格空間干擾。
將決策行為轉換為機率變數後，研究人員建立了一組線性規劃（LP，Linear Programming）模型。透過求解該線性規劃的對偶公式（Dual formulation），團隊在數學上嚴謹地證明：任何合法對偶解的目標值都不會超過 (e²+1)/(4e²)。將其取倒數後，完美呼應了 3.523 的下界，確認 Algorithm 1 已達到理論上的完美極限。
雙閾值機制的表現：達成1.83683弱競爭比
在補齊了強競爭比的學術拼圖後，研究團隊轉向難度極高的「弱競爭比」。由於弱離線最佳解受到預定到達順序的牽制，對線上演算法的容錯空間相對友善。團隊對此提出了一個極簡的演算法（Algorithm 2），成功達成數值為 2 的弱競爭比。
更進一步地，當限定賣家報價為 0（代表中間商一定會收購商品進行轉賣）這個特殊情境時，團隊設計出更精細的「雙閾值演算法（Algorithm 3）」。此演算法採用兩個不同的觀察期基準點來篩選潛在買家，最終將弱競爭比的上限壓低至 1.83683。同時，團隊也透過反證法確立了 1.76239 的弱競爭比下界，為未來的線上交易最佳化研究標定了明確的推進區間。
處理線上交易的隨機性時，將賣家與買家的控制權限脫鉤思考，是突破最佳停止理論（Optimal Stopping）數學極限的關鍵路徑。