｜透過無線競標進行公正拍賣

摘要：基於兩項特色，本文提出新的無線公正拍賣方法來改善資源的分配機制。首先是實作出賽局理論裡的斂核觀念來滿足公正的原則。從公正理論的觀點來看，透過斂核觀念所產生的價格比傳統用核觀念產生的價格好。其次是實作出密碼學裡的秘密分享技術。從務實面考量來說，這可以避免無線競價過程中潛在的圍標問題。此外為了彰顯本方法的實用性，本文已將無線公正拍賣方法在手機上實作出來。

Abstract: A new wireless justice-based auction method has been proposed as a better resource assignment mechanism due to two salient features. One is to implement the nucleolus concept in game theory for satisfying the requirements of justice. From a justice-theoretic viewpoint, the generated price based on the nucleolus is a better approach than the traditional price based the core concept. The other is to implement the secret-sharing technology in cryptography. From a practical consideration, this is to avoid the potential corruption problem in wireless bidding process. Moreover the proposed justice-based wireless auction method has been implemented on mobile phones for showing its feasibility.

關鍵詞：公正拍賣、斂核、無線競標、秘密分享技術、舒-瑞氏演算法

Keywords：Justice-based Auction, Nucleolus, Wireless Bidding, Secret-Sharing Technology, Solymosi-Raghavan Algorithm

前言
進行產權轉移時，大家都希望在公開、公平、公益及公正的環境下進行交易。這裡公開是指交易訊息的透明化，也就是說讓有能力參與交易的人都能參加。公平是指交易的人都在平等的基礎上競爭，而非某些人有特權。公益是指將交易的利益極大化，這樣參與交易的人才能分享最大的利益，也就是經濟學裡的柏瑞圖最佳化（Pareto-optimal）[1]結果。公正是指交易時能堅持照顧到弱勢團體的正義原則[10]，也就是說將最弱勢團體的利益極大化。目前採用單邊拍賣（One-sided Auction）[1]來進行產權轉移時，大都已能考量到公開、公平、及公益的原則，而本文將探討如何在單邊拍賣裡的同時拍賣（Simultaneous Auction）[1, 9]進行公正拍賣（Justice-based Auction）；特別是透過無線競標（Wireless Bidding）方式來進行公正的拍賣。

在單邊拍賣制度中，通常可再細分為順序拍賣（Sequential Auction）、同時拍賣及組合拍賣（Combinatorial Auction）三大類[4]，如圖一所示。這裡順序拍賣指的是將待拍賣物依照順序而分別拍賣之。如果待拍賣物彼此是獨立的，也就是說沒有互補性或替代性等關係，則順序拍賣常被採用。同時拍賣是指參與競價的人可對任一待拍賣物同時出價。如果限定參與競價的人最多只能得標一次，則該同時拍賣稱為指派賽局（Assignment Game）[1, 8, 13]。組合拍賣是指參與競價的人可對任一組待拍賣物出價[4]。同時拍賣及組合拍賣常用於待拍賣物是相關的場景裡，也就是說待拍賣物可能具有互補性或替代性的關係。對參與競價的人來說，他們在組合拍賣裡會比在同時拍賣裡有更多的選擇機會。

對待拍賣物來說，指派賽局可以產生核裡價格（The Imputation of Core）[1, 9]，也就是說經濟學裡的柏瑞圖最佳化結果。柏瑞圖最佳化的結果符合前述的公益原則，但不一定會符合公正原則。前述的公正原則來自公正理論（Justice Theory）[10]，隨後發現其理念可用賽局理論（Game Theory）裡的斂核（Nucleolus）[6, 9, 11]數學模式描述。在公正理論裡，這是指將最弱勢團體的福利最大化。在賽局理論裡，這是指將最小滿意度（Satisfaction）[14]團體的滿意度極大化。對指派賽局來說，其斂核的計算更可透過舒-瑞氏演算法（Solymosi-Raghavan Algorithm）[3, 14]來計算。當核裡價格存在時，這裡必須再強調的是斂核價格一定是核裡價格，但核裡價格不一定是斂核價格。

由於指派賽局常透過電腦網路來進行產權的轉移，例如我國的第三代行動通信執照[2, 3]就是透過開放式電腦網路進行同時拍賣並產生核裡價格。如果採用標單內容不開放方式來競標，則開標過程會有洩露底標的危機存在。針對此問題，本文將採用秘密分享技術（Secret Sharing Technology）[1, 12]並從無線競標的角度來說明如何防止洩露底標。秘密分享技術使得公正拍賣更容易進行。

為說明無線競標的公正拍賣，底下先說明指派賽局的公正拍賣架構。公正拍賣包含標單、得標者名單與得標價格三項要素，所以其內容可分成（1）用秘密分享技術[1, 12]產生標單矩陣（Bids Matrix）、（2）用利潤矩陣（Profits Matrix）產生得標者名單、與（3）用滿意度矩陣（Satisfaction Matrix）產生得標價格三項步驟來依序進行。隨後說明秘密分享技術的內容，並舉例來說明標單矩陣的產生。其次將標單矩陣轉成利潤矩陣，再說明如何透過匈牙利人法（Hungarian Method）[8]來從利潤矩陣產生得標者名單。隨後將利潤矩陣轉成滿意度矩陣後，再用舒-瑞氏演算法[14]算出得標價格。接著說明實作後的操作步驟；這包含採用J2ME（Java 2 Platform, Micro Edition）技術[5]來實作秘密分享方法，而用J2SE（Java 2 Platform, Standard Edition）技術[5]實作斂核開標系統。最後則是結論。