Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657870 | Theoretical Computer Science | 2005 | 9 Pages |
Abstract
We consider a social optimization model of pricing scheme in single-minded auctions, in cases where Walrasian equilibrium does not exist. We are interested in the maximization of the ratio, R, of happy bidders over all agents, in a feasible allocation-pricing scheme. We show NP-hardness of the optimization problem, establish lower and upper bounds of R, as well as develop greedy algorithms to approximate the optimal value of R.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Li-Sha Huang, Minming Li, Bo Zhang,