以獎金競賽尋求最短路徑解答之機制設計

Abstract

獎金競賽(Prize competition)是公開的去徵求專家以及創造力的一種方法，可以解決企業的問題並增加成功機會。一個集體的解答是一種由群體所提出的問題解決方法。雖然為尋求集體解決方案(collective solution)的獎金競賽已被廣泛採納，並已成功地激勵了集體的創新(collective innovation)；但還需要有對一個有效的方法來設計獎金競賽機制尋求集體解決方案。這些挑戰包括瞭解解答提供者(solution provider)提交解決方案的策略以便能制定合理的獎金和從所有的解決方案提供者提供的解答中，編織成一個更好的解決方案的機制設計。 在這篇論文中，我們考慮在交通網絡中搜尋最短路徑解答(shortest path solution seeking)的問題，其中有一個路徑解答搜尋者(path solution seeker, PSS)和許多路徑解答提供者(path solution provider, PSP)，他們彼此間的訊息為不對稱(information asymmetry)。PSS想在PSPs中徵求在交通網絡中兩個節點之間的最短路徑。但每個PSP都只有局部交通網絡訊息。PSS和PSP有著共同PSP的統計資訊。PSS將網絡劃分成若干區域，並宣布在每個區域中的比賽獎金，徵求指定的節點間的最短路徑。為了保護PSP的智慧財產權，一開始PSP只需提交路徑的距離。其提交一對節點間距離是最短的PSP贏得獎金，並提交最短路徑的路線。得到在每個區域中的最短路徑後，PSS可以進一步將它們連接成一個心目中想要節點間的最短路徑。剩下的設計問題是，在這樣一個獎金競賽機制下，獎金多寡應如何設計，使PSS可以以最低的獎金成本並最大化最短路徑的價值。為了設計最佳獎金競賽機制，具體的挑戰如下：（1）如何為路徑提供者對獎金競賽的路提交反應建模？ （2）如何設置在每個區域中的最佳獎金？ PSS的獎金制定問題在考慮PSP的提交路徑策略下被建模為一個領導者和多追隨者的訊息不完整博弈(a single-leader and multiple-follower Stackelberg game with incomplete information)。影響PSP提交行為包括：獎金，路徑計算成本，交通網絡資訊，更關鍵的是PSP對其他的PSP的競爭模型。從個別PSP的角度來看，贏得獎金表示其所提交的路徑距離短於其他的PSP所提交的最短路徑。因此，個人的PSP獲勝機率(winning probability)可以由其他的PSP的提交行為的不確定性來建模。這個PSP模型為PSS在獎金競賽機制中來制定最佳獎金的基礎。對於 PSS獎金的制定問題，除了路徑的價值和獎金的成本外，PSS將每個PSP視為同質性機率模型，PSS獲得的數據收集和經驗得知PSP的路徑計算費用、交通網絡的總節點數和路徑的距離的機率分佈均被建模。 我們對個別PSP對獎金競賽反應的競爭行為進行了分析，考慮不同的其他競爭的PSP的最短路徑提交分布情形。提交較短距離（更好的解決方案）的條件被推導為對獎金競賽的最佳反應。分析結果顯示，提交的路徑距離較短意味著其他PSP提交最短路徑距離的機率分佈平均值下降，但就下降的變異量來說，先提交較短路徑而後提交較長路徑。 數值研究結果如下： （1）對於個別PSP而言，是否會提出最短路徑的關鍵因素為獎金，而不是其他的PSP的路徑提交行為; （2）當獎金越高，PSS會得到較短期望最短路徑距離(較好解答)； （3）當獎金越高，PSS得到的期望最短路徑距離的下降幅度趨緩； （4）預期參與人數較少的區域需要較高的獎金以激勵競爭； （5）當預期有越多PSP參與比賽時，期望利潤較高。

Prize competition is an open approach of soliciting expertise and creativity from the public to increase business success or solving problems. A collective solution is a problem-solving method generated by a group after the problem is posed to the group. Although prize competitions for seeking collective solutions have been adopted and have successfully stimulated collective innovations in many cases, there are yet needs for methodology to design an effective prize competition for seeking collective solutions. The challenges include characterization of solution providers’ submission strategy for reasonable winning prize setting and mechanism design to connect the collective solutions from all solution providers and weave them into a better solution. In this thesis, we consider a problem of shortest path seeking in a transportation network, where there are one path solution seeker (PSS) and many path solution providers (PSPs) with asymmetric information. The PSS would like to solicit a shortest path solution between two nodes of the transportation network from PSPs. Individual PSPs have different and only partial network information. The PSS and PSPs have common statistical information about PSPs. The PSS divides the network into two sections and holds a prize competition in each section to solicit shortest path solutions from PSPs among specified pair of cities in the section. To protect PSPs’ intellectual right, PSPs first submit the distance of paths only. The PSP, whose submitted distance is the shortest for a pair of nodes, then submits the solution path of the pair and wins a prize. After procuring shortest paths in each section, the PSS can further connect them into a shortest path between the PSS’ desired pair of cities. A remaining design issue is that under such a prize competition mechanism, how the prize value should be designed so that the PSS can maximize the value of the shortest path with minimum cost of prizes. To design the optimal prize value, specific challenges are as follows: (1) How to formulate the PSPs' path provisioning response to the prize? (2) How to set the optimal prizes to each section as budget of the prize competition? The problem of PSS’ prize setting in consideration of individual PSPs’ strategy of submitting path solution is formulated as a single-leader and multiple-follower Stackelberg game with incomplete information. The factors affecting individual PSPs’ submission behavior include the prize, path computation cost, transportation network information, and crucially, one PSP model about competition with other PSPs. From individual PSPs’ viewpoint, one will win the prize competition when the distance of submission is shorter than the shortest path submitted by other PSPs. Therefore, individual PSPs’ winning probability can be modeled by uncertainty of other PSPs’ provision submission behavior. This model can be a foundation to design a mechanism for the PSS to set optimal prize. For PSS’ prize setting problem, in addition to value of path and cost of the winning prize, probability distribution of information about PSPs’ path computation cost, total number of nodes in a network and path distance obtained by data collection and experience are formulated. Individual PSPs’ competitive behavior response under the prize competition model is analyzed by considering different distributions of shortest path submitted by other competitive PSPs. Requirement to submit shorter distance (better solution) is deducted to the best response to prize competition. The analysis results show that the distance of submission path is shorter as mean of probability distribution of other PSPs’ distance of submission shortest path decreases but is shorter first and then becomes longer as variance of other PSPs’ probability distribution of submission distance of shortest path decreases. Finally, numerical study is performed and results are as follows： (1) For individual PSPs, the prize is the key factor to submit the shortest path (the best solution), not other PSPs’ submission behaviors； (2) When the prize is setting higher, the shorter distance (better solution) the PSS may procure； (3) Decreasing tendency of expected distance of shortest path the PSS procures becomes inconspicuous when prize is setting higher； (4) The section with fewer PSPs needs higher prize to induce competition than the other section ； (5) Expected profit is higher when more PSPs are expected to participate in the prize competition.