COMP30024 Artificial Intelligence
Week 9 Problem Sheet Solutions
• Tutors: These are not unique, complete (and definitely not optimally pedagogical) solutions. there are other ways of deriving these results and the way you prefer is to some extent an aesthetic judgement.
• Students: If you want to attain any benefit from the problems you should make a genuine attempt at them before you see the solutions.
Copyright By PowCoder代写 加微信 powcoder
Comments/corrections are as always greatly appreciated by the teaching team.
1. Auctions [T] Your class will conduct a set of in-class auctions to gain experience with each
type of action. The basic process is the following:
1. The auctioneer reveals the good to be auctioned.
2. You are given a card that indicates your redemption value (V ) of the good. You can think of this as your private value for the good.
3. Think of a rational bidding strategy for each type of auction. Record the bids made.
4. The auctioneer conducts the auction.
5. If you win the auction, you ’pay’ the auctioneer the appropriate amount based on the type of auction. Your profit/loss is P = V − W .
Follow the above process for (1) an English auction, (2) a Dutch auction, (3) a first-price, sealed-bid auction and (4) a second-price, sealed-bid auction. In the case of a sealed-bid auction, you should write your name and bid on a piece of paper, which is discreetly handed to the auctioneer.
(a) What strategy did you use in each auction?
(b) How did the amount paid to the auctioneer vary between auctions?
(c) How did the profit of the winning bidder vary between auctions?
Straightforward using definitions of auction types from lectures. Note in the Dutch and first- price sealed-bid auctions there is no dominant strategy. Bidder i has a private valuation vi but their optimal action depends on the private values of the other bidders, unknown to i. When the price reaches vi or below, the bidder must decide to bid and claim the item at a higher price than necessary, or wait and risk losing the item to another bidder. Their behaviour will depend on a probability model pi(v1, . . . , vn) over the private valuations of all n bidders.
This is similar to the first-price sealed-bid auction, where agents’ bids depend on estimation of the private valuations of other bidders.
2. Efficient Auctions [T] Argue that the optimal strategy for a participant in a sealed-bid, second-price auction is to bid at their private valuation.
• Assume player values item at value v and wants to maximize utility U = v − [Price Paid]. Let b be player’s bid and b′ be highest external bid.
• If b > v:
– b′ >b>v,equallygoodtobidvtoreceiveU=0.
– b>v>b′,equallygoodtobidvtoreceiveU=v−b′ >0.
–b>b′ >v. Win,butreceiveutilityU=v−b′ <0,soshouldhavebidv=bto receive U = 0.
• If b < v:
– b′ >v>b,equallygoodtobidvtoreceiveU=0.
– b′
– b
3. An Inconvenient Truth [T] The students in your tutorial tell the truth one third of the time. They lie with probability two-thirds. On an occasion, after the student to your right made a statement, you ask the student to your left ‘was that statement true?’ and they respond ‘yes’. What is the probability that the statement was indeed true?
Here you must distinguish between S, the random variable denoting whether or not the first student’s statement was true or false, with C, the random variable denoting what was said by the second student – ’true’ or ’false’. Note that C does not give the truth/falsity of the student’s second statement, but just indicates what they claim. We know from the definition of conditional probability
p(S = True,C = True) = p(S = True|C = True)p(C = True) = 19 From the law of total probability,
p(C = True) = p(C = True|S = True)p(S = True) + p(C = True|S = False)p(S = False) = 59 Hence p(S = True|C = True) = 15 .
4. Successive Wins [T] To encourage Emma’s promising tennis career, her father offers her a prize if she wins (at least) two tennis sets in a row in a three-set series to be played with her father and the club champion alternately: father-champion-father or champion-father- champion, according to Emma’s choice. The champion is a better player than Emma’s father. Which series should Emma choose?
Let pC be the probability that Emma beats the champion, and pF be the probability that Emmabeatsherfather,withpF >pC.Foreitheroption,thepossibleprize-winningsequences are either winning all three games, or winning the first pair or the last pair. For the first option, father-champion-father, these options yield a total probability of 2pF pC (1 − pF ) + p2F pC = pF pC (2 − pF ). For the second option, champion-father-champion, these options yield a total probability of pF pC (2 − pC ). Hence somewhat counterintuitively, Emma should choose the option where she plays the champion twice, as the importance of winning the middle game outweighs the disadvantage of playing the champion twice.
5. The Truel [T] A, B, and C are to fight a three-cornered pistol duel. All duelists are aware that A’s chance of hitting their target is 0.3, C’s is 0.5, and B never misses. A hit duelist loses further turns and is no longer shot at. They must fire at their choice of target in succession in the order A, B, C, cyclically until only one is left standing.
(a) What is the probability of A winning a duel with C, assuming C goes first?
Let At be the event that A is alive after t shots fired by A, then p(At) = (0.7)t × (0.5)t+1
and the probability that A wins is:
p(A wins) = p(A hits C|At)p(At) t=0
0.7t ×0.5t = 13 (b) Suppose A shoots at C first, what is the probability A wins?1
If A hits C, he will be certainly killed by B in the first round. The only possibility of
survival is to miss the shot to C. B kills the more dangerous C first, and A gets one
shot at B with probability p(A wins|C shot at) = 3 × 7 . 10 10
(c) Now suppose A shoots at B first, what is the probability A wins? Hence what is the optimal strategy for A?
If A hits B, the problem reduces to the A-C duel outlined in part (a). If A misses B, A waits for B to shoot C and hopes he doesn’t miss a second time…
1Note here that any player in a sequential truel maximizes their survival probability by firing at the more dangerous opponent, as the problem reduces to a duel if the shot connects, and it is always preferable to duel a weaker opponent.
p(A wins|B shot at) = p(A wins|B hit.B shot at)p(B hit|B shot at)
+ p(A wins|B not hit.B shot at)p(B not hit|B shot at)
= 3 × 3 + 3 × 7 = 363 > p(A wins|C shot at). 13 10 10 10 1300
(d) Suppose A can deliberately miss on the first shot, should they2?
Yes, because A hitting B and duelling C has less probability of A winning (3/13) than just missing the first shot (3/10) and gunning for B in the second round. So A deliberately misses and takes his chances with B in the next round. C is out of luck!
2Follow-up: is this an honourable course of action?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com