Transcript No Slide Title - BNRG - University of California, Berkeley

Berkeley-Helsinki Short Course
Lecture #8a: Auction Design
and Implementations for
Network Resource Allocation
Weidong Cui and Randy H. Katz
Electrical Engineering and Computer Science Department
University of California, Berkeley
Berkeley, CA 94720-1776
1
Outline
•
•
•
•
Motivation
Auction Design
Auction Implementations
Auction-based Applications for Resource
Allocation
• Bandwidth Trading
• Open Issues in Electronic Auctions for
Network Resource Allocation
2
Outline
•
•
•
•
Motivation
Auction Design
Auction Implementations
Auction-based Applications for Resource
Allocation
• Bandwidth Trading
• Open Issues in Electronic Auctions for
Network Resource Allocation
3
Motivation
• Auctions are one of the oldest form of markets!
(dating back to 500BC)
• A variety of commodities are sold using auctions
today!
– Spectrum (FCC)
– Oil (OPEC)
• Automated auctions using software agents fit the
requirements of network resource allocation very
well.
– Distributed selfish participants
– Fine time/space granularity
4
Outline
•
•
•
•
Motivation
Auction Design
Auction Implementations
Auction-based Applications for Resource
Allocation
• Bandwidth Trading
• Open Issues in Electronic Auctions for
Network Resource Allocation
5
Auctions - Definition
• A definition by McAfee and McMillan
– An auction is a market institution with an
explicit set of rules determining
resource allocation and prices on the
basis of bids from the market
participants.
6
Auction Design
• Auctions are the main focus of
economic mechanism design.
• Economic mechanism design
– Design “rules of interaction” for
economic transactions that will yield
some desired outcome.
• Tools
– Microeconomics
– Game Theory
7
Main Components of Auctions
• Bidding
– How to express bids efficiently?
– How to do auction communication?
• Allocation
– How to allocate resource once the bids are all in.
• Payment
– How much does each winner of the auction pay?
• Strategy
– Each (selfish) bidder is free to choose an arbitrary
bidding strategy once the auction’s protocol, allocation
and payment rules are fixed.
– For some mechanisms, truth-telling is the dominant
strategy.
8
Bidding
• Bids
– For combinatorial auctions, there are an exponential
number of bid combinations.
– Bids may be coded by the auction communication.
• Price-quotes
– Auctioneer send intermediate auction results to bidders.
– The format of price-quotes is dependent on auction type
and bidding state.
• Other interactions
– Bid withdrawal/Admittance/Rejection
– Transaction Notification
9
Bidding
• Efficiency is the key problem for bidding!
• Price-quantity graphs
– Bidders can express continuous preferences.
– It’s useful for divisible resources, e.g.,
bandwidth.
• OR bids or XOR bids
– For combinatorial auctions
• Code Bids
• Reduce bidding rounds
10
Allocation and Payment
• Economic Efficiency
– Social Welfare Maximization
– Seller Profit Maximization
• Computational Efficiency
– Compute allocation results and payment in
polynomial time
– Generally, it’s NP-hard for combinatorial
auctions.
• Incentive Compatible
– Bidders optimize their expected utilities by
bidding their true valuations for the good.
• Avoid Collusion
11
Allocation and Payment
• The trade-off between economic efficiency and
computational efficiency is constrained by the
underlying network technology.
– How much measurement (from usage to capacity pricing)
– The granularity of differently priced service offerings
(e.g., number of traffic classes)
– The level of resource aggregation – both in time and in
space – at which pricing is done (per packet/cell or per
connection, at the edge of the network or at each hop)
– The information requirement (how much a priori
knowledge of user behavior and preferences is
required/assumed by the network in computing prices)
Aurel A. Lazar and Nemo Semret
“Design and Analysis of the Progressive Second Price Auction for Network Bandwidth Sharing”.
12
Bidder’s Strategy
• Truth-telling (Risk Neutral)
– In incentive-compatible auctions, truth-telling
is the dominant strategy.
• Collusion
– Some subset of bidders coordinate their bids
to gain more value.
• Risk Aversion
– Bidders are likely to raise their bids so that
they are more likely to win.
• Bid Shading
13
Auctions - Taxonomy
• Criteria
–
–
–
–
–
–
–
–
–
–
single/double-sided
outcry/sealed-bid
ascending/descending bids
first price/second price
discriminatory/uniform price
single-object/combinatorial
single-unit/multi-unit
indivisible/divisible resources
close at once/continuous-bid
independent-private-value/common-value
14
Main Auction Types
single
SB
ascending
FPSB
Vickrey
English
double
outcry
descending SB
Dutch
Clearing
House
outcry
CDA
P.R. Wurman, M.P. Wellman, and W.E. Walsh,
“The Michigan Internet AuctionBot: A Configurable Auction Service for Human and Software Agents”, 1998.
15
Outline
•
•
•
•
Motivation
Auction Design
Auction Implementations
Auction-based Applications for Resource
Allocation
• Bandwidth Trading
• Open Issues in Electronic Auctions for
Network Resource Allocation
16
Auction Implementations
• The Michigan Internet AuctionBot
– Wurman, Wellman, and Walsh, University of
Michigan.
– A configurable auction service for human and
software agents
• eMediator
– Sandholm, Washington University.
– A next generation electronic commerce server
• A Secure Electronic Auction Protocol
– Srividhya Subramanian, The Ohio State
University
17
The Michigan Internet
AuctionBot
The AuctionBot Architecture
P.R. Wurman, M.P. Wellman, and W.E. Walsh,
“The Michigan Internet AuctionBot: A Configurable Auction Service for Human and Software Agents”, 1998.
18
The Michigan Internet
AuctionBot
• The AuctionBot supports a wide range of
auction types by decomposing the auction
design space into a set of orthogonal
parameters.
–
–
–
–
Bidding Restrictions
Auction Events
Information Revelation
Allocation Policies
19
The Michigan Internet
AuctionBot
• Bidding Restrictions
– Participation
• Single seller, multiple buyers
• Multiple sellers, single buyer
• Multiple sellers, multiple buyers
– Discrete Goods
• Reject bids for non-integer quantities
– Bid Rules
• Ascending
• Descending
• No withdrawal
20
The Michigan Internet
AuctionBot
• Auction Events
– Clearing Schedule/Quote Schedule
•
•
•
•
At scheduled times
At random times
By bidder activity
By bidder inactivity
– Closing Conditions
•
•
•
•
At a scheduled time
At a random time
After a period of inactivity
When designated bids are matched
21
The Michigan Internet
AuctionBot
• Information Revelation
– Price Quotes
• Bid quote: the highest price to sell
• Ask quote: the lowest price to buy
– Transaction History
• Whether publicize selected information about past
transactions or not
– Schedule Information
• Whether reveal the timing of upcoming clear and
quote events or not.
22
The Michigan Internet
AuctionBot
• Allocation Policies
– Currently support three policies.
– All are uniform-price and for discrete goods.
– Mth-price policy/(M+1)st-price policy
• M is the number of units offered for sale.
• Set the price at the Mth/(M+1)st highest among all
bids.
• When M=1, Mth-price policy is a first-price auction
and (M+1)st-price policy is a second-price auction.
– Chronological match policy
• Sort of Continuous Double Auction
23
The Michigan Internet
AuctionBot
• Real Time Issues
– The bidder interface is decoupled from the
auction processing completely.
– There is asynchrony between the scheduler and
the interface.
– Solution: keep track of the state of a bid
• Unprocessed, valid, rejected, expired, partially
transacted, transacted, replaced, withdrawnrequested, withdrawn.
• Denial-of-Service Attack
– What if some software agents submit bids and
information requests at high frequency?
24
eMediator
• eAuctionHouse
• Leveled Commitment Contract Optimizer
• eExchangeHouse
Tuomas Sandholm, “eMediator: A Next Generation Electronic Commerce Server”, 2000.
25
eMediator
• eAuctionHouse
– A variety of generalized combinatorial auctions
– Bidding via graphically drawn price-quantity
graphs
– Mobile agents
26
eMediator
Bid Type
Regular
Price Bids
Auction Setting
Single auction,
1 unit of 1 item
Pricing Scheme
First-Price
Single auction,
multiple units of 1 item
Price-Quantity
Graph Bids
Single auction,
multiple items, 1 unit of each
Single auction,
multiple items,
multiple units of each
Double auction,
1 unit of 1 item
2nd-Price
(Vickrey)
Multi-unit
Vickrey
OR-Bids
Double auction,
multiple units of 1 item
Groves
Double auction,
multiple items, 1 unit of each
OR-XOR-Bids
Double auction,
multiple items,
multiple units of each
Middle
Price
(50:50)
27
eMediator
• Mobile agents as auction participants
– Information agent
• Informs users auction progress
– Incrementor agent (for English auction)
• Bids a small increment more than the current highest price
• Stops if the user’s reservation price is reached
– N-agent
• Underbids when the number of bidders is N.
• Bids the user’s valuation times (N-1)/N.
– Control agent
• Submit very low noncompetitive bids
• Increases the number of bidders
• Misleads N-agents
– Discover agent
• Computes the expected gain from bidding a small increment
more than the current highest price according to the
agent’s current distribution of her valuation
28
eMediator
• Leveled Commitment Contract Optimizer
– Full commitment contract are unable to take
advantage of the possibilities that such future
events provide.
– Contingency Contracts
• The contract obligations are made contingent on
future events.
– Leveled Commitment Contracts
• The level of commitment by decommitment penalties
are specified in the contract.
29
eMediator
• eExchangeHouse
– A safe exchange planner.
– Make sure that the seller gets paid and the
buyer gets the good.
– Approach
• Divide the exchange into chunks where each party
delivers a small amount at a time,
• and the exchange proceeds with such alternation.
– A sequence is called safe if each party is
motivated to follow the exchange at every step
in anticipation of the profit from the rest of
the exchange instead of vanishing with what
the other party has delivered so far.
30
A Secure Electronic Auction
Protocol
• Security Issues in Electronic Auctions
– Anonymity of bidders
– Security from passive attacks, active attacks,
message corruption, and loss of messages
– Bidder’s privacy
– Atomicity of transaction
• By using a logic developed based on the
semantics of BAN-style logic, Subramanian
proves that the proposed secure electronic
auction protocol ensures all the properties.
Srividhya Subramanian,
“Design and Verification of a Secure Electronic Auction Protocol”, 1996.
31
Outline
•
•
•
•
Motivation
Auction Design
Auction Implementations
Auction-based Applications for Resource
Allocation
• Bandwidth Trading
• Open Issues in Electronic Auctions for
Network Resource Allocation
32
FCC Spectrum Auctions
• The US government sold spectrum right using an
innovative auction design, the simultaneous
ascending auction.
– Bidders bid on numerous communication licenses
simultaneously, with bidding remaining open on all licenses
until no bidder is willing to bid higher on any licenses.
• Collusive bidding in FCC spectrum auctions
– Bidders send messages to their rivals, telling them on
which licenses to bid and with to avoid.
– These strategies can help bidders coordinate a division
of the licenses, and enforce the proposed division by
directed punishments.
John McMillan, “Selling Spectrum Rights”, 1994.
Peter Cramton and Jesse A. Schwartz,
“Collusive Bidding: Lessons from the FCC Spectrum Auctions”, 1999.
33
Bandwidth Allocation Over Paths
• A set of simultaneous multi-unit descending
auctions, one per link of the network.
• To win bandwidth over a certain path, it suffices
to simultaneously bid for the quantity desired at
all relevant auctions.
• Prices at the various links drop at different rates,
following specified rules so that prices reflect the
demand exhibited for each link.
• A Vickrey-type pricing rule is used to address the
issue of incentive compatible pricing.
• Problems:
– How to break tie when two bids arrive almost
simultaneously?
– How to control the period of closing auctions?
Costas Courcoubetis, Manos P. Dramitinos, and George D. stamoulis,
“An Auction Mechanism for Bandwidth Allocation Over Path”, 2000.
34
“Smart Market”
• The price to send a packet would vary minute-byminute to reflect the current degree of network
congestion.
• No charge for sending packets when the networks
is not congested.
• Per-packet charge when the network is congested.
• Users only pay the market-clearing price, which is
always lower than the bids of all admitted packets.
• This is actually a “second-price” auction.
• Problem
– Not Scalable!
Jeffrey K. MacKie-Mason and Hal R. Varian, “Pricing the Internet”, 1994.
35
Congestion-based Pricing
• Critical resource reaches congestion levels, modify
prices to drive utilization back to “acceptable”
levels.
• Berkeley Computer Telephony Service Testbed
– Gateways as bottlenecks (limited PSTN access lines)
– Use congestion pricing (CP) to entice users to
• Talk shorter
• Talk later
• Accept lower quality
– Auction type???
• Upenn Modem Pool
– Mth-price auction
Jimmy Shih and Randy H. Katz, “???”, 2001.
Frank J. Klausz, David C. Croson, and Rachel T.A. Croson,
“An Experimental Auction to Allocate Congested IT Resources:
The Case of the Universtiy of Pennsylvania Modem Pool”, 1998.
36
Progressive Second Price Auction
for Network Bandwidth Sharing
• PSP is based on an exclusion-compensation
principle
– Each bidder pays for his allocation so as to exactly cover
the “social opportunity cost” which is given by the
declared willingness to pay (bids) of the bidders who are
excluded by his presence.
• PSP is incentive compatible and stable under
elastic demand.
• PSP is economically efficient in that the
equilibrium allocation maximizes total user value.
• Problems
– It can not be applied directly to path allocation in
networks!
Aurel A. Lazar and Nemo Semret,
“Design and Analysis of the Progressive Second Price Auction for Network Bandwidth Sharing”, 1999. 37
Charge-Sensitive TCP and Rate
Control
• How to achieve the system optimal rates in a
distributed environment, which maximize the total
user utility, using only the information available at
the end hosts?
– Decompose the system problem into two subproblems:
network and user problems,
– Introduce an incentive-compatible pricing scheme, while
maintaining proportional fairness.
• It’s demonstrated that, when users update their
parameters by solving their own optimization
problem, at an equilibrium the system optimum is
achieved.
Richard J. La and Venkat Anantharam,
“Charge-Sensitive TCP and Rate Control in the Internet”, 2000.
38
Market-based Routing in
Telecommunication Networks
• Economic agents
• Market institutions
– Call agent
– Path agent
– Link agent
Buyer
Call
Agents
– Path market
– Link market
Seller
Path
Maket
Buyer
Path
Agents
Seller
Link
Maket
Link
Agents
• This architecture shows a possible solution!
M.A. Gibney and N.R. Jennings,
“Dynamic Resource Allocation by Market-based Routing in Telecommunication Networks”, 1998.
39
Outline
•
•
•
•
Motivation
Auction Design
Auction Implementations
Auction-based Applications for Resource
Allocation
• Bandwidth Trading
• Open Issues in Electronic Auctions for
Network Resource Allocation
40
Bandwidth Trading
• History
– Enron completed its first bandwidth trade with
Global Crossing in December 1999.
– About 1000 bandwidth trades took place in
2000, about one-third of which involved Enron
as a counterpart.
• Why use bandwidth trading?
– The current negotiate market for exchanging
broadband capacity is too cumbersome and
costly!
– Other commodity (e.g., energy) trading is
successful!
41
Bandwidth Trading
• Prices going down, competition going up
42
Bandwidth Trading
• Players
– Market Makers/Traders
•
•
•
•
Enron
Williams Communications
Dynergy
LightTrade
•
•
•
•
Arbinet
Band-X
Ratexchange
Commerex
– Bandwidth Exchanges
43
Bandwidth Trading
• Requirements for making bandwidth a
commodity
–
–
–
–
–
Bandwidth liquidity
Price transparency
Standard contracts
Liquidated damages
Common quality benchmarks
• A Bandwidth Trading Organization (BTO)
trading agreement is expected by the end
of this year!
44
Pooling Points
• Enron Pooling Point Network (PPN)
Source: Enron Broadband Services
45
Pooling Points
• Primary function is
– to provide dynamic, real-time provisioning and
delivery of bandwidth between buyers and
sellers, and
– to provide the QoS measurements necessary to
create truly fungible units of capacity.
• One version of a pooling point is a highcapacity switch connected to a network
element of each participating capacity
buyer and seller.
– Demarcation point
– I/O ports
– Switch matrix
46
An Example of
an Interconnection Option
Source: Enron Broadband Services
47
Pooling Points
• Enron
– 2000: 21 pooling points
– 2001: 35 pooling points (expected)
– Enron claims the ability of change circuits
every 5 seconds.
– Based on Lucent network management
technology
• LightTrade
– 2000: 8 pooling points
– 2001: 15 pooling points (expected)
– Neutral pooling points
48
Other Interconnection Method
• Williams Communications is already
connected to most carriers through its own
links.
• It doesn’t have to “actively” seek a crossconnect by hooking up to pooling points.
49
Where do exchanges happen?
• Current exchanges can only function at
Layers 1 and 2.
• Providers are loath to automate the BGP
peering sessions needed to establish Layer
3 IP connectivity.
– Routing tables are not stable.
– The way the BGP peering sessions work across
networks is volatile.
– The lack of end-to-end QoS and the interdomain issues of MPLS.
50
What do we not know about
bandwidth trading?
• Can the bandwidth trading be automated?
• What mechanism is used to clear the
market?
• How’s the negotiation process performed?
51
Outline
•
•
•
•
Motivation
Auction Design
Auction Implementations
Auction-based Applications for Resource
Allocation
• Bandwidth Trading
• Open Issues in Electronic Auctions for
Network Resource Allocation
52
Open Issues in Electronic Auctions
for Resource Allocation
• How can we do bandwidth trading at Layer
3 at a fine grain time scale in wide-area
networks?
• In general, Combinatorial auctions are NPhard. Is it possible to apply combinatorial
auctions to path allocation in real time?
• Collusion detection and avoidance is very
important for real-world bandwidth
trading. How can we solve this problem?
53
Open Issues in Electronic Auctions
for Resource Allocation
• Is hierarchical auction a good way to allocate
resource in wide-area networks?
– A few small auctioneer distributes in the wide-area
network.
– Local users submit bids (resource requests) to the local
auctioneer.
– The local auctioneer aggregates users’ requests and
submit bids to a global auctioneer.
– The global auctioneer allocates resources (or exchange
resources) and inform local auctioneers.
– How local auctioneers function is a challenging problem.
54
Open Issues in Electronic Auctions
for Resource Allocation
• User’s utility is mentioned in every paper.
What is user’s utility in real network
environment?
• What is the requirement for end-to-end
QoS if we want to implement real end-toend bandwidth allocation?
• Can electronic auctions for resource
allocation take advantage of achievements
of overlay networks?
– Decentralized auctioneers construct an overlay
network!
55
Open Issues in Electronic Auctions
for Network Resource Allocation
• For the auction communication in wide-area
networks, can we learn some lessons from
wide-area signaling protocols?
• Is there any other mechanism better than
auctions for network resource allocation?
56