Ofra Amir edited sectioniBundle_for_M.tex  over 9 years ago

Commit id: 604d26cfc8762d2fb11ad85d7c5c676858c2ed20

deletions | additions      

       

\item Potentially large bundle sizes: agents might bid on a large set of items if their path to the goal is long.  \end{itemize}  Given the large number of bundles, requesting agents to place bids on all bundles they could potentially be interested in -- as done in sealed-bid auctions such as VCG -- will require infeasible computation from both the agents (which need to compute all possible paths and evaluate them) and the auctioneer (which needs to compute the optimal allocation). Iterative combinatorial auctions aim at addressing the problem of eliciting agents' preferences over bundles more efficiently and avoid the complex computation required by agents in sealed-bid auctions.   An iterative CA has multiple rounds, that gradually reveal agents' preferences and the value of bundles. Agents can adjust their bids over time and are not required to determine their exact valuation for every bundle. Prices are increased in every round according to the demand for items and agents can decide whether to keep bidding on bundles as their prices increase. For example, in an MAPF problem agents might start by bidding on their shortest paths, and then bid on longer paths if the prices of the shortest paths becomes too high. With this mechanism agents do not have to compute all of their possible paths ahead of time and only perform this computation when they are required to. We now describe how to implement a particular