Assortative Matching with Externalities and Farsighted Agents

We consider a one-to-one assortative matching problem in which matched pairs compete for a prize. With such externalities, the standard solution concept, pairwise stable matching, may not exist. In this paper, we consider farsighted agents and analyze the largest consistent set (LCS) of Chwe (1994). Despite the assortative structure of the problem, LCS tend to be large with the standard effectiveness functions: LCS can be the set of all matchings, including an empty matching with no matched pair. By modifying the effectiveness function motivated by Knuth (1976), LCS becomes a singleton of the positive assortative matching. Our results suggest that the choice of effectiveness function can sig..

Economic Design

Stability in Matching with Externalities: Pairs Competition and Oligopolistic Joint Ventures

This paper presents one-to-one matching and assignment problems with externalities across pairs such as pairs figure skating competition and joint ventures in oligopolistic markets. In these models, players care not only about their partners but also which and how many rival pairs are formed. Thus, it is important for a deviating pair to know which matching will realize after it deviates from a matching (an effectiveness function) in order to define pairwise stable matching. Using a natural effectiveness function for such environments, we show that the assortative matching is pairwise stable. We discuss two generalizations of our model including intrinsic preferences on partners and pair-spe..

Economic Design

Approximately Efficient Bilateral Trade

We study bilateral trade between two strategic agents. The celebrated result of Myerson and Satterthwaite states that in general, no incentive-compatible, individually rational and weakly budget balanced mechanism can be efficient. I.e., no mechanism with these properties can guarantee a trade whenever buyer value exceeds seller cost. Given this, a natural question is whether there exists a mechanism with these properties that guarantees a constant fraction of the first-best gains-from-trade, namely a constant fraction of the gains-from-trade attainable whenever buyer's value weakly exceeds seller's cost. In this work, we positively resolve this long-standing open question on constant-factor..

Economic Design

Foundations of Transaction Fee Mechanism Design

In blockchains such as Bitcoin and Ethereum, users compete in a transaction fee auction to get their transactions confirmed in the next block. A line of recent works set forth the desiderata for a "dream" transaction fee mechanism (TFM), and explored whether such a mechanism existed. A dream TFM should satisfy 1) user incentive compatibility (UIC), i.e., truthful bidding should be a user's dominant strategy; 2) miner incentive compatibility (MIC), i.e., the miner's dominant strategy is to faithfully implement the prescribed mechanism; and 3) miner-user side contract proofness (SCP), i.e., no coalition of the miner and one or more user(s) can increase their joint utility by deviating from the..

Economic Design

Obvious Manipulability of Voting Rules

The Gibbard-Satterthwaite theorem states that no unanimous and non-dictatorial voting rule is strategyproof. We revisit voting rules and consider a weaker notion of strategyproofness called not obvious manipulability that was proposed by Troyan and Morrill (2020). We identify several classes of voting rules that satisfy this notion. We also show that several voting rules including k-approval fail to satisfy this property. We characterize conditions under which voting rules are obviously manipulable. One of our insights is that certain rules are obviously manipulable when the number of alternatives is relatively large compared to the number of voters. In contrast to the Gibbard-Satterthwaite ..

Economic Design

Going... going... wrong: a test of the level-k (and cognitive hierarchy) models of bidding behaviour

In this paper, we design and implement an experiment aimed at testing the level-k model of auctions. We begin by asking which (simple) environments can best disentangle the level-k model from its leading rival, Bayes-Nash equilibrium. We find two environments that are particularly suited to this purpose: an all-pay auction with uniformly distributed values, and a first-price auction with the possibility of cancelled bids. We then implement both of these environments in a virtual laboratory in order to see which theory can best explain observed bidding behaviour. We find that, when plausibly calibrated, the level-k model substantially under-predicts the observed bids and is clearly out-perfor..

Economic Design

Nash Convergence of Mean-Based Learning Algorithms in First Price Auctions

We consider repeated first price auctions where each bidder, having a deterministic type, learns to bid using a mean-based learning algorithm. We completely characterize the Nash convergence property of the bidding dynamics in two senses: (1) time-average: the fraction of rounds where bidders play a Nash equilibrium approaches to 1 in the limit; (2) last-iterate: the mixed strategy profile of bidders approaches to a Nash equilibrium in the limit. Specifically, the results depend on the number of bidders with the highest value: - If the number is at least three, the bidding dynamics almost surely converges to a Nash equilibrium of the auction, both in time-average and in last-iterate. - If th..

Economic Design

Maskin Meets Abreu and Matsushima

The theory of full implementation has been criticized for using integer/modulo games which admit no equilibrium (Jackson (1992)). To address the critique, we revisit the classical Nash implementation problem due to Maskin (1999) but allow for the use of lotteries and monetary transfers as in Abreu and Matsushima (1992, 1994). We unify the two well-established but somewhat orthogonal approaches in full implementation theory. We show that Maskin monotonicity is a necessary and sufficient condition for (exact) mixed-strategy Nash implementation by a finite mechanism. In contrast to previous papers, our approach possesses the following features: finite mechanisms (with no integer or modulo game)..

Economic Design

Stability and Efficiency of Random Serial Dictatorship

This paper establishes non-asymptotic convergence of the cutoffs in Random serial dictatorship in an environment with many students, many schools, and arbitrary student preferences. Convergence is shown to hold when the number of schools, $m$, and the number of students, $n$, satisfy the relation $m \ln m \ll n$, and we provide an example showing that this result is sharp. We differ significantly from prior work in the mechanism design literature in our use of analytic tools from randomized algorithms and discrete probability, which allow us to show concentration of the RSD lottery probabilities and cutoffs even against adversarial student preferences.

Economic Design

Equilibria in Matching Markets with Soft and Hard Liquidity Constraints

We consider a matching with contracts model in the presence of liquidity constraints on the buyers side. Liquidity constraints can be either soft or hard. A convergent sequence of economies with increasingly stringent soft liquidity constraints is an economy with hard liquidity constraints at the limit. The limit of a corresponding convergent sequence of competitive equilibria may fail to be a competitive equilibrium in the limit economy. We establish limit results of two alternative notions of competitive equilibrium, quantity-constrained competitive equilibrium and expectational equilibrium, which do not suffer from such discontinuity problems. The implications of these limit results are d..

Economic Design

Decentralized Payment Clearing using Blockchain and Optimal Bidding

In this paper, we construct a decentralized clearing mechanism which endogenously and automatically provides a claims resolution procedure. This mechanism can be used to clear a network of obligations through blockchain. In particular, we investigate default contagion in a network of smart contracts cleared through blockchain. In so doing, we provide an algorithm which constructs the blockchain so as to guarantee the payments can be verified and the miners earn a fee. We, additionally, consider the special case in which the blocks have unbounded capacity to provide a simple equilibrium clearing condition for the terminal net worths; existence and uniqueness are proven for this system. Finall..

Economic Design

Constrained School Choice with Incomplete Information

School choice is the two-sided matching market where students (on one side) are to be matched with schools (on the other side) based on their mutual preferences. The classical algorithm to solve this problem is the celebrated deferred acceptance procedure, proposed by Gale and Shapley. After both sides have revealed their mutual preferences, the algorithm computes an optimal stable matching. Most often in practice, notably when the process is implemented by a national clearinghouse and thousands of schools enter the market, there is a quota on the number of applications that a student can submit: students have to perform a partial revelation of their preferences, based on partial information..

Economic Design

Matching markets with middlemen under transferable utility

This paper studies matching markets in the presence of middlemen. In our framework, a buyer-seller pair may either trade directly or use the services of a middleman; and a middleman may serve multiple buyer-seller pairs. Direct trade between a buyer and a seller is costlier than a trade mediated by a middleman. For each such market, we examine an associated cooperative game with transferable utility. First, we show that an optimal matching for a matching market with middlemen can be obtained by considering the two-sided assignment market where each buyer-seller pair is allowed to use the mediation service of the middlemen free of charge and attain the maximum surplus. Second, we prove that t..

Economic Design

Auctioning with Strategically Reticent Bidders

Classic mechanism design often assumes that a bidder's action is restricted to report a type or a signal, possibly untruthfully. In today's digital economy, bidders are holding increasing amount of private information about the auctioned items. And due to legal or ethical concerns, they would demand to reveal partial but truthful information, as opposed to report untrue signal or misinformation. To accommodate such bidder behaviors in auction design, we propose and study a novel mechanism design setup where each bidder holds two kinds of information: (1) private \emph{value type}, which can be misreported; (2) private \emph{information variable}, which the bidder may want to conceal or parti..

Economic Design

Potentials and Solutions of Cooperative Games.

This study considers strategic communication before voting. Voters have partially conflicting interests rather than common interests. That is, voters cannot tell whether a collective decision is a matter of truth, such as guilty or innocent, or a matter of taste, such as left or right. A set of imperfectly informed voters communicates before casting their votes. From a statistical perspective, truth-telling by all voters in deliberation, coupled with majority rule, may lead to desirable outcomes asymptotically as the population of voters increases. Thus, from a statistical perspective, increasing the population of voters is desirable. This study, however, shows that truthful communication is..

Economic Design

Large mechanism design with moment-based allocation externality

In many mechanism design problems in practice, often allocation externality exists (e.g., peer effects in student allocation, and post-license com- petition in oligopoly). Despite the practical importance, mechanism design with allocation externality has not been much explored in the literature, per- haps due to the tractability issue of the problem. In this paper, we propose a simple and tractable model of mechanism design with allocation externality. We characterize the optimal mechanism, which has a very simple form in the sense that it is identified by only a few parameters. This simplicity of the optimal mechanism is also useful to obtain comparative statics results.

Economic Design

Type-contingent Information Disclosure

We study a mechanism design problem where the principal can also manipulate the agent’s information about a payoff-relevant state. Jointly designing information and allocation rule is proved equivalent to certain multi-dimensional screening problem. Based on this equivalence, when the agent’s types are positively-related, full disclosure is proved optimal under regularity conditions; while with negatively-related types, the optimal disclosure policy takes the form of a bad-state alert, which is in general a type-contingent disclosure policy. In a binary environment, we fully charac- terize the optimal mechanisms and discuss when type-contingent disclosure strictly benefits the principal ..

Economic Design

Characterizing the Top Cycle via Strategyproofness

Gibbard and Satterthwaite have shown that the only single-valued social choice functions (SCFs) that satisfy non-imposition (i.e., the function's range coincides with its codomain) and strategyproofness (i.e., voters are never better off by misrepresenting their preferences) are dictatorships. In this paper, we consider set-valued social choice correspondences (SCCs) that are strategyproof according to Fishburn's preference extension and, in particular, the top cycle, an attractive SCC that returns the maximal elements of the transitive closure of the weak majority relation. Our main theorem implies that, under mild conditions, the top cycle is the only non-imposing strategyproof SCC whose o..

Economic Design

Reduced-Form Allocations for Multiple Indivisible Objects under Constraints: A Revision

We examine the implementation of reduced-form allocation rules that assign multiple indivisible objects to many agents, with incomplete information and distributional constraints across objects and agents. To obtain implementability results, we adopt a lift-and-project approach, which enables us to and a general condition called total unimodularity, a well-recognized class of matrices with simple entries of -1, 0, or 1. This condition yields several new and general characterization results including those on hierarchies, bihierarchies, and consecutiveness. Our model and results extend and unify many well-known ones considerably, find new applications, and also apply to both ordinal and cardi..

Economic Design

Nonlinear Pricing with Finite Information

We analyze nonlinear pricing with finite information. We consider a multi-product environment where each buyer has preferences over a d-dimensional variety of goods. The seller is limited to offering a finite number n of d-dimensional choices. The limited menu reflects a finite communication capacity between the buyer and seller. We identify necessary conditions that the optimal finite menu must satisfy, for either the socially efficient or the revenue-maximizing mechanism. These conditions require that information be bundled, or "quantized," optimally. We introduce vector quantization and establish that the losses due to finite menus converge to zero at a rate of 1/n^2/^d. In the canonical ..

Economic Design

Level-strategyproof Belief Aggregation Mechanisms

In the problem of aggregating experts' probabilistic predictions over an ordered set of outcomes, we introduce the axiom of level-strategy\-proofness (level-SP) and prove that it is a natural notion with several applications. Moreover, it is a robust concept as it implies incentive compatibility in a rich domain of single-peakedness over the space of cumulative distribution functions (CDFs). This contrasts with the literature which assumes single-peaked preferences over the space of probability distributions. Our main results are: (1) a reduction of our problem to the aggregation of CDFs; (2) the axiomatic characterization of level-SP probability aggregation functions with and without the ad..

Economic Design

Uncertainty in Mechanism Design

This paper studies the design of mechanisms that are robust to misspecification. We introduce a novel notion of robustness that connects a variety of disparate approaches and study its implications in a wide class of mechanism design problems. This notion is quantifiable, allowing us to formalize and answer comparative statics questions relating the nature and degree of misspecification to sharp predictions regarding features of feasible mechanisms. This notion also has a behavioral foundation which reflects the perception of ambiguity, thus allowing the degree of misspecification to emerge endogenously. In a number of standard settings, robustness to arbitrarily small amounts of misspecific..

Economic Design

Two-Person Fair Division of Indivisible Items: Compatible and Incompatible Properties

Suppose two players wish to divide a finite set of indivisible items, over which each distributes a specified number of points. Assuming the utility of a player’s bundle is the sum of the points it assigns to the items it contains, we analyze what divisions are fair. We show that if there is an envy-free (EF) allocation of the items, two other desirable properties—Pareto-optimality (PO) and maximinality (MM)—can also be satisfied, rendering these three properties compatible, but other properties—balance (BL), maximum Nash welfare (MNW), maximum total welfare (MTW), and lexicographic optimality (LO)—may fail. If there is no EF division, as is likely, it is always possible to satisfy..

Economic Design

Who Cares More? Allocation with Diverse Preference Intensities

Goods and services -- public housing, medical appointments, schools -- are often allocated to individuals who rank them similarly but differ in their preference intensities. We characterize optimal allocation rules when individual preferences are known and when they are not. Several insights emerge. First-best allocations may involve assigning some agents "lotteries" between high- and low-ranked goods. When preference intensities are private information, second-best allocations always involve such lotteries and, crucially, may coincide with first-best allocations. Furthermore, second-best allocations may entail disposal of services. We discuss a market-based alternative and show how it diffe..

Economic Design

Selling Impressions: Efficiency vs. Competition

In digital advertising, a publisher selling impressions faces a trade-off in deciding how precisely to match advertisers with viewers. A more precise match generates efficiency gains that the publisher can hope to exploit. A coarser match will generate a thicker market and thus more competition. The publisher can control the precision of the match by controlling the amount of information that advertisers have about viewers. We characterize the optimal trade-off when impressions are sold by auction. The publisher pools premium matches for advertisers (when there will be less competition on average) but gives advertisers full information about lower quality matches.

Economic Design

Dynamic assignment without money: Optimality of spot mechanisms

We study a large market model of dynamic matching with no monetary transfers and a continuum of agents. Time is discrete and horizon finite. Agents are in the market from the first date and, at each date, have to be assigned items (or bundles of items). When the social planner can only elicit ordinal preferences of agents over the sequences of items, we prove that, under a mild regularity assumption, incentive compatible and ordinally efficient allocation rules coincide with spot mechanisms. A spot mechanism specifies “virtual prices” for items at each date and, at the beginning of time, for each agent, randomly selects a budget of virtual money according to a (potentially non-uniform) d..

Economic Design

Order Symmetry: A New Fairness Criterion for Assignment Mechanisms

We introduce a new fairness criterion, order symmetry, for assignment mechanisms that match n objects to n agents with ordinal preferences over the objects. An assignment mechanism is order symmetric with respect to some probability measure over preference profiles if every agent is equally likely to receive their favorite object, every agent is equally likely to receive their second favorite, and so on. When associated with a sufficiently symmetric probability measure, order symmetry is a relaxation of anonymity that, crucially, can be satisfied by discrete assignment mechanisms. Furthermore, it can be achieved without sacrificing other desirable axiomatic properties satisfied by existing m..

Economic Design