this is for holding javascript data
Ofra Amir edited sectioniBundle_for_M.tex
over 9 years ago
Commit id: e68455922742d07b4117fbcc0827fc5074ea7afd
deletions | additions
diff --git a/sectioniBundle_for_M.tex b/sectioniBundle_for_M.tex
index e335a7a..dfb890e 100644
--- a/sectioniBundle_for_M.tex
+++ b/sectioniBundle_for_M.tex
...
\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 very complex 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).
Representing all these possible bundles is also infeasible. 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. offer a solution to these problems.
An Iterative CA mechanisms were designed to address the problem of eliciting agents' preferences over bundles. In contrast with sealed-bid auctions, in iterative CA
has agents are not required to report their valuations for all bundles. Instead, the auction consists of multiple rounds,
that gradually
reveal revealing agents'
preferences and the value of valuations for bundles. Agents can adjust their bids over time and are not required to determine their exact valuation for every
bundle. bundle at the onset of the auction. 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 describe an implementation of a particular iterative
CA CA, called
\emph{iBundle}~\cite{parkes1999bundle} \emph{iBundle}~\cite{parkes1999bundle}, to solve the MAPF problem. In addition to providing an iterative mechanism, iBundle is optimal (i.e., maximizes the social welfare) and has desired strategyproofness properties. Each round of iBundle is composed of three stages:
\begin{enumerate}
\item \emph{Bidding}: agents place bids on their desired bundles. Agents are allowed to place $XOR$ bids, meaning that they would like to get any of the bundles they bid on but not more than one of them.
\item \emph{Winner determination}: the auctioneer determines and announces a provisional allocation of bundles to agents. This allocation must be feasible, that is no item is allocated to more than one agent and is chosen to maximize the auctioneer's profit.