Valuation Uncertainty and Imperfect Introspection in Second-Price Auctions by David Robert Martin Thompson A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science in The Faculty of Graduate Studies (Computer Science) The University of British Columbia July, 2007 © David Robert Martin Thompson 2007 Abstract In auction theory, agents are typically presumed to have perfect knowledge of their valuations. In practice, though, they may lace barriers to this knowledge due to trans-action costs or bounded rationality. Modeling'and analyzing such settings has been the focus of much recent work, though a canonical model of such domains has not yet emerged. We begin by proposing a taxonomy of auction models with valuation un-certainty and showing how it categorizes previous work. We then restrict ourselves to single-good sealed-bid auctions, in which agents have (uncertain) independent private values and can introspect about their own (but not others') valuations through possibly costly and imperfect queries. We investigate second-price auctions, performing equi-librium analysis for cases with both discrete and continuous valuation distributions. We identify cases where every equilibrium involves either randomized or asymmetric in-trospection. We contrast the revenue'properties of different equilibria, discuss steps the seller can take to improve revenue, and identify a form of revenue equivalence across mechanisms. A version of this document has been accepted for publication. Thompson. 13.R.M, and Lcyton-IJrown. K. (2007) Valuation Uncertainty and Imperfect Introspection in Second-Price Auctions. / \ / \ /U iii Table of Contents Abstract ii Table of Contents iii List of Figures v List of Tables ' vi Acknowledgements N ' i i Dedication viii 1 Introduction 1 2 Foundations: Decision Theory and Game Theory 2 2.1 Decision Theory 2 2.2 Normal Form Games 4 2.3 Extensive Form Games 1 2.4 Bayesian Games 8 3 Foundations: Mechanism Design and Auction Theory 13 3.1 Social Choice . 13 3.2 Mechanism Design 13 3.3 Auction Theory 16 4 Deliberative Agents 19 4.1 Terminology _ 19 4.2 Taxonomy : 20 4.3 Previous work • 21 5 Our Model 24 6 Second price auctions 26 6.1 Costly Introspection 26 6.2 Limited Introspection 31 7 Revenue relationships and bounds 33 Table of Contents 8 Conclusion 37 Bibliography 38 List of Figures 2.1 The probability of possible worlds in the umbrella game 3 2.2 The utility of outcomes in the umbrella game 3 2.3 Rock, Paper, Scissors as a normal form game . . 5 2.4 The Prisoners' Dilemma 5 2.5 Two cars approaching a blind intersection as a normal form game . . . 7 2.6 The cake-cutting game 7 2.7 "Three-card Monte" game 8 2.8 The cake-cutting game in induced normal form .8 2.9 "Three-card Monte" in induced normal form 9 2.10 Stock market game 9 2.11 Market spying game 10 2.12 Stock market game in induced normal form II 2.13 Market spying game in induced normal form II 3.1 The revelation principle . 15 5.1 Induced valuation distribution of an introspection 25 6.1 Induced normal-form game for two bidders who have valuations of 0 or 1 26 6.2 Expected revenue under pure and mixed strategies 29 6.3 Probability of ex post perfect efficiency under pure and mixed strategies 30 6.4 Induced normal form of the 2-biclcler limited deliberation case . . . . 32 vi List of Tables 4.1 The features of our taxonomy 20 4.2 Classification of previous work on deliberative agents 22 Acknowledgments First and foremost, I am indebted to my supervisor, Kevin Leyton-Brown, for his teach-ing, inspired ideas and guidance, for pushing me when 1 would have stalled and for sticking around through the night for those early morning paper deadlines. My UBC professors and peers have taught me more than 1 ever thought 1 was capable of learning. Nando de Freitas (my second reader), Erik Zawadzki, Albert Xin Jiang, Baharak Rastegari and Jennifer Tillett all deserve special mention for their help with this work (and for listening to my same talk over and over again). Many people in the larger research community have given me support and con-structive feedback, especially Jason Hartline, Michael Rothkopf, Eric Rasmusen, Kate Larson, Tuomas Sandholm and Liad Blumrosen. 1 am grateful to all of the professors and students at University of Guelph that helped to give me a start in A.I. and research: David Calvert, Deborah Stacey, Gary Grevval, Finnegan Southey and everyone else in GNCG and M P C 2 . I want to thank all my friends and family, for their love and understanding, with special mention to everyone in and around "Guelphtown", for making Vancouver feel like home: Tristram, Qixing, Dawn, McLean, Chau, Jason. Matt, Stacey, Sneha, Brook and Michelle. Finally, a big "thank you" to Fern, for being awesome. viii Dedication To my father Bill, for all the years of unwavering, quiet support and to my mother Ruth, for the life-lessons that I'll always carry. I Chapter 1 Introduction Imagine deciding to bid for a particular car at an auction, and trying to determine what price you would be prepared to pay. You would probably start out very uncertain—is the new car worth more than $10,000? $15,000? $18,526? You would probably have actions available to you that could increase your level of certainty, such as test driving the car, checking online reviews, and so on. But these actions would consume quite a lot of effort: pretty quickly you might feel compelled to make up your mind one way or the other, even if you were not yet entirely certain of your valuation. Similarly, imagine the problem of submitting a bid on behalf of your new startup company in an online advertisement auction. The value of a customer's click on your ad would not be obvious: at the moment of creating the ad you might not yet have accurate information about demographics, conversion rates, and so on. As before, it would be possible to collect additional information that would allow you to make a better decision; also as before, the cost of gathering such information would probably lead you to submit your bid even despite some residual uncertainty about your valuation. Both of these scenarios illustrate a fact that most canonical models of auctions fail to capture: bidders are often uncertain about their own valuations. While it is often possible for bidders to introspect, or otherwise gather information, in order to reduce this uncertainty, doing so is costly. Furthermore, such introspection is usually imperfect, in the sense that it does not entirely eliminate uncertainty. Bidders must be prepared to place bids despite residual uncertainty. In this paper, we explore the problem of building formal game-theoretic models to describe such settings. In what follows, we will begin by describing the essential concepts from game the-ory and auction theory that our results are based on. We define terminology and then offer a taxonomy of auction models in which bidders are uncertain about their valua-tions. We use this taxonomy to survey related work from the literature. We propose a novel auction model that aims to capture settings like those described above. Apply-ing this model to the special case of second-price auctions, we offer several theoretical results, identifying equilibria and making revenue comparisons. 2 Chapter 2 Foundations: Decision Theory and Game Theory Decision theory and game theory are essential for discussing the behavior of agents in auctions. Decision theory is the study of how to make decisions optimally. Game theory extends this to strategic interactions (i.e. situations where there are multiple participants, each of which has an interest in and influence over the outcome). 2.1 Decision Theory Decision theory studies how to behave optimally in systems with only a single partic-ipant. We will describe these systems in the simplest terms possible while introducing the concepts of agents, utility, rationality, policy and value of information. Although there is no universal consensus on the exact definition of an agent, we will use a simple definition compatible with most work in game theory: Definition 1 (Agent) An agent (or player) is an entity that lias preferences over the states of a system and can act to influence those states. Throughout decision theory and game theory, these preferences are defined in terms of von Neumann-Morgenstern utility theory. We will restrict'ourselves to the case of finite decision systems (i.e. systems that are guaranteed to terminate and for which the end-state is a sufficient statistic for any sequence of intermediate states). Definition 2 (Outcome) An outcome is any end-state of the system. Definition 3 (Lottery-) A lottery is a distribution over outcomes (and is itself an. out-come for thejmrpose of preference modeling). Using outcomes and lotteries as our formalism for. the events that the agent has preferences over, we can clarify how we model preferences: Definition 4 (Utility) Utility is a real-valued quantity measuring an agent's happi-ness. Definition 5 (Utility function) A utility function is a mapping from outcomes to utili-ties. The agent is indifferent between outcomes with equal utilities and strictly prefers outcomes with higher utilities. Chapter 2. Foundations: Decision Theory and Game Theory 3 Weather Forecast Probability Rain Rain 0.4 Rain Clear 0.1 Clear Rain 0.1 Clear Clear 0.4 Figure 2.1: The probability of possible worlds in the umbrella game. Weather Umbrella Utility Rain True 2 Rain False 0 Clear True 4 Clear False 5 Figure 2.2: The utility of outcomes in the umbrella game. Von Neumann and Morgenstern showed that for any "reasonable" (subject to com-pleteness, transitivity, substitutability, decomposability, monotonicity and continuity) set of preferences there is a utility function such that the agent's utility for any lottery is the expectation of their utility over the outcomes. Definition 6 (Rationality) A rational agent is an agent that acts to maximize its ex-pected utility. Example 7 (Umbrella game) Consider the problem of whether to bring an umbrella out given the weather forecast. We can express the probability of possible worlds and the utility of different outcomes in tabular form. (See Figures 2.1 and 2.2.) The above example illustrates some important points about decision theory. The agent does not have absolute control or complete information. He must use the infor-mation available to respond to circumstances outside his control. Definition 8 (Policy) A policy is a mapping front available information to actions. Definition 9 (Optimal policy) An optimal policy is a policy that maximizes expected utility.. Example 10 (Optimal policy of the umbrella game) The optimal policy of this game is to bring an umbrella only when the forecast calls for rain, which gives an expected utility of 0.4 * 2 + 0.1 * 0 + 0.1 * 4 + 0.4 * 5 = 3.2. One other concept that is particularly relevant to our work is value.of information. Definition 11 (Value of information) The value of a piece of information is the dif-ference in expected utilities of the optimal policies with and without that piece of infor-mation. Chapter 2. Foundations: Decision Theory and Game Theory 4 Example 12 (Umbrella game) The optimal policy given knowledge of the weather is to bring an umbrella when it is going to rain, which gives an expected utility of 0.4 * 2 + 0.1 * 2 + 0.1 * 5 + 0.4 * 5 = 3.5. Thus, the value of information for the weather is 3.5-3.2=0.3. 2.2 Normal Form Games Game theory extends decision theory to the case where there are multiple agents influ-encing the outcome. One fundamental assumption of game theory is that all agents are rational and aware of each other's rationality (and aware of each other's awareness of their rationality, and so on). Normal form games are a canonical representation of one of the simplest forms of interaction studied in game theory, where every agent acts simultaneously with no information about the other agents' behaviors. Because every agent has an influence over the outcome, it is useful to talk about their behavior in aggregate: Definition 13 (Action profile) An action profile is a vector of actions, one per agent in the system. Definition 14 (Strategic equivalence) Two games are strategically equivalent if there is a mapping between pure strategies in each game where for any strategy profile in either game, there is a corresponding strategy profile in the other game that yields exactly the same expected utility for every player. Because of strategic equivalence, when analyzing games we frequently omit the outcomes and map directly from action profiles to utilities: Definition 15 (Game) A game is a system that has a set of agents, each of which has a set of actions and a utility function over action profiles. Definition 16 (Normal form game) A normal form game is a tabular representation of a game. In the two-dimensional case (i.e. for two agents) the first agent chases the row while the second choses the column. Each cell contains a vector of utility values, one per player. Two classic examples of normal form games are Rock, Paper, Scissors and the Prisoner's Dilemma: Example 17 (Rock, Paper, Scissors) Consider the game of rock, paper, scissors. Both players simultaneously choose rock, paper or scissors. Rock beats scissors, scissors beat paper and paper beats rock. The normal form game is in Figure 2.3. Example 18 (Prisoner's Dilemma) Two prisoners are being questioned separately for the same crime. If they cooperate with each other and say nothing to the police, each will receive a short sentence. If one criminal turns in the other, he will be set free (while the other gets the worst possible sentence). If they both turn in each other, they will each receive a moderate sentence. (See Figure 2.4.) Chapter 2. Foundations: Decision Theory and Game Theory 5 Rock Paper Scissors Rock 0,0 -1,1 1,-1 Paper 1,-1 0,0 -1,1 Scissors - u 1,-1 0,0 Figure 2.3: Rock, Paper, Scissors as a normal form game Cooperate Defect Cooperate Defect 3,3 0,5 5,0 1,1 Figure 2.4: The Prisoners' Dilemma Intuitively, we would not want to deterministically play one action in rock, paper, scissors. We capture a richer set of options by allowing for strategies with an element of randomness. Definition 19 (Pure strategy (normal form game)) A pure strategy for a normal form game is a single action. Definition 20 (Mixed strategy) A mixed strategy is a probability distribution over pure strategies. Definition 21 (Support) The support of a. mixed strategy is the set of pure strategies that have non-zero probability. As with actions, it is useful to talk about agents' strategies in aggregate. Definition 22 (Strategy profile) A strategy profile is a vector of strategies, one per agent. Unlike decision theory, there is not necessarily an optimal policy. Whether or not an agent maximizes his utility by playing a particular strategy will depend on the behavior of the other agents. Definition 23 (Best response) A best response is a strategy (pure or mixed) which maximizes the agent's expected utility given the strategies of all the other agents. Chapter 2. Foundations: Decision Theory and Game Theory 6 Best response can be weak or strict, depending on whether the expected utility is weakly or strictly maximized. (A mixed strategy cannot be a strict best response because it cannot be better than any action in its support.) Definition 24 (Dominant strategy) A dominant strategy is a strategy that is a best response regardless of the strategies of the other players. A dominant strategy is strict if it is always strictly a best response, semi-strict if it is sometimes a strict best response and weak otherwise. With these concepts, we can finally define some "solution concepts" for normal form games. These are stable configurations of the game. Definition 25 (Nash equil ibrium) A Nash Equilibrium is ct strategy profile where ev-ery agent is playing a best response to the actions of the others. We can characterize a Nash equilibrium as being a pure-strategy or mixed-strategy equilibrium. It is also useful to distinguish equilibria in dominant strategies. Definition 26 (Finite game) A finite game is a game where the sets of agents and ac-tions are finite. Theorem 27 (Nash (1950)) Every finite game has at least one Nash equilibrium. Example 28 (Nash equi l ibr ium of Rock, Paper, Scissors) The unique Nash equilib-rium of rock, paper scissors is to play a mixed strategy which assigns each action equal probability. Example 29 (Nash equi l ibr ium of Prisoner 's Dilemma) The unique Nash equilibrium of the prisoner's dilemma is for both agents to defect. Definition 30 (Symmetric game) A symmetric game is one where all the agents have identical action sets, and for any strategy profile exchanging the actions of any two agents exchanges their expected utilities. Nash showed that every symmetric game has a symmetric equilibrium (i.e. one where every agent chooses the same strategy), though it can also have asymmetric-ones. Definition 31 (Correlated equil ibrium) /// a correlated equilibrium, each agent gets a signal that tells them which pure strategy to play (with these signals being correlated). Given the joint distribution over signals, each agent's pure strategy is a best response to the distribution over other agents' pure strategies. . Correlated equilibria allow agents to coordinate to asymmetric Nash equilibria and to arrive at different distributions of expected utility among the agents. Example 32 (Traffic game) Consider the problem of two cars approaching a blind intersection. Drivers that stop will he slightly delayed. However, if they both enter the intersection without stopping, they will collide. (See Figure 2.5.) The only symmetric Nash equilibrium of the traffic game is for each agent to wait with probability 10/11, which only gives them an expected utility off). By a correlated signal (traffic lights), they can mix between (Go, Wait) and (Wait,Go) outcomes with no risk of miscoordinating and colliding. Chapter 2. Foundations: Decision Theory and Game Theory 1 Go Wait -10,-10 1,0 0.1 0,0 Figure 2.5: Two cars, approaching a blind intersection as a normal form game i (0.25,0.75) (0.75,0.25) (0.07,0.33) ' (0.33,0.07) (0.5,0.5) (0.5,0.5) Figure 2.6: The cake-cutting game 2.3 Extensive F o r m Games Extensive form games allow us to model sequential settings. In many real-world strate-gic interactions, agents get to observe each other's behavior over time and condition their strategies on previous observations. Some examples include chess, tic-tac-toe and go. Definition 33 (Perfect information extensive form game) Perfect information exten-sive form games are games in tree representation where every inner node represents a choice by a single agent, with the out-edges of the node being the possible actions. Each leaf node is an outcome labeled by a vector of utilities (one per agent). Example 34 (Cake-cutting) Consider the problem of two agents trying to share a cake. First one agent choses what ratio of pieces to cut the cctke into, then the sec-ond agent can choose which piece to take. (See Figure 2.6.) We can further generalize extensive form games to cover settings where the agents have less than perfect observations of each other's behavior. Definition 35 (Imperfect information extensive form game) Impeifect information extensive form games are extensive form games where the agent cannot distinguish two or more choice nodes (those nodes are said to belong to an equivalence set). Example 36 ("Three-card Monte") Consider the problem of two agents playing a card game. The first agent arranges three cards face down (one of which is the queen). The second agent wins if he can guess which card is the queen. (See Figure 2.7.) Chapter 2. Foundations: Decision Theory and Game Theory 8 ( -1 :0 ( 0 - 0 (0-1) ( O - O ( -1 :0 ( 0 - 0 (0-1) ( 0 - 1 ) ( -1 , 0 Figure 2.7: "Three-card Monte" game b. b. b b. b. s b. s. b b. s. s s. b. b s. b. s s. s. b ,s. s. s 0.25.0.75 0.25.0.75 0.25.0.75 0.25.0.75 0.25.0.75 0.75.0.25 0.75.0.25 0.75.0.25 0.75.0.25 0.33.0.67 0.33.0.67 0.33,0.67 0.67.0.33 0.67.0.33 0.33.0.67 0.33.0.67 0.67.0.33 0.67.0.33 0.5.0.5 0.5.0.5 0.5.0.5 0.5,0.5 0.5.0.5 0.5.0.5 0.5.0.5 0.5.0.5 0.5.0.5 Figure 2.8: The. cake-cutting game in induced normal form • Definition 37 (Pure strategy (extensive form game)) /\ pure strategy for an exten-sive form game is a mapping from nodes or equivalence sets to actions {analogous to a policy in decision theory.) Definition 38 (Induced normal form (extensive form game)) We can convert an ex-tensive form game into a normal form game (called the "induced normal form ") where the normal form game's actions are pure strategies in the extensive form game. The payoffs in the normal form game are taken front the leaf-node reached by following those strategies. Because every extensive form game has a corresponding induced normal form game, it must have a Nash equilibrium (by Theorem 27). The induced normal forms of the cake-cutting game and Three-card Monte are in Figures 2.8 and 2.9 respectively. 2.4 Bayes ian Games Often, strategic interactions involve some notion of random events and private infor-mation. We model these using Bayesian games. Many card games (for example, poker) are instances of this type of interaction. Definition 39 (Type) An agent's type is a complete representation of his private infor-mation. 0 Chapter 2, Foundations: Decision Theory and Game Theory 1 m i' -1,1 1,-1 1,-1 1,-1 -1,1 1,-1 -1,1 -1,1 -1,1 Figure 2.9: "Three-card Monte" in induced normal form Buy Sell Rise (p = 0.5) B l | y 1,1 2,0 Sell 0,2 -1,-1 Buy Sell Fall (p = 0.5) B u v -1,-1 0,2 Sell 2,0 1,1 Figure 2.10: Stock market game Definition 40 (Type profile) A type profile is a vector of types, one per agent. One simple but powerful way to represent Bayesian games is to say that the agents have different information about which normal form game they are actually playing. Definition 41 (Bayesian game) A Bayesian game is a set of players, each of which has a set of types, a set of actions and a utihty function mapping action and type profiles to utility. A Bayesian game also includes a distribution over type profiles. Example 42 (Stock market game) Two investors must decide whether to sell off their stocks in a particular company or to buy more. Agent one has insider information and can correctly predict whether the price will rise or fall in the short term while agent two cannot. If both agents buy or sell it will have a significant, temporary impact on the stock's price. (See Figure 2.10.) As with decision theory and extensive form games, agents condition their behavior on the available information: Chapter 2. Foundations: Decision Theory and Game Theory 10 (2.(1) (11.2) ( - 1 . - 1 ) ( - 1 . - 1 ) (11.2) Figure 2.11: IVIarket spying game Definition 43 (Pure strategy (Bayesian game)) A pure strategy in a Bayesian game is a function mapping from type to action. An alternative way of representing Bayesian games is to model them as extensive form games where one of the agents is actually a random process (with all the real agents having full common knowledge of the probabilities): Definition 44 (Bayesian game (extensive form representation)) The extensive form representation of a Bayesian game augments a conventional imperfect information ex-tensive form game with "chance nodes" where each branch is chosen according to some (commonly known) probability. Extensive form representations of Bayesian games have the same pure strategy space as regular extensive form games. Example 45 (Market spying game) Consider the same problem as the Market game, except that agent one cannot buy or sell stock without agent two finding out. (See Figure 2.11.) Definition 46 (Induced normal form (Bayesian game)) The induced normal form of a Bayesian game is a normal form game where each action is a pure strategy in the Bayesian game. The values in the cells of the table are filed in by computing the ex ante expected utility of each pure strategy prof le. When discussing the properties of Bayesian games, the amount of information available must be defined (particularly when taking expectations). We characterize this by the terms ex ante, ex interim and ex post. Definition 47 (Ex ante) Ex ante refers to situations where no agent's type is fixed or known. Definition 48 (Ex interim) Ex interim refers to situations where exactly one agent's type is known. Definition 49 (Expost) Ex ante refers to situations where all agent's types are known. Chapter 2. Foundations: Decision Theory and Game Theory Buy Sell Buy, Buy 0,0 1,1 Buy, Sell 1.5,0.5 1.5,0.5 Sell, Buy -0.5,0.5 -0.5,0.5 Sell, Sell 1,1 0,0 Figure 2.12: Stock market game in induced normal form Buy, Buy Buy, Sell Sell, Buy Sell, Sell Buy, Buy 0,0 0,0 1,1 1,1 Buy, Sell 1.5,0.5 I.I 2,0 1.5,0.5 Sell, Buy -0.5,-0.5 - U 0,2 -0.5,0.5 Sell, Sell 1,1 U 0,0 0,0 Figure 2.13: Market spying game in induced normal form Chapter 2. Foundations: Decision Theory and Game Theory 12 Using these terms, we can discuss how strong an equilibrium is terms of available information: Definition 50 (Ex interim Hayes Nash equilibrium) An ex interim Bayes Nash equi-librium is a strategy profile where every agent's strategy maximizes his ex interim ex-pected utility, for every type he can have. The Nash equilibrium of the induced normal form must be (at least) an ex interim Bayes Nash equilibrium in the corresponding Bayesian game. Because of this (and Theorem 27), at least an ex interim Bayes Nash equilibrium exists in any game. Definition 51 (Ex post Bayes Nash equilibrium) An ex post Bayes Nash equilibrium is a strategy profile where every agent's strategy maximizes his utility for any type profile. Ex post BayesNash equilibrium is a stronger condition than ex interim Bayes Nash equilibrium in that it requires that even if an agent were to learn the types of all the other agents, he would not prefer to change his strategy. Bayesian games can also have equilibria in dominant strategies. Chapter 3 13 Foundations: Mechanism Design and Auction Theory 3.1 S o c i a l C h o i c e Social choice is the study ol preference aggregation: given that many agents have dif-fering preferences over outcomes, how can we combine those preferences in a way that has desirable properties like fairness or optimality? Voting systems are the canonical example of this. Essentially, a social choice function picks an outcome given all the agents' preferences. Definition 52 (Social choice function) A social choice function is a mapping from the preferences of a set of agents to an outcome. Although social choice is a rich field, social choice functions are the only concept we need to introduce from this field in order to discuss mechanism design. 3 . 2 M e c h a n i s m D e s i g n Mechanism design is the inverse problem to game theory. Rather than trying to ana-lyze how agents will want to behave in a given system, mechanism design attempts to make systems where a desirable outcome is researched, given that agents will behave strategically and have types unknown to the mechanism designer. Definition 53 (Mechanism) A mechanism is a set of actions for each agent, and ct mapping from action profiles to outcomes. A mechanism, combined with a set of agents with possible types and utility func-tions, and a distribution over type profiles, results in a Bayesian game. Definition 54 (Implementation) For every type profile, under equilibrium the agents-will play some strategy profile, and given that strategy profile, the mechanism will choose the corresponding outcome. Thus, there is a mapping from type profile to out-come: a social choice function. We say that the mechanism implements this social choice function. We can characters the strength of an implementation, as Bayesian (ex interim), ex post or dominant strategies, depending on what kind of equilibria the induced Bayesian game has. Chapter 3, Foundations: Mechanism Design and Auction Theory 14 Definition 55 (Mechanism design) Mechanism design is the study of how to design a mechanism that implements a desired social choice function. The space of possible mechanisms that can implement a given social choice func-tion is extremely large. In mechanism design, we frequently ourselves to the space of direct, truthful mechanisms as this restriction is without loss of generality. Definition 56 (Direct) A mechanism is direct, if for every agent the set of actions is the set of types, i.e. the agents can directly reveal their types. Definition 57 (Truthful (or incentive compatible)) A direct mechanism is truthful, if in equilibrium, every agent prefers in reveal his true type. Theorem 58 (Revelation principle) //' a social choice function can be implemented with a given strength, it can be implemented with that same strength by a direct truthful mechanism. Proof. Given any equilibrium of any mechanism, we can construct a set of proxies (as part of a new mechanism) that act on behalf of the agents. These proxies take their agent's type as an input and then follow the equilibrium strategy for that type. If some agent prefers to deviate from truthfully revealing his type, that implies that the original equilibrium was not actually an equilibrium. (See Figure 3.1.) • There are many criteria, that are desirable to meet when designing a mechanism. The designer frequently wants to maximize revenue or social welfare, or satisfy con-straints such as budget balance and individual rationality. Definition 59 (Social welfare) Social welfare is the sum of all agents' utilities for the outcome. Definition 60 ((Economic) efficiency) A mechanism is (economically) efficient if in equilibrium, social welfare is maximized. Definition 61 (Transferable utility) A setting supports transferable utility if there is some transferable, continuously-divisible commodity (for example, money) where for any transfers between a pair of agents, the sum of their utilities is preserved. Definition 62 (Revenue) Revenue is the amount of utility transfered to the mechanism. Definition 63 (Budget balance) A mechanism is budget balanced if expected revenue is zero, or weakly budget balanced if the expected revenue is weakly greater than zero. Budget balance can be ex ante or ex post, depending on how much information is known when computing expected revenue. Definition 64 (Individual rationality) A mechanism is individually rational if every agent's expected utility is weakly greater than zero. Individual rationality can be ex ante, ex interim or ex post, depending on how much information the agent has when computing his expected utility. Chapter 3. Foundations: Mechanism Design and Auction Theory Type .Type Agent 1 Original Strategy 1: Action = f1(Type)J Agent 2 Original ^ Strategy 2: Action = f2(Type), Action Action _Ty_pe Type Agent 1 Strategy 1: Action = Type Agent 2 Strategy 2: Action = Type Direct Truthful Mechanism Proxy 1 i f Original .Type y\ . Strategy 1: ^Action = fl (Type)j Action Type Proxy 2 I ^ Original ^ r > Strategy 2: Action r ^Action = f2(Type)j i Figure 3.1: The revelation principle Chapter 3. Foundations: Mechanism Design and Auction Theory 16 Definition 65 (Groves mechanism) The Groves mechanism is a direct mechanism where an efficient outcome is chosen given the declared types of all the agents. Each agent also receives a transfer from the mechanism equal to the sum of the utilities of every other agent for the chosen outcome. Each agent can he charged a tax. but this tax cannot depend on his declared type. The Groves mechanism is efficient and dominant strategy truthful. However it can involve the mechanism making large payouts. Definition 66 (Clarke tax) The Clarke tax is a tax that can be used in a Groves mech-anism. With a Clarke tax, each agent must pay an amount equal to the social welfare generated by the mechanism if he had not been present, given the declared types of all other agents. The Clarke tax allows the Groves mechanism to be weakly budget balanced in cases where no agent has a negative utility for any outcome. The combination of a Groves mechanism with a Clarke tax is called the Vickiey-Clarke-Groves mechanism (or VCG), because it is a generalization of the Vickrey auction (see below in Definition 69). 3.3 Auction Theory Auction theory is the specialization of mechanism design to the problem of dividing up limited resources, ln addition "to studying conventional auctions, auction theory has been applied to problems like job markets, campaign finance and arms races. Throughout, we will make a number of assumptions that are common, but not universal in auction theory. First, we will assume that the auction is selling a single in-divisible good. Second, we will assume that there are no "externalities" (i.e. no agent has any positive or negative utility for anything that happens to the other agents and that does not affect him directly). With these assumptions and the assumption of trans-ferable utility, we can massively simplify our representation of an agents preferences. Definition 67 (Valuation) An agent's valuation is the maximum amount that he would be willing to pay for a good. Sealed-bid auctions are a special case of auctions where agents send a single pri-vate bid to the seller, and receive no information from the seller or the other agents. (Typically, an agent's type and bid can both be a single monetary value, making sealed bid auctions the equivalent of direct mechanisms.) This seems extremely limited, but there are a variety of sealed-bid auctions for single goods. Definition 68 (First-price auction) A first-price auction is a sealed-bid auction where the agent with the highest bid wins the good and must pay the amount he bid. Definition 69 (Vickrey (or second-price) auction) A Vickrey auction is a sealed-bid auction where the agent with the highest bid wins the good and mitsr pay the amount of the second highest bid. Chapter 3. Foundations: Mechanism Design and Auction Theory 17 Theorem 70 The Vickrey auction is truthful in dominant strategies. Proof. Let v be any agent's valuation and v be his bid. Let h be the highest of the bids of the other agents. If v > h, then any v > b yields v — h utility (where v — b > 0), and any v < b yields 0. Thus, v = v is a best response. If v < b, then any v > b yields v — b utility (where v — b < 0). and any v < b yields 0. Thus, v = v is a best response. For any agent, for any b, v = v is a (weakly) dominant strategy. • Definition 71 (All-pay auction) Au ah-pay auction is a sealed-bid auction where the agent with the highest bid wins the good. Each agent pays the amount that he hid. regardless of whether or not he won. Intuitively, one would think that a seller would prefer a first-price or all-pay auction to a second-price as they get a higher revenue. However, this does not take into account the equilibrium bidding strategies of the agents. In fact, there is a theorem which proves that revenue is constant across these auctions for a reasonable set of assumptions: Theorem 72 (Revenue Equivalence) /// any auction setting where • all agents' valuations are independent and identically distributed according to cumulative distribution F(v); • the valuation distribution has bounded support (on [v. v}) and F(V) is differen-' tiable and increasing on that interval; • there is an equilibrium that results in an efficient allocation; and • any agent with the minimum possible valuation has an ex interim expected utility of zero in that equilibrium. any two auction types result in the same ex interim expected utility for every agent result in the same ex ante expected revenue for the seller under those equilibria. Proof. We can write an expression for the ex interim expected utility of an agent with valuation v bidding according to the equilibrium strategy for agents with valuation t). Let jv be the ex interim probability-af an agent with declared valuation v winning the good and p(v) be the ex interim expected payment and agent with declared valuation v must pay. u(v\v) = •y(v)v-p(v) Because the agent is playing his equilibrium strategy, we know that that v =.v maxi-mizes his.expected utility: Su(v\v) = 5(7(v)v) 6P(v) = Q 5v 6v Sv Chapter3. Foundations: Mechanism Design and Auction Theory 18 We can solve for (he payment rule p(v) For any valuation distribution, and any fixed allocation rule there is a fixed -y(v). The above equation shows that for any fixed -y(v) in equilibrium, two auctions can only differ in p(v) by a constant. Since the auction is efficient, we have a fully specified 7(1;): the probability of an agent with type v winning the good is the probability that all other n — 1 agents have valuations less than v. i(v) = F"-](v) Since an agent with v = v has no change of winning the auction, his payment must be fixed to zero (which implies that c = 0). Thus for any auction meeting these criteria, agents have the same ex interim ex-pected payment and expected utility. Because the revenue is just the sum of payments, the ex ante expected revenue is also fixed. • j :n{x)6x + c 19 Chapter 4 Deliberative Agents 4.1 T e r m i n o l o g y It is common in auction theory to refer to an agent's type, meaning both the agent's private information (or signal) and the agent's valuation. Even in the classical litera-ture there are settings in which this is not reasonable, such as common values: here agents all have the same valuation for the good, but they are uncertain about what it is and all have (potentially) different private signals. We will follow Bergemann and Morris (2006) in dividing type into belief type (private information) and payoff'type (valuation). We must also be careful with the notions of ex ante, ex interim and ex post. Over the course of an auction, an agent might receive several signals, updating his beliefs after each. In such settings, it is not immediately clear which belief type ex interim should refer to. We will use ex interim to refer to all of them (so ex interim individually rational becomes a stronger condition: no sequence of signals should cause an agent to strictly prefer to drop-out of the auction), while ex ante refers to taking an expectation with respect to an agent's beliefs given no private information. By ex post we refer to taking an expectation conditioned on all agents' final belief types (so ex post efficiency means maximizing the expected social welfare). We will introduce ex interim perfect to refer to perfect knowledge of a single agent's valuation, and ex post perfect to refer to such knowledge of all agents' valuations (so ex post perfect efficiency means maximizing the actual social welfare). Definition 73 (Deliberation) A deliberation is an action that updates an agent's be-liefs. ' ' ' ' Because so-called "deliberative agents"-must make decisions about how to deliber-ate and how to bid conditioned on the results of that deliberation, the underlying game is extensive-form. We distinguish two types of deliberation. Definition 74 (Introspection) An introspection is a deliberation where the signal pro-vides information about the deliberator's valuation. Definition 75 (Strategic deliberation; Larson and Sandholm (2001b)) A strategic deliberation is a deliberation where the signal depends on another agent's valuation. Chapter 4. Deliberative Agents •20 Parameter Possible values Valuation distribution: Independent, common, interdependent . Secrecy: Secret, non-secret Perfection: Perfect certainty, residual uncertainty Volatility: Volatile, non-volatile Costliness: Costly, free Limitations: .Limited, unlimited Separability: Separable, inseparable Table 4.1: The features of our taxonomy 4.2 T a x o n o m y Deliberating agents have been studied under a variety of assumptions, models and names. In order to survey the literature, we first introduce a unifying taxonomy with a number of free parameters (summarized in Table 4.1). Definition 76 (Valuation distribution) if all agents' valuations are independent, we call the setting independent value. If every agent has the same valuation, we call the setting common value. We call all other cases interdependent value. Definition 77 (Secret) //; secret settings, the only deliberations agents can perform are introspections. Notably, researchers have studied independent non-secret values (for example, Lar-son (2006)). Definition 78 (Perfection) A setting with perfect certainty requires agents to discover their exact valuation. Otherwise, the setting allows residual uncertainty. One example of a perfect setting is when agents must find a feasible solution to a constrained optimization problem (e.g., vehicle scheduling and routing), to discover how to use the good and thus its exact value. Without a feasible solution, the agent cannot consume the good. The seller can also impose perfection by requiring bidders to commit to such a solution while bidding. Definition 79 (Volatile) In volatile settings, deliberation can change an agent's un-derlying valuation. Like perfection, this can be motivated by the example of agents solving a con-strained optimization problem. Feasible solutions tell the agent how to use the good and thus its value. By finding another solution, the agent might be able to update this value. Perfection is a special case of volatility where agents' valuations are 0 until they perform a perfect introspection. Definition 80 (Costly) Performing costly deliberations costs an agent some utility. Costly settings involve costly deliberations. Chapter 4. Deliberative Agents 21 We will model costs as another term in quasi linear utility: v.; =Vj{x) - ti -ci(q) where <;,(./:) is a value for outcome /;, is a transfer from agent to seller and c,((/) is the cost of deliberation policy q. Costly deliberation is not equivalent to an entry fee because it is not transferred to the seller. Definition 81 (Limited) Limited settings have hard constraints about when any par-ticular deliberation is possible. ^ For example, agents might be limited as to how many deliberations are possible during a particular stage. Definition 82 (Separability) //; separable settings, no deliberations are possible once the mechanism begins. (This is a special case of limited settings.) A l l sealed-bid mechanisms are trivially separable. Some staged auctions are also separable. (For example, in some auctions for antiques, bidders are only free to exam-ine the goods until the English auction begins.) Because the problem of deliberation is equivalent whether the source of the infor-mation is internal or external, there is an equivalence between costly deliberation (with secrecy and non-volatility) and costly communication to a proxy. 4 . 3 P r e v i o u s w o r k The earliest work on modeling agents with valuation uncertainty is probably Wilson's (1967) work on common values. This model has been extensively studied since then, but primarily in settings in which agents are not deliberative. Another related litera-ture considers tractably expressing bidder preferences in multi-good auctions (Ausubel & Milgrom, 2002; Blumrosen & Nisan. 2005; Nisan & Segal, 2005; Sandholm & Boutilier, 2006). We are specifically interested in deliberative agents. We wil l classify the existing work on this topic according-to our taxonomy, though the classification is not always precise: some of the existing work spans and contrasts classes, and some results are more general than their authors state. To the extent that we are able, we classify work according to its most general results. A number of researchers have considered the problem of deliberative agents in set-tings requiring perfect certainty. Parkes (2005) stated that handling residual uncertainty "appears beyond the scope of current methods (either analytic or computational), even for simple auctions such as an ascending-price auction for a single item." His paper focused on the dual problem to our own: auction and proxy design with costly com-munication. Parkes demonstrated that incremental revelation mechanisms can achieve the same allocations as direct mechanisms with lower communication costs. Cremer Chapter 4. Deliberative Agents 22 Paper Values Secret Perfect Volatile Costly Limits Separable Cromer ei at (2003) hid yes yes no ves no no Parkcs (2005) all yes both no ves no no Larson & Sandholm (2005) i nd no yes yes yes no yes Larson (2006) ind no yes no yes no no Larson & Sandholm (2001a) all no mi yes no yes both Larson & Sandholm (2001b) all no no yes yes no both . Blumrosen & Nisan (2002) ind yes no no IH) ves yes fleigemann & Valimaki (2002) all no no yes no both Persico (2000) inter no no yes yes yes Larson & Sandholm(2003) all no no yes' yes yes yes Larson & Sandholm (2004) ind no no yes yes yes yes Compte & .lehicl (2001) ind yes no no yes no both Sandholm (2000) ind yes mi no yes no yes Rasmusen (2006) ind yes no no yes yes no Our Paper ind yes no no yes yes yes Table 4.2: Classification of previous work on deliberative agents (Bold text indicates similar assumptions to _our model. * indicates cases where values are secret but inter-dependent.) Chapter 4. Deliberative Agents 23 et al. (2003) described how to extract full surplus from agents who commit to par-ticipating in the auction prior to deliberating, using a sequential auction based on op-timal search. Larson and Sandholm (2005) proved that no (interesting) mechanism exists in which agents have no incentive to strategically deliberate or to mislead the seller and the mechanism does not depend on knowledge of agents' deliberation costs and limits. The proof depends on costly deliberations, volatility (or non-volatile, per-fect certainty), and non-secrecy. Larson (2006) described an optimal search auction in which agents never strategically deliberate or mislead the seller. Larson and Sandholm (2001a; 2001b) provided a very general model for costly and/or limited deliberations in auctions and showed that under costly deliberation models and in a number of com-mon auction types (Vickrey, English, Dutch, first price and (for multiple goods) VCG) bidders perform strategic deliberation in equilibrium. There has been a small number of papers analyzing deliberative agents in settings that allow residual uncertainty. (Blumrosen & Nisan, 2002) showed that in auctions with severely limited communication (equivalent to severely limited deliberation), so-cial welfare can be improved by using asymmetric proxies (equivalent to asymmetric deliberation strategies). Bergemann and Valimaki (2002) showed that in independent secret settings, V C G is ex past efficient and provides ex ante incentives to deliberate. For common value settings, they showed that no mechanism can achieve both proper-ties. Larson and Sandholm (2003) demonstrated that in Vickrey auctions the ratio of computing costs between the social optimum and the worst case Nash equilibrium is unbounded, but that this can be improved by mechanism design. Larson and Sandholm (2004) described an experimental evaluation of deliberations on Vickrey auctions in non-secret settings. In simulation, no strategic deliberations occurred when agents had symmetric cost functions. Compte and Jehiel (2001) showed that sellers can get more revenue from Japanese-like ascending auctions than from second price auctions. Sand-holm (2000) demonstrated that in second price auctions, bidding one's true expected valuation is a dominant strategy for risk neutral bidders but not for risk averse ones. He also demonstrated that second price auctions do not always have dominant deliberation strategies when deliberation is costly. Rasmusen (2006) presented residual uncertainty as a motivation for sniping on eBay auctions: buyers do not have time to deliberate in the last seconds of an auction, but do not deliberate earlier because of the cost. Persico (2000) demonstrated that when valuations are correlated (i.e. secrecy is not absolute), the value of information is greater in first price auctions than in second price auctions, because bidding strategies are conditioned on beliefs about opponents'.valuations. 24 Chapter 5 Our Model In our work we make the strong assumption of separability. Existing work shows that staged auctions are better than sealed bid for maximizing revenue and minimizing de-liberation costs (Compte & Jehiel. 2001; Parkes, 2005; Bergemann & Valimaki, 2002). However, separability can arise when deliberations are too time-consuming to occur between bidding rounds: e.g., the deliberation might involve analysis of a broadcast spectrum market or drilling control wells in an offshore oil patch. Furthermore, many other real-world auctions are inherently separable (e.g., sealed-bid auctions). We also make a number of more traditional assumptions: independence, secrecy, symmetry and non-volatility. Our setting is a six-tuple: (A'\ /', Q. A, p. c). N is a set of agents, each of whom has a valuation u, drawn from distribution / , which has support on the interval [v,v]. Q is the set of possible introspections, from which each agent % chooses one, </,- € Q\ A is the set of possible signals the agent can receive, according to conditional probability distribution /)(a, jry,. i;,); and c(</,-/a,) is the cost of the signal a, £ A. Since agents can choose not to deliberate, we assume the existence of a special deliberation q0 that costs nothing and is uninformative. No agent (including the seller) knows how any other agent deliberated. This model restricts the model of Larson and Sanclholm (2001b) to the case of secrecy, non-volatility and separability. It is without loss of generality with respect to a number of important features. Proposition 83 This model is equivalent to one in which separability holds and agents can perforin multiple introspections. Proof. For any possible policy s of introspections, we can construct a single introspec-tion q that is strategically equivalent. For any history of signals h that is possible given s, we add /), to A. p{h,\<i, w,)Js set equal to the conditional probability of Ii given .s and v,. c(q. 11.) is set equal to the sum of the costs incurred given h. and s. Any limits on possible combinations of introspections can be incorporated into the model by restricting the set of possible policies s can be chosen from. • Proposition 84 This model is equivalent to one in which agents can start off with use-ful information. Proof. Since Propositions 83 allows for arbitrary restrictions on policies, one restric-tion it supports is the case where agents have some free introspection that they must perform before any others. • Proposition 85 This model is equivalent to one in which the cost of introspection de-pends on an agent's true valuation. Chapter 5. Our Model 25 •Figure 5.1: Induced valuation distribution of an introspection: Given any introspection q, the agent receives some signal a. Given a the agent has some posterior beliefs about his valuation, and that posterior has a strategically equivalent point mass distribution. Weighting each point mass by the ex ante probability of a yields an induced valuation distribution. Proof. For any introspection r/, we can construct a strategically equivalent introspec-tion (/', where the cost does not depend on the true valuation. For any signal-cost pair (a, a), we add (a,a) to A. p((a..a)\q'.v.,) is set equal to the conditional probability of (a. a) given q and y,, and c(r/'. (a. a)) is set equal to a. Replacing q with q' in any setting preserves strategic equivalence. • Proposition 86 Risk neutral agents with residual uncertainty should always hid as though their expected valuations were their exact known valuations, as long as inde-pendence, secrecy and separability hold. Proof. Having won the good, agent i would be indifferent between the good and a fixed transfer of E[t>,|a,, i wins auction]. However, when independence and secrecy hold, the event of winning the auction is uninformative about v-, (because all the seller knows about v, was revealed by i). Thus the agent can bid as though v, = E[t;,|o,], once he decides not to perform any more deliberations. From separability, the agent cannot bid before this point. • Because agents facing residual uncertainty bid as though their signals informed them of an exact valuation, we can define an induced valuation distribution (see Figure 5.1): the valuation distribution an agent acts as though he had, given his deliberation. The induced valuation distribution /',, of deliberation q is defined as where 5(e) is the Kronecker delta: 6(e) = 1 iff e is true and 5(e) = 0 otherwise. Chapter 6 Second price auctions 26 In this chapter we find and characterize the equilibria of second price auctions for some simple value distributions and sets of possible introspections. We show cases where there are two qualitatively different classes of equilibria having different revenue and efficiency characteristics. Throughout, we assume (for reasons of simplicity and tractability) that agents are risk neutral and always follow the dominant strategy of bidding their expected valuations truthfully (see Proposition 86). This means that the second price auction is trivially ex post efficient (for any set of deliberation strategies), though not necessarily ex post perfect efficient. 6.1 Cos t ly Introspection In this section, we consider the example case of agents that must decide whether to pay some cost to exactly determine their valuation or to not pay the cost and bid totally un-informed. We demonstrate by example that in settings where introspections are costly, there are instances where all Nash equilibria are either asymmetric or mixed-strategy. We show that these two classes of equilibria generate different amounts of revenue and have different probabilities of ex post perfect efficiency. We begin with the case of two bidders with valuations equally likely to be either 0 or I. They can chose between a perfect introspection <], = q* having fixed cost c (where 0 < c < 0.25 ') or not introspecting, q, = r/ 0 . This yields the induced normal form game given in Figure 6.1. 'For any oilier value of c, llie problem becomes trivial. For c — 0. the information is free and acquiring it is a dominant strategy. For c > 0.25. the information is too expensive for the agents lo recover their costs in the auction. .25 >:: .25 - .;>:, .25 - c. .25, .25 .25, .25 - c, .25 0,0, .5 Figure 6.1: Induced normal-form game for two bidders in a second-price auction who have valuations of 0 or I with equal probability. The third payoff is the seller's revenue. Chapter 6. Second price auctions 27 This game has a number or" noteworthy features: the value of information for delib-eration q* depends on the other agent's deliberation action, and equilibrium involves either randomization or asymmetry. These two flavors of equilibria lead to very differ-ent revenues. Under the asymmetric pure strategy equilibria, the deliberation cost does not affect bidding strategies or revenue. Under a symmetric mixed strategy equilibrium (each bidder introspecting with probability p = 1 —4c). the probability of introspection wil l vary continuously with costs, meaning that revenue will vary with costs as well. Both agents weakly prefer the pure strategy equilibria, which also maximize the so-cial welfare, but face a coordination problem to reach them. If they follow symmetric strategies, they wi l l sometimes miscoordinate and so expected social welfare decreases. By providing the agents with a correlated signal to condition their deliberations on, the seller would enable the agents to coordinate (i.e. correlated equilibrium). In this par-ticular case, this would also cause the seller's revenue to decrease, but that is an artifact of having so few bidders. We can show that these two sets of equilibria also exist for versions of this game involving larger numbers of agents. L e m m a 87 In every pure strategy equilibrium of this game exactly agents introspect while the other agents bid their (uninformed) expected valuations. Proof Sketch. Let k denote the number of agents that introspect. We can write expres-sions for the expected utility of any agent given k: ,_ r ,, , f EfsurplusWall ' low signals!*;) k — n—\ E [ v , # ! f / ( - = r M ] = | Q l ( l /2 ) ( l /2* ) fc = n - l 0 o.-w. ,. _ l _ / E[surplus]yj('i has only high signal\k) — c k = n ["•i I'•: <7, — l0\ — <^ E[ s u lpius]p('/; has only high signal jfc) — c o.tu. ( l ) ( l / 2 f c ) - c k-( l - l / 2 ) ( ] / 2 f c ) - o o.i , and" A set of equilibria exist with k agents introspecting iff E[m\k, qi = q0] > E[ui\k + 1 ,qt = q*}, and R[lH\k - I, q, = q0] < E[-uy|fe, qt = q*]. Solving this system of inequalities for k gives that min(71, — 1. |_— log2(c)J — 1) agents introspect. • Chapter 6. Second price auctions 28 Theorem 88 When introspection is costly, there are symmetric settings where the sec-ond price auction has no symmetric pure strategy- Nash equilibrium. This follows from Lemma 87 since there is no equilibria for k — n or k — 0. L e m m a 89 77H'.V game lias a symmetric mixed strategy where every agent introspects with probability p. ProofSketch. Each agent's expected utility under a symmetric mixed strategy profile where they each introspect with probability p is £ B(j: n, p)(pB[u,\:j + I. q*] .+ (1 - p)E[ui\j.. q0}), J='J where B(k,-.n,p) is the binomial distribution. Since the game is symmetric, it must have a symmetric Nash equilibrium at some?)*, which much satisfy A n analytic expression for the equilibrium can be found by solving the system of equa-tions for p given a particular u . • Theorem 90 /;; second price auctions with costly introspection, the pure strategy equi-libria can yield different revenue from the symmetric equilibria. ProofSketch. The seller's expected revenue under the pure strategy equilibria is ( 1 - 2~k - k,2~k k = n E[revenue|fc] = \ 1 - 2~k - k2-k~l k = n - 1 . [ 1 - 2- f c - ' - k2-k~l o.w. Under the symmetric (mixed) strategy equilibrium strategy profile p, the seller's ex-pected revenue is: B(j: n. p)E[revenue|k = //]. Under the equilibria above, these two quantities are not equal. • Using these analytic expressions for equilibrium revenue, we can compare the rev-enue of the different classes of Nash equilibria as n varies. The qualitative revenue properties of the equilibria are consistent with the intuition from two bidder example (see Figure 6.2). For pure strategy equilibria, all costs have the same revenue for low values of n. When n becomes too large, adding more agents wi l l have no effect on Chapter 6. Second price auctions 29 Figure 6.2: Expected revenue under pure (top) and mixed (bottom) strategies (plotted in 3D to more clearly illustrate when values are exactly overlapping) the number of agents that introspect, causing the revenue to plateau. Notably, this threshold only increases linearly for exponential decreases in costs, so that this limit applies to relatively small numbers of bidders, even when the cost is orders of mag-nitude smaller than the agents' valuations. For mixed strategy equilibria, the revenue decreases continuously as costs increase. As in the two-bidder case, symmetric mixed strategy equilibria involve a probability of miscoordinating which increases with the number of agents. As n gets large the probability of introspection wil l tend to 0. and the expected revenue wil l tend to the uninformed expected valuation (though in this case it does so extremely slowly). Although the second price auction is always ex post efficient, the equilibrium reached wi l l affect the probability of ex post perfect efficiency (the probability of actu-ally maximizing social welfare). Mixed strategy equilibria tend to have worse proba-bilities of ex post perfect efficiency (see Figure 6.3) because of the risk of miscoordi-nation. The analytic expression for the probability of ex post perfect efficiency of pure strategy equilibria is Chapter 6. Second price auctions 30 • c=0.1 • c=0.01 • c=0.001 • c=0.0001 0.95 0.9 0.85 O j T t - C D C O O C \ l ^ r C D C O O C \ l ^ r c D C O O C N J ^ - ! X ) 0 0 0 p(Efficiency) "~ *" "~ ^ ^ N ^ ^ ^ ^ r o " " " " - * 1 • c=0.1 • c=0.01 • c=0.001 • c=0.0001 0.95 0.9 0.85 0.! C N ^ J - C C O O O C M ^ C D C O O r M ^ J - C D O O O C M ^ t C O C O O p(Efficiency) "~ *~ *~ *~ ™^ ™ < N < M « « " « r o ^ t -Figure 6.3: Probability of ex post perfect efficiency under pure (top) and mixed (bot-tom) strategies ep(k.n) I — j p(k low|.fc) ^ p.(j low in n — k)p(winner e j) -fc-1 I I (1/2*) £ " '•• 1 1 u — k The analytic expression for the probability of ex post perfect efficiency of mixed strategy equilibria is <<n{p-ii) = y^j)(k agents introspect)^ p(k. fc=0 n = J2B(k:n.p)cp(k.n). k=0 Chapter 6. Second price auctions 31 6.2 L i m i t e d Introspection In this section, we consider the case of agents that can only make limited queries about their valuations. As with the previous case, we demonstrate by example that in settings where introspections are limited, there are instances where all Nash equilibria are either asymmetric or mixed-strategy. Let agents have valuations drawn from a uniform distribution on the interval [0, I]. Agents can perform one deliberation of the following type: for any value on the interval [0,1], they can discover (by a I-bit signal) whether their valuation is above or below it. Since the action space of deliberations is continuous (and purely cooperative, though this is a coincidence due to n = 2), we graph the (continuous) induced normal form in Figure 6.4. Again, the only pure strategy equilibria—[qi = l/'i.qo = 2/3] and [f/i = 2/3, q-2 = 1/3]—are asymmetric, even though deliberations are no longer costly. This finding mirrors those of Blumrosen and Nisan (2002), that agents benefit from asymmetry when severe limitations apply (though in this case, the asymmetric meaning of the 1 -bit signal is chosen by the bidder rather than by the mechanism or proxy). The agents could randomize across these two'strategies, though again this would cause them to lose expected utility through miscoordination. By ordering the bidders by weakly increasing r/,, we can write a expression for the expected utility of any number of agents under any pure strategy profile: i4«/l';i. B y differentiating the above expression for all v'. we arrive at the following system of equations whose solutions ace the pure strategy Nash equilibria: E;=I ( ( i -g? ) (n t ,V ' ? f c ) ) • 2 ( E ; : , ' ( ( i - ^ ) ( n i = , i / ^ ) ) ) E}=. ( ( i - f f i ( n t . !/</*))+<?,, 2 ( E ; ; 1 ((i-«?,)(nLi I M ) ) + 1 ) In this chapter, we have demonstrated that when introspection is costly or limited, it can introduce a coordination problem for the bidders. Unfortunately, there is no clear revenue dominance between coordinated and uncoordinated bidders. Whether coordination produces greater revenue can depend on the number of bidders and the costs. Chapter 6. Second price auctions 32 Figure 6.4: Graphical representation of the induced normal form of the 2-bidder limited deliberation case. The peaks (pure equilibria) do not fall on the <p = r / 2 line, so they are not symmetric. 33 Chapter 7 Revenue relationships and bounds This section contains theoretical results: we wi l l show a limited application of revenue equivalence, an upper bound on the revenue of separable auctions with costly deliber-ation and an impossibility result. The first thing we wil l demonstrate theoretically is that the revenue equivalence theorem can still hold in this setting. Obviously, this cannot be generically true because the Vickrey auction is not revenue equivalent with itself across all ex post efficient equilibria. However, we can show that for symmetric equilibria, all ex post efficient (i.e. awarding the good to the agent with the highest expected valuation.given the available information) sealed-bid auctions are revenue equivalent (given constraints on the family of available signals, analogous to those required by the revenue equivalence theorem). Theorem 91 In all symmetric, separable IPV settings where for every deliberation q the induced cumulative valuation distribution Fq is different table and increasing on the interval [«, v], all ex post efficient auctions are revenue equivalent under symmetric equilibria. Proof. This proof has two parts: First, we show that any symmetric introspection strat-egy wil l result in the same ex interim expected payments across ex post efficient auc-tions (by showing that the bidding subgame is strategically equivalent to a setting where the revenue equivalence theorem applies). Second, we show if a symmetric introspec-tion strategy is an equilibrium of one ex post efficient auction, it must be an equilibrium of all others. Part I: If agents all perform the same introspection q, followed by a symmetric increasing bidding strategy (necessary for ex post efficiency), then the revenue equiv-alence theorem applies. This is because the bidding subgame given q is strategically equivalent to the problem of how to bid in an auction where all valuations are drawn from Fq (as shown in Proposition 86). Any strategy .s that mixes over introspections leads to an induced valuation distribution: Fs(v)[= £ y > ( r / | s ) F , , ( > ) . Since Fq is increasing and differentiate on [u_. v] for every q in Q, Fs must be Chapter 7. Revenue relationships and bounds 34 increasing and dilTerentiable for any s. This will still satisfy the necessary conditions for the revenue equivalence theorem. Part 2: Let s be some introspection strategy that is an equilibrium of some ex post efficient auction A (where 7.4 (v,) is the ex interim probability of winning the good and /. .4 (<.>;) is m e £.v interim expected transfer). The ex interim expected utility of agent i playing introspection strategy when all other agents play a is E[ul\s,s'i..A] = y / , ; ( • « ; ) (7,1 (w,0 - / . , iM)<^; - E[c,-|s<]. Ff fi is another ex post efficient auction, then 7/3 = 74 and Is = I A — c (by the revenue equivalence theorem). The ex interim expected utility under auction 13 is E[u,\s, s';, 13} = J ' fg, (Vi) (7.4(1*,) - (•«,-)) - E[c,-| S;] + c = E[u;\.s.,v':A] + c. The expected gain from agent i deviating from .5, to .s' in auction fi is E[i/,,-.|.s; fi] - E[u , |.s: fi] = (E[v/.,!*; A] + c) - (E[M,-|.S; /l] + c) = E [« , ; | . i ' : *; ; /1 ] - E [ v / . ; | . S ; S , - ; A] . Therefore, if s is a best response in A it must also be a best response in fi. Conclusion: Subject to the constraints above, for any symmetric introspection po l : icy s, ex interim expected payments are equal across auction types. Any s that is possible in equilibrium in one auction must be possible in all others. Therefore, all auctions are revenue equivalent under symmetric introspection policies. • This is significant because it demonstrates that no ex post efficient sealed-bid mech-anism can overcome the coordination problems that arose in our second price examples in Chapter 6. We can also show an extremely general (though loose) revenue bound, which ap-plies to all separable auction settings and all allocation rules. Although bidders do not always pass their information costs directly on to the seller, by individual rationality they must always recover enough expected surplus to cover those costs. Theorem 92 //) any ex ante individually-rational, separable auction, the expected rev-enue is bounded from above by v — Yl; E[c,] where E[c,] is i's expected cost of delib-eration. Proof. Let 7,(s) be the marginal probability of i receiving the good given strategy profile s. Let /.,(«) be ?7s expected transfer to the seller given s. The expected utility of Chapter 7. Revenue relationships and bounds 35 agent i is 7;(*)E[v,-|.v« wins] - /;,(.s) - E[c,>,-]. By individual rationality, i's utility must be non-negative, which gives an upper bound on the transfer i I makes to the seller: Taking the sum over these payments (and noting that 7 , ( 4 ) must sum to I) gives us a bound on the revenue: Although previous work has already shown that Vickrey auctions do not necessarily have dominant strategies in the case where deliberations are costly, this bound allows us to generalize that finding into a broader impossibility result. Corol lary 93 No budget-balanced, individually-rational, separable mechanism can have a dominant strategy that involves ait unbounded number of agents performing costly deliberations. Proof. There must exist some n where nc > v, where c is the cost of the cheapest deliberation. If more than n agents perform a deliberation with cost > c, then the seller's expected revenue becomes negative. • This result is significant in that it gives a constraint on the space of possible mechanisms that can be applied to deliberative agents. For a mechanism to have an equilibrium in dominant strategies it must treat agents asymmetrically (such that the number of agents-performing costly introspections is bounded) or it must reimburse agents for their introspection costs. Lastly, we can show an upper bound on the value of information for any deliber-ation. This is a generalization of the effect shown in Lemma 87: large decreases in the cost of an introspection have only a small impact on the number of agents that wil l perform it. Theorem 94 //( ex post efficient, separable auctions with independent secret values, the maximum value of information , cq for any deliberation q falls off exponentially in the number of agents performing it (denoted by k). /•;(*) < • (7,-(s)-5-E[c,-| S |-)). < £ ( 7 , - ( s ) - S - E [ c , - | S , - ] ) c,, < za: (X < 1 k Chapter 7. Revenue relationships and bounds 36 Proof. Suppose we only allowed agents who performed deliberation q to bid. For any signal a,, i's probability of receiving the good is proportional to Fk~ 1 (E[v;, |a,]), where Fq(v) is the cumulative induced valuation distribution of q. Hence, it's expected surplus (and the value of information) must fall off exponentially in k. Al lowing agents to bid without performing deliberation q weakly decreases the value of q (by reducing the probability of receiving the good and increasing the expected payment) and weakly increases the value of not performing q. ' • One argument against modeling costly introspection is that often the costs are so small relative to the value of the good. However, this result shows that as the number of bidders increases, even extremely small costs of information become strategically relevant. 37 Chapter 8 Conclusion We have expanded on previous work that shows that the problem ol' how to deliberate prior to bidding adds a significant extra layer of strategic complexity to auctions. We showed that limited and costly deliberation can impose a coordination problem on bid-ders, that the chance of miscoordination has an impact on revenue and the probability of efficiency, and that these issues are present even when deliberation costs are small relative to valuations. Future work could relax assumptions about distribution, secrecy and separability. For example, a model could describe the costs to the seller (and other bidders) of waiting for slow deliberations, allowing a continuous trade-off of the speed of sealed auctions against the lower deliberation costs and higher revenue of staged auctions. 38 Bibliography Ausubel. L . , & Milgrom, P. (2002). Ascending auctions with package bidding. Fron-tiers of Theoretical Economics, /(I), 1-42. Bergemann, D., & Morris, S. (2006). Robust implementation: The case of direct mechanisms. Coweles foundation discussion paper 1561. Bergemann, D., & Valimaki, J. (2002). Information acquisition and efficient mecha-nism design. Econometrica. 70(3), 1007-1033. Blumrosen, L . , & Nisan, N . (2002). Auctions with severely bounded communication. FOCS (pp. 406-415). Blumrosen, L. , & Nisan, N . (2005). On the computational power of iterative auctions. ACM-EC (pp. 29-43). Compte, O., & Jehiel, P. (2001). Auctions and information acquisition: Sealed-bid or dynamic formats, working paper. Cremer, J., Spiegel, Y., & Zheng, C. (2003): Optimal selling mechanisms with costly information acquisition (Technical Report). Working paper, August. Krishna, V. (2002). Auction theory. Academic Press. Larson, K. (2006). Reducing costly information acquisition in auctions. AAMAS (pp. 1167-1174). Larson, K. , & Sandholm, T. (2001a). Computationally limited agents in auctions. AGENTS. Larson, K. , & Sandholm, T. (2001 b). Costly valuation computation in auctions. TARK (pp. 169-182). Larson, K. , & Sandholm, T. (2003). Miscomputing ratio: The social cost of selfish computing. AAMAS (pp. 273-280). Larson, K. , & Sandholm, T. (2004). Experiments on deliberation equilibria in auc-tions. AAMAS. Larson, K. , & Sandholm, T. (2005). Mechanism design and deliberative agents. AA-MAS (pp. 650-656). Nisan, N . , & Segal, I. (2005). The communication requirements of efficient alloca-tions and supporting prices. Journal of Economic Theory. Bibliography 39 Parkes, D. (2005). Auction design with costly preference elicitation. Annals of Math-ematics and Artificial Intelligence, 44(3), 269-302. Persico, N . (2000). Information acquisition in auctions. Econotnetrica, 68(\), 135-148. Rasmusen, E. (2006). Strategic implications of uncertainty over ones own private value in auctions. Advances in Theoretical Economics, 6(1). Sandholm, T. (2000). Limitations of the Vickrey auction in computational multiagent systems. International Journal of Electronic Commerce, 4(3), 107-129. Sandholm, T., & Boutilier, C. (2006). Preference elicitation in combinatorial auctions. In Cramton, Shoham and Steinberg (Eds.), Combinatorial auctions, chapter 10. Shoham. Y.. & Leyton-Bcown. K. (2007). Foundations of multiagent systems: Al-gorithmic, game-theoretic and logical models of competition and cooperation. In preparation. Wilson, R. (1967). Competitive bidding with asymmetric information. Management Science, I3( \ I), 816-820. Wilson, R. (1969). Competitive bidding with disparate information. Management Science, 15(1), 446-448.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Valuation uncertainty and imperfect introspection in...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Valuation uncertainty and imperfect introspection in second-price auctions Thompson, David Robert Martin 2007
pdf
Page Metadata
Item Metadata
Title | Valuation uncertainty and imperfect introspection in second-price auctions |
Creator |
Thompson, David Robert Martin |
Publisher | University of British Columbia |
Date Issued | 2007 |
Description | In auction theory, agents are typically presumed to have perfect knowledge of their valuations. In practice, though, they may face barriers to this knowledge due to transaction costs or bounded rationality. Modeling and analyzing such settings has been the focus of much recent work, though a canonical model of such domains has not yet emerged. We begin by proposing a taxonomy of auction models with valuation uncertainty and showing how it categorizes previous work. We then restrict ourselves to single-good sealed-bid auctions, in which agents have (uncertain) independent private values and can introspect about their own (but not others') valuations through possibly costly and imperfect queries. We investigate second-price auctions, performing equilibrium analysis for cases with both discrete and continuous valuation distributions. We identify cases where every equilibrium involves either randomized or asymmetric introspection. We contrast the revenue properties of different equilibria, discuss steps the seller can take to improve revenue, and identify a form of revenue equivalence across mechanisms. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-03-11 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
IsShownAt | 10.14288/1.0052005 |
URI | http://hdl.handle.net/2429/32362 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2007-0614.pdf [ 2.2MB ]
- Metadata
- JSON: 831-1.0052005.json
- JSON-LD: 831-1.0052005-ld.json
- RDF/XML (Pretty): 831-1.0052005-rdf.xml
- RDF/JSON: 831-1.0052005-rdf.json
- Turtle: 831-1.0052005-turtle.txt
- N-Triples: 831-1.0052005-rdf-ntriples.txt
- Original Record: 831-1.0052005-source.json
- Full Text
- 831-1.0052005-fulltext.txt
- Citation
- 831-1.0052005.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0052005/manifest