Matching algorithm of the auctions on Ebay

t to be 
traded. Therefore, it is necessary to develop 
a new matching mechanism to solve the 
online auction problem. 
Definition: Matching with a given 
object for sale
The matching process with a given 
object for sale is to determine a set of 
outcomes. An outcome is a result of 
the matching process whenever a bid is 
placed for a given object for sale during 
the fixed ending time. A set of outcomes 
accumulates all outcomes during the 
interval time of the auction.
Let Oj(gi, Si, Bi, pi
j) is denoted an 
outcome of matching algorithm for given 
good i from seller i and a buyer who submit 
pi
j at the time j. (j },...,1{ k∈ ). Therefore, a 
set of outcomes is a finite lattice subjected 
to pi
j.
From our notation, a set of outcomes 
includes k elements and the final outcome 
is Ok (gi, Si, Bi, Pi
k). The final outcome is 
playing a very important role in determining 
whether the auction is successful or not. If 
Pi
k is at least equal to rsi, then the auction 
is successful vice versa. 
The final outcome is a stable outcome 
and a Pareto optimal in this market if Pi
k is at 
least equal to rsi, i.e, outcomes are satisfied 
by the substitute condition because a seller 
prefers the latest outcome to any other 
outcomes. She has preferences over the set 
of outcomes as follows.
Ok Ok-1O1
Two outcomes can have the same seller-
buyer pair since they are two different bid 
prices thus two outcomes are independent 
of each other and a set of outcomes is 
independent and strictly increases.
42 Ho Chi Minh City Open University Journal of science- No. 1(1) 2011
The seller’s expected profit increases 
with the number of outcomes. Because, a 
set of outcomes is finite lattice, the more 
increase in outcomes, the larger gap between 
Pi
k and rsi is. Here, the value of Pi
k cannot 
exceed the buyer’s reserve price.
Each buyer’s choices are independent 
from those of other buyers but his behavior 
does affect his competitors. A buyer who 
increases the current winning bid causes 
either to increase competitors’ bids or else 
withdraw from the auction. In other words, 
a bidder will continue the auction if her/his 
reserve price is still above the current price, 
otherwise she/he has to withdraw.
The outcomes in our model are similar 
to the contracts of Hatfield and Milgrom’s 
model (2005). They are also satisfied by 
two main conditions, substitute and law of 
aggregate demand conditions. In particular, 
in our model the lower seller’s reserve 
price, the more number of outcomes is (law 
of aggregate demand condition satisfied) 
and a seller most prefers the final outcome 
to any other ones (substitute condition 
satisfied). However, the outcomes in our 
model also have some particular things. 
First, if Pi
k is at least equal to rsi, there exists 
only one stable outcome at the termination 
time (the final outcome). Meanwhile there 
may have more than one stable contract and 
the time element is not an important one in 
Milgrom’s model. Second, in the generally 
matching algorithm, based on both agents’ 
preferences, both agents such as doctors 
and hospitals, man and woman or workers 
and firms are matched to form each pair, 
but in our model based on a given good for 
sale, the matching process is to determine 
a set of outcomes with all feasible seller-
buyer pairs, and then the final outcome with 
a seller-buyer pair to sign the contract if a 
seller’s reserve price is met. Finally, each 
seller can offers more than one object for 
sale and each buyer can also bid many 
objects at the same time under the condition 
in which all objects for sale are independent 
of each other and satisfy our assumption.
eBay is playing important role as a 
central intermediary in matching to create a 
set of outcomes. On eBay auction, a buyer is 
a person who could belong to history set (H) 
or completely different from H at the time 
(t) and she/he and a seller Si are matched to 
create an outcome. A matching is a rule that 
specifies all such possible outcomes linked 
into a set. At the deadline time, all bidders 
participating in the auction are already 
included the set of outcomes, therefore the 
final outcome of the online auction is an 
endogenous matching in which the auction 
contract is accomplished by a seller-buyer 
pair if the seller’s reserve price is met. 
Similarly to other markets, the 
online auction market has also some main 
characteristics as follows. First, if the 
auction is successful then there is only one 
equilibrium price satisfy Pareto efficiency, 
i.e., any contract with lower price than pi
k 
makes at least one buyer better off, but 
making at least one seller worse off. Second, 
there is always a subset of the buyers who 
lose in the auction. The more bidders 
participating in the auction is the larger size 
of the unmatched subset. However, this 
market has some particular situations making 
it be different from the other markets.
First, one of the most important 
factors making matching results on eBay be 
much more different from the other markets 
is that the game can only stop at the fixed 
end time (k) of auction. Therefore, during 
the interval time [1, k], a new bid price will 
completely depend on the current bid price. 
i.e, every bidder offers the price totally 
based on her/his previous competitors. In 
other words, the game can not finish at the 
time t, even though an outcome includes 
a seller and a buyer who are able to be 
matched to form a pair and the potential 
contract may be signed. Meanwhile, in the 
other matching algorithm such as men and 
women in the marriage market, workers and 
employers in the labor market or students 
and college in the admission market, if one 
of the agents rejects the match, the other 
43Ho Chi Minh City Open University Journal of science- No. 1(1) 2011
agent is indifferent between accepting and 
rejecting. Furthermore, if both players are 
matched and got the optimal choice, then the 
contracts will be signed between the couple, 
no one wants to change their partner and the 
matching process is finished. In other words, 
the game will immediately end when two 
agents are matched to form a pair. 
Second, the final outcome plays an 
important role in determining the winner 
of the auction. This property is completely 
different from the other markets. For 
instance, in the financial market, an outcome 
is stable if there is no intermediary-firm pair 
that would be strictly better off than the 
initial outcome (Dam and Perez-Castrillo, 
2006). Obviously, the initial outcome plays 
a significant role in the financial market. 
Moreover, this property contrasts totally in 
many normal markets in which the expression 
“First Come First Serve” is used as a service 
policy whereby the requests of customers 
are attended to in the order at they arrived, 
without other preferences (Roth, Alvin and 
Marilda Sotomayor, 1990). The policy can 
be employed when processing sales orders 
or in determining restaurant seating, for 
examples. This natural difference would be 
expressed under the phrase “Last Come First 
Serve” used for the online auction on eBay. 
The final outcome has impacted on bidders’ 
strategy. In particular, bidders are intensive 
to bid late. As a result, many bidders could 
be lost a chance to place their true price due 
to the expiration time.
Third, given an object for sale, the 
matching process is performed totally 
independent among individual agents. In 
other words, matchmaker performs the 
matching algorithm for each good with 
bidders attending the auction of that good 
independently even though a seller can offer 
many goods for auctioning and a bidder 
can also participate in many auctions. This 
matching mechanism is simpler than that of 
other markets. The sellers and buyers do not 
need to meet each other during the auction 
and when the final outcome determines the 
winner to form a pair and the contract will be 
signed. The final bid price pi
k and the private 
reserve price ri are the most important factors 
for the successful auction on eBay.
Now we consider whether each agent 
can get benefit to state his or her true 
preferences to the matchmaker or not. In the 
marriage market, they have proved that, at 
least sometime, “honesty” may not be the 
best policy (Roth and Sotomayor, 1990). 
In the online auction, both agents can also 
misrepresent his or her preferences to the 
matchmaker because a seller can change 
the reserve price and a bidder can also place 
other bid prices during the interval time. In 
reality, a buyer always wants to place the 
bid prices as low as possible but a seller 
wants to sell the goods with a price as high 
as possible. Hence, a bidder often keeps 
his true price until the last minute to avoid 
bidding overvalued price, otherwise, a 
seller sometimes sets the high reserve price 
to extract consumer surplus as much as 
possible. However, sellers’ strategy should 
be changed as soon as possible, if no bid 
price is placed higher the reserve price for a 
while. In this case, a seller has to adjust the 
private reserve price equal to her marginal 
cost. Therefore, at the beginning time of 
auction, the misrepresentative strategies 
are seemed to be better off for both agents. 
However, in the nearly end time of auction, 
both agents should represent the true price 
to make sure the items to be traded at the 
fixed deadline because no one can change 
the price pi
k and ri at the time k. If one of 
them misrepresents his or her offering price 
then he or she might not have a chance to 
represent her true price at the last minute, 
even though her true price is higher than pi
k. 
As a result, she will not be the winner in the 
auction. Hence, the fixed deadline property 
has played an important role in determining 
when they need to summit the true price to 
make sure a successful auction. Moreover, 
placing true price will help the bidder 
44 Ho Chi Minh City Open University Journal of science- No. 1(1) 2011
saving more time during participating in the 
auction if he actually likes that good.
Social Welfare
Intuitively, a seller always wants 
to extract as much as possible a buyer’s 
surplus. In contrast, a buyer always wants 
to pay as low as possible. In the online 
auction, each buyer’s surplus from the 
successful auction is r
bi
 – pi
k and each 
seller’s surplus pi
k - rsi therefore, social 
welfare for this market is equal to
∑
=
n
i 1
(r
bi
 – pi
k) + ∑
=
n
i 1
(pi
k - rsi) = ∑
=
n
i 1
(r
bi
 - rsi)
v. model with the Job market
Our model may explore in the job 
market when employers and employees 
throughout a broker company or a head 
hunter company to recruit or look for a job. 
The head hunter company plays a role as a 
matchmaker. Given available positions from 
the employers, the matchmaker matches 
each employee who applies for such an 
available position with each employer. 
The outcome of the matching algorithm 
includes an available position, an employer, 
an employee and an application profile. 
Like the online auction, the matchmaker 
also informs the termination time to 
receive application form. However, the 
final outcome is not so important element 
like in the online auction because the first 
comers may fill up all available positions. 
Furthermore, a set of outcomes in this 
market does not necessary to be a finite 
lattice and there may exist more than one 
stable outcome, any outcome can lead to the 
successful employment contract. To sum up, 
our model can flexible to solve a particular 
market if our assumption is satisfied.
vI. Conclusion
This paper introduces a simple model 
of matching with a given object for sale 
in eBay auction market to create a set of 
outcomes in which the final outcome is 
playing an important role in determining 
the successful auction. The fixed deadline 
is a significant element in planning agents’ 
strategies and performing the matching 
process. In other words, both agents induce 
their own polices to determine the suitable 
time when they can misrepresent the 
preferences and when they should offers the 
true prices. The final outcome in this market 
contrasts with many normal markets that can 
be summarized in a phrase “LAST COME 
FIRST SERVE” instead of “FIRST COME 
FIRST SERVE”. The model may extend the 
job market when employers and employees 
throughout the head hunter companies to 
recruit and look for a job. Finally, this model 
should be developed to explore the general 
case in which there exist at least two objects 
for sale dependent of each other.
vII. References
Abdulkadiroglu, Atila and Tayfun Sönmez. 
(2003). School Choice: A Mechanism 
Design Approach. The American 
Economic Review , 729-747.
Anderson, T. Steven, Daniel Friedman, 
Garrett Milam, and Nirvikar Singh. 
(2007). Seller Strategies on eBay: Does 
size matter? International Journal of 
Electronic Business , 643-669.
Dam, Kaniska and David Perez-Castrillo. 
(2006). The Principal-Agent Matching 
Market. The Berkeley Electronic 
Journal of Theoretical Economics .
Gale, David and Lloyd Shapley. (1962). 
College Admissions and the Stability 
of Marriage. American Mathematical 
Monthly , 9-15.
Hatfield, W. John and Paul R. Milgrom. 
(2005). Matching with Contracts. 
The American Economic Review , 
913-935.
Hof, R. (2003). The Ebay economy. 
Businessweek (August 25) , 125-128.
Lucking-Reily, David, Doug Bryan, Naghi 
Prasad, and Daniel Reeves. (2007). 
45Ho Chi Minh City Open University Journal of science- No. 1(1) 2011
Pennies from Ebay: the Determinants 
of Price in Online Auctions. The 
Journal of Industrial Economics , 
223-233.
Milgrom, R. Paul and Robbert J. Webber. 
(1982). A Theoary of Auctions and 
Competitive Bidding. Econometrica , 
1089-1122.
Resnick, Paul and Richard Zeckhauser. 
(2002). Trust among strangers in 
internet transactions: Empirical 
analysis of eBay’ s reputation system. 
Advances in Applied Microeconomics 
, 127-157.
Riley, G. John and William F. Samuelson. 
(1981). Optimal Auctions. The 
American Economic Review , 381-392.
Roth, Alvin and Marilda Sotomayor. (1990). 
Two-Sided Matching: A Study in Game-
Theoretic Modeling and Analysis. 
Cambridge University Press.
Roth, E. Alvin and Elliott Paranson. (1999). 
The Redesign of the Matching Market 
for American Physicians: Some 
Engineering Aspects of Economic 
Design. The American Economic 
Review , 748-780.
Song, U. (2004). Nonparametric Estimation 
of an eBay Auction Model with 
an Unknown Number of Bidders. 
University of British Columbia.
46 Ho Chi Minh City Open University Journal of science- No. 1(1) 2011