MATCHING AND MARKET DESIGN: AN INTRODUCTION TO SELECTED TOPICS*

This paper provides a survey of the research in matching and market design. We discuss both basic theories and recent advances. Emphasis is placed on applications of the theory to practical problems.     

STRATEGIC CANDIDACY AND SINGLE‐PEAKEDNESS*

In elections, the voting outcomes are affected by strategic entries of candidates. We study a class of voting rules immune to strategic candidacy. Dutta et al. (2001 ) show that such rules satisfying unanimity are dictatorial if all orderings of candidates are admissible for voters’ preferences. When voters’ preferences are single‐peaked over a political spectrum, there exist non‐dictatorial rules immune to strategic candidacy. An example is the rule selecting the m‐th peak from the left among the peaks of voters’ preferences, where m is any natural number no more than the number of voters. We show that immunity from strategic candidacy with basic axioms fully characterizes the family of the m‐th leftmost peak rules.     

Bidder collusion

We analyze bidder collusion at first-price and second-price auctions. Our focus is on less than all-inclusive cartels and collusive mechanisms that do not rely on auction outcomes. We show that cartels that cannot control the bids of their members can eliminate all ring competition at second-price auctions, but not at first-price auctions. At first-price auctions, when the cartel cannot control members’ bids, cartel behavior involves multiple cartel bids. Cartels that can control bids of their members can suppress all ring competition at both second-price and first-price auctions; however, shill bidding reduces the profitability of collusion at first-price auctions.     

ON THE NEUTRALITY OF COALITION FORMATION IN A PURE BARGAINING PROBLEM*

We consider the sequential bargaining game à la Stahl–Binmore–Rubinstein with random proposers, juxtaposing an ex ante coalition formation stage to their bargaining game. On the basis of the expected outcomes in the negotiation over how to split a dollar, players can form coalitions in a sequential manner, within each of which they can redistribute their payoffs. It turns out that the grand coalition does form, and that each player receives his discounted expected payoff, which is obtained by playing as a single player in the negotiation, although there could be many equilibria in the bargaining stage.     

Interlinkage and Generous Tit‐for‐Tat Strategy

We investigate an infinitely‐repeated prisoners' dilemma with imperfect monitoring and consider the possibility that the interlinkage of the players' distinct activities enhances implicit collusion. We show a necessary and sufficient condition for the existence of a generous tit‐for‐tat Nash equilibrium. Such an equilibrium, if it exists, is unique. This equilibrium achieves approximate efficiency when monitoring is almost perfect, where the discount factors are fixed.     

Role of honesty in full implementation

This paper introduces a new concept of full implementation that takes into account agents’ preferences for understanding how the process concerning honest reporting works. We assume that the agents have intrinsic preferences for honesty in the sense that they dislike the idea of lying when it does not influence their welfare but instead goes against the intention of the central planner. We show that the presence of such preferences functions in eliminating unwanted equilibria from the practical perspective, even if the degree of the preference for honesty is small. The mechanisms designed are detail free and involve only small fines.     

Information in conflicts

We consider two-player contests for a prize of common but uncertain value. For settings where one player knows the value of the prize, while the other only knows its prior distribution, we give conditions for when the uninformed agent is ex ante strictly more likely to win the prize than is the informed agent. In the special case of a lottery contest, equilibrium expenditures are lower under asymmetric information than if either both agents are informed or neither agent is informed.     

On the informational inefficiency of discriminatory price auctions

We analyze bidding behavior in large discriminatory-price auctions in a common value setting where the number of objects is a non-trivial proportion of the number of bidders. We show that the average price paid in the auction is biased downward from the expected value of the objects, even in the competitive limit. We show that conditional on a signal that falls below a threshold, a bidder bids no more than the expected value of an object conditional on the signal and winning; while conditional on any signal that lies above the threshold the bid is strictly lower than the expected value conditional on the signal and winning.     

Strategy-proof assignment on the full preference domain

We consider the problem of efficiently allocating several indivisible objects between agents who are to receive at most one object and whose preferences are private information. We examine this standard “assignment” problem from the perspective of mechanism design giving up the usual assumption of linear preferences and instead using a full preference domain (with indifferences permitted). We characterize two classes of mechanisms: (i) Bi-polar Serially Dictatorial Rules by Essential Single-Valuedness, Pareto Indifference, Strategy-Proofness and Non-Bossiness; and (ii) all selections from Bi-polar Serially Dictatorial Rules by Single-Valuedness, Efficiency, Strategy-Proofness and Weak Non-Bossiness. We compare the outcomes from the (Bi-polar) Serially Dictatorial Rules with the outcomes obtained using a market based approach, namely the “core” of the market. We show that all strongly efficient outcomes in the core can be generated using Serially Dictatorial Rules. Moreover, we argue that Serially Dictatorial Rules have an advantage over the market based approach in that they yield strongly efficient solutions for all preference profiles, making it possible to use randomization to restore equity. When preferences are private information, this type of ex ante equity cannot be implemented using the market based approach.     

Would letting people vote for multiple candidates yield policy moderation?

We investigate whether letting people vote for multiple candidates would yield policy moderation. We do so in a setting that takes three key features of elections into account, namely, strategic voting, endogenous candidacy and policy motivation on the part of the candidates. We consider two classes of voting rules. One class consists of the voting rules where each voter casts several equally-weighed votes for the different candidates. The other class consists of the voting rules where each voter rank-orders the candidates. We identify conditions under which these voting rules yield policy moderation. We also show that these voting rules may yield policy extremism instead of policy moderation if one (or several) of the conditions is not satisfied! Finally, we find that amongst these voting rules the extent of policy moderation is maximal under the Borda Count if we consider only equilibria where all candidates are serious contenders. However, this result does not carry over to spoiler equilibria, where Approval Voting can yield more moderate policy outcomes than the Borda Count.     

Dynamic Multi‐Activity Contests*

We develop a model of dynamic multi‐activity contests. Players simultaneously choose efforts in long‐run activities, observe each other's efforts in these activities, and then simultaneously choose efforts in short‐run activities. A player's long‐run and short‐run efforts complement each other in determining the player's probability of winning. We compare the outcomes of this two‐stage model to those of the corresponding model in which players choose efforts in all activities simultaneously. Interestingly, effort expenditures are always lower in the sequential multi‐activity contest than in the simultaneous multi‐activity contest. The implications of this result for the organization of military, litigation, innovation, academic, and sporting contests are highlighted.     

THE SECOND‐PRICE AUCTION SOLVES KING SOLOMON'S DILEMMA*

The planner wants to give k identical, indivisible objects to the top k valuation agents at zero costs. Each agent knows her own valuation of the object and whether it is among the top k. Modify the (k+ 1)st‐price sealed‐bid auction by introducing a small participation fee and the option not to participate in it. This simple mechanism implements the desired outcome in iteratively undominated strategies. Moreover, no pair of agents can profitably deviate from the equilibrium by coordinating their strategies or bribing each other.     

A three-player dynamic majoritarian bargaining game

We analyze an infinitely repeated divide-the-dollar bargaining game with an endogenous reversion point. In each period a new dollar is divided among three legislators according to the proposal of a randomly recognized member—if a majority prefer so—or according to previous period's allocation otherwise. Although current existence theorems for Markovian equilibria do not apply for this dynamic game, we fully characterize a Markov equilibrium. The equilibrium is such that irrespective of the discount factor or the initial division of the dollar, the proposer eventually extracts the whole dollar in all periods. We also show that proposal strategies are weakly continuous in the status quo that equilibrium expected utility is not quasi-concave, and the correspondence of voters’ acceptance set (the set of allocations weakly preferred over the status quo) fails lower hemicontinuity.     

Bargaining foundations of the median voter theorem

We give a game-theoretic foundation for the median voter theorem in a one-dimensional bargaining model based on Baron and Ferejohn's [D. Baron, J. Ferejohn, Bargaining in legislatures, Amer. Polit. Sci. Rev. 83 (1989) 1181-1206] model of distributive politics. We prove that as the agents become arbitrarily patient, the set of proposals that can be passed in any pure strategy, subgame perfect equilibrium collapses to the median voter's ideal point. While we leave the possibility of some delay, we prove that the agents' equilibrium continuation payoffs converge to the utility from the median, so that delay, if it occurs, is inconsequential. We do not impose stationarity or any other refinements. Our result counters intuition based on the folk theorem for repeated games, and it contrasts with the known result for the distributive bargaining model that as agents become patient, any division of the dollar can be supported as a subgame perfect equilibrium outcome.     

Partially Binding Platforms: Campaign Promises vis‐à‐vis Cost of Betrayal

This study examines and models the effects of partially binding campaign platforms in a political competition. Here, a candidate who implements a policy that differs from the platform must pay a cost of betrayal, which increases with the size of the discrepancy. I also analyse endogenous decisions by citizens to run for an election. In particular, the model is able to show two implications that previous frameworks have had difficulty with. First, candidates with different characteristics have different probabilities of winning an election. Second, even knowing that he/she will lose an election, a candidate will still run, hoping to make an opponent's policy approach his/her own policy.     

Menu-dependent preferences and revelation principle

We extend the set of preferences to include menu-dependent preferences and characterize the domain in which the revelation principle holds. A weakening of the well-known contraction consistency is shown to define a subset of this domain. However, we show that minimax-regret preference can be outside the domain.     

A simple sufficient condition for strong implementation

In an important step forward Maskin [E. Maskin, Nash equilibrium and welfare optimality, Rev. Econ. Stud. 66 (1999) 23–38] showed that two properties – monotonicity and no veto power – are together sufficient for Nash implementation. In contrast to the vast literature that followed, this characterization has two major advantages: First, it is often easy to verify, and second, it has an elegant and simple interpretation. However, there does not exist a similar condition for social choice correspondences that are implementable in strong equilibrium. All existing characterizations are either hard to verify or apply only to comprehensive preference domains. In this paper we improve the situation by giving one such condition. Moreover, using well-known examples we show that this is a practical tool.     

Informational limitations of ascending combinatorial auctions

We study the inherent limitations of natural widely-used classes of ascending combinatorial auctions. Specifically, we show that ascending combinatorial auctions that do not use both non-linear prices and personalized prices cannot achieve social efficiency with general bidder valuations. We also show that the loss of efficiency can be severe and that only a diminishing fraction of the social welfare may be captured. This justifies the added complexity in the auctions suggested by, e.g., Parkes and Ungar (2000) [29] and Ausubel and Milgrom (2002) [2].     

WHO SEARCHES?*

We consider a directed search model with buyers and sellers and determine whether buyers look for sellers or vice versa. The buyers and sellers can choose to search or wait; what they do in equilibrium depends on the relative size of the two populations and the price formation mechanism. We study bargaining and auctions and find that when one population is much larger than the other the former searches and the latter waits. Under auction with roughly equal populations some buyers and sellers search and some wait. Our results challenge the practice of postulating who searches and who waits.     

Substitutes and stability for matching with contracts

We consider the matching with contracts framework of Hatfield and Milgrom [20], and we introduce new concepts of bilateral and unilateral substitutes. We show that the bilateral substitutes condition is a sufficient condition for the existence of a stable allocation in this framework. However, the set of stable allocations does not form a lattice under this condition, and there does not necessarily exist a doctor-optimal stable allocation. Under a slightly stronger condition, unilateral substitutes, the set of stable allocations still does not necessarily form a lattice with respect to doctors' preferences, but there does exist a doctor-optimal stable allocation, and other key results such as incentive compatibility and the rural hospitals theorem are recovered.