Information Technology Reference
In-Depth Information
Complete-Search(
allocation
-
from
-
parent
)
1
global
-
utility ←
0
2
final
-
allocation ←∅
cleared
-
goods ←
b∈allocation
-
from
-
parent
b
g
3
4
valid
-
bid
-
pool ←{b ∈ bid
-
pool
|∀
g∈b
g
b∈ cleared
-
goods }
5
if
child
=
∅
Iamleaf.
6
then
final
-
allocation ← allocation
-
from
-
parent ∪
arg max
b∈valid
-
bid
-
pool
w
(
b
)
7
return
final
-
allocation
8
if
valid
-
bid
-
pool
=
∅
9
then
final
-
allocation ← child .
Complete-Search(
allocation
-
from
-
parent
)
10
else
11
for
bid ∈ valid
-
bid
-
pool
12
do
new
-
allocation ← allocation
-
from
-
parent ∪ bid
13
allocation
-
from
-
successor ← child .
successor(
new
-
allocation
)
14
if
V
(
allocation
-
from
-
successor
)
>V
(
global
-
utility
)
15
then
global
-
utility ← V
(
allocation
-
from
-
successor
)
16
final
-
allocation ← new
-
allocation
17
return
final
-
allocation
Fig. 1.
Complete search algorithm. It is started by calling the root agent with
Complete-Search(
∅
).
-
bid
-
pool
is the list of bids in which it is present,
-
final
-
allocation
is the best allocation encountered thus far in the execution,
-
global
-
utility
is the utility of the final-allocation,
Each agent adds zero-valued singleton bid for itself, even if a singleton bid is
present in the list of bids. This bid enables the agent to search for the allocations
where the agent is not cleared in any bid. The head agent (whose execution is
initiated by the controller
3
) does not have any parent. Similarly the last agent
in the ordering does not have a child agent so it does not send a message to child
or wait for a reply. The agents search all the possible allocations to determine
the optimal winner, see Figure 1.
We can prove the correctness of this algorithm by observing that the algo-
rithm is performing a linear search of all the feasible allocations
4
. The agents
simply implement a depth first search over all possible bid sets except that they
only check feasible bid sets. As such, this algorithm sequentializes the agents'
execution so it has a long running time.
5
Individual Hill-Climbing Algorithm
We now present an algorithm that creates a feasible allocation using a simple
hill-climbing approach. In this approach, the agents simply clear bids in a greedy
3
The controller does not control any agents, it simply initiates the execution of the
head agent.
4
Proofs omitted due to lack of space.
