Patent ID: 7636678

Claim:
A system comprising: one or more processors that execute the following computer executable components stored on at least one computer readable medium; an auction component that receives, from each bidder of a set of bidders, a private bid and a private fixed budget associated with one or more items auctioned in a multi-unit auction; a partition component that randomly separates the set of bidders into two sets of bidders, with a probability of 0.5; a pricing component that asymptotically computes a profit maximizing price for each of the two sets of bidders, each price is determined by a component that maximizes revenue as a function of private bids and private fixed budgets associated with its set of bidders based on, at least in part, the following function: i o = min i ⁢ ∑ j = 1 i - 1 ⁢ b j ≥ u i ⁢ m 2 wherein b i is the maximum budget submitted by a bidder i; u i is the utility value for one item, submitted by the bidder i; and m is the number of indivisible items being auctioned; and an allocation component that utilizes the profit maximizing price associated with a set of bidders of the two sets of bidders with an other set of bidders of the two sets of bidders to allocate auctioned items to the set of bidders.