Single-minded Auction In Vilna Balanced Computational Problems

In this thesis we study a special type of combinatorial auction, the single-minded auction.In single-minded auciton each buyer wants to buy a subset of the auctioned commodities, i.e. there exists a subset A, (?)B, if A (?) B, then v(B) = v;otherwise v(B) = 0. We define the Walrasian Equilibrium of single-minded auction. Using the duality theorem [22] we establish the necessary and sufficient condition for the existence of Walrasian Equilibrium.We characterize the problem by graph theory language. We prove that for bipartite graph Walrasian Equilibrium always exists. We also give a polynomial time algorithm to compute the equilibrium for this class.We also study the communication complexity of single-minded auction. Communication complexity was proposed by Yao [27]. It has been widely used in computational theory. We studied the necessary communication between the buyers and the auctioneer. We give a (?)(mn) result for n buyers, m commodities single-minded auction.