Making Collective Decisions – Auctions Chapter 17.6 – COMP30024 – Artificial Intelligence
Making Collective Decisions – Auctions
Chapter 17.6
Copyright By PowCoder代写 加微信 powcoder
COMP30024 – Artificial Intelligence
Dr Wafa Johal
University of Melbourne
Introduction
• Single agents: one agent doing the sensing, planning and acting.
• Enviroment with multiple actors: Multi-agent systems
When each of the agent is a decision maker we can consider several cases:
⋄ common goal => coordination problem
⋄ own personal perferences => opposed (zero-sum games) or more
complex preferences …
Game Theory: the theory of strategic decision making.
• Agent design: GT used to determine what is the best strategy against
rational players
• Mechanisim design: GT used to define the rules of the environment
AIMA Slides © and ; Dr Wafa Johal 2
• Mechanism design for allocating scarce resources
• Properties of auctions
• Types of auctions
• On-line auctions in practice
Draws on material from
– Wooldridge ”An Introduction to MultiAgent Systems”, Wiley, 2009
AIMA Slides © and ; Dr Wafa Johal 3
Complex decisions
So far we have looked at problems involving single agent search
or pairs of agents for adversarial game search
In practice, complex applications can involve multi-agent systems,
where multiple agents are competing for a scarce resource, e.g.,
– farmers needing a water allocation in an irrigation system
– mobile phone companies competing for radio spectrum
– advertisers competing for ad space on high profile media
Traditional approach: a centralised authority makes an allocation to each agent
Issue – How to make sure that the scarce resource goes to those who value it
the most, and that the owners of the resource maximise their financial return
AIMA Slides © and ; Dr Wafa Johal 4
Example – Selling and buying land
How does each side make sure they get a good deal?
AIMA Slides © and ; Dr Wafa Johal 5
Example – Selling and buying land
Any Saturday in Melbourne – house auction
What concerns do you have (1) as a buyer, (2) as a seller?
AIMA Slides © and ; Dr Wafa Johal 6
Mechanism design
Mechanism design is the problem of how to design a ”game” that results in
maximising a global utility function in a multi-agent system, given that each
agent pursues their own (selfish) rational strategy
In AI, mechanism design aims to construct smart systems out of simpler
(possible uncooperative) systems to achieve goals that are beyond the reach of
any single system
We focus on mechanism design for auctions
Formally, an auction takes place between an auctioneer agent, who allocates a
good or service among a set of agents called bidders
A mechanism for an auction consists of three main components
– a language to describe the allowable strategies an agent can follow
– a protocol for communicating bids from bidders to the auctioneer, and
– an outcome rule, used by the auctioneer to determine the outcome
AIMA Slides © and ; Dr Wafa Johal 7
Dimensions of auction protocols
Winner determination: which bidder wins, and what do they pay?
– First-price auctions bidder with highest bid is allocated the good
– Second-price auctions bidder with highest bid wins
but pays the auctioneer the price of the second highest bidder!
Knowledge of bids: who can see the bids?
– Open-cry every bidder can see all bids from all other bidders
– Sealed-bid bidder can see only its own bids,
not those of other bidders
Order of bids: in what order can bids be made?
– One-shot each bidder can make only on bid
– Ascending each successive bid must exceed the previous bid
– Descending auctioneer starts from a high price, and each bid
must be lower than the previous bid
AIMA Slides © and ; Dr Wafa Johal 8
Dimensions of auction protocols (cont.)
Number of goods: How many goods are for sale?
– Single good only one indivisible good is for sale
– Many goods many goods are available in the auction,
so bids can include both the price and number of goods wanted
by the bidder (e.g., auctioning mobile phone spectrum),
known as a combinatorial auction
We focus on single good auctions
AIMA Slides © and ; Dr Wafa Johal 9
Factors affecting mechanism design
A major factor is how bidding agents put a value on the good to be auctioned.
Private value: Each bidder i has a utility value vi that reflects
the worth of the good to the bidder
Common value: The worth of the good is the same for all bidders,
but that worth is unknown a priori, and must be estimated by each bidder
For example, an ounce of gold has the same value to each bidder
as they each have the same use for it,
but they do not know what that value is.
In contrast, a gold earring may have different private values to each bidder
based on the beauty of the earring and the fame of its previous owner.
AIMA Slides © and ; Dr Wafa Johal 10
Desirable properties of an auction
What kinds of properties characterise an effective mechanism design
for auctions?
Efficent: The goods go to the agent who values them the most
Discourage collusion: The auction mechanism should discourage illegal or
unfair agreements between two or more bidders to manipulate prices
Dominant strategy: There exists a dominant strategy for bidders,
where a strategy is dominant if it gives the bidder a better pay-off
than any other strategy
Truth-revealing: The dominant strategy results in bidders revealing their
true value for the good
AIMA Slides © and ; Dr Wafa Johal 11
What does this have to do with AI?
• Modern on-line auctions require autonomous agents who can bid on our
• These agents need to model user’s preferences for their bidding strategy
• These agents need a representation language for bids
AIMA Slides © and ; Dr Wafa Johal 12
Types of auctions
• English auction (ascending-bid)
• Dutch auction (descending-bid)
• First-price sealed-bid auction
• Vickrey auction
AIMA Slides © and ; Dr Wafa Johal 13
English auction
Typically a first-price, open-cry, ascending auction.
Protocol and outcome rule:
– auctioneer starts by asking for a minimum (reserve) price
– auctioneer invites bids from bidders, which must be
higher than the current highest price received
(perhaps requiring a minimum bid increment)
– auction ends when no further bids received,
and good is sold if final bid exceeds reserve price
– price paid by winner is their final (highest) bid
Dominant strategy: keep bidding in small bids while the current cost
is below your utility value vi for the good
English auctions became famous through art auction houses such as Sotheby’s
and Christie’s in London in the 1700’s
AIMA Slides © and ; Dr Wafa Johal 14
Properties of English auction
• Is efficient, provided the reserve is realistic
(too high – bidder who values good may not bid;
too low – seller may lose revenue)
• Can suffer from the winner’s curse: has winner valued the good
too highly because no one else made that high bid?
• Can be susceptible to collusion
– bidders can agree beforehand to keep bids artificially low
– auctioneers can plant ”dummy”or bogus bidders to inflate prices
AIMA Slides © and ; Dr Wafa Johal 15
Dutch auction
Typically an open-cry, descending auction.
Protocol and outcome rule:
– auctioneer starts by asking for an extremely high initial price
– auctioneer repeatedly lowers the price of the good in smal steps
– auction ends when someone makes a bid at the current offer price
– price paid by winner is the price when their bid was made
Can suffer from similar problems to the English auction
Dutch auctions were used for flower auctions in the Netherlands
AIMA Slides © and ; Dr Wafa Johal 16
Collusion in the world’s biggest auction
In the 1990s, mobile telephone use was experiencing explosive growth,
along with the prospective demand for mobile data services.
The capacity of mobile networks is heavily dependent to the amount of
radio spectrum (bandwidth) available to the network. Mobile network carriers
require a licence to operate within a certain range of the radio spectrum.
Governments realised they could make billions of dollars out of selling the
rights to use the radio spectrum.
To maximise the value of their radio spectrum, governments turned
to auctions as a truth-revealing mechanism to achieve the ”true value” of this
AIMA Slides © and ; Dr Wafa Johal 17
Collusion in the world’s biggest auction
Germany 1999 – auction held on 10 blocks of radio spectrum
These 10 blocks were simultaneously auctioned using an English auction,
where any bid must be at least 10% higher than the last bid.
Bidders could bid on any subset of the 10 blocks at any stage.
Two companies were serious bidders: Mannesman and T-Mobile.
Mannesman bid 20M DM (deutschmarks) on blocks 1–5,
and 18.18MDM on blocks 6–10.
Why the strange figure of 18.18M DM? It turns out that a 10% increase
on 18.18M is 19.99M. This sent a signal to the other main bidder (T-Mobile)
that Mannesman did not really want to compete for blocks 6–10.
Both could get half the spectrum without really competing.
The two carriers were able to collude by using the bidding mechanism
as a way to communicate!
AIMA Slides © and ; Dr Wafa Johal 18
Winner’s curse in the world’s biggest auction
In 2000, the British government ran a spectrum auction using
an English auction, with a minimum bid set by the auctioneer at each round,
which is an increase of the maximum bid in the last round.
Bidders must make a bid in every round of the auction to stay
active in the auction. Otherwise they exit that auction.
The auction raised 22.5 billion pounds, equivalent to 570 pounds
per person in Britain!
It is thought this excessive expenditure weighed heavily on the balance sheets
of the participating telcos, and exacerbated the ”dot com” crash.
Truly a ”winner’s curse”!
AIMA Slides © and ; Dr Wafa Johal 19
First-price sealed-bid auction
Protocol and outcome rule:
– each bidder makes a single bid
– bid sent to auctioneer so that bidders cannot see each other’s bid
– winner is the bidder who made the highest bid
– price paid by winner is the highest bid
Dominant strategy: not clear – bid less that your true value vi,
but how much less depends on other agents’ bids, which are unknown
Often used for tender bids for government contracts
AIMA Slides © and ; Dr Wafa Johal 20
Properties of first-price sealed-bid auction
• May not be efficient, since agent with highest value vi
might not win the auction
• Much simpler communication than English or Dutch auctions
• Sealed bids make it harder for the type of collusion that occurred
in the German spectrum auction
AIMA Slides © and ; Dr Wafa Johal 21
Vickrey auction
Typically a second-price, sealed-bid auction.
Protocol and outcome rule:
– essentially the same as first-price, sealed-bid auction
– however, price paid by winner is the price of the second-highest bid
Dominant strategy: can show that it is to simply bid your value vi for the good
Named after (1914-1996), won for economics
and died of a heart attack three days later!
Why does winner pay the price of the second-highest bid?
– you have nothing to lose by bidding your true value, since if it is much higher
than the second-highest bid, you still only pay the second-highest price
This helps overcome the winner’s curse
AIMA Slides © and ; Dr Wafa Johal 22
Properties of Vickrey auction
• Is efficient,and truth-revealing, since dominant strategy
is to bid your value vi
• Harder for collusion to occur
• Can be a bit counter-intuitive for human bidders
• Its computational simplicity makes it popular for use
in multi-agent AI systems and on-line auctions
AIMA Slides © and ; Dr Wafa Johal 23
Case Study – Online auctions
Sites such as eBay make it easy for sellers to find potential bidders for
specialist goods
A key characteristic of these specialist goods is that their value is unclear
(recall private values)
eBay provides limited support for automated proxy bidding
One of the first items sold on the original version of eBay is reported to have
been a broken laser pointer. Appearently it was bought by someone who
collects broken laser pointers!
eBay made over US$16billion in revenue in 2013
AIMA Slides © and ; Dr Wafa Johal 24
Case Study – Online auctions
This supports a mixture of English and Vickrey auction with the following
modifications:
– highest winning bid is sealed
– current second highest bid is public to help establish value of good
– bidders can make multiple bids
– a deadline is used, so that bids received after the deadline are not valid
A problem in eBay-style auctions is sniping, where bids that are higher than the
most recent advertised bid are submitted just before the deadline
Sniping aims to beat the truth-revealing mechanism of Vickrey auctions, since
the private valuation of last moment bidders do not get a chance to be made
Other sites such as Amazon use different rules to finish the auction – if a bid
arrives within a certain time before the deadline, then the auction is extended.
This change of mechanism has been found to change the behaviour of bidders
in terms of whether last-moment bids are received.
AIMA Slides © and ; Dr Wafa Johal 25
Case Study – Google AdWords
AIMA Slides © and ; Dr Wafa Johal 26
Case Study – Google AdWords
Google sells advertising space on their results web page by using auctions
The ”good” to be sold is the space on the results web page for your search
The ”bidders” are advertisers who have a product or service that is relevant to
your interests, based on your search query
Bidders (advertisers) can register their interest in participating in auctions that
involve specific search terms
When you type your query:
– bidders are found based on your search terms
– a Vickrey auction is held
– the winner is selected based on their bid price and their relevance
– the winning bidder’s advertisement is displayed
– and this all happens in real-time (approx 104 auctions / second)!
Google made over US$42billion in advertising revenue in 2012
AIMA Slides © and ; Dr Wafa Johal 27
Auctions are a mechanism to allocate resources in mutli-agent environments
Appropriate mechanism design can achieve desirable behaviour
among selfish agents
Types of auctions in theory
Practical case studies of on-line auctions
Examples of skills expected:
• Compare and contrast different types of auctions
• Describe the properties of a given type of auction
• Select the most appropriate type of auction for a given application
AIMA Slides © and ; Dr Wafa Johal 28
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com