Implementation with a Bounded Action Space  [Extended Abstract]  ∗  Liad Blumrosen  School of Engineering and Computer Science  The Hebrew University  Jerusalem, Israel  liad@cs.huji.ac.il  Michal Feldman  School of Engineering and Computer Science  The Hebrew University  Jerusalem, Israel  mfeldman@cs.huji.ac.il  ABSTRACT  While traditional mechanism design typically assumes   isomorphism between the agents" type- and action spaces, in  many situations the agents face strict restrictions on their  action space due to, e.g., technical, behavioral or regulatory  reasons. We devise a general framework for the study of  mechanism design in single-parameter environments with   restricted action spaces. Our contribution is threefold. First,  we characterize sufficient conditions under which the   information-theoretically optimal social-choice rule can be   implemented in dominant strategies, and prove that any   multilinear social-choice rule is dominant-strategy implementable  with no additional cost. Second, we identify necessary   conditions for the optimality of action-bounded mechanisms, and  fully characterize the optimal mechanisms and strategies in  games with two players and two alternatives. Finally, we  prove that for any multilinear social-choice rule, the optimal  mechanism with k actions incurs an expected loss of O( 1  k2 )  compared to the optimal mechanisms with unrestricted   action spaces. Our results apply to various economic and   computational settings, and we demonstrate their applicability  to signaling games, public-good models and routing in   networks.  Categories and Subject Descriptors  J.4 [Social and Behavioral Sciences]: Economics; K.4.4  [Electronic Commerce]: Payment schemes    1. INTRODUCTION  Mechanism design is a sub-field of game theory that   studies how to design rules of games resulting in desirable   outcomes, when the players are rational. In a standard   setting, players hold some private information - their types  - and choose actions from their action spaces to   maximize their utilities. The social planner wishes to implement  a social-choice function, which maps each possible state of  the world (i.e., a profile of the players" types) to a single  alternative. For example, a government that wishes to   undertake a public-good project (e.g., building a bridge) only  if the total benefit for the players exceeds its cost.  Much of the literature on mechanism design restricts   attention to direct revelation mechanisms, in which a player"s  action space is identical to his type space. This focus is  owing to the revelation principle that asserts that if some  mechanism achieves a certain result in an equilibrium, the  same result can be achieved in a truthful one - an   equilibrium where each agent simply reports his private type [15].  Nonetheless, in many environments, direct-revelation  mechanisms are not viable since the actions available for the  players have a limited expressive power. Consider, for   example, the well-studied screening model, where an   insurance firm wishes to sell different types of policies to different  drivers based on their caution levels, which is their private  information. In this model, drivers may have a continuum of  possible caution levels, but insurance companies offer only  a few different policies since it might be either infeasible or  illegal to advertise and sell more then few types of policies.  There are various reasons for such strict restrictions on  the action spaces. In some situations, firms are not willing,  or cannot, run a bidding process but prefer fixing a price for  some product or service. The buyers in such environemnts  face only two actions - to buy or not to buy - although they  may have an infinite number of possible values for the item.  In many similar settings, players might be also reluctant to  reveal their accurate types, but willing to disclose partial   information about them. For example, agents will typically be  unwilling to reveal their types, even if it is beneficial for them  in the short run, since it might harm them in future   transactions. Agents may also not trust the mechanism to keep  their valuations private [16], or not even know their exact  type while computing it may be expensive [12]. Limitations  on the action space can also be caused by technical   constraints, such as severe restrictions on the communication  lines [5] or from the the need to perform quick transactions  (e.g., discrete bidding in English auctions [9]).  62  Consider for example a public-good model: a social   planner needs to decide whether to build a bridge. The two  players in the game have some privately known benefits  θ1, θ2 ∈ [0, 1] from using this bridge. The social planner  aims to build the bridge only if the sum of these benfits   exceeds the construction cost of the bridge. The social planner  cannot access the private data of the players, and can only  learn about it from the players" actions. When direct   revelation is allowed, the social planner can run the well-known  VCG mechanism, where the players have incentives to   report their true data; hence, the planner can elicit the exact  private information of the players and build the bridge only  when it should be built. Assume now that the players   cannot send their entire secret data, but can only choose an  action out of two possible actions (e.g., 0 or 1). Now,  the social planner will clearly no longer be able to always  build the bridge according to her objective function, due to  the limited expressivness of the players" messages. In this  work we try to analyze what can be achieved in the presence  of such restrictions.  Restrictions on the action space, for specific models, were  studied in several earlier papers. The work of Blumrosen,  Nisan and Segal [4, 6, 5] is the closest in spirit to this paper.  They studied single-item auctions where bidders are allowed  to send messages with severely bounded size. They   characterized the optimal mechanisms under this restriction, and  showed that nearly optimal results can be achieved even with  very strict limitations on the action space. Other work   studied similar models for the analysis of discrete-bid ascending  auctions [9, 11, 8, 7], take-it-or-leave-it auctions [17], or for  measuring the effect of discrete priority classes of buyers  on the performance of electricity markets [19, 14]. Our work  generalizes the main results of Blumrosen et al. to a   general mechanism-design framework that can be applied to a  multitude of models. We show that some main properties  proved by Blumrosen et al. are preserved in more general  frameworks (for example, that dominant-strategy   equilibrium can be achieved with no additional cost, and that the  loss diminishes with the number of possible actions in a   similar rate), where some other properties do not always hold  (for example, that asymmetric mechanisms are optimal and  that players must always use all their action space).  A standard mechanism design setting is composed of  agents with private information (their types), and a   social planner, who wishes to implement a social choice   function, c - a function that maps any profile of the agents"  types into a chosen alternative. A classic result in this   setting says that under some monotonicity assumption on the  agents" preferences - the single-crossing assumption (see  definition below) - a social-choice function is implementable  in dominant strategies if and only if it is monotone in the  players" types. However, in environments with restricted   action spaces, the social planner cannot typically implement  every social-choice function due to inherent informational  constraints. That is, for some realizations of the players"  types, the decision of the social planner will be incompatible  with the social-choice function c. In order to quantitatively  measure how well bounded-action mechanisms can   approximate the original social-choice functions, we follow a   standard assumption that the social choice function is derived  from a social-value function, g, which assigns a real value  for every alternative A and realization of the players" types.  The social-choice function c will therefore choose an   alternative that maximizes the social value function, given the type  vector  −→  θ = (θ1, .., θn), i.e., c(  −→  θ ) = argmaxA{g(  −→  θ , A)}.  Observe that the social-value function is not necessarily the  social welfare function - the social welfare function is a   special case of g in which g is defined to be the sum of the  players" valuations for the chosen alternative. Following are  several simple examples of social-value functions:  • Public goods. A government wishes to build a bridge  only if the sum of the benefits that agents gain from  it exceeds its construction cost C. The social value  functions in a 2-player game will therefore be:  g(θ1, θ2,build)=θ1+θ2-C and  g(θ1, θ2,do not build)=0.  • Routing in networks. Consider a network that is   composed of two links in parallel. Each link has a secret  probability pi of transferring a message successfully.  A sender wishes to send his message through the   network only if the probability of success is greater than,  say, 90 percent - the known probability in an alternate  network. That is,  g(p1, p2, send in network)=1-(1-p1)·(1-p2) and  g(p1, p2,send in alternate network)=0.9.  • Single-item auctions. Consider a 2-player auction,  where the auctioneer wishes to allocate the item to the  player who values it the most. The social choice   function is given by: g(θ1, θ2, player 1 wins) = θ1 and for  the second alternative is g(θ1, θ2, player 2 wins) =  θ2.  1.1 Our Contribution  In this paper, we present a general framework for the  study of mechanism design in environments with a limited  number of actions. We assume a Bayesian model where  players have one-dimensional private types, independently  distributed on some real interval.  The main question we ask is: when agents are only allowed  to use k different actions, which mechanisms achieve the   optimal expected social-value? Note that this question is   actually composed of two separate questions. The first question  is an information-theoretic question: what is the optimal  result achievable when the players can only reveal   information using these k actions (recall that their type space  may be continuous). The other question involves   gametheoretic considerations: what is the best result achievable  with k actions, where this result should be achieved in a  dominant-strategy equilibrium. These questions raise the  question about the price of implementation: can the   optimal information-theoretic result always be implemented in  a dominant-strategy equilibrium? And if not, to what   extent does the dominant-strategy requirement degrades the  optimal result? What we call the price of implementation  was also explored in other contexts in game theory where  computational restrictions apply: for example, is it always  true that the optimal polynomial-time approximation ratio  (for example, in combinatorial auctions) can be achieved in  equilibrium? (The answer for this interesting problem is still  unclear, see, e.g., [3, 2, 13].)  Our first contribution is the characterization of sufficient  conditions for implementing the optimal   informationtheoretic social-choice rule in dominant strategies. We show  that for the family of multilinear social-value functions (that  63  is, polynomials where each variable has a degree of at most  one in each monomial) the dominant-strategy   implementation incurs no additional cost.  Theorem: Given any multilinear single-crossing   socialvalue function, and for any number of alternatives and   players, the social choice rule that is information-theoretically  optimal is implementable in dominant strategies.  Multilinear social-value functions capture many   important and well-studied models, and include, for instance, the  routing example given above, and any social welfare   function in which the players" valuations are linear in their types  (such as public-goods and auctions).  The implementability of the information-theoretically   optimal mechanisms enables us to use a standard routine in  Mechanism Design and first determine the optimal   socialchoice rule, and then calculate the appropriate payments  that ensure incentive compatibility. To show this result, we  prove a useful lemma that gives another characterization for  social-choice functions whose price of implementation is  zero. We show that for any social-choice function, incentive  compatibility in action-bounded mechanisms is equivalent  to the property that the optimal expected social value is  achieved with non-decreasing strategies (or threshold   strategies).1  In other words, this lemma implies that one can  always implement, with dominant strategies, the best   socialchoice rule that is achievable with non-decreasing strategies.  Our second contribution is in characterizing the optimal  action-bounded mechanisms. We identify some necessary  conditions for the optimality of mechanisms in general, and  using these conditions, we fully characterize the optimal  mechanisms in environments with two players and two   alternatives. The optimal mechanisms turn out to be diagonal  - that is, in their matrix representation, one alternative will  be chosen in, and only in, entries below one of the main   diagonals (this term extends the concept of Priority Games  used in [5] for bounded-communication auctions). We   complete the characterization of the optimal mechanisms with  the depiction of the optimal strategies - strategies that are  mutually maximizers. Since the payments in a   dominantstrategy implementation are uniquely defined by a monotone  allocation and a profile of strategies, this also defines the  payments in the mechanism. We give an intuitive proof for  the optimality of such strategies, generalizing the concept  of optimal mutually-centered strategies from [4].   Surprisingly, as opposed to the optimal auctions in [4], for some  non-trivial social-value functions, the optimal diagonal  mechanism may not utilize all the k available actions.  Theorem: For any multilinear single-crossing social-value  function over two alternatives, the informationally optimal  2-player k-action mechanism is diagonal, and the optimal  dominant strategies are mutually-maximizers.  Achieving a full characterization of the optimal   actionbounded mechanism for multi-player or multi-alternative  environments seems to be harder. To support this claim,  we observe that the number of mechanisms that satisfy the  necessary conditions above is growing exponentially in the  number of players.  1  The restriction to non-decreasing strategies is very   common in the literature. One remarkable result by Athey [1]  shows that when a non-decreasing strategy is a best response  for any other profile of non-decreasing strategies, a pure  Bayesian-Nash equilibrium must exist.  Our next result compares the expected social-value in  k-action mechanisms to the optimal expected social value  when the action space is unrestricted. For any number of  players or alternatives, and for any profile of independent  distribution functions, we construct mechanisms that are  nearly optimal - up to an additive difference of O( 1  k2 ). This  result is achieved in dominant strategies.  Theorem: For any multilinear social-value function, the  optimal k-action mechanism incurs an expected social loss  of O( 1  k2 ).  This is the same asymptotic rate proved for specific   environments in [19, 9, 5]. Note that there are social-choice  functions that can be implemented with k actions with no  loss at all (for example, the rule always choose alternative  A). However, we know that in some settings (e.g.,   auctions [5]) the optimal loss may be proportional to 1  k2 , thus  a better general upper bound is impossible.  Finally, we present our results in the context of several  natural applications. First, we give an explicit solution for  a public-good game with k-actions. We show that the   optimum is achieved in symmetric mechanisms (in contrast to  action-bounded auctions [5]), and that the optimal   allocation scheme depends on the value of the construction cost  C. Then, we study the celebrated signaling model, in which  potential employees send signals about their skills to   potential employers by means of the education level they acquire.  This is a natural application in our context since education  levels are often discrete (e.g., B.A, M.A and PhD). Lastly,  we present our results in the context of routing in networks,  where it is reasonable to assume that links report whether  they have low or high loss rates, but less reasonable to   require them to report their accurate loss rates. The latter  example illustrates how our results apply to settings where  the goal of the social planner is not welfare maximization  (nor variants of it like affine maximizers).  The rest of the paper is organized as follows: our model  and notations are described in Section 2. We then describe  our general results regarding implementation in multi-player  and multi-alternative environments in Section 3, including  the asymptotic analysis of the social-value loss. In   Section 4, we fully characterize the optimal mechanisms for   2player environments with two alternative. In Section 5, we  conclude with applying our general results to several   wellstudied models. Due to lack of space, some of the proofs  are missing and can be found in the full version that can be  found on the authors" web pages.  2. MODEL AND PRELIMINARIES  We first describe a standard mechanism-design model for  players with one-dimensional types. Then, in Subsection  2.2, we impose limitation on the action space. The   general model studies environments with n players and a set  A = {A1, A2, ..., Am} of m alternatives. Each player has a  privately known type θi ∈ [θi, θi] (where θi, θi ∈ R, θi < θi),  and a type-dependent valuation function vi(θi, A) for each  alternative A ∈ A. In other words, player i with type θi is  willing to pay an amount of vi(θi, A) for alternative A to be  chosen. Each type θi is independently distributed according  to a publicly known distribution Fi, with an always positive  density function fi. We denote the set of all possible type  profiles by Θ = ×n  i=1[θi, θi].  64  The social planner has a social-choice function c : Θ → A,  where the choice of alternatives is made in order to maximize  a social-value function g(  −→  θ ) : Θ × A → R. That is, c(  −→  θ ) ∈  argmaxA∈A{g(  −→  θ , A)}  We assume that for every alternative A ∈ A, the function  g(·, A) is continuous and differentiable in every type. Since  the players" types are private information, in order to choose  the optimal alternative, the social planner needs to get the  players" types as an input. The players reveal information  about their types by choosing an action, from an action set  B.  Each player uses a strategy for determining the action he  plays for any possible type. A strategy for player i is   therefore a function si : [θi, θi] −→ B. We denote a profile of  strategies by s = s1, ..., sn and the set of the strategies of all  players except i by s−i. The utility of player i of type θi from  alternative A under the payment pi is ui = vi(θi, A) − pi.  2.1 Dominant-Strategy Implementation  Following is a standard definition of a mechanism. The  action space B is traditionally implicit, but we mention it  explicitly since we later examine limitations on B.  Definition 1. A mechanism with an action set B is a  pair (t, p) where:  • t : Bn  → A is the allocation rule.2  • p : Bn  → Rn  is the payment scheme (i.e., pi(b) is the  payment to the ith player given a vector of actions b).  The main goal of this paper is to optimize the expected   social value (in action-bounded mechanisms) while preserving  a dominant-strategy equilibrium.  We say that a strategy si is dominant for player i in   mechanism (t, p) if player i cannot increase his utility by reporting  a different action than si(θi), regardless of the actions of the  other players b−i.3  Definition 2. We say that a social-choice function h is  implementable with a set of actions B if there exists a   mechanism (t, p) with a dominant-strategy equilibrium s1, ..., sn  (where for each i, si : [θi, θi] −→ B) that always chooses an  alternative according to h, i.e., t(s1(θ1), ..., sn(θn)) = h(  −→  θ ).  A fundamental result in the mechanism-design literature  states that under the single-crossing condition, the   monotonicity of the social-choice function is a sufficient and   necessary condition for dominant-strategy implementability  (in single-parameter environments). The single-crossing   condition (also known as the Spence-Mirrlees condition)   appears, very often implicitly, in almost every paper on   mechanism design in one-dimensional domains. Without this   assumption, general sufficient condition for implementability  are unknown (for a survey on this topic see [10]).   Throughout this paper, we assume that the valuation functions of  the players are single-crossing, as defined below. A player"s  valuation function will be single-crossing if the effect of an  increment in the player"s type on the player"s valuation for  2  We will show that, w.l.o.g., we can focus on deterministic  allocation schemes.  3  That is, for every type θi and every action bi, we have  that vi ( θi, t(si(θi), b−i) )-pi(si(θi), b−i)¿vi ( θi, t(bi, b−i)   )pi(bi, b−i)  two alternatives is always greater for one of these   alternatives. The single-crossing condition on the players"   preferences actually defines an order on the alternatives. For  example, if the value of player i for alternative A increases  more rapidly than his value for alternative B, we can denote  it by A i B. Later on, we will use these orders for defining  monotonicity of social-choice functions.  Definition 3. A function h : Θ × A → R is single   crossing with respect to i if there is a weak order i on the  alternatives, such that for any two alternatives Aj i Al we  have that for every  −→  θ ∈ Θ,  ∂h(  −→  θ , Aj )  ∂θi  >  ∂h(  −→  θ , Al)  ∂θi  and if Aj ∼ Al (that is, Al i Aj and Aj i Al) then  h(·, Aj) ≡ h(·, Al) (i.e., the functions are identical).  The definition of monotone social-choice functions also   requires an order on the actions. This order is implicit in  most of the standard settings where, for example, it is   defined by the order on the real numbers (e.g., in direct   revelation mechanisms where each type is drawn from a real  interval). When the action space is discrete, the order can  be determined by the names of the actions, for example,  0, 1,...,k-1 for k-action mechanisms. (We therefore  describe this order with the standard relation on natural  numbers <, >.)  Definition 4. A deterministic mechanism is monotone  if when player i raises his reported action, and fixing the  actions of the other players, the mechanism never chooses  an inferior alternative for i. That is, for any b−i ∈ {0, ..., k−  1}n−1  if bi > bi then t(bi, b−i) i t(bi, b−i).  Following is a classic result regarding the implementability  of social-choice functions in single-parameter environments.  Note, however, that this characterization does not hold when  the action space is bounded.  Proposition 1. Assume that the valuation functions  vi(θi, A) are single crossing and that the action space is   unrestricted. A social-choice function c is dominant-strategy  implementable if and only if c is monotone.  2.2 Action-Bounded Mechanisms  The set of actions B is usually implicit in the literature,  and it is assumed to be isomorphic to the type space. In this  paper, we study environments where this assumption does  not hold. We define a k-action game to be a game in which  the number of possible actions for each player is k, i.e., |B| =  k. In k-action games, the social planner typically cannot  always choose an alternative according to the social choice  function c due to the informational constraints. Instead,  we are interested in implementing a social-choice function  that, with k actions, maximizes the expected social value:  E−→  θ  g  −→  θ , t (s1(θ1), ..., sn(θn))    .  Definition 5. We say that a social-choice function h :  Θ → A is informationally achievable with a set of actions B  if there exists a profile of strategies s1, ..., sn (where for each  i, si : [θi, θi] −→ B), and an allocation rule t : Bn  → A,  such that t chooses the same alternative as h for any type  profile, i.e., t(s1(θ1), ..., t(θn)) = h(  −→  θ ). If |B| = k, we say  that h is k-action informationally achievable.  65  Note that this definition does not take into account   strategic considerations. For example, consider an environment  with two alternatives A = {A, B}, and the following   socialchoice function: ec(θ1, θ2) = A iff {θ1 > 1/2 and θ2 > 1/2}. ec  is informationally achievable with two actions: if both   players bid 0 when their value is greater than 1/2 and 1  otherwise, then the allocation rule choose alternative A iff  both players report 1 derives exactly the same allocation  for every profile of types. In contrast, it is easy to see that  the function ˆc(θ1, θ2) = A iff θ1 + θ2 > 1/2 is not   informationally achievable with two actions.  We now define a social-choice rule that maximizes the  social value under the information-theoretic constraints that  are implied by the limitations on the number of actions.  Definition 6. A social-choice function is k-action   informationally optimal with respect to the social-value function  g, if it achieves the maximal expected social value among all  the k-action informationally achievable social-choice   functions.4  Earlier in this section, we defined the single-crossing   property for the players valuations. We now define a   singlecrossing property on the social-value function g. This   property clearly ensures the monotonicity of the corresponding  social choice rule, and we will later show that it is also useful  for action-bounded environments.  Definition 7. We say that the social-choice rule g(  −→  θ , A)  exhibits the single-crossing property if for every player i, g  exhibits the single-crossing property with respect to i.  Note that the definition above requires that g will be   single crossing with respect to every player i, given her   individual order i on the alternatives. That is, the social value  function g will be compatible in this sense with the   singlecrossing conditions on the players" preferences.  Finally, we call attention to a natural set of strategies  - non-decreasing strategies, where each player reports a  higher action as her type increases. Equivalently, such  strategies are threshold strategies - strategies where each  player divides his type support into intervals, and simply  reports the interval in which her type lies.  Definition 8. A real vector x = (x0, x1, ..., xk) is a   vector of threshold values if x0 ≤ x1 ≤ ... ≤ xk.  Definition 9. A strategy si is a threshold strategy based  on a vector of threshold values x = (x0, x1, ..., xk), if for any  action j it holds that si(θi) = j iff θi ∈ [xj , xj+1]. A strategy  si is called a threshold strategy, if there exists a vector x of  threshold values such that si is a threshold strategy based on  x.  3. IMPLEMENTATION WITH A LIMITED  NUMBER OF ACTIONS  In this section, we study the general model of   actionbounded mechanism design. Our first result is a sufficient  and necessary condition for the implementability of the   optimal solution achievable with k actions: this condition says  that the optimal social-choice rule is achieved when all the  4  For simplicity, we assume that a maximum is attained and  thus the optimal function is well defined.  players use non-decreasing strategies. The basic idea is that  with non-decreasing strategies (i.e., threshold strategies), we  can apply the single-crossing property to show that when a  player raises his reported action, the expected value for his  high-priority alternatives increases faster; therefore,   monotonicity must hold. The result holds for any number of   players and alternatives, and for any profile of distribution   functions on the players" types, as long as they are statistically  independent. (It is easy to illustrate that this result does  not hold if the players" types are dependent.)  Lemma 1. Consider a single-crossing social-value   function g. The informationally optimal k-action social-choice  function c∗  (with respect to g) is implementable if and only if  c∗  achieves its optimum when the players use non-decreasing  strategies.  Next, we show that for a wide family of social-value   functions - multilinear functions - the price of implementation  is zero. That is, the information-theoretically optimal rule  is dominant-strategy implementable. This family of   functions captures many common settings from the literature.  In particular, it generalizes the auction setting studied by  Blumrosen et al. [4, 6].  Definition 10. A multilinear function is a polynomial  in which the degree of every variable in each monomial is at  most 1.5  We say that a social-choice rule g is multilinear,  if g(·, A) is multilinear for every alternative A ∈ A.  The basic idea behind the proof of the following theorem is  as follows: for every player, we show that the expected social  welfare when he chooses any action (fixing the strategies of  the other players) is a linear function of his type. This is a  result of the multilinearity of the social-value function and  of the linearity of expectation. The maximum over a set of  linear functions is a piecewise-linear function, hence the   optimal social value is achieved when the player uses threshold  strategies (the thresholds are the switching points). Since  the optimum is achieved with threshold strategies, we can  apply Lemma 1 to show the monotonicity of this   socialchoice rule. Note that in this argument we characterize the  players" strategies that maximize the social value, and not  the players" utilities.  Theorem 1. If the social-value function is multilinear  and single crossing, the informationally optimal k-action  social-choice function is implementable.  Proof. We will show that for any k-action mechanism,  the optimal expected social value is achieved when all   players use threshold strategies. This will be shown by proving  that for any player i and for any action bi of player i, the  expected welfare when she chooses the action bi is a   linear function in player i"s type θi. Then, it will follow from  Lemma 1 that the social choice function is implementable.  For every action bi of player i, let qA denote the   probability that alternative A is allocated, i.e.,  qA = Pr−→  θ  h  t(s(  −→  θ )) = A|si(θi) = bi  i  5  For example, f(x, y, z) = xyz + 5xy + 7.  66  Due to the linearity of expectation, the expected social  value when player i with type θi reports bi is:  X  A∈A  qA Eθ−i ( g(θi, θ−i, A) | t(bi, s−i(θ−i)) = A ) (1)  =  X  A∈A  qA  Z  θ−i  g(θi, θ−i, A)fA  −i(θ−i)d(θ−i) (2)  where fA  −i(θ−i) equals  Q  j=i fj (θj )  qA  for types profiles θ−i such  that t(bi, s−i(θ−i)) = A, and 0 otherwise.  Since g is multilinear, every function g(θi, θ−i, A) is a   linear function in θi, where the coefficients depend on the   values of θ−i. Denote this function by g(θi, θ−i, A) = λθ−i θi +  βθ−i . Thus, we can write Equation 2 as:  X  A∈A  qA  Z  θ−i  `  λθ−i θi + βθ−i  ´  fA  −i(θ−i)d(θ−i)  =  X  A∈A  qA θi  Z  θ−i  λθ−i fA  −i(θ−i)d(θ−i) +  Z  θ−i  βθ−i fA  −i(θ−i)d(θ−i)  !  In this expression, each integral is a constant   independent of θi when the strategies of the other player are fixed.  Therefore, each summand, thus the whole function, is a   linear function in θi. For achieving the optimal expected social  value, the player must choose the action that maximizes the  expected social value. A maximum of k linear functions is a  piecewise-linear function with at most k−1 breaking points.  These breaking points are the thresholds to be used by the  player. For all types between subsequent thresholds, the  optimum is clearly achieved by a single action; Since linear  functions are single-crossing, every action will be maximal  in at most one interval.  The same argument applies to all the players, and   therefore the optimal social value is obtained with threshold  strategies.  Observe that the proof of Theorem 1 actually works for  a more general setting. For proving that the   informationtheoretically optimal result is achieved with threshold   strategies, it is sufficient to show that the social-choice function  exhibits a single-crossing condition on expectation: given  any allocation scheme, and fixing the behavior of the other  players, the expected social value in any two actions (as a  function of θi) is single crossing. Theorem 1 shows that this  requirement holds for multilinear functions, but we were not  able to give an exact characterization of this general class of  functions.  The implementability of the information-theoretically   optimal solution makes the characterization of the optimal  incentive-compatible mechanisms significantly easier: we  can apply the standard mechanism-design technique and  first calculate the optimal allocation scheme and then find  the right payments.  Observe that if the valuation functions of the players are  linear and single crossing, then the social-welfare function  (i.e., the sum of the players" valuations) is multilinear and  single-crossing. This holds since the single-crossing   conditions on the valuations are defined with a similar order on  the alternatives as in the social-value function. Therefore,  an immediate conclusion from Theorem 1 is that the   optimal social welfare, which is achievable with k actions, is  implementable when the valuations are linear.  Corollary 1. If the valuation functions vi(·, A) are   single crossing and linear in θi for every player i and for every  alternative, then the informationally optimal k-action social  welfare function is implementable.  3.1 Asymptotic Analysis  In this section we show that the social value loss of   multilinear social-value rules diminishes quadratically with the  number of possible actions, k. This is the same asymptotic  ratio presented in the study of specific models in the same  spirit [19, 5, 18, 9]. The main challenge here, compared  to earlier results, is in dealing with the general   mechanismdesign framework, that allows a large family of social-value  functions for any number of players and alternatives. As   opposed to the specific models, the social-value function may  be asymmetric with respect to the players" types; for   instance, the social-value loss may a-priori occur in any   entry (i.e., profile of actions).  The basic intuition for the proof is that even for this   general framework, we can construct mechanisms where the  probability of having an allocation that is incompatible with  the original social-choice function is O( 1  k  ). (This fact holds  for all single-crossing social-choice functions, not only for  multilinear functions.) Then, we can use the multilinearity  to show that the social-value loss will always be O( 1  k  ) in  the mechanisms we construct. Taken together, the expected  loss becomes O( 1  k2 ). Our proof is constructive - we present  an explicit construction for a mechanism that exhibits the  desired loss in dominant strategies. The additive expected  social-value depends on the length of the support of the type  space. Hence, we assume that the type space is normalized  to [0, 1], that is, for every player i, θi = 0 and θi = 1.  Theorem 2. Assume that the type spaces are normalized  to [0, 1]. For any number of players and alternatives, and  for any set of distribution functions of the players" types, if  the social-value function g is single crossing and   multilinear, then the informationally optimal k-action social-choice  function (with respect to g) incurs an expected social-value  loss of O( 1  k2 ).  Moreover, as discussed in [4], this bound is asymptotically  tight. That is, there exists a set of distribution functions  for the players (the uniform distribution in particular) and  there are social-value functions (e.g., auctions) for which any  mechanism incurs a social-value loss of at least Ω( 1  k2 ). In  that sense, auctions are the hardest problems with respect to  the incurred loss. Yet, note that this claim does not imply  that the loss of any social-choice function will be   proportional to 1  k2 . For example, in the social choice function that  chooses the same alternative for any type profile, no loss will  be incurred (even with 0 actions).  67  4. OPTIMAL MECHANISMS FOR TWO  PLAYERS AND TWO ALTERNATIVES  In this section, we present a full characterization of the  optimal mechanisms in action-bounded environments with  two players and two alternatives, where the social-choice  functions are multilinear and single crossing.  Note that in this section, as in most parts of this paper,  we characterize monotone mechanisms by their allocation  scheme and by a profile of strategies for the players. Doing  this, we completely describe which alternative is chosen for  every profile of types of the players. It is well known that  in monotone mechanisms for one dimensional environments,  the allocation scheme uniquely defines the payments in the  dominant-strategy implementation. We find this   description, which does not explicitly mention the payments, easier  for the presentation.  A key notion in our characterization of the optimal   actionbounded mechanism, is the notion of non-degenerate   mechanisms. In a degenerate mechanism, there are two actions  for one of the players that are identical in their allocation.  Intuitively, a degenrate mechanism does not utilize all the  action space it is allowed to use, and therefore it cannot  be optimal. Using this propery, we then define diagonal  mechanisms that turns out to exactly characterize the set of  optimal mechanisms.  Definition 11. A mechanism is degenerate with respect  to player i if there exist two actions bi, bi for player i such  that for all profiles b−i of actions of the other players, the  allocation scheme is identical whether player i reports bi or  bi (i.e., ∀b−i, t(bi, b−i) = t(bi, b−i)).  For example, a 2-player mechanism is degenerate with   respect to the rows player, if there are two rows with   identical allocation in the matrix representation of the game.  Definition 12. A 2-player 2-alternative mechanism with  k-possible actions is called diagonal if it is monotone, and  non-degenerate with respect to at least one of the players.  The term diagonal originates from the matrix   representation of these mechanisms, in which one of the diagonals  determines the boundary between the choice of the two   alternatives (see Figure 1). Simple combinatorial   considerations show that diagonal mechanisms may come in very few  forms. Interestingly, one of these forms is degenerate with  respect to one of the players; that is, it can be described as  a mechanism with k − 1 actions for this player.  Proposition 2. Any diagonal 2-player mechanism has  one of the following forms:  1. If both players favor the same alternative (w.l.o.g.,  B i A for i = 1, 2) then either  (a). t(b1, b2) = B iff b1 + b2 ≥ k − 1  (b). t(b1, b2) = B iff b1 + b2 ≥ k.  2. If the two players have conflicting preferences (e.g.,  A 1 B and B 2 A) then either  (a). t(b1, b2) = B iff b1 ≥ b2  (b). t(b1, b2) = B iff b1 > b2.  In both cases, the optimal mechanism can also take the  form of one of the possibilities described, except one of the  players is not allowed to choose the fixed allocation action.  To complete the description of the optimal allocation  scheme, we now move to determine the optimal strategies  in diagonal mechanisms. We define the notion of   mutuallymaximizer thresholds, and show that threshold strategies  based on such thresholds are optimal. The reason why  mutually-maximizer strategies maximize the expected social  value in monotone mechanisms is intuitive: Consider some  action i (row in the matrix representation) for player 1. In  a monotone mechanism, the allocation in such a row will be  of the form [A, A, ..., B, B] (assuming that B 2 A). That  is, the alternative A will be chosen for low actions of player  2, and the alternative B will be chosen for higher actions of  player 2. By determining a threshold for player 2, the social  planner actually determines the minimal type of player 2  from which the alternative B will be chosen. For   optimizing the expected social value, this type for player 2 should  clearly be the type for which the expected social value from  A equals the expected social value from B (given that player  1 plays i); for greater values of player 2, the single-crossing  condition ensures that B will be preferred.  Definition 13. Consider a monotone 2-player   mechanism g that is non-degenerate with respect to the two   players, where the players use threshold strategies based on the  threshold vectors x, y. We say that the threshold xi of one  player (w.l.o.g. player 1) is a maximizer if  Eθ2 ( g(xi, θ2, A) | θ2 ∈ [yj , yj+1] ) =  Eθ2 ( g(xi, θ2, B) | θ2 ∈ [yj , yj+1] )  where j is the action of player 2 for which the mechanism  swaps the chosen alternative exactly when player 1 plays i,  i.e., t(i, j) = t(i − 1, j) (we denote, w.l.o.g., t(i, j) = A,  t(i − 1, j) = B).  The threshold vectors x, y are called mutually maximizers  if all their thresholds are maximizers (except the first and  the last).  It turns out that in 2-player, 2-alternative environments,  where the social-choice rule is multilinear and single   crossing, the optimal expected social value is achieved in   diagonal mechanisms with mutually-maximizer strategies. In the  proof, we start with a k × k allocation matrix, and show  that the mechanism cannot be degenerate with respect to  one of the players (we show how to choose this player). If  the player, w.l.o.g., the columns player, is degenerate, then  there are two columns with an identical allocation. These  two columns can be unified to a single action, and the   mechanism can therefore be described as a k × k − 1 matrix. We  then show that we can insert a new missing column, and  an appropriately chosen threshold, and strictly increase the  expected social value in the mechanism. Therefore, the   original mechanism was not the optimal k-action mechanism.  Theorem 3. In environments with two alternatives and  two players, if the social-value function is multilinear and  single crossing, then the optimal k-action mechanism is   diagonal, and the optimum is achieved with threshold strategies  that are mutually maximizers.  A corollary from the proof of Theorem 1 is that the optimal  2-player k-action mechanism may be degenerate for one of  the players (that is, equivalent to a game where one of the  players has only k − 1 different actions). However, the proof  identifies the following sufficient condition under which the  68  0 1 2 3  0 A A A B  1 A A B B  2 A B B B  3 B B B B  0 1 2 3  0 A A A A  1 A A A B  2 A A B B  3 A B B B  0 1 2 3  0 B B B B  1 A B B B  2 A A B B  3 A A A B  0 1 2 3  0 A A A B  1 A A B B  2 A B B B  Figure 1: The three left tables show all possible diagonal allocation scheme with 4 possible actions for each player.  The rightmost table show an example for a diagonal allocation scheme where one of the player has only k − 1 possible  actions.  optimal mechanism will be non-degenerate with respect to  both players: if the players" preferences are correlated (e.g.,  A 1 B and A 2 B), then the optimal alternative must be  the same under the profiles (θ1, θ2) and (θ1, θ2). Similarly,  if the players" preferences are conflicting (e.g., A 1 B and  B 2 A), then the optimal alternative must be the same  under the profiles (θ1, θ2) and (θ1, θ2). Examples in which  this condition holds are the public good model presented in  section 5 and auctions [5].  We do not know how to give an exact characterization of  the optimal mechanisms in multi-player and multi-alternati  ve environments. The hardness stems from the fact that the  necessary conditions we specified before for the optimality  of the mechanisms (i.e., non-degenrate and monotone   allocations) are not restrictive enough for the general model. In  other words, for n > 2 players, the number of monotone and  non-degenerate mechanisms becomes exponential in n.  Proposition 3. The number of monotone non-   degenerate k-action mechanisms in an n-player game is exponential  in n, even if |A| = 2.  5. EXAMPLES  Our results apply to a variety of economic, computational  and networked settings. In this section, we demonstrate the  applicability of our results to public-good models, signaling  games and routing applications.  5.1 Application 1: Public Goods  The public-good model deals with a social planner (e.g.,  government) that needs to decide whether to supply a   public good, such as building a bridge. Let Y es and No denote  the respective alternatives of building and not building the  bridge. v = v1, . . . , vn is the vector of the players"   typesthe values they gain from using the bridge. The decision that  maximizes the social welfare is to build the bridge if and only  if  P  i vi is greater than its cost, denoted by C. If the bridge  is built, the social welfare is  P  i vi − C, and zero otherwise;  thus, g(v, Y es) =  P  i vi − C, and g(v, No) = 0. The utility  of player i under payment pi is ui = vi − pi if the bridge is  built, and 0 otherwise. It is well-known that under no   restriction on the action space, it is possible to induce truthful  revelation by VCG mechanisms, therefore full efficiency can  be achieved. Obviously, when the action set is limited to  k actions, we cannot achieve full efficiency due to the   informational constraints. Yet, since g(v, Y es) and g(v, No)  are multilinear and single crossing, we can directly apply  Theorem 1. Hence, the information-theoretically optimal   kaction mechanism is implementable in dominant strategies.  Corollary 2. The k-action informationally optimal   social welfare in the n-player public-good game is  implementable in dominant strategies.  Moreover, as Theorem 3 suggests, in the k-action 2-player  public-good game, we can fully characterize the optimal  mechanisms. In the proof of Theorem 3, we saw that when  for both players g(θi, θi, A) = g(θi, θi, B), the mechanism is  non-degenerate with respect to both players.6  This   condition clearly holds here (1+ 0− C = 0+ 1− C), therefore the  optimal mechanisms will use all k actions.  Corollary 3. The optimal expected welfare in a 2-player  k-action public-good game is achieved with one of the   following mechanisms:7  1. Allocation: Build the bridge iff b1 + b2 ≥ k.  Strategies: Threshold strategies based on the vectors  −→x ,−→y where for every 1 ≤ i ≤ k-1,  xi = C − E[v2|v2 ∈ [yk−i, yk−i+1]]  yi = C − E[v1|v1 ∈ [xk−i, xk−i+1]]  2. Allocation: Build the bridge iff b1 + b2 ≥ k − 1.  Strategies: Threshold strategies based on the vectors  −→x ,−→y where for every 1 ≤ i ≤ k-1:  xi = C − E[v2|v2 ∈ [yk−i−1, yk−i]]  yi = C − E[v1|v1 ∈ [xk−i−1, xk−i]]  Recall that we define the optimal mechanisms by their   allocation scheme and by the optimal strategies for the   players. It is well known, that the allocation scheme in   monotone mechanisms uniquely defines the payments that ensure  incentive-compatibility. In public-good games, these   payments satisfy the rule that a player pays his lowest value for  which the bridge is built, when the action of the other player  is fixed. Therefore, the payments for the players 1 and 2   reporting the actions b1 and b2 are as follows: in mechanism  1 from Proposition 3, p1 = xb2 and p2 = yb1 ; in mechanism  2 from Proposition 3, p1 = xb2−1 and p2 = yb1−1.  We now show a more specific example that assumes   uniform distributions. The example shows how the optimal  mechanism is determined by the cost C: for low costs,   mechanism of type 1 is optimal, and for high costs the optimal  mechanism is of type 2. An additional interesting feature of  the optimal mechanisms in the example is that they are   symmetric with respect to the players. This come as opposed to  the optimal mechanisms in the auction model [5] that are  asymmetric (even when the players" values are drawn from  identical distributions).  6  More precisely, the condition for non-degeneracy when  B 1 A and B 2 A is that sign(g(θi, θi, A)−g(θi, θi, B)) =  sign(g(θi, θi, A) − g(θi, θi, B)) (when sign(0) is considered  both negative and positive).  7  We denote x0 = y0 = 0 and xk = yk = 1.  69  C ≤ 1 0 1  0  No  p1 = p2 = 0  No  p1 = p2 = 0  1  No  p1 = p2 = 0  Yes  p1 = p2 = 2  3  C − 1  3  C ≥ 1 0 1  0  No  p1 = p2 = 0  Yes  p1 = 0; p2 = 2C  3  1  Yes  p1 = 2C  3  ; p2 = 0  Yes  p1 = p2 = 0  Figure 2: Optimal mechanisms in a 2-player, 2-alternative, 2-action public-goods game, when the types are uniformly  distributed in [0, 1]. The mechanism on the left is optimal when C ≤ 1 and the other is optimal when C ≥ 1.  Example 1. Suppose that the types of both players are  uniformly distributed on [0, 1]. Figure 2 illustrates the   optimal mechanisms for k = 2, and shows how both the   allocation scheme and the payments depend on the construction  cost C. Then, the welfare-maximizing mechanisms are:  • If the cost of building is at least 1:  Allocation: Build iff b1 + b2 ≥ k  Strategies: The thresholds of both players are (for i =  {1, . . . , k − 1}), xi = 2(k−i)·C  2k−1  − 2k−4i+1  2k−1  • If the cost of building is smaller than 1:  Allocation: Build iff b1 + b2 ≥ k − 1  Strategies: The thresholds of both players are (for i =  {1, . . . , k − 1}), xi = 2iC  2k−1  5.2 Application 2: Signaling  We now study a signaling model in labor markets. In  this model, the type of each worker, θi ∈ [θ, θ], describes  the worker"s productivity level. The firm wants to make her  hiring decisions according to a decision function f(  −→  θ ). For  example, the firm may want to hire the most productive  worker (like the auction model), or hire a group of   workers only if their sum of productivities is greater than some  threshold (similar to the public-good model). However, the  worker"s productivity is invisible to the firm; the firm only  observes the worker"s education level e that should convey  signals about her productivity level. Note that the   assumption here is that acquiring education, at any level, does not  affect the productivity of the worker, but only signals about  the worker"s skills.  A main component in this model, is the fact that as the  worker is more productive, it is easier for him to acquire  high-level education. In addition, the cost of acquiring   education increases with the education level. More formally,  a continuous function C(e, θ) describes the cost to a worker  from acquiring each education level as a function of his   productivity. The standard assumptions about the cost   function are: ∂C  ∂e  > 0, ∂C  ∂θ  < 0, ∂C  ∂e∂θ  < 0, where the latter   requirement is exactly equivalent to the single-crossing   property (when C is differentiable in both variables). The utility  of a worker is determined according to the education level he  chooses and the wage w(e) attached to this education level,  that is, ui(e, θi) = −C(θi, e) + w(e).  An action for a worker in this game is the education level  he chooses to acquire. In standard models, this action space  is continuous, and then a fully separating equilibrium   exists (under the single-crossing conditions on the cost   function). That is, there exists an equilibrium in which every  type is mapped into a different education level; thus, the  firm can induce the exact productivity levels of the workers  by this signaling mechanism. However, it is hard to imagine  a world with a continuum of education levels. It is usually  the case that there are only several discrete education levels  (e.g., BSc, MSc, PhD).  With k education levels, the firm may not be able to   exactly follow the decision function f. For achieving the best  result in k actions, the firm may want the workers to play   according to specific threshold strategies. It turns out that the  standard condition, the single-crossing condition on the cost  function, suffices for ensuring that these threshold strategies  will be dominant for the players. We can now apply   Theorem 2, and show that if the decision function f of the firm  is multilinear (i.e., the decisions are made to maximize a  set of multilinear functions), then the firm can design the  education system such that the expected loss will be O( 1  k2 ),  with a dominant-strategy equilibrium. Note that while in  the classic example of the job market it is not reasonable for  each firm to select the education level, in other reasonable  applications the social planners may be able to determine  the thresholds, e.g., by fixing the levels of qualifying exams  or other means for the players to demonstrate their skills.  Corollary 4. Consider a multilinear decision function  f, and a single-crossing cost function for the players. With k  education levels, the firm can implement in dominant   strategies a decision function that incurs a loss of O( 1  k2 ) compared  with the decision function f.  5.3 Application 3: Routing  In our last example, we show the applicability of our   results to routing in lossy networks. In such systems, a sender  needs to decide through which network to transmit his   message. It is natural to assume that the agents (i.e., links) may  not be able to report their accurate probabilities of success,  but only, e.g., whether these are low, intermediate, or  high. In this example, we focus on parallel-path networks.  Let N1, N2 denote two networks, where each network is  composed of multiple parallel paths with variable lengths  from a given source to a given sink (an example for such a  network appears in Figure 3). The edges in these networks  are controlled by different selfish agents, and each edge   appears only in one of the networks. Suppose that the sender,  who wishes to send a message from the source to the sink,  knows the topology of each network, but the probability of  success on each link, pi, is the link"s private information.  The problem of the sender is to decide whether to send a  message through the network N1 or through an alternate  network N2. Obviously, the sender wishes to send the   message through N1 only if the total probability of success in N1  is greater than the success probability in N2. Let fN  (−→p )   denote the probability of success in network N with a   successprobability vector −→p . The social choice function in this   example is thus: c(−→p ) ∈ argmax{N1,N2}{fN1  (−→p ), fN2  (−→p )}.  70  p5p4  p3  p2p1  s t  Figure 3: An example for a parallel-path network,  where each link has a probability pi for transmission   success. We show that the overall probability of success in  such networks is multilinear in pi, and thus the optimal  k-action social-choice function is dominant-strategy   implementable.  In this example, we assume that every agent has a   singlecrossing valuation function over the alternatives. That is,  each player wishes that the message will be sent through  his network, and his benefit is positively correlated with his  secret data (e.g., the valuation of player i may be exactly  pi). We would like to emphasize that the social planner  in this example (the sender) does not aim to maximize the  social welfare. That is, the social value is not the sum of the  players" types nor any weighted sum of the types (affine  maximizer).  The success probability of sending a message through a  parallel-path network is multilinear, since it can be expressed  by the following multilinear formula (where P denotes the  set of all paths between the source and the sink):  1 −  Y  P ∈P  (1 −  Y  j∈P  pj) (3)  For example, in the network presented in figure 3, the  probability of success is given by  f(−→p ) = 1 − (1 − p1p2) · (1 − p3) · (1 − p4p5)  Thus, if all the candidate networks are parallel-path   networks, the social-value function is multilinear, and we can  apply Theorem 1 and get the following corollary. Note that  for every link i, the partial derivative in pi of the success  probability written in Equation 3 is positive. In all the other  networks, that do not contain link i, the partial derivative  is clearly zero. Therefore, the social-value function is single  crossing and our general results can be applied.  Corollary 5. For any social-choice function that   maximizes the success probability over parallel-path networks,  the informationally optimal k-action social-choice function  is implementable (for any k).  Acknowledgment. We thank Noam Nisan for helpful   discussions and anonymous referees for helpful comments. This  work is supported by grants from the Israeli Academy of  Sciences and the USA-Israel Binational Science Foundation.  The work of the second author is also supported by the Lady  Davis Trust Fellowship.  6. REFERENCES  [1] S. Athey. Single crossing properties and the existence  of pure strategy equilibria in games of incomplete  information. Econometrica, 69(4):861-89, 2001.  [2] M. Babaioff and L. Blumrosen.  Computationally-feasible auctions for convex bundles.  In APPROX 04, pages 27-38, 2004.  [3] M. Babaioff, R. Lavi, and E. Pavlov. Mechanism  design for single-value domains. In AAAI"05, pages  241-247, 2005.  [4] L. Blumrosen and N. Nisan. Auctions with severely  bounded communications. 43th Annual Symposium on  Foundations of Computer Science (FOCS 2002), 2002.  [5] L. Blumrosen, N. Nisan, and I. Segal. Auctions with  severely bounded communications. Working paper,  The Hebrew University. Preliminary versions appeared  in FOCS 2002 and ESA 03., 2003.  [6] L. Blumrosen, N. Nisan, and I. Segal. Multi-player  and multi-round auctions with severely bounded  communication. ESA 2003, 2003.  [7] M. Chwe. The discrete bid first price auction. In  Economics Letters, volume 31, pages 303-306, 1989.  [8] E. David, A. Rogers, J. Schiff, S. Kraus, and  N. Jennings. Optimal design of english auctions with  discrete bid levels. In EC 05.  [9] R. M. Harstad and M. H. Rothkopf. On the role of  discrete bid levels in oral auctions. Europian Journal  of Operations Research, pages 572-581, 1994.  [10] B. E. Hermalin. Lecture notes in economics, 2005.  [11] A. Kress and C. Boutilier. A study of limited  precision, incremental elicitation in auctions. In  AAMAS 04.  [12] K. Larson and T. Sandholm. Costly valuation  computation in auctions. In 8th conference of  theoretical aspects of knowledge and rationality, 2001.  [13] R. Lavi, A. Mu"alem, and N. Nisan. Towards a  characterization of truthful combinatorial auctions. In  In Proceedings of the 44th Annual IEEE Symposium  on Foundations of Computer Science (FOCS), 2003.,  2003.  [14] P. McAfee. Coarse matching. Econometrica,  70(5):2025-2034, 2002.  [15] R. B. Myerson. Optimal auction design. Mathematics  of Operations Research, 6(1):58-73, 1981.  [16] M. Naor, B. Pinkas, and R. Summer. Privacy  preserving auctions and mechanism design. In ACM  Conference on Electronic Commerce, 1999.  [17] T. Sandholm and A. Gilpin. Sequences of  take-it-or-leave-it offers: Near-optimal auctions  without full-valuation revelation. In AMEC-V, 2003.  [18] M. A. Satterthwaite and S. R. Williams. The  optimality of a simple market mechanism.  Econometrica, 70(5):1841-1863, 2002.  [19] R. Wilson. Efficient and competitive rationing.  Econometrica, 57:1-40, 1989.  71