Price updating in iBundle works as follows: initial prices for all bundles are \(0\). At the end of each round, the prices of bundles that “unhappy” agents bid on are raised. Specifically, the price is raised to the maximal amount bid on the bundle by an agent plus \(epsilon\), where \(epsilon\) is a parameter of the auction. The MDDs compactly represent all the paths (bundles) agents bid on. Thus, the price of the entire MDD can be increased directly rather than considering each path separately.
For example, recall that at the end of the first iteration of an auction for the problem from Figure \ref{fig:mapf}(a), the provisional allocation includes two agents. Let us assume that paths for \(a_1\) and \(a_3\) were arbitrarily chosen to be included in the provisional allocation. Then, the price for the paths \(a_2\) bid on, namely \(MDD^3_2\), is raised by \(\epsilon\).
The choice of \(\epsilon\) affects the efficiency and optimality of the auction. Generally, as \(\epsilon\) approaches \(0\) the iBundle auction is known to terminate with the optimal allocation when agents use the best response bidding strategy. However, using smaller values of \(\epsilon\) leads to more iterations of the auction and thus sometimes a larger value is preferred to speed-up the auction (giving up optimality).
Interestingly, due to the particular valuation function in MAPF, while increasing \(\epsilon\) leads to fewer iterations, each iteration requires more computation in the winner determination stage. This is because when we increase the price of an MDD by a greater amount, agents will bid on additional MDDs (assuming agents have unlimited budgets). For example, consider increasing the price of paths with travel cost 4 from 0 to 5. Now, the agent should bid on all paths that are within \(\epsilon\) of its best price. It will thus submit more bids (i.e., MDDs with \(c=5,6,7\) and \(8\)). This requires more computation at each iteration and therefore does not reduce complexity. Setting \(\epsilon=1\) is the smallest increment that would cause agents to submit bids on new MDDs. Choosing lower value will only make the auction slower, but will not lead to a different result.