T(a)tonnement Mechanisms for Combinatorial Exchanges
Combinatorial exchanges are double sided marketplaces with multiple sellers and multiple buyers trading with the help of combinatorial bids. The allocation and other associated problems in such exchanges are known to be among the hardest to solve among all economic mechanisms. It has been shown that the problems of surplus maximization or volume maximization in combinatorial exchanges are inapproximable even with free disposal. In this paper, the surplus maximization problem is formulated as an integer linear programming problem and we propose a Lagrangian relaxation based heuristic to find a near optimal solution. We develop computationally efficient t(a)tonnement mechanisms for clearing combinatorial exchanges where the Lagrangian multipliers can be interpreted as the prices of the items set by the exchange in each iteration. Our mechanisms satisfy Individual-rationality and Budget-nonnegativity properties. The computational experiments performed on representative data sets show that the proposed heuristic produces a feasible solution with negligible optimality gap.
Shantanu Biswas Y. Narahari
Education & Research Infosys Technologies Bangalore, India Dept. of Computer Science & Automation Indian Institute of Science Bangalore, India
国际会议
上海
英文
25-31
2010-11-10（万方平台首次上网日期，不代表论文的发表时间）