Approximation in Economic Design 1 Jason D. Hartline Draft: April 15, 2012 1Northwestern University, Evanston, IL 60208. Email: [email protected]. 2 Contents 1 Approximation and Mechanism Design 7 1.1 Example: Congestion Control and Routing in Computer Networks . . . . . . 8 1.1.1 Non-monetary payments . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.1.2 Posted Pricing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.1.3 General Routing Mechanisms . . . . . . . . . . . . . . . . . . . . . . 16 1.2 Mechanism Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3 Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3.1 Philosophy of Approximation . . . . . . . . . . . . . . . . . . . . . . 19 1.3.2 Approximation Factors . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2 Equilibrium 25 2.1 Complete Information Games . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2 Incomplete Information Games . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3 Bayes-Nash Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.4 Single-dimensional Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.5 Characterization of Bayes-Nash equilibrium . . . . . . . . . . . . . . . . . . 30 2.6 Characterization of Dominant Strategy Equilibrium . . . . . . . . . . . . . . 34 2.7 Revenue Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.8 Solving for Bayes-Nash Equilibrium . . . . . . . . . . . . . . . . . . . . . . . 36 2.9 The Revelation Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3 Optimal Mechanisms 43 3.1 Single-dimensional Environments . . . . . . . . . . . . . . . . . . . . . . . . 44 3.2 Social Surplus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.3 Profit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.3.1 Quantile Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.3.2 Revenue Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.3.3 Expected Revenue and Virtual Values . . . . . . . . . . . . . . . . . . 50 3.3.4 Optimal Mechanisms and Regular Distributions . . . . . . . . . . . . 51 3.3.5 Single-item Auctions . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.4 Irregular Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.4.1 Ironed Revenue Curves . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.4.2 Optimal Mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3 3.4.3 Single-item Auctions . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4 Bayesian Approximation 63 4.1 Single-item Auctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.1.1 Regular Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.1.2 Irregular Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.1.3 Anonymous Reserves . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.2 General Feasibility Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.2.1 Monotone-hazard-rate Distributions (and Downward-closed Feasibility) 73 4.2.2 Matroid Feasibility (and Regular Distributions) . . . . . . . . . . . . 76 5 Prior-independent Approximation 83 5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.2 “Resource” Augmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.2.1 Single-item Auctions . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.2.2 Matroid Environments . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.3 Single-sample Mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.3.1 The Geometric Interpretation . . . . . . . . . . . . . . . . . . . . . . 87 5.3.2 Random versus Monopoly Reserves . . . . . . . . . . . . . . . . . . . 88 5.3.3 Single-sample versus Optimal . . . . . . . . . . . . . . . . . . . . . . 89 5.4 Prior-independent Mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.4.1 Digital Good Environments . . . . . . . . . . . . . . . . . . . . . . . 91 5.4.2 General Environments . . . . . . . . . . . . . . . . . . . . . . . . . . 92 6 Prior-free Mechanisms 95 6.1 The Digital Good Environment . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.1.1 Deterministic Auctions . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6.1.2 Random Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 6.1.3 Decision Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 6.1.4 Lower bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 6.2 The Envy-free Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 6.3 Multi-unit Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.4 Matroid Permutation and Position Environments . . . . . . . . . . . . . . . 113 6.5 Downward-closed Permutation Environments . . . . . . . . . . . . . . . . . . 117 7 Multi-dimensional Approximation 123 7.1 Item Pricing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 7.2 Reduction: Unit-demand to Single-dimensional Preferences . . . . . . . . . . 125 7.2.1 Single-dimensional Analogy . . . . . . . . . . . . . . . . . . . . . . . 126 7.2.2 Upper bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 7.2.3 Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 7.2.4 Instantiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 7.3 Lottery Pricing and Randomized Mechanisms . . . . . . . . . . . . . . . . . 130 4 7.4 Beyond Independent Unit-demand Environments . . . . . . . . . . . . . . . 133 7.5 Optimal Lottery-pricing via Linear Programming . . . . . . . . . . . . . . . 133 8 Computational Tractability 137 8.1 Tractability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 8.2 Single-minded Combinatorial Auctions . . . . . . . . . . . . . . . . . . . . . 139 8.2.1 Approximation Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 139 8.2.2 Approximation Mechanisms . . . . . . . . . . . . . . . . . . . . . . . 142 8.3 Bayesian Algorithm and Mechanism Design . . . . . . . . . . . . . . . . . . 144 8.3.1 Monotonization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 8.3.2 Blackbox Computation . . . . . . . . . . . . . . . . . . . . . . . . . . 149 8.3.3 Payment Computation . . . . . . . . . . . . . . . . . . . . . . . . . . 149 8.4 Computational Overhead of Payments . . . . . . . . . . . . . . . . . . . . . 151 8.4.1 Communication Complexity Lower Bound . . . . . . . . . . . . . . . 152 8.4.2 Implicit Payments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 A Mathematical Reference 161 A.1 Big-oh Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 A.2 Common Probability Distributions . . . . . . . . . . . . . . . . . . . . . . . 161 A.3 Expectation and Order Statistics . . . . . . . . . . . . . . . . . . . . . . . . 162 A.4 Integration by Parts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 A.5 Hazard Rates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 5 Author’s Note This text is suitable for advanced undergraduate or graduate courses; it has been developed at Northwestern U. as the primary text for such a course since 2008. This text provides a look at select topics in economic mechanism design through the lens of approximation. It reviews the classical economic theory of mechanism design wherein a Bayesian designer looks to find the mechanism with optimal performance in expectation over the distribution from which the preferences of the participants are drawn. It then adds to this theory practical constraints such as simplicity, tractability, and robustness. The central question addressed is whether these practical mechanisms are good approximations of the optimal ones. The resulting theory of approximation in mechanism design is based on results that come mostly from the theoretical computer science literature. The results presented are the ones that are most directly compatible with the classical (Bayesian) economic theory and are not representative of the entirety of the literature. – Jason D. Hartline 6 Chapter 1 Approximation and Mechanism Design Our world is an interconnected collection of economic and computational systems wherein individuals optimize to achieve their own, perhaps selfish, goals subject to basic laws of the system. Some of these systems perform well, e.g., the national residency matching program which assigns medical students to residency programs in hospitals, e.g., auctions for online advertising on Internet search engines; and some of these systems perform poorly, e.g., financial markets during the 2008 meltdown, e.g., gridlocked transportation networks. The success and failure of these systems depends on the basic laws governing the system. Financial regulation can prevent disastrous market meltdowns, congestion protocols can prevent gridlock in transportation networks, and market and auction design can lead to mechanisms for exchanging goods or services that are good in terms of revenue or social benefit. The two sources for economic considerations are the preferences for individuals and the performance of the system. For instance, bidders in an auction would like to maximize their gains from buying; whereas, the performance of the system could (i.e., from the perspective of the seller) be measured in terms of the revenue it generates. Likewise, the two sources for computational considerations are the individuals who must optimize their strategies, and the system which must enforce its governing rules. For instance, bidders in the auction must fig- ureout howto bid, andtheauctioneer must calculate thewinner andpayments fromthebids received. While these calculations may seem easy when auctioning a painting, they both be- come quite challenging when, e.g., the Federal Communications Commission (FCC) auctions cell phone spectrum for which individual lots have a high-degree of complementarities. These economic and computational systems are complex. The space of individual strate- gies is complex and the space of possible rules for the system is complex. Optimizing among strategies or system rules in complex environments should lead to complex strategies and system rules, yet the individuals’ strategies or system rules that are successful in practice are often remarkably simple. This simplicity may be a result of computational tractability or due to desired robustness, especially when these desiderata do not significantly sacrifice performance. 7 This text focuses on a combined computational and economic theory for the study and design of mechanisms. A central theme in will be a tradeoff between optimality and other desirable properties such as simplicity, robustness, computational tractability, and practi- cality. This tradeoff will be quantified by a theory for approximation which measures the loss of a simple, robust, and practical approximation in comparison to the complicated and delicate optimal mechanism. The theory provided does not necessarily suggest mechanisms that should be deployed in practice, instead, it pinpoints salient features of goodmechanisms that should be a starting point for the practitioner. In this chapter we will explore mechanism design for routing and congestion control in computer networks as an example. Our study of this example will motivate a number of questions that will be addressed in subsequent chapters of the test. We will conclude the chapter with a formal discussion of approximation and the philosophy that underpins its relevance to the theory of mechanism design. 1.1 Example: Congestion Control and Routing in Com- puter Networks We will discuss novel mechanisms for congestion control and routing in computer networks to give a preliminary illustration of the interplay between strategic incentives and approxi- mation in mechanism design. Consider a hypothetical computer network where network users reside at computers and these computers are connected together through a network of routers. Any pair of routers in this network may be connected by a network link and if such a network link exists then each router can route a message directly through the other router. We will assume that the network is completely connected, i.e., there is a path of network links between all pairs of users. The network links have limited capacity; meaning, at most a fixed number of messages can be sent across thelink inany given interval of time. Given this limited capacity the network links are a resource that may be over demanded. To enable the sending of messages between users in the network we will need mechanisms for congestion control, i.e., determining which messages to route when a network link is over-demanded, and routing, i.e., determining which path in the network each message should take. There are many complex aspects of this congestion control problem: dynamic demands, complex networks, and strategic user behavior. Let us ignore the first two issues at first and focus on the latter: strategic user behavior. Consider a static version of this routing problem over a single network link with unit capacity: each user wishes to send a message across the link, but the link only has capacity for one message. How shall the routing protocol select which message to route? There is nothing special about the fact that the resource that the users (henceforth: agents) are vying for is a network link; we will therefore cast the problem as a more general single-item resource allocation problem. An implicit assumption in this problem is that it is better to allocate the item to some agents over others. For instance, we can model the 8 agents as having value that each gains for receiving the item and it would be better if the item went to an agent that valued it highly. Definition 1.1. The single-item allocation problem is given by a single indivisible item available, • n strategic agents competing for the item, and • each agent i has a value v for receiving the item. i • The objective is to maximize the social surplus, i.e., the value of the agent that receives the item. The social surplus is maximized if the item is allocated to agent with the highest value, denoted v . If the values of the agent are publicly known, this would be a simple allocation (1) protocol to implement. Of course, e.g., in our routing application, it is rather unlikely that values are publicly known. A more likely situation is that each agent’s value is known privately to that agent and unknown to all other parties. A mechanism that wants to make use of this private information must then solicit it. Consider the following mechanism as a first attempt at an single-item allocation mechanism. 1. Ask agents to report their values. ( agent i reports b ) i ⇒ 2. Select the agent with highest report. ( i∗ = argmax b ) ⇒ i i 3. Allocate the item to agent i∗. Suppose you were one of the agents and your value was $10 for the item; how would you bid? What should we expect to happen if we ran this mechanism? It should be pretty clear that there is no reason your bid should be at all related to your value; in fact, you should always bid the highest number you can think of. The winner is the agent who thinks of and reports the highest number. Clearly, we will not be able to say nice things about this mechanism. There are two natural ways to try to address this unpredictability. First, we can accept that the bids are meaningless, ignore them (or not even solicit them), and pick the winner randomly. Second, we could attempt to penalize the agents for bidding a high amount, for instance, with a monetary payment. Mechanism 1.1 (Lottery). 1. Select a uniformly random agent. 2. Allocate the item to this agent. 9 The social surplus of a mechanism is total value it generates. In this routing example the social surplus is the value of the message routed. It is easy to calculate the expected surplus of the lottery. It is 1 v . This surplus is a bit disappointing in contrast to the n i i surplus available in the case where the values of the messages were publicly known, i.e., P v = max v . In fact, by setting v = 1; v = ǫ (for i = 1); and letting ǫ go to zero we (1) i i 1 i 6 can observe that the surplus of the lottery approaches v /n; therefore, its worst-case is at (1) best an n-approximation to the optimal surplus v . Of course, the lottery always obtains (1) at least an nth of v ; therefore, its worst-case approximation factor is exactly n. It is fairly (1) easy to observe, though we will not discuss the details here, that this approximation factor is the best possible by any mechanism without payments. Theorem 1.2. The surplus of the lottery mechanism is an n-approximation to the highest agent value. If instead it is possible to charge payments, such payments, if made proportionally to the agents’ bids, could discourage low-valued agents from making high bids. This sort of dynamic allocation and pricing mechanism is referred to as an auction. Definition 1.3 (Single-item Auction). A seller has a single item to sell to a number of interested buyers, each buyer has a value for receiving the item. A single-item auction solicits bids, picks a winner, and determines payments. A natural allocation and pricing rule that is used, e.g., in government procurement auc- tions, is the first-price auction. Mechanism 1.2 (First-price Auction). 1. Ask agents to report their values. ( agent i reports b ) i ⇒ 2. Select the agent with highest report. ( i∗ = argmax b ) ⇒ i i 3. Allocate the item to agent i∗. 4. Charge this agent her bid, bi∗. To get some appreciation for the strategic elements of the first price auction note that an agent who wins wants to pay as little as possible, so bidding a low amount is desirable. Of course, if they bid too low, then they probably will not win. Strategically, this agent must figure out how to balance this tradeoff. Of course, since agents may not report their true values, the agent with the highest bid may not be the agent with the highest-valued message. See Figure 1.1. Wewillbeabletoanalyzethefirst-priceauctionandwewilldo soinChapter 2. However, for two reasons, there is little hope of generalizing it beyond the single-network-link special case (i.e., to large asymmetric computer networks) which is our eventual goal. First, calcu- lating equilibrium strategies in general asymmetric environments is not easy; consequently, there would be little reason to believe that agents would play by the equilibrium. Second, 10