this is for holding javascript data
guni edited Theorem_maximum_soci.tex
over 9 years ago
Commit id: 153a5c6e167e747f94ad996299c714e6971a0a40
deletions | additions
diff --git a/Theorem_maximum_soci.tex b/Theorem_maximum_soci.tex
index 05f907c..83f55d1 100644
--- a/Theorem_maximum_soci.tex
+++ b/Theorem_maximum_soci.tex
...
\subsection{Optimal MAPF}
[[TODO: Define social welfare and best response]]
A line of previous work was devoted to the optimal variant of MAPF. In the optimal variant a solution which minimizes the summation of single agent paths is required.
Optimizing In CA optimizing the summed utility over all agents is known as maximum social welfare. Many CA solvers guarntee maximum social welfare as long as agents use the myopic best response bidding strategy (Parkes 1999). According to this strategy, agents allways bid on the best bundle (according to thier evaluation) given the current prices.
This is a reasonable strategy for agents, and it has been
shown that A myopic best response
MAPF agent will aspire to minimize its own path cost.
The utility of agiven path $p$, for a given agent is
$-c$ where $c=cost(p)$.
Since the
best strategy for maximal price an agent
given that other agents are acting based is willing to pay on
this strategy
(Parkes 2001). a bundle (path) can not be negative, we suggest setting $price(p)=max_{p' \in P}[cost(p')]-cost(p)$ where $P$ is the set of all possibale paths in the optimal solution and $p' \in P$ is the path with the maximal cost.
-this is guaranteed when each agent gives its best response
-setting the cost for each bundle