• Non ci sono risultati.

Silvia Rossi

N/A
N/A
Protected

Academic year: 2021

Condividi "Silvia Rossi"

Copied!
23
0
0

Testo completo

(1)

Lezione n.

Corso di Laurea:

Insegnamento:

Email:

A.A. 2014-2015

Silvia Rossi

Auctions

15

Informatica

Sistemi

multi-agente

silrossi@unina.it

(2)

Reaching Agreements - Auctions

(W: 7.2, 9.2.1 MAS: 11.1)

2

(3)

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

(4)

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

(5)

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

(6)

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

(7)

• 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

(8)

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

(9)

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

(10)

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

(11)

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.

(12)

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.

(13)

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.

(14)

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

(15)

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

(16)

FIPA – English auction

(17)

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

(18)

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.

(19)

FIPA - Dutch auction

(20)

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

(21)

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

(22)

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

(23)

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

Riferimenti

Documenti correlati

Computing all of the equilibria of a two-player, general- sum game requires worst-case time that is exponential in the number of actions for each

4 (Reduction Size) Given constants ki for each player i, does there exist a maximally reduced game where each player i has exactly ki actions.. For iterated strict dominance

Approval voting: Each voter can cast a single vote for as many of the candidates as he wishes; the candidate with the most votes is selected...

Mechanism design is a strategic version of social choice theory, which adds the assumption that agents will behave so as to maximize their..

•  If the core is non-empty then the grand coalition is stable, since nobody can benefit from defection.. Problems with

•  possible-worlds semantics; an agent's beliefs, knowledge, goals, etc., are characterized as a set of so-called possible worlds, with an accessibility relation holding

•  Intentional Stance: Attributing attitudes (beliefs, desires, whishes) to systems whose precise internal function

Problems with symbolic reasoning led to a reaction against this — the so-called reactive agents!.