Transcript 1 2 3

Double Auctioning in a P2P environment
(an attempt)
Zoran Despotovic
EPFL-I&C-IIF
Distributed Information Systems Laboratory
{zoran.despotovic}@epfl.ch
©2003, Zoran Despotovic, EPFL-I&C,
Laboratoire de systèmes d'informations répartis
Overview
1.
2.
3.
4.
A Bit of Microeconomics
Single-sided Auctions
Double-sided Auctions
Double Auctioning in P2P?
©2003, Zoran Despotovic, EPFL-I&C,
Laboratoire de systèmes d'informations répartis
1. Microeconomics
• Microeconomics: a set of theories with the aim to
help us gain an understanding of the process by
which scarce resources are allocated among
alternative users, and of the role of prices and
markets in this process
• Scarce resource: the demand at a zero price
exceeds the available supply
©2003, Zoran Despotovic, EPFL-I&C,
Laboratoire de systèmes d'informations répartis
The Market Equilibrium
• The demand and supply curves
• The competitive equilibrium price
Price
Supply
P0
Demand
Q0
Quantity
• The main problem: how to determine the CE price when no
one knows the curves
©2003, Zoran Despotovic, EPFL-I&C,
Laboratoire de systèmes d'informations répartis
A more realistic example
Price
10
8
6
4
2
Quantity
2
4
©2003, Zoran Despotovic, EPFL-I&C,
Laboratoire de systèmes d'informations répartis
6
8
10
2. Single-sided auctions
• One seller and many buyers (or vice versa)
Price
10
8
6
4
2
Quantity
2
4
6
8
10
• What mechanism should the seller choose to get at least
the equilibrium price no matter how the buyers behave?
©2003, Zoran Despotovic, EPFL-I&C,
Laboratoire de systèmes d'informations répartis
Single-sided Auctions - Four Main Types
• English auction (open cry ascending bid)
– Increase the price until only one buyer remains; this
buyer pays the price of his last bid
• Dutch (descending offer)
– Start with a high price and decrease it until a buyer
accepts it;
• Sealed-bid first price
– All buyers submit sealed bids; the buyer with the highest
bid wins the item and pays the price of his bid
• Sealed-bid second price (Vickrey – Nobel Prize)
– All buyers submit sealed bids; the buyer with the highest
bid wins the item and pays the price of the second
highest bid
©2003, Zoran Despotovic, EPFL-I&C,
Laboratoire de systèmes d'informations répartis
The Four Auction Types – Buyers‘ View
• English Auction: bid until your reservation price is reached
• Vickrey Auction: bid your reservation price!
– Incentive compatible
• Sealed-bid first price: bid slightly below your reservation
price
• Dutch Auction: same as the sealed-bid first price auction
• The sellers‘ gain? The same expected value with all four
types – the second highest valuation! (Revenue equivalence
theorem)
©2003, Zoran Despotovic, EPFL-I&C,
Laboratoire de systèmes d'informations répartis
3. Double Auctions
• Sealed-bid Double Auction (Call Market):
– The bidders (both buyers and sellers) submit sealed bids
and offers
– The auctioneer constructs the D-S curves, determines
the price and clears the market
• Truthful bidding is not an equlibrium but all
equilibria are within O(1/M) of the truthful bidding
and the expected inefficiency of any equilibrium is
O(1/M2)
©2003, Zoran Despotovic, EPFL-I&C,
Laboratoire de systèmes d'informations répartis
The Continuous Double Auction
• The rules:
– A number of traders entitled to buy or sell one or more
units of a given commodity
– All the traders are allowed to make verbal „shouts“
(quotes) of a price: „I am selling at $10“, „I am buying
at $6“
– At any time, any buyer (seller) is free to accept a seller‘s
(buyer‘s) offer (bid). When this happens the buyer and
the seller are assumed to enter into a binding contract
• Nice. But, why another Nobel prize (V. Smith)?
©2003, Zoran Despotovic, EPFL-I&C,
Laboratoire de systèmes d'informations répartis
Convergence towards the CE price
©2003, Zoran Despotovic, EPFL-I&C,
Laboratoire de systèmes d'informations répartis
4. Double Auctioning in P2P?
• Call Markets
– Where to keep the bids and how to make them sealed
(auctioneer)
• The CDA:
–
–
–
–
Binding contracts for bid or sell accepts
Everything is publicly observable
No deviations from the rules are possible
The mechanism is not self-enforceable
©2003, Zoran Despotovic, EPFL-I&C,
Laboratoire de systèmes d'informations répartis
The CDA in P2P?
• Peers may be tempted to reply to offers and bids not by
taking (or leaving) the observed prices but by offering new,
better ones. This cannot be observed!
3
1
t=12ms;
receive offer;
send accept
2
t=0; sell offer
t=20ms; receive
accept
t=24ms; receive
accept
©2003, Zoran Despotovic, EPFL-I&C,
Laboratoire de systèmes d'informations répartis
t=10ms;
receive offer;
send accept
Our Idea
• Introduce the possibility for the peers to reply with new
offers explicitly into the mechanism
• Set the price at the middle point between two offers
• Trading prices? Do they converge towards the CE price?
– Good news:
• good convergence in the fully periodic case
• The market can be cleared easily
©2003, Zoran Despotovic, EPFL-I&C,
Laboratoire de systèmes d'informations répartis
Simulations 
• Choose some reasonable bidding strategies and
observe how the system behaves when these
strategies are used by the bidders
–
–
–
–
When to submit a bid and what price to bid
For how long to collect the answers
To which bids to answers and with what price
How to evolve eventual answers with time
• Starting point: Zero Intelligence Plus (ZIP)
traders
©2003, Zoran Despotovic, EPFL-I&C,
Laboratoire de systèmes d'informations répartis
Mathematica – a piece of advice
• Don‘t write a Mathematica simulation quickly! Time needed
for debugging it is inversely proportional to the time you
spend to write it! Especially if you are used to Java or C++.
©2003, Zoran Despotovic, EPFL-I&C,
Laboratoire de systèmes d'informations répartis