Ofra Amir edited subsectionBidding_Al.tex  over 9 years ago

Commit id: e155206d1b8d4adec7d1c780ba7ffcc87336d1b1

deletions | additions      

       

A reasonable strategy for the agents is the \emph{myopic best response} strategy~\cite{parkes1999bundle}.According to this strategy, agents bid on their best bundles at each iteration given the current prices and always place bids with the current price (i.e., they are not considering raising the price before it has been raised by the auctioneer). It has been shown that myopic best response is the best strategy for an agent given that other agents are acting based on this strategy~\cite{parkes2001iterative}. In MAPF, an agent's best response is to bid on all paths that minimize $c+p$ at their current ask price ($p$).  For example, in the first iteration of an auction for the problem shown in Figure~\ref{fig:mapf}(a), $a_1$'s best response bid in the first round is to bid on its shortest path, $[\langle A,t_1\rangle,\langle C,t_2\rangle]$. $a_2$ $a_2$'s  best response is to place a $XOR$ bid on its three shortest paths:$[\langle B,t_1\rangle,\langle A,t_2,\langle C,t_3,\langle E,t_4\rangle]$; $[\langle B,t_1\rangle,\langle D,t_2,\langle C,t_3,\langle E,t_4\rangle]$; $[\langle B,t_1\rangle,\langle D,t_2,\langle G,t_3,\langle E,t_4\rangle]$. Similarly, $a_3$ $a_3$'s  best response is to bid on all of its shortest paths (paths with $c=4$). Note that if agents bid on paths that end at an earlier time than some of the other agents' paths, we extend their paths by adding their last location to the next time steps. As prices increase, agents begin to consider longer paths. Specifically, their best response should include all paths that reach the goal with a minimum value of $c+p$. For example, given that all paths with $c=3$ that $a_2$ can traverse to reach its goal are priced at 1 ($p=1$) and paths with $c=4$ are priced at 0, $a_2$ will bid on all paths with $c=3$ at price 1 and all paths with $c=4$ at price 0, as they have the same total cost ($c+p=4$).