I want to auction a set of ASSETS ($A$) and fetch the maximum total price. The bidding is simultaneous and works as follows.

Say I have a collection of BIDDERS ($B$) who, individually, bid to purchase a subset of the assets $A$. Each bidder is constrained by a maximum outlay which is typically less than the total price of their bids. I.e., Bidders can not generally purchase all the assets they bid on. They must settle on a subset as determined by the AUCTIONEER.

What method, algorithm or protocol can the auctioneer follow to ensure he fetches the MAXIMUM TOTAL PRICE? (Your ideal answer would include pseudocode.)

There is a similar assignment problem which the Hungarian Algorithm solves. Here is an online implementation. However, that doesn't exactly solve this problem because more than one asset can be assigned to each bidder subject to their total outlay constraints.


To clarify the question a bit. I am seeking an algorithm or, ideally, computer code or a program that can solve the problem in polynomial time or better.

New contributor
Mowzer is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

closed as unclear what you're asking by Steven Landsburg, David Handelman, RP_, Chris Godsil, YCor Oct 11 at 13:27

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • I am not sure I understand the question, but is this what you mean? We have an array of non-negative real numbers $b_{ij}$, and a list of non-negative real numbers $B_i$. We want to find a function $f$ that maximizes $\Sigma_j b_{f(j),j}$ subject to the constraints $\Sigma_{f(j)=i} b_{ij}\le B_j$ (all $i$). – Steven Landsburg Oct 11 at 2:44
  • Also: Clearly the answer to the question as you've posed it is that (assuming the index sets are finite), you try every possible $f$. Presumably you're looking for a method that is optimal in some sense. To make this a math problem, you need to specify that sense. – Steven Landsburg Oct 11 at 2:47
  • @StevenLandsburg: I edited the question for clarity. I added a generic chart of bids and assets. And clarified I'm seeking a solution in polynomial time or better. I think brute force might only get to exponential or factorial time which might make the solution unfeasible for large enough m and n. Does that help at all? – Mowzer Oct 11 at 3:16
  • I'm still not entirely sure whether your intended question is as in my first comment, or whether it's some other (closely related) question. It would be much clearer to strip out the bidders and the auctioneer (except maybe in a brief motivational aside) and just ask the math question. And the big matrix continues to take up a lot of space to no apparent purpose. – Steven Landsburg Oct 11 at 3:37
  • @StevenLandsburg: I don't know how to ask the question in strictly mathematical terms. Should I ask a separate question about how to translate the current English description into a purely mathematical question? In any case, I suspect the question you suggest in your first comment doesn't work because I am not seeking a function. I am seeking a specific assignment of each asset to exactly one bidder subject to bidder constraints that maximizes total price. But more specifically, I am seeking an algorithm or computer code that accomplishes that task. Is that what you mean by a function, $f$? – Mowzer Oct 11 at 4:32