Partner selection is critical to the success of a Virtual Enterprise. This paper studies the partner selection problem under the virtual organization breeding environment where candidates have private information about their cost to undertake the tasks. A systematic solution is provided to reveal the true value of the private information and then select the optimal partners. This solution mainly comprises two steps: (1) For each possible cost combination, a multi-objective integer nonlinear programming model and an algorithm are designed to obtain the optimal partners. Then, a social choice correspondence, which indicates the optimal partners for any cost combination, is formulated. (2) An incentive mechanism is constructed to implement the social choice correspondence and ensure that candidates will announce their values of cost truthfully. Furthermore, a numerical study is provided to illustrate the effectiveness of the solution and to investigate the relationship between the construction of the collaborative network and the utility to partners. We find that the number of candidates in each period affects the utility of partners as well as the expected surplus of the leading company significantly.