Explanation on the auction algorithm

Question

I am currently studying the auction algorithm developed by Bertsekas and other people.

Indeed, auction algorithms can be used to solve the optimal assignment problem.

Say you have $n$ agents and $n$ objects, one agent $i$ has a benefit $\beta_{ij}$ to get object $j$. In short, the auction algorithm maximizes \begin{equation} \sum_{ij}\beta_{ij}x_{ij} \end{equation} where $x_{ij}=1$ if object $j$ is assigned to agent $i$, $0$ otherwise. The strong dual theorem is the bridge between this maximization problem, which can be solved by other algorithms such as the hungarian one, and the auction process. The dual problem makes appear some lagrangian multipliers for agents and objects : those for agents are called marginal profit ($\pi_i$) and those for the objects are the prices ($p_j$).

To fix ideas, let's consider the simplest case where any object can be assigned only once and any agent can assign only one object. Here are roughly the main steps of the algorithm :

1. Bidding phase

   Loop over all unassigned agents $i$ :

   • compute the marginal profit for all objects $\pi_i^j = \beta_{ij} - p_j$
   • choose the object $j_i$ which maximizes the marginal profit when positive
   • compute the bid $b_i$ for that object :

   \begin{equation} b_i = \pi_i^{j_i} - \max_{j\ne j_i}\{\pi_i^j\} + \varepsilon \end{equation}

2. Assignment phase

   Loop on bidded objects, assign them to best bidders

3. Return to step 1 until there are no more unassigned agents

I apologize in advance for this poor algorithm representation, searching "bertsekas + auction + algorithms" on internet will lead you to more comprehensive descriptions.

My question is about the bid computation. I understand that if an agent has an interest in several objects for which the marginal profits are close, it will put a small bid because he knows that if he loses, he still have other objects with close marginal profits.

However, I wonder how this formula can be explained from a mathematical point of view. Where does it come from ? Why this formula and not another ? It is never explained in the associated litterature.

I think it is linked with game theory in which many auction schemes are explicited, among them the second price Vickrey auction, and that this bid formula is what ensures the algorithm to reach the maximm. But I am not sure.

Having failed to find an explanation in the litterature as well on internet, I come to you in the hope that it is something evident for any game theory specialist.

Thanks in advance for your attention

Regards