Prize Competition Mechanism Design for Seeking Shortest Path Solution
Date Issued
2011
Date
2011
Author(s)
Ho, Ting-Yu
Abstract
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.
Subjects
Prize Competition
Collective Solution
Shortest Path Solution Seeking
Incomplete Information
Mechanism Design
Stackelberg game
Competitive Behavior
SDGs
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-100-R98921013-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):42f10ea0b7bdf4bf2744d2d518fd4ec1