Lezione n.
Corso di Laurea:
Insegnamento:
Email:
A.A. 2014-2015
Silvia Rossi
Auctions
15
Informatica
Sistemi
multi-agente
silrossi@unina.it
Reaching Agreements - Auctions
(W: 7.2, 9.2.1 MAS: 11.1)
2
Auction and Market Mechanisms Why important
E-commerce (1990s->)
Distributed computing (2000s->)
Mechanisms for allocation of resources Studied using tools from:
Game theory & economic mechanism design Dynamical systems and evolutionary theory Computer science
Emerging applications
Shared computational resources
Grid systems P2P networks
On-demand computing
How to allocate shared resources in distributed networks?
There may be no central authority (internet) Signaling and feedback may be inefficient and
subject to delays
Participant may be self-interested
Auctions
An auction takes place between an agent known as the auctioneer and a collection of agents
known as the bidders
The goal of the auction is for the auctioneer to allocate the good to one of the bidders
In most settings the auctioneer desires to
maximize the price; bidders desire to minimize price
Asta di 1 euro
• Per alzata di mano
• L’euro è assegnato a chi offrirà il prezzo più alto (che dovrà pagare)
• Anche il secondo più elavato offerente dovrà pagare, ma non riceverà nulla in cambio
• Quanto sareste disposti ad offrire per un euro?
6
• Può capitare che le offerte superino il valore di un euro?
• Perché chi offre può eccedere il valore di un euro?
• Se avete l’occasione di ripetere l’esperienza come vi comportate? Perché?
7
Consideriamo il caso di offerte in busta chiusa.
Tutti gli agenti offrono 0.99 (equilibrio di Nash) Guadagno di 0.01 con probabilità 1/n
Nel caso in cui anche il secondo paga non esiste un equilibrio (valore casuale da offrire)
8
Valuation
Special case: Common value goods
The value of the good(s) is the same to all bidders
Private value goods
The value of the good(s) to a bidder depends only on the bidder’s own preferences
Economic theory usually assumes that each bidder’s private values are known to him/herself at the start of the auction
Correlated (or Interdependent) value goods
The value of the good(s) to a bidder also depends on the preferences of other bidders
Hence, the value of the goods(s) is unknown to bidders at the start of the auction
Auction Parameters
Goods can have
private value
public/common value correlated value
Winner determination may be
first price second price
Bids may be
open cry (common knowledge) sealed bid
Bidding may be
one shot ascending descending
Some auction concepts
Forward auctions:
Single potential seller & many potential buyers Seller usually wants highest possible price.
Reverse auctions:
Single potential buyer & many potential sellers Buyer usually wants lowest possible price.
Double auctions:
Many potential buyers and many potential sellers.
English auction protocol
Auctioneer calls for bids:
The auctioneer may start at the reserve price
Potential buyers call out the price they are willing to pay
Each bidder calls a higher price than previously, until no one is willing to bid again
It ends after a fixed period during which no new bids
are made
The winner is the person bidding the highest The winner pays the amount he or she bid.
English auction protocol
In some auctions, bidder must increase the next bid by a specified percentage on the previous
bid.
Also, in some auctions, bidders must declare when leaving the auction
These are called open exit auctions.
English Auctions
Most commonly known type of auction:
first price open cry ascending
Dominant strategy is for agent to successively bid a small amount more than the current
highest bid until it reaches their valuation, then withdraw
Susceptible to:
winner’s curse shills
English Auctions
Dominant strategy is for agent to successively bid a small amount more than the current
highest bid until it reaches their valuation, then withdraw
In a private value auction where the valuation vi for each agent i is drawn independently from a uniform distribution between 0 and v,
there is a Nash equilibrium where every agent i bids (|A|-1)/|A| * vi
FIPA – English auction
Japanese auctions
• The auctioneer sets a starting price for the good
• Each agent must choose whether or not to be “in”
• The auctioneer then calls out successively increasing prices in a regular fashion
• After each call each agent must announce whether he is still in
• When he drops out it is irrevocable
• The auction ends when there is exactly one agent left in
• The agent must then purchase the good for the current price
17
Dutch Auctions
Dutch auctions are examples of open-cry descending auctions:
auctioneer starts by offering good at artificially high value
auctioneer lowers offer price until some agent makes a bid equal to the current offer price the good is then allocated to the agent that
made the offer
Goods must be sold quickly;
There is no dominant strategy for Dutch auctions in general.
FIPA - Dutch auction
First-Price Sealed-Bid Auctions
First-price sealed-bid auctions are one-shot auctions:
There is a single round Fast protocols
The bidders write their proposed bid on a piece of paper and submit it in a sealed envelope to the auctioneer
The auctioneer opens the envelopes and ranks the bids
The winner is the bidder with the highest bid winner pays price of highest bid
First-Price Sealed-Bid Auctions
Best strategy is to bid less than true valuation In all three of these protocols, winners may
suffer from the “winner’s curse”
They may bid much more the item that anyone else
For example; in a mobile license in New Zealand in 1994, the top two bids were:
Winner: NZ$7,000,000 Second-highest: NZ$5,000
Alice wants to get the best price she can for her house.
There are two potential buyers, Horace and Maurice.
If she knew the maximum each would be willing to pay, her problem would be easy.
However, although she doesn't know their reservation prices, she is not entirely ignorant.
• It is common knowledge that each potential buyer has a
reservation price of either three million or four million dollars, and that each value is equally likely.
22
second-price auction
Each bidder secretly seals his bid in an envelope.
The envelopes are then publicly opened, and the house is sold to the highest bidder,
but not at the price he bid. Instead it is sold to him at the highest price bid by a loser.
The advantage of such an arrangement, the auctioneer explains, is that it induces rational people to bid their true reservation prices.
23