Graduate Artificial Intelligence 15-780Homework 6: Automated Mechanism Design⊗An optional homework, for extra homework credit only.Out on April 26Due on May 5Homework 6 Graduate Artificial Intelligence 15-780First, we’re going to need to review some game theory concepts. In the simple auction setting, an agent’stype simply corresponds to their value for the item. We denote the type of agent i as θi∈ Θi.A (single-item) auction works by receiving a vector of type reports (θ1, . . . , θn) ∈ Θ1× · · · × Θnfromthe n agents, and producing an allocation aiand payment πifor each agent, where aiis binary and πiisnon-negative. We can add an extra agent 0 to denote the seller keeping the item; if a0= 1 the item isunallo c ated. In a single-item auction, the aimust be allocated exactly once:Xiai= 1The expected revenue of an auction is just the expectation taken over the payments π.Agent i’s utility is given by the difference between their value for their allocation and the price they payui= aiθi− πiSince the auction mechanism determines aiand πifrom the type reports, we can abuse notation anddefineui(θ,~θ−i)as agent i’s utility from reporting θ when the other agents report~θ−i.Throughout this problem, we will assume that the probability distribution over true types is commonknowledge, known to all agents and the auctioneer.Now we can define various properties of an auction.Definition. An auction is efficient if it always allocates the good to the agent that reports the highest type.Formallyai= 1 −→ θi= maxjθjDefinition. An auction is individually rational if an agent is never charged more than their value for theallocation they receive. Formally, for all agents i, all true types θi, and all set of other type reports~θ−iui(θi,~θ−i) ≥ 0Definition. An auction is truth promoting in dominant strategies for agent i if that agent is never incen-tivized to misreport their true type. Formally, for all true types θi, all other reports of agents~θ−i, and allmisreported typesˆθui(θi,~θ−i) ≥ ui(ˆθ,~θ−i)if this holds for all agents, it is a dominant strategy equilibrium (DSE).We can also relax DSE, so that agents are only incentivized to report truthfully in expectation over thereports of the other agents.Definition. An auction is truth promoting in expectation for agent i if that agent is never incentivized inexpectation to misreport their true type. Formally, for all true types θiand all misreported typesˆθE~θ−iui(θi,~θ−i) ≥ E~θ−iui(ˆθ,~θ−i)where the expectation is taken over the type reports of the other agents. If this holds for all agents, it is aBayes-Nash equilibrium (BNE).Observe that DSE is strictly stronger than BNE.The key insight of automated mechanism design is that all of these properties can be embedded into aMIP in a straightforward fashion. Consider, for instance, how to embed the individual rationality constraintsPage 1 of 2Homework 6 Graduate Artificial Intelligence 15-780into a MIP. Let a~θibe a binary representing whether agent i is allocated the item when the agents reporttypes~θ, and let π~θisimilarly represent the payment of agent i for that report. Then for every agent i, everytrue type θ ∈ Θi, and every agent type report~θ the following relation must hold:θa~θi− π~θi≥ 0As another example, it is possible to mandate efficiency just by hardcoding in the proper values for thea~θivariables (to select the agent with the highest valuation).Problem 1: Auction Design (60 points)A plutocrat football-team owner has installed a massive luxury suite in his new stadium. In this problem,you will use your knowledge of game theory and mixed-integer programming to get him the highest dollarfor season tickets to his luxury suite by designing an optimal auction.Here, there are three possible agents interested in the tickets, each of whom has one of two possiblevaluations:a) The Advertising Executive. He’s got a reasonable shot at needing to entertain a big account. He valuesthe tickets at 400 thousand dollars with probability 1/4, and values the tickets at 100 thousand withprobability 3/4.b) The Lumber B aron. Being a comfortable and secure captain of industry, he is relatively comfortableand secure in his valuations. He values the tickets at 300 thousand or at 250 thousand, each withprobability 1/2.c) The Disgraced C EO. He’s currently facing federal charges, but there’s a small chance he could wigglehis way out of liability. He values the tickets at 500 thousand dollars with probability 1/6, and valuesthe tickets at 75 thousand with probability 5/6.All values for the agents are drawn independently. Agents know their own valuations, and the probabilitiesof agents having their valuations are common knowledge, including common knowledge to the auctioneer.Therefore, the revenue-maximizing auction maximizes revenue in expectation.• Write out and solve the MIP corresponding to the revenue-maximizing, individually-rational, efficient,truth promoting in DSE auction. That is, describe the allocations and payments for all 8 possibleinputs.• Solve for the revenue-maximizing, individually-rational auction that truth promotes in DSE. What isthe expected revenue? How often are the tickets not sold to the highest bidder? How often are thetickets not sold at all? (Recall that you can model the tickets not being sold by introducing a dummyagent.)• Solve for the revenue-maximizing, individually-rational auction that truth promotes in BNE. What isthe expected revenue? How often are the tickets not sold to the highest bidder?• Write out a MIP for the expected revenue of the revenue-maximizing, individually-rational auction thatis truth-promoting in BNE, subject to the tickets being sold to the highest bidder (i.e., the auctionbeing efficient) with probability at least p. Plot expected revenue against p ∈ [0, 1].Page 2 of
View Full Document
Unlocking...