Most profitable multi unit open auction design

Question

Imagine a seller have 300 apples to sell

• Bidders can offer their budget to buy apples.
• Bidders can buy multiple apples.
• Apple price must be same for everyone.

Bidders can put bids like this:

Karen: I put 500 USD

Jessica: I put 300 USD

Albert: I put 22 USD

What would be best formula to decide apple price to get maximum profit. If there are less bidders than apples to collect all the money we can just sum all bids and divide by apple amount so seller won't leave any money on the table. But when there are 1000 bidders. Seller have to leave some money on the table. So what would be the formula to decide apple price to leave minimum amount money on the table.

Here is a simple bidder generator: https://output.jsbin.com/yekufak

Answer 1

as I understand your algorithm of selling apples looks like this:

budgets are sorted into decreasing order with $b_1$ being highest budget with apple prince $p$ and amount of apples $a$: $$a_1 = max(a, \lfloor b_1/p \rfloor), a_2 = max(a-a_1, \lfloor b_2/p \rfloor),...$$ until seller run out of apples

in this case one of ideas is to search best value with bisection search, but probably you want to monitor if seller will sell all apples

starting from some reasonable lowest possible price like $ 0.01\$$ calculate profit and amount of apples sold, in next step current_price=2*last_price and now calculate profit and amount of apples sold, at some point profit will drop because amount of sold apples will drop sharply and this means that last_price was last maximum and you should look in this area for best price with bisection search but now price interval is bounded, in real life probably monitoring amount of apples sold with given price will bound your price to reasonable level

this idea is very crude and can be improved, with more remarks someone could add more ideas

Answer 2

From what I understand of the setup, you have $N$ people, each bidding on one apple, there are $k$ apples, and you will set the price of one apple to leave with maximum profit. (Note: If they can bid on multiple apples, just duplicate their entries).

First, sort all your bids in decreasing order, call this list $b[n]$. (So $b[1]$ is the largest bid) Then, your best option would be to find

$$\lambda = \text{argmax}_{i \in [k]} i \cdot b[i] $$

and then set the apple price to be $b[\lambda]$. This is essentially a case by case analysis, where you are finding the optimal price for giving away $i$ apples, for which it is easy to see that the optimal price would be what the top $i$ bidders bid$._{ _{\text{Of course, this is all assuming you are maximizing revenue; maybe you have some other loss function (like well-being of the society!)}}}$