Information Technology Reference
In-Depth Information
Cleared(
j
)
1
list
-
of
-
bids ←{b ∈ list
-
of
-
bids | j∈ b}
2
Update-Best-Bid
Ready(
j, bid
)
1
ready
[
j
]
← bid
if
∀
g∈bid
g
ready
[
g
]=
bid
2
then for
g ∈ neighbors
3
4
do
g.
Cleared(
i
)
5
Exit
Cleared my good with
bid
.
Tell-Ask-Value(
j, val
)
1
ask
-
value
[
j
]
← val
2
Update-Best-Bid()
Fig. 3.
Modified MCP message receiving procedures
for a long time by sociologists studying social networks [15], and by economics
studying social networks [16] (note that their networks are different, even if they
refer to them by the same name). We use two approaches for addressing the
issue of revenue division. The first technique is inspired from the well-studied
monotonic-concession protocol [17] and in the second approach we borrow results
from sociological network exchange theory [15].
7.1
Modified Monotonic Concession Protocol
In this section we propose a modified version of the Monotonic Concession Pro-
tocol (MCP). In MCP the two negotiating nodes alternately propose a deal that
allocates the revenue between the agents. A deal
d
consists of the tuple (
p
1
,p
2
)
such that
p
1
+
p
2
=
b
p
,where
p
1
is the amount agent 1 gets and
p
2
is what agent
2 gets. If the receiving node gets an offer where it gets more than or equal to
what it had asked for in the last round the protocol terminates. If the receiving
node does not agree to the offer, in next round it should propose a new deal,
subject to the condition that its payment for the other agent must be strictly
higher than in the previous deal. This protocol will either converge to a solution
or terminate without agreements if time runs out. Unfortunately, MCP can only
be used for bi-party negotiation.
We propose a modified-MCP (mMCP) that can be used for simultaneous
multi-party negotiation for the division of the revenue. In it, each agent maintains
an
ask
-
value
which is initialized to the maximum the agent can expect to get
given the bids it is involved in. The algorithm then proceeds as follows:
1. At each time-step, the agents send their
ask
-
value
to other agents with which
it is involved in negotiation. As in MCP, the agents have to reduce their
ask
-
value
from what they demanded in the previous round.
2. Upon receiving the
ask
-
value
of its neighbors the agent checks if it can still get
its
ask
-
value
for the bids in which it is present, that is,
i∈b
g
ask
-
value
i
≤
b
p
.
