Algorithms for Distributed Winner Determination in Combinatorial Auctions - Agent-Mediated Electronic Commerce - page 47

Cleared( sender )
1 list - of - bids ←{b ∈ list - of - bids | sender ∈ b g }

2 if list - of - bids = ∅

3 then Exit We are done. I did not sell my good.

4 Send-Accept()

Accept( sender , bid )
1 accepted [ bid ] ← accepted [ bid ] ∪ sender

if accepted [ best - bid ]= best - bid g

2 Everyone has accepted it.

3 then for agent ∈ neighbors

4 do agent . Cleared( g i )

5 Exit We are done. I sold my good.

Send-Accept()
1

if best - bid ∈ list - of - bids

2 then best - bid ← arg max b∈list - of - bids w ( b )

accepted [ best - bid ]= accepted [ best - bid ] ∪ g i

3

for agent ∈ best - bid g 4

do agent . Accept( g i , best - bid )

5

Hill-Climbing()
1

list - of - bids ← g i

← b∈g i b g 2 neighbors

3 best - bid ←∅

4 Send-Accept()

Fig. 2. Hill-Climbing algorithm. It is started by having all agents execute Hill-

Climbing.

fashion ordered by w ( b ), the average value per good until there are no more bids
that can be cleared. In fact, this algorithm is but a variation of the algorithm
given in [14] for coalition formation.
The algorithm proceeds as follows: Each agent finds the bid in its list - of - bids
which has the highest average value. The agent then sends an Accept message
to the goods that are present in this bid. The agent clears this bid only when
it receives an Accept message from all the goods in this bid. This ensures
that a bid is cleared if and only if all the goods in the bid agree to clear it.
When an agent clears a bid, it sends a Cleared to all its neighbors—the set
of agents with which it shares some bid—telling them that it has cleared and
all bids including the agent should be dropped from consideration. The agents
that receive a Cleared message from agent sender delete the bids sender b .
The agents stop execution when they clear a bid or the list - of - bids is empty. See
Figure 2 for the complete algorithm.
It is easy to show that this algorithm always finds a feasible allocation and
never enters a deadlock as it only considers feasible solutions. However, the