CS代考 COMP30024 - Artificial Intelligence

Making Collective Decisions – Auctions Chapter 17.6 – COMP30024 – Artificial Intelligence

Making Collective Decisions – Auctions
Chapter 17.6

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

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

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

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

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.

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

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

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts