Silvia Rossi

Lezione n.

Corso di Laurea:

Insegnamento:

Email:

A.A. 2014-2015

Silvia Rossi

Auctions

16

Informatica

Sistemi

multi-agente

silrossi@unina.it

Reaching Agreements - Auctions

(W: 7.2, 9.2.1 MAS: 11.1)

2

Auctions as Structured Negotiations

Any negotiation mechanism that is:

•  market-based (determines an exchange in terms of currency)

•  mediated (auctioneer)

•  well-specied (follows rules)

Defined by three kinds of rules:

•  rules for bidding

•  rules for what information is revealed

•  rules for clearing

3

Auctions as Structured Negotiations

Dened by three kinds of rules:

•  rules for bidding

•  who can bid, when

•  what is the form of a bid

•  restrictions on offers, as a function of:

•  bidder's own previous bid

•  auction state (others' bids)

•  eligibility (e.g., budget constraints)

•  expiration, withdrawal, replacement

•  rules for what information is revealed

•  rules for clearing

Auctions as Structured Negotiations

Dened by three kinds of rules:

•  rules for bidding

•  rules for what information is revealed

•  when to reveal what information to whom

•  rules for clearing

Auctions as Structured Negotiations

Dened by three kinds of rules:

•  rules for bidding

•  rules for what information is revealed

•  rules for clearing

•  when to clear

•  at intervals

•  on each bid

•  after a period of inactivity

•  allocation (who gets what)

•  payment (who pays what)

Intuitive comparison of 5 auctions

How should agents bid in these auctions? Intuitive Comparison of 5 auctions

• How should agents bid in these auctions?

English Dutch Japanese 1 ^st -Price 2 ^nd -Price

Duration #bidders, increment

starting price, clock

speed

#bidders, increment

fixed fixed

Info Revealed

2 ^nd -highest val; bounds

on others

winner’s bid

all val’s but winner’s

none none

Jump bids yes n/a no n/a n/a

Price

Discovery yes no yes no no

Regret no yes no yes no Fill in “regret” after

the fun game

Second-Price

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.

8

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.

9

Example

Horace, for example, would reason like this:

Suppose that Maurice's bid is for less than my reservation price;

Then I want to win the auction, and I can do so just by bidding my own reservation price truthfully.

If Maurice bids more than my reservation price;

Then I don’t want to win and I can guarantee not doing so by bidding my own reservation price truthfully.

10

Vickrey Auctions

The auction proceeds either by English

(ascending auction) or by sealed-bid protocol The winner is the bidder with the highest bid The winner pays the amount which the

second-highest bidder bid

This protocol reduces the extent of the winner’s curse

The amount paid by the winner is equal to

the price the winner would get if he/she

sold it immediately in another auction

Vickrey Auctions

Vickrey auctions susceptible to antisocial behavior

Lying auctioneer

Second-Price proof

Truth-telling is a dominant strategy in a second- price auction.

Assume that the other bidders bid in some arbitrary way. We must show that i's best response is always to bid truthfully. We'll break the proof into two cases:

1 Bidding honestly, i would win the auction 2 Bidding honestly, i would lose the auction

13

• Bidding honestly, i is the winner

• If i bids higher, he will still win and still pay the same amount

• If i bids lower, he will either still win and still pay the same amount. . . or lose and get utility of zero.

14

Bidding honestly, i is not the winner

If i bids lower, he will still lose and still pay nothing If i bids higher, he will either still lose and still pay nothing. . . or win and pay more than his valuation.

15

English and Japanese auctions

• A much more complicated strategy space

•  extensive form game

•  bidders are able to condition their bids on information revealed by others

•  in the case of English auctions, the ability to place jump bids

• intuitively, though, the revealed information doesn't make any difference in the IPV setting.

Theorem

Under the independent private values model (IPV), it is a dominant strategy for bidders to bid up to (and not beyond) their valuations in both Japanese and English auctions.

16

First-Price and Dutch

• In both first-price and Dutch, a bidder must decide on the amount he's willing to pay, conditional on having placed the highest bid.

•  despite the fact that Dutch auctions are extensive-form games, the only thing a winning bidder knows about the others is that all of them have decided on lower bids

•  e.g., he does not know what these bids are

•  this is exactly the thing that a bidder in a first-price auction assumes when placing his bid anyway .

• Note that this is a stronger result than the connection between second-price and English.

17

Discussion

• So, why are both auction types held in practice?

•  First-price auctions can be held asynchronously

•  Dutch auctions are fast, and require minimal

communication: only one bit needs to be transmitted from the bidders to the auctioneer.

• How should bidders bid in these auctions?

18

Discussion

• So, why are both auction types held in practice?

•  First-price auctions can be held asynchronously

•  Dutch auctions are fast, and require minimal

communication: only one bit needs to be transmitted from the bidders to the auctioneer.

• How should bidders bid in these auctions?

•  They should clearly bid less than their valuations.

•  There's a tradeo between:

•  probability of winning

•  amount paid upon winning

•  Bidders don't have a dominant strategy any more.

19

Risk

20

Utility

Let s _i denote the bid of player i, and v _i denote his true valuation.

If player i wins, his payoff is u _i = v _i − s _i ; If he loses, it is u _i = 0.

21

Analysis

22

Analysis

23

Analysis

24

More tha two bidders

• Still, first-price auctions are not incentive compatible

•  hence, unsurprisingly, not equivalent to second-price auctions

• proven using a similar argument, but more involved calculus

• a broader problem: that proof only showed how to verify an

• equilibrium strategy.

•  How do we identify one in the first place?

25

Revenue Equivalence

Which auction should an auctioneer choose? To some extent, it doesn't matter...

26

Revenue Equivalence

Thus, when bidders are risk neutral and have

independent private valuations, all the auctions we have spoken about so far—English, Japanese, Dutch, and all sealedbid auction protocols—are revenue equivalent.

27

Risk Attitudes

What kind of auction would the auctioneer prefer?

Buyer is not risk neutral:

•  no change under various risk attitudes for second price

•  in first-price, increasing bid amount increases probability of winning, decreases profit. This is good for risk-averse bidder, bad for risk-seeking bidder.

•  Risk averse, IPV: First > [Japanese = English = Second]

•  Risk seeking, IPV: Second > First

28

Risk Attitudes

What kind of auction would the auctioneer prefer?

Buyer is not risk neutral:

•  no change under various risk attitudes for second price

•  in first-price, increasing bid amount increases probability of winning, decreases profit. This is good for risk-averse bidder, bad for risk-seeking bidder.

•  Risk averse, IPV: First > [Japanese = English = Second]

•  Risk seeking, IPV: Second > First Auctioneer is not risk neutral:

•  revenue is fixed in first-price auction (the expected amount of the second-highest bid)

•  revenue varies in second-price auction, with the same

expected value thus, a risk-averse seller prefers first-price to

second-price. 29

For risk-averse bidders (i.e. bidders that would prefer to get the good even if they paid slightly more for it than their private valuation), Dutch and first-price sealed-bid protocols lead to higher expected revenue for the

auctioneer.

This is because in these protocols, a risk-averse agent can 'insure‘

himself by bidding slightly more for the good than would be offered by a risk-neutral bidder.

Risk-averse auctioneers, however, do better with Vickrey or English auctions.

30

Revenue Equivalence and Non-Equivalence

All of the four auction protocols produce the same expected revenue to the auctioneer in private value auctions where the values are

independently distributed, and bidders axe risk- neutral.

31

Lies and Collusion

The various auction protocols are susceptible to lying on the part of the auctioneer, and collusion among bidders, to varying degrees

All four auctions (English, Dutch, First-Price Sealed Bid, Vickrey) can be manipulated by bidder collusion

A dishonest auctioneer can exploit the Vickrey auction by lying about the 2 ^nd -highest bid

Shills can be introduced to inflate bidding prices

in English auctions

Design choices for market mechanisms Number and frequency of rounds

Who can participate?

Rules for participant collaboration and proxies Rules for utterances

Can participant leave before the end?

Rules for termination

How winner is selected?

What price does the winner pay?

What price do the others pay?

What can happen subsequently?

Evaluation of auction mechanisms Traditional economic-theoretic criteria

Maximization of revenue to single seller Efficiency of resource allocation

Other economic criteria

Social welfare

Allocation efficiency (eg, Pareto-optimal outcomes) Individual rationality

Stability against manipulation Low transaction costs

Rule transparency

Buyer vs. seller market power

Luca, come regalo di Natale, riceve un iPod da 5Gb. Tale oggetto ha valore nullo per Luca in quanto già possiede in iPod da 40Gb e decide così di metterlo all’asta.

Supponendo che solo 3 persone siano interessate a

partecipare all’asta e che la loro valutazione dell’oggetto sia 25€, 37€ e 40€. Quale sarebbe il profitto di Luca se l’asta fosse una second-price sealed-bid o una first

price?

35

Working Together

Why and how do agents work together?

Important to make a distinction between:

benevolent agents

self-interested agents

Benevolent Agents

If we “own” the whole system, we can design agents to help each other whenever asked

In this case, we can assume agents are benevolent: our best interest is their best interest

Problem-solving in benevolent systems is

cooperative distributed problem solving (CDPS)

Benevolence simplifies the system design task

enormously!

Self-Interested Agents

If agents represent individuals or organizations, (the more general case), then we cannot make the benevolence assumption

Agents will be assumed to act to further their own interests, possibly at expense of others Potential for conflict

May complicate the design task enormously

Task Sharing and Result Sharing

Two main modes of cooperative problem solving:

task sharing:

components of a task are distributed to component agents

result sharing:

information (partial results, etc.) is

distributed

The Contract Net

A well known task-sharing protocol for task allocation is the contract net:

1.  Recognition

2.  Announcement 3.  Bidding

4.  Awarding

5.  Expediting

Recognition

In this stage, an agent recognizes it has a problem it wants help with.

Agent has a goal, and either…

realizes it cannot achieve the goal in isolation

— does not have capability

realizes it would prefer not to achieve the goal in isolation (typically because of

solution quality, deadline, etc.)

Announcement

In this stage, the agent with the task sends out an announcement of the task which includes a specification of the task to be achieved

Specification must encode:

description of task itself (maybe executable) any constraints (e.g., deadlines, quality

constraints)

meta-task information (e.g., “bids must be submitted by…”)

The announcement is then broadcast

Bidding

Agents that receive the announcement decide for themselves whether they wish to bid for the task

Factors:

agent must decide whether it is capable of expediting task

agent must determine quality constraints &

price information (if relevant)

If they do choose to bid, then they submit a

tender

Awarding & Expediting

Agent that sent task announcement must

choose between bids & decide who to “award the contract” to

The result of this process is communicated to agents that submitted a bid

The successful contractor then expedites the task

May involve generating further manager-

contractor relationships: sub-contracting

Issues for Implementing Contract Net

How to…

…specify tasks?

…specify quality of service?

…select between competing offers?

…differentiate between offers based on

multiple criteria?

The Contract Net

An approach to distributed problem

solving, focusing on task distribution Task distribution viewed as a kind of

contract negotiation

“Protocol” specifies content of communication, not just form

Two-way transfer of information is

natural extension of transfer of control

mechanisms

Four Phases to Solution, as Seen in Contract Net

1. Problem Decomposition 2. Sub-problem distribution 3. Sub-problem solution

4. Answer synthesis

The contract net protocol

deals with phase 2.

Contract Net

The collection of nodes is the “contract net”

Each node on the network can, at different

times or for different tasks, be a manager or a contractor

When a node gets a composite task (or for any reason can’t solve its present task), it breaks it into subtasks (if possible) and announces them (acting as a manager), receives bids from potential contractors, then awards the job (example domain: network resource

management, printers, …)

Manager

Task Announcement

Node Issues Task Announcement

Manager

Manager Manager

Potential Contractor

Idle Node Listening to Task Announcements

Manager

Potential Contractor

Bid

Node Submitting a Bid

Manager

Potential Contractor

Potential Contractor Bids

Manager listening to bids

Manager

Contractor Award

Manager Making an Award

Manager

Contractor Contract

Contract Established

Domain-Specific Evaluation

Task announcement message prompts potential contractors to use domain specific task

evaluation procedures; there is deliberation

going on, not just selection — perhaps no tasks are suitable at present

Manager considers submitted bids using domain

specific bid evaluation procedure

Contract-net

Iterated


Contract-net