How to maximize the total auction price for a set of bids subject to bidder constraints

Question

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.)

Fig 1. Matrix of assets and bids

              ASSETS -- (A)
         ---------------------------------------------
               A1    A2    A3    ...    Ai   ...    An
            +  --    --    --    ---    --   ---    --

BIDDERS  B1 | A1B1  A2B1  A3B1   ...   AiB1  ...   AnB1
(B)
         B2 | A1B2  A2B2  A3B2   ...   AiB2  ...   AnB2

         B3 | A1B3  A2B3  A3B3   ...   AiB3  ...   AnB3

        ... | ....  ....  ....   ...   ....  ...   ....

         Bj | A1Bj  A2Bj  A3Bj   ...   AiBj  ...   AnBj

        ... | ....  ....  ....   ...   ....  ...   ....

         Bm | A1Bm  A2Bm  A3Bm   ...   AiBm  ...   AnBm

Edit:

As mentioned in the comments, 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.

Answer 1

I think you have a generalized assignment problem. In general the GAP is NP-hard, but Wikipedia mentions a greedy approximate algorithm. You could also apply integer programming techniques to get approximate solutions.