报告人: Prof. Mengdi Wang, Princeton University

时间： 2015-07-07 15:10-16:10

地点： 理科一号楼 1479

Abstract: Consider the optimization problem that involves multiple participants driven by self interests and some common goods. We focus on the case where individual preferences are not necessarily convex, making the problem NP-hard. We analyze the nonconvex duality and provide a complete mathematical characterization of the duality gap, which often vanishes to zero as the number of participants goes to infinity. Moreover, we show that there exists an approximate optimum by solving the dual problem and provide a coordinative dual algorithm to achieve the optimum in polynomial time.