|
on Economic Design |
|
Issue of 2023‒01‒16
ten papers chosen by Guillaume Haeringer, Baruch College and Alex Teytelboym, University of Oxford |
| By: | Federico Echenique; Mat\'ias N\'u\~nez |
| Abstract: | We describe a two-stage mechanism that fully implements the set of efficient outcomes in two-agent environments with quasi-linear utilities. The mechanism asks one agent to set prices for each outcome, and the other agent to make a choice, paying the corresponding price: Price \& Choose. We extend our implementation result in three main directions: an arbitrary number of players, non-quasi linear utilities, and robustness to max-min behavior. Finally, we discuss how to reduce the payoff inequality between players while still achieving efficiency. |
| Date: | 2022–12 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2212.05650&r=des |
| By: | Ata Atay (University of Barcelona and BEAT); Ana Mauleon (CEREC and CORE/LIDAM, UCLouvain); Vincent Vannetelbosch (CORE/LIDAM, UCLouvain) |
| Abstract: | We consider priority-based school choice problems with farsighted students. We show that a singleton set consisting of the matching obtained from the Top Trading Cycles (TTC) mechanism is a farsighted stable set. However, the matching obtained from the Deferred Acceptance (DA) mechanism may not belong to any farsighted stable set. Hence, the TTC mechanism provides an assignment that is not only Pareto efficient but also farsightedly stable. Moreover, looking forward three steps ahead is already sufficient for stabilizing the matching obtained from the TTC. |
| Keywords: | School choice, top trading cycle, stable sets, farsighted students. |
| JEL: | C70 C78 D47 |
| Date: | 2022 |
| URL: | http://d.repec.org/n?u=RePEc:ewp:wpaper:437web&r=des |
| By: | Ata Atay (University of Barcelona and BEAT); Ana Mauleon (CEREC and CORE/LIDAM, UCLouvain); Vincent Vannetelbosch (CORE/LIDAM, UCLouvain) |
| Abstract: | We consider priority-based matching problems with limited farsightedness. We show that, once agents are sufficiently farsighted, the matching obtained from the Top Trading Cycles (TTC) algorithm becomes stable: a singleton set consisting of the TTC matching is a horizon-$k$ vNM stable set if the degree of farsightedness is greater than three times the number of agents in the largest cycle of the TTC. On the contrary, the matching obtained from the Deferred Acceptance (DA) algorithm may not belong to any horizon-$k$ vNM stable set for $k$ large enough. |
| Keywords: | Priority-based matching, top trading cycle, stable sets, limited farsightedness. |
| JEL: | C70 C78 D47 D61 |
| Date: | 2022 |
| URL: | http://d.repec.org/n?u=RePEc:ewp:wpaper:438web&r=des |
| By: | Yannai A. Gonczarowski; Clayton Thomas |
| Abstract: | We study various novel complexity measures for two-sided matching mechanisms, applied to the popular real-world school choice mechanisms of Deferred Acceptance (DA) and Top Trading Cycles (TTC). In contrast to typical bounds in computer science, our metrics are not aimed to capture how hard the mechanisms are to compute. Rather, they aim to capture certain aspects of the difficulty of understanding or explaining the mechanisms and their properties. First, we study a set of questions regarding the complexity of how one agent's report can affect other facets of the mechanism. We show that in both DA and TTC, one agent's report can have a structurally complex effect on the final matching. Considering how one agent's report can affect another agent's set of obtainable options, we show that this effect has high complexity for TTC, but low complexity for DA, showing that one agent can only affect another in DA in a quantitatively controlled way. Second, we study a set of questions about the complexity of communicating various facets of the outcome matching, after calculating it. We find that when there are many more students than schools, it is provably harder to concurrently describe to each student her match in TTC than in DA. In contrast, we show that the outcomes of TTC and DA are equally hard to jointly verify, and that all agents' sets of obtainable options are equally hard to describe, showcasing ways in which the two mechanisms are comparably complex. Our results uncover new lenses into how TTC may be more complex than DA. This stands in contrast with recent results under different models, emphasizing the richness of the landscape of complexities of matching mechanisms. Our proofs uncover novel structural properties of TTC and DA, which may be of independent interest. |
| Date: | 2022–12 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2212.08709&r=des |
| By: | Naveen Durvasula |
| Abstract: | Results from the communication complexity literature have demonstrated that stable matching requires communication: one cannot find or verify a stable match without having access to essentially all of the ordinal preference information held privately by the agents in the market. Stated differently, these results show that stable matching mechanisms are not robust to even a small number of labeled inaccuracies in the input preferences. In practice, these results indicate that agents must go through the time-intensive process of accurately ranking each and every potential match candidate if they wish for the resulting match to be guaranteedly stable. Thus, in large markets, communication requirements for stable matching may be impractically high. A natural question to ask, given this result, is whether some higher-order structure in the market can indicate which large markets have steeper communication requirements. In this paper, we perform such an analysis in a regime where agents have a utility-based notion of preference. We consider a dynamic model where agents only have access to an approximation of their utility that satisfies a universal multiplicative error bound. We apply guarantees from the theoretical computer science literature on low-distortion embeddings of finite metric spaces to understand the communication requirements of stable matching in large markets in terms of their structural properties. Our results show that for a broad family of markets, the error bound may not grow faster than $n^2\log(n)$ while maintaining a deterministic guarantee on the behavior of stable matching mechanisms in the limit. We also show that a stronger probabilistic guarantee may be made so long as the bound grows at most logarithmically in the underlying topological complexity of the market. |
| Date: | 2022–12 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2212.04024&r=des |
| By: | Frank Yang |
| Abstract: | We study optimal bundling when consumers differ in one dimension. We introduce a partial order on the set of bundles defined by (i) set inclusion and (ii) sales volumes (if sold alone and priced optimally). We show that if the undominated bundles with respect to this partial order are nested, then nested bundling (tiered pricing) is optimal. We characterize which nested menu is optimal: Selling a given menu of nested bundles is optimal if a smaller bundle in (out of) the menu sells more (less) than a bigger bundle in the menu. We apply these insights to connect optimal bundling and quality design to price elasticities and cost structures: (i) when price elasticities are quasi-convex on the set of bundles, nested bundling is always optimal and the optimal mechanism simply creates nests in the order of price elasticities; (ii) when consumers' preferences are multiplicative, the optimal quality design can be characterized by the lower monotone envelope of the average cost curve. |
| Date: | 2022–12 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2212.12623&r=des |
| By: | Dirk Bergemann (Cowles Foundation, Yale University); Alessandro Bonatti |
| Abstract: | We propose a model of intermediated digital markets where data and heterogeneity in tastes and products are defining features. A monopolist platform uses superior data to match consumers and multiproduct advertisers. Consumers have heterogenous preferences for the advertisers' product lines and shop on- or off-platform. The platform monetizes its data by selling targeted advertising space that allows advertisers to tailor their products to each consumer's preferences. We derive the equilibrium product lines and advertising prices. We identify search costs and informational advantages as two sources of the platform's bargaining power. We show that privacy-enhancing data-governance rules, such as those corresponding to federated learning, can lead to welfare gains for the consumers. |
| Keywords: | Data, Privacy, Data Governance, Digital Advertising, Competition, Digital Platforms, Digital Intermediaries, Personal Data, Matching, Price Discrimination |
| JEL: | D18 D44 D82 D83 |
| Date: | 2022–08 |
| URL: | http://d.repec.org/n?u=RePEc:cwl:cwldpp:2343&r=des |
| By: | Dominik Peters (LAMSADE - Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision - Université Paris Dauphine-PSL - PSL - Université Paris sciences et lettres - CNRS - Centre National de la Recherche Scientifique); Ariel D. Procaccia (SEAS - Harvard John A. Paulson School of Engineering and Applied Sciences - Harvard University [Cambridge]); David Zhu (SEAS - Harvard John A. Paulson School of Engineering and Applied Sciences - Harvard University [Cambridge]) |
| Abstract: | In fair rent division, the problem is to assign rooms to roommates and fairly split the rent based on roommates' reported valuations for the rooms. Envy-free rent division is the most popular application on the fair division website Spliddit. The standard model assumes that agents can correctly report their valuations for each room. In practice, agents may be unsure about their valuations, for example because they have had only limited time to inspect the rooms. Our goal is to find a robust rent division that remains fair even if agent valuations are slightly different from the reported ones. We introduce the lexislack solution, which selects a rent division that remains envy-free for valuations within as large a radius as possible of the reported valuations. We also consider robustness notions for valuations that come from a probability distribution, and use results from learning theory to show how we can find rent divisions that (almost) maximize the probability of being envy-free, or that minimize the expected envy. We show that an almost optimal allocation can be identified based on polynomially many samples from the valuation distribution. Finding the best allocation given these samples is NP-hard, but in practice such an allocation can be found using integer linear programming. |
| Date: | 2022–11–28 |
| URL: | http://d.repec.org/n?u=RePEc:hal:journl:hal-03883471&r=des |
| By: | Nikita Miku |
| Abstract: | It is well known that Sperner lemma is equivalent to Brouwer fixed-point theorem. Tanaka [12] proved that Brouwer theorem is equivalent to Arrow theorem, hence Arrow theorem is equivalent to Sperner lemma. In this paper we will prove this result directly. Moreover, we describe a number of other statements equivalent to Arrow theorem. |
| Date: | 2022–12 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2212.12251&r=des |
| By: | Bhowmik, Anuj |
| Abstract: | This paper analyses the properties of (strong) core allocations in a two-period asymmetric information economy that also involves both negligible and non-negligible agents as well as an infinite dimensional commodity space. Within this setup, we allow the consumption set of each agent to be an arbitrary subset of the commodity space that may not have any lower bound. Our first result deals with the robustness of the core and the strong core allocations with respect to the restrictions imposed on the size of the blocking coalitions in an economy with only non-negligible agents. The second result is a generalization of the first result to an economy that allows the simultaneous presence of negligible as well as non-negligible agents with the consideration of Aubin coalitions. Finally, we show that (strong) core allocations are coalitional fair in the sense that no coalition of negligible agents could redistribute among its members the net trade of any other coalition containing all non-negligible agents in a way that could assign a preferred bundle to each of its members, and vice versa. |
| Keywords: | Mixed Economy; Core; Vind's theorem; Coalitionally fair allocations. |
| JEL: | D50 D51 D8 D82 |
| Date: | 2022–12–01 |
| URL: | http://d.repec.org/n?u=RePEc:pra:mprapa:115795&r=des |