Project 1: Building a Second-Price Auction (Modeling and Strategy) You have been hired by a major retailer to develop al

[answerhappygod]

Project 1: Building a Second-Price Auction (Modeling andStrategy) You have been hired by a major retailer to developalgorithms for an online ad auction. Your client knows a littleabout the multi-armed bandit literature and recognizes that it canspend money to explore, learn how likely users are to click on ads,or to exploit, spending on the most promising users to maximizeimmediate payoffs. At the same time, there are other companiesparticipating in the auction that may outbid your client,potentially interfering with these goals. Your task is to model thead auction and develop an effective algorithm for bidding in alandscape of strategic competitors. Your client plans to test yourbidding algorithm against other bidding algorithms contributed byother data scientists, in order to select the most promisingalgorithm. The Auction Rules The Auction is a game, involving a setof Bidder s on one side, and a set of User s on the other. Eachround represents an event in which a User navigates to a websitewith space for an ad. When this happens, the Bidder s will placebids, and the winner gets to show their ad to the User . The Usermay click on the ad, or not click, and the winning Bidder gets toobserve the User 's behavior. This is a second price sealed-bidAuction . There are num_users User s, numbered from 0 to num_users- 1 . The number corresponding to a user will be called its user_id. Each user has a secret probability of clicking, whenever it isshown an ad. The probability is the same, no matter which Biddergets to show the ad, and the probability never changes. The eventsof clicking on each ad are mutually independent. When a user iscreated, the secret probability is drawn from a uniformdistribution from 0 to 1. There is a set of Bidder s. Each Bidderbegins with a balance of 0 dollars. The objective is to finish thegame with as high a balance as possible. At some points during thegame, the Bidder 's balance may become negative, and there is nopenalty when this occurs. The Auction occurs in rounds, and thetotal number of rounds is num_rounds . In each round, asecond-price auction is conducted for a randomly chosen User . Eachround proceeds as follows: 1. A User is chosen at random, with allUser s having the same probability of being chosen. Note that aUser may be chosen during more than one round. 2. Each Bidder istold the user_id of the chosen User and gets to make a bid. The bidcan be any non-negative amount of money in dollars. A Bidder doesnot get to know how much any other Bidder has bid. 3. The winner ofthe auction is the Bidder with the highest bid. In the event thatmore than one Bidder ties for the highest bid, one of the highestBidder s is selected at random, each with equal probability. 4. Thewinning price is the second-highest bid, meaning the maximum bid,after the winner's bid is removed, from the set of all bids. If themaximum bid was submitted by more than one bidder then the secondprice will be the maximum bid. For example, if two bidders bid 2and no one else bids higher then 2 is the winning price. 5. TheUser is shown an ad and clicks or doesn't click according to itssecret probability. 6. Each Bidder is notified about whether theywon the round or not, and what the winning price is. Additionally,the winning Bidder (but no other Bidder ) is notified about whetherthe User clicked. 7. The balance of the winning Bidder is increasedby 1 dollar if the User clicked (0 dollars if the user did notclick). It is also decreased by the winning price (whether or notthe User clicked). This is also described in the sequence diagramat the bottom of this document which helps visualize the process ofa single round Architecture You are asked to design the followingclasses: A User class that includes: an initializer method with thedefinition def __init__(self) . a private __probability attributeto represent the probability of clicking on an ad. When a user iscreated, the secret probability is drawn from a uniformdistribution from 0 to 1. (Please use the random or numpy.randommodules) a show_ad method with the definition def show_ad(self)that represents showing an ad to this User . This method shouldreturn True to represent the user clicking on and ad and Falseotherwise. A Bidder class that includes: an initializer with thedefinition def __init__(self, num_users, num_rounds) , in whichnum_users contains the number of User objects in the game, andnum_rounds contains the total number of rounds to be played. TheBidder might want to use this info to help plan its strategy. a bidmethod with the definition def bid(self, user_id) , which returns anon-negative amount of money, in dollars. a notify method with thedefinition def notify(self, auction_winner, price, clicked) , whichis used to send information about what happened in a round back tothe Bidder . Here, auction_winner is a boolean to represent whetherthe given Bidder won the auction ( True ) or not ( False ). priceis the amount of the second bid, which the winner pays. If thegiven Bidder won the auction, clicked will contain a boolean valueto represent whether the user clicked on the ad. If the givenBidder did not win the auction, clicked will always contain None .An Auction class that includes: an initializer with the definitiondef __init__(self, users, bidders) . Here, users is expected tocontain a list of all User objects. bidders is expected to containa list of all Bidder objects. an execute_round method with theheader def execute_round(self) . This method should execute allsteps within a single round of the game. a balances attribute,which contains a dictionary of the current balance of every Bidder. (optional - not graded) a plot_history method with the definitiondef plot_history(self) , which creates a visual representation ofhow the auction has proceeded. It is up to you do decide what thegraphic looks like, and this method is meant to help you assess howyour algorithm is performing. Note: You can use the python standardlibrary, numpy, matplotlib or seaborn only. The autograder can'tinstall matplotlib or seaborn so please comment out / delete thoseimports and the plot_history method on your submission. Warning:You may create additional attributes beyond those described above.However, during the competition and in testing your code, yourclasses will interact with those written by the instructors, sothey can only interact through the methods listed above. Forexample, if you write your own Auction.get_user method and call itfrom your Bidder , that will cause an error when we test yourBidder against the instructor Auction . Deliverable You shouldsubmit two files both on gradescope and to your github repo. Titledauction_.py and bidder_.py : auction_.py should include the classdefinition of Auction and the class definition of User and nothingelse. bidder_.py should include the class definition of Bidder andnothing else.