本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
我們研究了在三類集合系統中僱用代理商團隊的真實機制：頂點覆蓋拍賣、k 流拍賣和切割拍賣。對於頂點覆蓋拍賣，頂點由自私且理性的代理人擁有，拍賣師希望從他們那裡購買頂點覆蓋。對於 k 流拍賣，邊由代理商擁有，對於給定的 s 和 t，拍賣師希望購買 k 條邊不相交的 s-t 路徑。在相同的設定中，對於切割拍賣，拍賣師希望購買 s-t 切工。只有代理人知道他們的成本，拍賣師需要根據代理人的出價選擇可行的組合和付款。我們為所有三套系統提供持續競爭的真實機制。也就是說，對於該類別中的每個設定係統，該機制的最大超額支付在任何真實機制的最大超額支付的恆定因子內。頂點覆蓋的機制是基於透過從某個矩陣的主特徵向量導出的乘數來縮放每個出價。 k 流的機制將圖修剪為最小 (k+1) 連接，然後套用頂點覆蓋機制。類似地，切割機制會收縮圖，直到所有 s-t 路徑的長度恰好為 2，然後套用頂點覆蓋機制。