｜線性規劃法分析上昇拍賣裡的品項下限效應

摘要：本文提出線性規劃法來分析上昇拍賣裡的品項下限效應。如果在上昇拍賣裡加入品項購買數目的最小下限，拍賣員可能直覺地好奇買方會買更多的品項。在本分析裡，拍賣品項被視為是原始空間裡的指派問題，而上昇拍賣是在其對偶空間裡尋找可行解的過程。依據對偶理論，這尋找結果可以用來產生原始與對偶空間裡的最佳解。由於品項下限會縮小尋找範圍，有可能尋找結果無法滿足互斥補數條件。當這情況發生時，它代表原來的指派問題無法產生最大的收入解。這項研究結果顯示品項下限效應是負面的。換言之，在上昇拍賣裡，品項下限可能對品項的提供者造成巨大的損失。

Abstract: Linear Programming method is proposed for analyzing the lot floor effect in ascending auction. An auctioneer may intuitively wonder bidders might buy more lots if a lot floor is added as a minimal number constraint for a given ascending auction. In this analysis, the ascending auction is interpreted as a process for searching a feasible solution in dual space if all the lots are treated as an assignment problem in primal space. According to the duality theorem, the search result is used to generate optimal solutions in primal and dual spaces. Since the search domain is smaller under the lot floor constraint, it is possible that no search result satisfies the complementary slackness condition. Whenever this case occurs, it means no maximal revenue solution for the original assignment problem. The research result shows the lot floor effect is negative. In other words, lot floor effect may produce a big damage to the owner who offers the lots in the ascending auction.

關鍵詞：上昇拍賣、品項下限效應、線性規劃法、同時多回合拍賣、組合拍賣

Keywords：Ascending Auction, Lot Floor Effect, Linear Programming Method, Simultaneous Multiple Round Auction (SMRA), Combinatorial Clock Auction (CCA)

前言
很多的拍賣都是採用上昇拍賣（Ascending Auction）的方式來進行。例如毛豬交易裡的英國式拍賣（English Auction）及頻譜釋照（Spectrum License Award）[1, 2]裡的同時多回合拍賣（Simultaneous Multiple Round Auction, SMRA）、組合拍賣（Combinatorial Clock Auction, CCA）[3]等。有時候拍賣員可能會在上昇拍賣裡加入活動法則（Activity Rule）[7]來規範競價行為。這些設計出來的活動法則可能會有正面效果，但也有可能會產生負面效果。例如拍賣員意圖讓競價者買更多的品項，故可能會加入品項下限的活動法則。本文將用線性規劃法（Linear Programming Method）[4]來說明品項下限會產生負面的效果。

要說明品項下限效應（Lot Floor Effect）前，這裡要先了解為何會產生上昇拍賣現象。早期上昇競價常採用競爭均衡（Competitive Equilibrium）[9, 10]的方式來闡釋，但其數學推導較為複雜。近年來，為了容易推廣上昇拍賣的觀念，學者常用線性規劃法[3]來說明上昇拍賣的原理。目前用線性規劃法來解釋拍賣原理已成為世界潮流。這種解釋方式主要來自三個原因。第一是線性規劃很容易了解，例如高中的數學課程就有介紹線性規劃的基本觀念。第二是管理科學裡的機制設計（Mechanism Design）[5, 6]常用線性規劃來設計。實務上，拍賣機制常會和其它的管理機制一起搭配使用;採用共同的線性規劃法來設計可以讓不同機制的整合更容易進行。第三是線性規劃的求解很容易，尤其是和傳統的微分方程式解法比較。

為了說明品項下限所產生的負面效應，底下分三部份來說明，即線性規劃法的重要觀念、這些性質的經濟意義及品項下限效應的分析。就線性規劃法來說，這是要介紹重要的觀念供後面的証明使用。它包括對偶性定理（Duality Theorem）[4]、互斥補數條件（Complementary Slackness Condition）[4]、華卡斯引理（Farkas’ Lemma）[4]及核端點（Extreme Points of Core）[8, 11]的計算。前兩者在說明原始空間（Primal Space）與對偶空間（Dual Space）[4]的轉換關係。華卡斯引理說明在更大的空間裡如何隔離這兩子空間。由於對偶空間具有核的特性，核端點計算是要了解核的範圍。本文已開發電腦程式來計算核的端點。

就經濟意義來說，品項與競價者的數量都顯現在原始空間的限制式，但競價者的資訊都顯現在目標式裡。由於非對稱資訊（Asymmetrical Information）的關係，這造成無法在原始空間內直接求解。在對偶空間裡，競價者的資訊都顯現在限制式裡，而品項與競價者的數量就出現在目標式。由於非對稱資訊的特色，這裡稱原始空間為拍賣員空間（Auctioneer Space），而對偶空間為競價者空間（Bidder Space）。在競價者空間裡，華卡斯引理暗示價格的提昇可以用來測試是否滿足互斥補數條件。這價格的提昇過程就稱為上昇拍賣。依對偶性定理，競價者空間的上昇拍賣可以間接的產生拍賣員空間的最大收入解。對核端點的計算來說，這可協助判斷上昇拍賣是否產生核裡價格（Core Price）。

就品項下限效應來說，這是依品項數目、選項數目與出價方式三者而將上昇拍賣分成英國式拍賣、同時單選拍賣、同時複選拍賣與組合拍賣四大類。品項下限效應只會出現在同時複選拍賣與組合拍賣裡。接著再針對這兩種拍賣方法進行品項下限效應的分析。分析結果顯示品項下限效應可能帶來負面效應，並對品項的提供者造成傷害。最後則是結論。