Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

COMP30024 Artificial Intelligence > Week 10 (Chapter 17) - Making Complex Decisions > Flashcards

Week 10 (Chapter 17) - Making Complex Decisions Flashcards

1
Q

What is the main issue that ‘Making Complex Decisions’ aims to address?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is the traditional approach to making complex decisions.

A

Centralised authority - such as Government

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

In an auction (for property), what are the concerns for a Buyer?

A
  • When to start bidding (strategy)
  • What is your maximum price
  • What is long term growth
  • What are alternatives on the market
  • What increment to bid by (strategy)
  • Are the other bidders real
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

In an auction (for property), what are the concerns for a Seller?

A
  • How much are the goods worth
  • What should be my reserve
  • How to encourage bidders to bid more
  • When to stop asking for bids
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

WTF is ‘Mechanism Design’?

A

In AI, this means constructing a smart system out of simpler (possibly uncooperative) systems to achieve goals that are beyond the reach of any single system.

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are the 3 main components of a mechanism for an auction?

A
  • A language to describe the allowable strategies an agent can follow
  • A protocol for communicating bids from bidders to the auctioneer
  • An outcome rule, used by the auctioneer to determine the outcome
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are some dimensions of auction protocols?

A
  • WINNER DETERMINATION: which bidder wins, and what do they pay?
  • KNOWLEDGE OF BIDS: who can see the bids?
  • ORDER OF BIDS: in what order can bids be made?
  • NUMBER OF GOODS: how many goods are for sale?
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are 2 approaches to “Winner determination” dimension in auction protocols?

A
  • FIRST-PRICE AUCTION: bidder with the highest bid is allocated the win and pays the price THEY BIDDED
  • SECOND-PRICE AUCTION: bidder with the highest bid wins, but pays the price of THE SECOND HIGHEST BIDDER
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What are 2 approaches to “Knowledge of bids” dimension in auction protocols?

A
  • OPEN-CRY: every bidder can see all bids from all other bidders (house auction)
  • SEALED-BIDS: bidder can see only its own bids, not those of other bidders (bid for a project for work)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are 2 approaches to “Order of bids” dimension in auction protocols?

A
  • ONE-SHOT: each bidder can only make one 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are 2 approaches to “Number of goods” dimension in auction protocols?

A
  • SINGLE GOOD: only one indivisible good is for sale (house) - THIS IS WHAT WE FOCUS ON IN SUBJECT

======

  • MANY GOODS: many goods are available in the auction (japanese fish market), bids can include both the price and the quantity of goods wanted. THIS IS KNOWN AS COMBINATORIAL AUCTION
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What factors can affect “mechanism design”?

A

A major factor is how bidding agents put a value on the good being auctioned.

  • PRIVATE VALUE: each bidder (i) has a utility value (Vi) that reflects the worth of the good to the bidder (e.g. 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)
  • 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 (e.g. 1 ounce of gold has the same value to each bidder, but they do not know what the value for it is)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What kinds of ‘properties’ characterises an effective ‘mechanism design’ for auctions?

A
  • EFFICIENT: The goods to go 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What do auctions have to do with AI?

A
  • Modern on-line auctions require autonomous agents who can bid on your behalf (e.g. Algorithmic trading?)
  • These agents need to model user’s preference for their bidding strategy
  • These agents need a representation language for bids
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are the 4 types of auctions?

A
  • English auction (ascending-bid)
  • Dutch auction (descending-bid)
  • First-price sealed-bid auction
  • Vickrey auction
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is ‘English Auction’?

A

Typically a first-price, open-cry, ascending auction.

Used in real estate.

Protocol and outcome rule:

  • Auctioneer starts by asking for a minimum price
  • Auctioneer invites bids from bidders which must be higher than current highest bid (sometimes there’s a minimum increment bid)
  • Auction ends when no further bids are received, and good is sold if final bid exceeds reserve price
  • Price paid by final 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

17
Q

Properties of English Auction?

A
  • Efficient, provided the minimum price is realistic
    (too high = bidder may not bid; too low = seller loses revenue)
  • Can suffer from winner’s curse: has the winner valued the good too highly because no one else made that high bid? (e.g. “did i bid too much?” - doubt)
  • Susceptible to collusion
    • bidders agree beforehand to keep bids low
    • auctioneer can plant dummy bidders to inflate prices
18
Q

What is ‘Dutch Auction’

A

Typically open-cry, descending auction

Protocol and outcome rule:

  • Auctioneer starts by asking for an extremely high price (opposite of English)
  • Auctioneer repeatedly lowers the price of the good in small steps
  • Auctioneer ends when someone makes a bid at the current offer price (one shot only)
  • Price paid by winner is the price when their bid was made

Suffers from the same problems as English Auction
- can be efficient, winner’s curse, susceptible to collusion

Difference to English auction? Auctioneer can control the time.

19
Q

What is ‘First-price sealed-bid auction’?

A

Mainly used by governments for contracts

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 than your true value (Vi) but how much less depends on other agents’ bids, which are unknown

20
Q

Properties of ‘First-price sealed-bid auction’?

A
  • May not be efficient, since agent with the highest value may not win (they might not bid their highest true value because they’re worried of winner’s curse)
  • Much simpler than English or Dutch auctions (only one round)
  • Makes it difficult for collusion
  • Winner’s curse is still prevelant
21
Q

What is ‘Vickrey auction’?

A

Typically a second-price, sealed-bid auction

Protocol and outcome rule:

  • 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

22
Q

What’s the point behind second-highest bid (Vickrey auction)?

A

Helps to overcome the winner’s curse

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

23
Q

Why is First-price sealed-bid auction may not be efficient?

A

May not be efficient, since agent with the highest value may not win (they might not bid their highest true value because they’re worried of winner’s curse)

24
Q

Properties of ‘Vickrey auction’?

A
  • Efficient
  • Truth revealing
  • Hard for collusion to occur
  • Counter-intuitive for human bidders
  • Its computational simplicity makes it popular for use in multi-agent AI systems and online auctions
25
Q

Which auction type is preferred for multi-agent AI systems and online auctions? And why? What are the properties

A

Vickrey auction for its computational simplicity

  • Efficient
  • Truth revealing
  • Hard for collusion to occur
26
Q

What does eBay use for their auctions?

A

A mixture of English and Vickrey

  • Highest winning bid is sealed (vickrey)
  • Current second highest is public to help establish value of good (english)
  • Bidders can make multiple bids (english)
  • Deadline is used

Problem with eBay is sniping, this beats out the truth-revealing mechanism of Vickrey auctions since the private valuation of last moment bidders do not get a chance to be made public.

Amazon counters sniping by extending deadline whenever a bid is made within a certain time before the deadline.

COMP30024 Artificial Intelligence (10 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions