Membership design involves allocating an economic good whose value to any individual depends on who else receives it. We introduce a framework for optimal membership design by combining an otherwise standard mechanism-design model with allocative externalities that depend flexibly on agents' observable and unobservable characteristics. Our main technical result demonstrates that the optimal mechanism offers distinct membership tiers—differing in prices and level of access—and that the number of membership tiers is increasing in the complexity of the externalities. This insight may help explain a number of mechanisms used in practice to sell membership goods, including musical artists charging below-market-clearing prices for concert tickets, certain admission procedures used by colleges concerned about the diversity of the student body, heterogeneous pricing tiers for access to digital communities, and the use of vesting and free allocation in the distribution of network tokens.

In an auction, a seller may masquerade as one or more bidders in order to manipulate the clearing price. We characterize single-item auction formats that are shill-proof in the sense that a profit-maximizing seller has no incentive to submit shill bids. We distinguish between strong shill-proofness, in which a seller with full knowledge of bidders' valuations can never profit from shilling, and weak shill-proofness, which requires only that the expected equilibrium profit from shilling is nonpositive. The Dutch auction (with a suitable reserve) is the unique (revenue-)optimal and strongly shill-proof auction. Moreover, the Dutch auction (with no reserve) is the unique prior-independent auction that is both efficient and weakly shill-proof. While there are multiple ex-post incentive compatible, weakly shill-proof, and optimal auctions; any optimal auction can satisfy only two properties in the set {static, ex-post incentive compatible, weakly shill-proof}.

Conspicuous consumption occurs when a consumer derives value from a good based on its social meaning as a signal of wealth, taste, and/or community affiliation. Common conspicuous goods include designer footwear, country club memberships, and artwork; conspicuous goods also exist in the digital sphere, with non-fungible tokens (NFTs) as a prominent example. The NFT market merits deeper study for two key reasons: first, it is poorly understood relative to its economic scale; and second, it is unusually amenable to analysis because NFT transactions are publicly available on the blockchain, making them useful as a test bed for conspicuous consumption dynamics. This paper introduces a model that incorporates two previously identified elements of conspicuous consumption: the bandwagon effect (goods increase in value as they become more popular) and the snob effect (goods increase in value as they become rarer). Our model resolves the apparent tension between these two effects, exhibiting net complementarity between others' and one's own conspicuous consumption. We also introduce a novel dataset combining NFT transactions with embeddings of the corresponding NFT images computed using an off-the-shelf vision transformer architecture. We use our dataset to validate the model, showing that the bandwagon effect raises an NFT collection's value as more consumers join, while the snob effect drives consumers to seek rarer NFTs within a given collection.

In the modular robot reconfiguration problem, we are given $n$ cube-shaped modules (or robots) as well as two configurations, i.e., placements of the $n$ modules so that their union is face-connected. The goal is to find a sequence of moves that reconfigures the modules from one configuration to the other using "sliding moves," in which a module slides over the face or edge of a neighboring module, maintaining connectivity of the configuration at all times. For many years it has been known that certain module configurations in this model require at least $Ω(n^2)$ moves to reconfigure between them. In this paper, we introduce the first universal reconfiguration algorithm -- i.e., we show that any $n$-module configuration can reconfigure itself into any specified $n$-module configuration using just sliding moves. Our algorithm achieves reconfiguration in $O(n^2)$ moves, making it asymptotically tight. We also present a variation that reconfigures in-place, it ensures that throughout the reconfiguration process, all modules, except for one, will be contained in the union of the bounding boxes of the start and end configuration.

Innovation is a major driver of economic and social development, and information about many kinds of innovation is embedded in semi-structured data from patents and patent applications. Though the impact and novelty of innovations expressed in patent data are difficult to measure through traditional means, machine learning offers a promising set of techniques for evaluating novelty, summarizing contributions, and embedding semantics. In this paper, we introduce the Harvard USPTO Patent Dataset (HUPD), a large-scale, well-structured, and multi-purpose corpus of English-language patent applications filed to the United States Patent and Trademark Office (USPTO) between 2004 and 2018. With more than 4.5 million patent documents, HUPD is two to three times larger than comparable corpora. Unlike other NLP patent datasets, HUPD contains the inventor-submitted versions of patent applications, not the final versions of granted patents, allowing us to study patentability at the time of filing using NLP methods for the first time. It is also novel in its inclusion of rich structured data alongside the text of patent filings: By providing each application’s metadata along with all of its text fields, HUPD enables researchers to perform new sets of NLP tasks that leverage variation in structured covariates. As a case study on the types of research HUPD makes possible, we introduce a new task to the NLP community -- patent acceptance prediction. We additionally show the structured metadata provided in HUPD allows us to conduct explicit studies of concept shifts for this task. We find that performance on patent acceptance prediction decays when models trained in one context are evaluated on different innovation categories and over time. Finally, we demonstrate how HUPD can be used for three additional tasks: Multi-class classification of patent subject areas, language modeling, and abstractive summarization. Put together, our publicly-available dataset aims to advance research extending language and classification models to diverse and dynamic real-world data distributions.

We propose an economic framework for determining the optimal allocation of a scarce supply of vaccines that become gradually available during a public health crisis, such as the Covid-19 pandemic. Agents differ in observable and unobservable characteristics, and the designer maximizes a social welfare function over all feasible mechanisms---accounting for agents' characteristics, as well as their endogenous behavior in the face of the pandemic. The framework emphasizes the role of externalities and incorporates equity as well as efficiency concerns. Our results provide an economic justification for providing vaccines immediately and for free to some groups of agents, while at the same time showing that a carefully constructed pricing mechanism can improve outcomes by screening for individuals with the highest private and social benefits of receiving the vaccine. The solution casts light on the classic question of whether prices or priorities should be used to allocate scarce public resources under externalities and equity concerns.

In many real-world resource allocation problems, optimization is computationally intractable, so any practical allocation mechanism must be based on an approximation algorithm. We study investment incentives in strategy-proof mechanisms that use such approximations. In sharp contrast with the Vickrey-Clark-Groves mechanism, for which individual returns on investments are aligned with social welfare, we find that some algorithms that approximate efficient allocation arbitrarily well can nevertheless create misaligned investment incentives that lead to arbitrarily bad overall outcomes. However, if a near-efficient algorithm "excludes bossy negative externalities," then its outcomes remain near-efficient even after accounting for investments. A weakening of this "XBONE" condition is necessary and sufficient for the result.

Many economic-theoretic models incorporate finiteness assumptions that, while introduced for simplicity, play a real role in the analysis. Such assumptions introduce a conceptual problem, as results that rely on finiteness are often implicitly nonrobust; for example, they may depend upon edge effects or artificial boundary conditions. Here, we present a unified method that enables us to remove finiteness assumptions, such as those on datasets, market sizes, and time horizons. We then apply our approach to a variety of revealed preference, matching, and exchange economy settings.

We study revenue-optimal pricing and driver compensation in ridesharing platforms when drivers have heterogeneous preferences over locations. If a platform ignores drivers' location preferences, it may make inefficient trip dispatches; moreover, drivers may strategize so as to route towards their preferred locations. In a model with stationary and continuous demand and supply, we present a mechanism that incentivizes drivers to both (i) report their location preferences truthfully and (ii) always provide service. In settings with unconstrained driver supply or symmetric demand patterns, our mechanism achieves (full-information) first-best revenue. Under supply constraints and unbalanced demand, we show via simulation that our mechanism improves over existing mechanisms and has performance close to the first-best.

Even when global income redistribution is not feasible, market designers can seek to mitigate inequality within individual markets. If sellers are systematically poorer than buyers, for example, they will be willing to sell at relatively low prices. Yet a designer who cares about inequality might prefer to set higher prices precisely when sellers are poor -- effectively, using the market as a redistributive tool. In this paper, we seek to understand how to design goods markets optimally in the presence of persistent inequality. Using a mechanism design approach, we find that redistribution through markets can indeed be optimal. When there is substantial inequality across sides of the market, the designer uses a tax-like mechanism, introducing a wedge between the buyer and seller prices, and redistributing the resulting surplus to the poorer side of the market via lump-sum payments. When there is significant within-side inequality, meanwhile, the designer imposes price controls even though doing so induces rationing.

We consider general trading networks with bilateral contracts. We show that a suitably adapted chain stability concept is equivalent to stability if all agents' preferences are jointly fully substitutable and satisfy the Laws of Aggregate Supply and Demand (a condition we call monotone - substitutability). We also present three examples to show that are results are sharp, demonstrating that: If preferences of some agents do not satisfy the Laws of Aggregate Supply and Demand, then chain stable outcomes may not be stable. " If preferences of some agents are not fully substitutable, then chain stable outcomes may likewise not be stable. " If blocking sets are restricted to chains that do not "cross" themselves (i.e., chains that involve each agent in at most two contracts), then an outcome that is robust to such blocks may not be robust to richer blocks. Our results imply that in trading networks with transferable utility, an outcome is consistent with competitive equilibrium if and only if it is not blocked by any chain of contracts. We show moreover that, from a computational perspective, checking whether an outcome is chain stable is substantially easier than checking whether that outcome is stable directly. Indeed, we show that as the size of the economy grows, the number of chains of trades (corresponding to possible blocking chains) becomes infinitely smaller than the number of general sets of trades (corresponding to possible blocking sets).

In many-to-one matching with contracts, agents on one side of the market, e.g., workers, can fulfill at most one contract, while agents on the other side of the market, e.g., firms, may desire multiple contracts. Hatfield and Molgrom [6] showed that when firms' preferences are substitutable and size monotonic, the worker-proposing cumulative offer mechanism is stable and strategy-proof (for workers).

Substitutable preferences, i.e., preferences without complementarities, are necessary to guarantee the existence of stable outcomes in many market design settings. In this paper, we highlight a form of "hidden substitutability" that arises in many-to-one matching markets with contracts: some preferences over contracts that exhibit complementarity in fact have an underlying substitutable structure. Specifically, we show that some preferences that are not substitutable in the setting of many-to-one matching with contracts become substitutable when an employer is allowed to sign multiple contracts with an individual worker. These substitutably completable preferences guarantee the existence of stable contracting outcomes, even though stable outcomes are not guaranteed, in general, when complementarities are present. Our results imply the existence of a stable, strategy-proof mechanism for allocating workers with specialized skillsets; moreover, our results give new insight into the existing applications of matching with contracts to cadet--branch matching and the design of affirmative action programs.

Various forms of substitutability are essential for establishing the existence of equilibria and other useful properties in diverse settings such as matching, auctions, and exchange economies with indivisible goods. In this paper, we extend earlier models' canonical definitions of substitutability to a setting in which an agent can be a buyer in some transactions and a seller in others, and show that all the different substitutability concepts are equivalent. Next, we introduce a new class of fully substitutable preferences that models the preferences of intermediaries with production capacity. We then prove that substitutability is preserved under economically important transformations such as trade endowments, mergers, and limited liability. We show that full substitutability can be recast in terms of submodularity of the indirect utility function, the single improvement property, a "no complementarities" condition, and a condition from discrete convex analysis called M♮-concavity. Finally, we show that substitutability implies two key monotonicity conditions known as the Laws of Aggregate Supply and Demand. All of our results explicitly incorporate economically important features such as indifferences, non-monotonicities, and unbounded utility functions that were not fully addressed in prior work.

OBJECTIVE: To design and implement a tool that creates a secure, privacy preserving linkage of electronic health record (EHR) data across multiple sites in a large metropolitan area in the United States (Chicago, IL), for use in clinical research. METHODS: The authors developed and distributed a software application that performs standardized data cleaning, preprocessing, and hashing of patient identifiers to remove all protected health information. The application creates seeded hash code combinations of patient identifiers using a Health Insurance Portability and Accountability Act compliant SHA-512 algorithm that minimizes re-identification risk. The authors subsequently linked individual records using a central honest broker with an algorithm that assigns weights to hash combinations in order to generate high specificity matches. RESULTS: The software application successfully linked and de-duplicated 7 million records across 6 institutions, resulting in a cohort of 5 million unique records. Using a manually reconciled set of 11 292 patients as a gold standard, the software achieved a sensitivity of 96% and a specificity of 100%, with a majority of the missed matches accounted for by patients with both a missing social security number and last name change. Using 3 disease examples, it is demonstrated that the software can reduce duplication of patient records across sites by as much as 28%. CONCLUSIONS: Software that standardizes the assignment of a unique seeded hash identifier merged through an agreed upon third-party honest broker can enable large-scale secure linkage of EHR data for epidemiologic and public health research. The software algorithm can improve future epidemiologic research by providing more comprehensive data given that patients may make use of multiple healthcare systems.

The market design literature has successfully designed mechanisms that achieve desirable properties such as strategy-proofness (incentive compatibility) and efficiency at the allocation stage. However, agents must often make investment decisions before participating in allocation mechanisms. These decisions are endogenous, in the sense that market participants' investments depend on the choice of mechanism.

Diversity and financial aid concerns often lead schools to "reserve" some slots for specific types of students or tuition contracts. Students only care about their school assignments and contractual terms---they are indifferent among slots within a school. These indifferences can be resolved in multiple ways. As we illustrate using the cases of Chicago and Boston public schools, the method of indifference resolution impacts the eventual allocation, and thus presents a novel opportunity for market design.

No abstract available.

When no agent has substantial influence on a public good outcome, he or she can demand the full surplus. Thus, in rich environments, private (voluntary and self-financing) provision of public goods---or bads such as land assembly---to a large number of self-interested citizens is impossible. This holdout problem is well-known and ubiquitous throughout economics: Holdout was first formalized by Cournot [2], and takes its precise modern form in the work of Mailath and Postelwaite [4]. Unlike in classical auction settings, where increasing competition may offset imperfections in market design ([1,3]), there is no easy way around the necessity of social engineering to solve holdout. Consequently, holdout concerns have informed wide-ranging policy decisions, including eminent domain and corporate takeover laws. In this paper, we study holdout in settings where a good owned by a disparate community of sellers is desired by a buyer only in its entirety; for concreteness, we focus on the particularly salient application of land assembly. In these settings, no mechanism can simultaneously achieve full efficiency and complete individual rationality ([4]). However, as we show, it is possible to strike an attractive balance between these two goals.

We introduce a new matching model in which firms trade goods via bilateral contracts which specify a buyer, a seller, and the terms of the exchange. This framework subsumes all classical matching models, including that of Ostrovsky [5]. The generality our model affords allows us to make two substantial contributions.

We introduce the problem of shape replication in the Wang tile self-assembly model. Given an input shape, we consider the problem of designing a self-assembly system which will replicate that shape into either a specific number of copies, or an unbounded number of copies. Motivated by practical DNA implementations of Wang tiles, we consider a model in which tiles consisting of DNA or RNA can be dynamically added in a sequence of stages. We further permit the addition of RNase enzymes capable of disintegrating RNA tiles. Under this model, we show that arbitrary genus-0 shapes can be replicated infinitely many times using only O(1) distinct tile types and O(1) stages. Further, we show how to replicate precisely n copies of a shape using O(log n) stages and O(1) tile types.

We give a new, purely coding-theoretic proof of Koch's criterion on the tetrad systems of Type II codes of length 24 using the theory of harmonic weight enumerators. This approach is inspired by Venkov's approach to the classification of the root systems of Type II lattices in $\mathbb{R}^{24}$ and gives a new instance of the analogy between lattices and codes.

We prove that any finite collection of polygons of equal area has a common hinged dissection, that is, a chain of polygons hinged at vertices that can be folded in the plane continuously without self-intersection to form any polygon in the collection. This result settles the open problem about the existence of hinged dissections between pairs of polygons that goes back implicitly to 1864 and has been studied extensively in the past ten years. Our result generalizes and indeed builds upon the result from 1814 that polygons have common dissections (without hinges). We also extend our result to edge-hinged dissections of solid 3D polyhedra that have a common (unhinged) dissection, as determined by Dehn's 1900 solution to Hilbert's Third Problem. Our proofs are constructive, giving explicit algorithms in all cases. For a constant number of planar polygons, both the number of pieces and running time required by our construction are pseudopolynomial. This bound is the best possible even for unhinged dissections. Hinged dissections have possible applications to reconfigurable robotics, programmable matter, and nanomanufacturing.