J. Service Science & Management, 2009, 2: 92-95
Published Online June 2009 in SciRes (www.SciRP.org/journal/jssm)
An Improved Simultaneous-Revelation
Resolution Procedure that Induces Truthfulness
Linlan Zhang1,*, Chunmei Wu2, Zhongyan Wang2 , Zefang Li3
1Institute of Systems Engineering, Huazhong University of Science and Technology, Wuhan, Hubei, 430074, China; 2Department of
the Basics, Air Force Radar Academy, Wuhan, Hubei, 430019, China; 3Institute of Computer Technology, Wuhan Institute of Tech-
nology, Wuhan, Hubei, 430047, China.
Received February 2nd, 2009; revised May 25th, 2009; accepted April 20th, 2009.
ABSTRACT
Alternating-offer bargaining protocol is the most predominant way for solving bilateral bargaining problem in daily life.
However, alternating-offer consumed more time and caused a lower efficiency in some cases. One proposed solution is
called simultaneous-revelation resolution by which both parties reveal their reservation prices at the same time. But
most simultaneous-revelation resolution procedures are inefficient because they encourage exaggerations. But it is fast
and uncomplicated, this resolution procedure still has merit
— especially if the parties can refrain from undue exaggera-
tion. The paper designs a truthful mechanism for simultaneous-offer bargaining negotiation. In this mechanism, a rule
manipulator can induce buyer and seller both to reveal their real prices by introducing suitable adjustment functions.
And we show the honest revelations are in Nash equilibrium.
Keywords: mechanism design, simultaneous-offer, bargaining, truthfulness, nash equilibrium
1. Introduction
Agent mediated negotiation has received considerable
attention in the field of electronic commerce [1,2]. The
simplest form of negotiation involves two agents and a
single-issue. Negotiation is a process that allows disput-
ing agents to decide how to divide the gains from coop-
eration [3,4]. The face-to-face, open-ended bargaining is
the most commonly used way for solving the problems.
Bargaining is normally studied using either the axiomatic
approach introduced by Nash [5], or the strategic ap-
proach, for which Rubinstein’s [6] alternating offer
model is probably the most influential [7]. However,
alternating-offer consumed more time and caused a
lower efficiency in some cases. Informal bargaining,
without any imposed structure for negotiations and
without tight time constrains, leads to more efficient
outcomes than do most formal methods. One proposed
structured alternative to informal bargaining is the pro-
cedure by which both parties reveal their reservation
prices at the same time. If the buyer's bid is at least as
large as the seller’s ask, then the item is sold at a price
between the two offers and the agreement will be settled.
The conflicts between parties are resolved and the par-
ties’ payoffs both are better off [8]. If the offers do not
overlap, then no trade takes place and the negotiations
are broken off.
This mechanism was first modeled by Chatterjee
Samuelson [9], and then studied in more details by
Myerson and Satterthwaite [10], Leininger et al. [11].
This alternative, though appealing, does not work very
well [12]. According to a commonly proposed symmetric
resolution procedure, the parties simultaneously submit
their reservation prices to the mediator. Let these dis-
closed values be
&
s

(not necessarily the true reservation
price
s
) for the seller, and (not necessarily the true
reservation price ) for the buyer. If , then the
negotiation is broken off ; If
b
bbs 

s
b, the final contract
will be



*/2xbs, the midpoint between b

and
s

(see Figure 1).
When this simultaneous-revelation resolution proce-
dure was tried, most parties gave truthful revelations:
s

equaled
s
, and b

equaled [12]. However, in some
cases
b
s

was greater than
s
(because the seller want the
midpoint drift right), and less than ( because the
buyer want the midpoint drift left); indeed, in some of
bb
*Corres
p
ondin
g
autho
r
, Tel.: [phone], Fax: [phone].

LINLAN ZHANG, CHUNMEI WU, ZHONGYAN WANG, ZEFANG LI 93
Figure 1. The simultaneous revelation produce
Figure 2. Case in which there is a Zone of Agreement in real but not in revealed values
these cases, there was in fact a zone of agreement (
s
was less than ) but the parties did not detect it (
b
s

was greater than ) and an inefficiency resulted. If both
parties exaggerate a lot, then the chances for an agree-
ment are very poor (see Figure 2).
b
Thus, the simultaneous-revelation resolution proce-
dure is inefficient because it encourages exaggerations;
but it’s fast and uncomplicated. If time is at a premium
or if one is engaged in many such bargaining problems,
then this resolution procedure still has merit –especially
if the parties can refrain from undue exaggeration. Per-
haps the most interesting questions are those that game
theoretic ones. Possibly the most central problem of this
form is the difficulty of getting efficient truthful mecha-
nisms. The basic game-theoretic requirement in mecha-
nism design is that of “truthfulness” (incentive compati-
bility), i.e. that each participating agent is motivated to
cooperate with the protocol and to report his true valua-
tion [13].
This paper gives an improved simultaneous-revelation
resolution procedure that can engender truthfulness. In
this mechanism, rule manipulator can induce buyer and
seller both reveal their real prices with suitable adjust-
ment functions. And we show honest revelations are in
Nash equilibrium [14].
The rest of this paper is structured as follows. In Sec-
tion 2 we formally present our model and notations. In
Section 3 we show three propositions about honestly
revelation. Section 4 concludes.
2. Negotiation Model and Discussions
We formally present our model: the mechanism under
consideration, its basic components and the assumptions
on the parties.
2.1 Bargaining Rules
Suppose that there is a seller S, a buyer B, and a rules
manipulator M. Before bargaining starts, S and B must
submit their reservation prices and the sincerity prices
(price constraints that a trader considers the opponent’s
offer have to satisfy) to M. These valuations are their
private information. Let 1
s
and denote the reserva-
tion price and the sincerity price of S respectively; Let
and
1
b
2
b2
s
denote the reservation price and the sincerity
price of B respectively. They must satisfy the relation
11 2
bs s
2
b

. Let and denote the offer of S and B
respectively. M stipulates:
sb
s
and must satisfy b
12
bbb

 and 12
s
ss

; otherwise considers they
does not have the sincerity and does not permit the
transaction. If
s
b

, then the final contract will be the
midpoint . In addition, both the parties
may obtain an adjusted amount that the opponent will
*()/s 2xb

LINLAN ZHANG, CHUNMEI WU, ZHONGYAN WANG, ZEFANG LI 94
pay them that depends on the price they announce. If
, they can’t get anything from disagreement.
bs
2.2 Assumptions
It’s important to keep in mind that the parties must agree
to the payoff procedure before they begin to bargain. The
adjusted amount is extracted according to following ad-
justed function respectively. We express the adjusted
function of S and B with ()
f
s and ()
g
b respectively
as follows:



 




 

221
21 1
121
21 2
2,
2
2,
2
bbbsbbss ss
fs
bs ss
1
2
s
sbsbbss bb
gb
bs bb





 




Notice that the number s is bigger, the function
value of ()
f
s is smaller, namely the higher s the
lower the adjusted payment S will receive from B. Simi-
larly, the number b is smaller, the function value of
()
g
b is smaller, namely the lower the lower the ad-
justed payment B will receive from S. Hence, there is
less incentive for S to exaggerate and for B to lessen with
the adjustment. We will prove the adjusted functions can
induce S and B to make honest revelations:
b
1
s
s,2 bb

,
and honest revelations are in Nash equilibrium. All this
assumes that they are trying to maximize their utility and
they both are risk neutral.
2.3 Main Results
According to the rule, we know that the utility function
of seller S and buyer B respectively is:
  
  
1
2
2
2.
S
B
Ubs sfsgb
Ubbs gbfs
 
 
，
We could obtain the following proposition.
Proposition 1. No matter the buyer whether to offer
honestly, 1
s
s is optimal for the seller.
Proof. Considering the following two cases:
1) : in this case, if
2
bb1
s
s

, we have
 
11121 2
221 2Ubs sbsbbs 
S.
If 1
s
s, we have
  
 
21 12
1121
22
.
1
bssbsss bsbbss
bsss bsbbss
  
 
S
U
From the relation 12
s
sbb , we have






121
0ss bsbbss

.
Then we have

21 2
2
S
Ubsbb s
1

 , i.e.,
2S
UU
1S

. Therefore, against the optimum re-
sponse of seller S is
2
bb
1
s
s

.
2) 2 bb

: in this case, if 1
s
s,we have




1211 21
22
S
Ubs sbs  .
If 1
s
s

, we have




22121 1
22
S
Ubssbsss 2 .
According to the relation 2
s
b, we have

12ss




21
2bs, i.e., 21S
U
S
U. Therefore, against 2 bb

the optimum response of seller S is 1
s
s.
Thus, no matter buyer B whether to offer honestly,
1
s
s

is optimal for seller S.
Proposition 2. No matter the seller whether to offer
honestly, 2
bb

is optimal for the buyer.
Proof. Considering the following two cases:
1) 1
s
s

: in this case, if , we have
2
bb





12 221
21
22
2.
B
Ubbs bs
bss
 

If 2 bb

, we have


2
22
21
2
2
21
22
.
B
bbbs
bs bs
Ub bbss
bbbs
bsbbss





 
According to the relation 12
s
sbb , we have






221
0.bbbsbbss

Then we have

22 21
2
B
Ubsbss, i.e.,
21
B
B
UU

. Thus against 1
s
s the optimum response
of buyer B is 2 bb

.
Figure 3. The strategic form game of the buyer and the
seller

LINLAN ZHANG, CHUNMEI WU, ZHONGYAN WANG, ZEFANG LI 95
2) : in this case, if
1
ss2 bb

, there is

1221 21
22
B
Ubbsbs .
If , there is
2
bb
 221 212
22
B
Ubbsbsbb 2.
According to the relation 1
s
b, we have the relation

22
22bb bs
1
, i.e., 21
B
B
UU. Therefore,
against the optimum response of buyer B is
.
1
ss
2
bb
Thus, no matter seller S whether to offer honestly,
is optimal for buyer B.
2
bb
Let and denote two strategies of S:
Let and denote two
strategies of B: This strategic
form game is available from Figure 3. According to the
following four inequalities:
1
S
11
:,s
2
S
2
:s1
122
:b b
.
2
.
Ss Ss
Bb
1
B
:,B
2
B
b
21 2
21 21
,,,
SS BB
SS BB
UUUUUUU U
1
,
We could obtain the following proposition.
Proposition 3. Strategy combination forms a
Nash equilibrium, and in this case,
22
(, )SB
SB
UU


, the net side payment of the seller and the
buyer both are zero, i.e.,

21
/2bs
() ()fs gb0

.
Proof. The first half part is obvious, we prove the
second half. Whenand , we have
. Then we have
1
ss
)/2
2
bb
21
()()(fsgbbs () ()
f
sgb

, and 0
 


   
12
2
2
1
21
2
22.
S
B
Ubssfsgbbs
Ubbsgbfsbs
 
 
,
[11
i.e., . The proof is completed.

21
/2
SB
UU bs
3. Conclusions
In this study, our results have important constructions for
procedure design of a simultaneous-offer bargaining
system that can engender truthfulness. But in order to
implement this scheme, the seller and the buyer have to
approve of the rules manipulator before they start the
agreement. It is rather restrictive, but the result is so ap-
pealing that it should not be lightly dismissed. With
suitable adjustment functions, honest revelations are in
Nash equilibrium: each party should tell the truth if the
other does. It would be wonderful if someone could ap-
ply this scheme to real-world situations. This is also the
direction we will study diligently in the future.
REFERENCES
[1] R. P. Maes and A. G. Moukas, “Agents that buy and
sell,” Communications of the ACM, Vol. 42, No. 3, pp.
81–91, 1991.
[2] T. Sandholm, “Agents in electronic commerce: Compo-
nent technologies for automated negotiation and coalition
formation,” Autonomous Agents and Multi-Agent Sys-
tems, Vol. 3, No. 1, pp. 73–96, 2000.
[3] J. S. Rosenschein and G. Zlotkin, “Rules of encounter,”
The MIT Press, 1994.
[4] S. Kraus, “Strategic negotiation in multi-agent environ-
ments,” Cambridge: The MIT Press, Massachusetts, 2001.
[5] J. Nash, “The bargaining problem,” Econometrica, No.
18, pp. 155–162, 1950.
[6] A. Rubinstein, “Perfect equilibrium in a bargaining
model,” Econometrica, No. 50, pp. 97–110, 1982.
[7] G. J. Grenier, et al., “Sociological theory,” B. SYA6126,
Spring 2007.
[8] Y. J. Hu, “Trusted agent-mediated E-commerce transac-
tion services via digital certificate management,” Elec-
tronic Commerce Research, Vol. 3, pp. 221–243, 2003.
[9] K. Chatterjee and W. Samuelson, “Bargaining under in-
complete information,” Operations Research, No. 31, pp.
835–851, 1983.
[10] R. B. Myerson and M. A. Satterthwaite, “Efficient mecha-
nisms for bilateral trading,” Journal of Economic Theory,
No. 29, pp. 265–281, 1983.
] W. Leininger, P. B. Linhart, and R. Radner, “Equilibria
of the sealed-bid mechanism for bargaining with incom-
plete information,” Journal of Economic Theory, Vol. 48,
pp. 63–106, 1989.
[12] H. Raiffa, “The art and science of negotiation,” Cam-
bridge: Harvard University Press, MA, 1982.
[13] A. Mu’alem and N. Nisan, “Truthful approximation
mechanisms for restricted combinatorial auctions,”
Games and Economic Behavior, Doi: 10.1016/j.geb.2007.
12.009, 2008.
[14] Y. F. Luo, “Game theory course,” Peking: Tsinghua
University Press, Peking Jiaotong University Press, 2007.