nep-des New Economics Papers
on Economic Design
Issue of 2022‒04‒04
seven papers chosen by
Guillaume Haeringer, Baruch College and Alex Teytelboym, University of Oxford

  1. Stability and strategy-proofness for matching with interval constraints By Tsuyoshi Adachi; Yuki Ishibashi
  2. Strong core and Pareto-optimal solutions for the multiple partners matching problem under lexicographic preferences By P\'eter Bir\'o; Gergely Cs\'aji
  3. Strategyproof and Budget Balanced Mechanisms for Assembly By Soumendu Sarkar
  4. Selling to a principal and a budget-constrained agent By Debasis Mishra; Kolagani Paramahamsa
  5. How Likely A Coalition of Voters Can Influence A Large Election? By Lirong Xia
  6. Competition under incomplete contracts and the design of procurement policies By Rodrigo Carril; Andres Gonzalez-Lira; Michael S. Walker
  7. School Choice By Abdulkadiroglu, Atila; Andersson, Tommy

  1. By: Tsuyoshi Adachi (Faculty of Political Science and Economics, Waseda University); Yuki Ishibashi (Graduate School of Economics, Waseda University)
    Abstract: We consider a matching problem with interval constraints under the hierarchical region structure. We proposes new stability, interval respecting stability, for matching problems with interval constraints, which defines ceiling respecting stability (Kamada and Kojima, 2018) using a blocking coalition instead of a pair, following floor respecting stability (Akin, 2021). Interval respecting stability coincides with floor respecting stability in problems with floor constraints and implies ceiling respecting stability in problems with ceiling constraints. In addition, interval respecting stability generally implies Pareto efficiency, unlike ceiling respecting stability. We also propose a generalized flexible deferred acceptance algorithm for a problem with interval constraints, which is a flexible deferred acceptance algorithm (i.e., cumulative offer process) that allocates quotas between regions, reserving additional numbers for doctors’ future offers needed to fill the floor constraints even if there are no offers now. Under acceptability, we show that further combining the above algorithm with the serial dictatorship yields an algorithm that satisfies interval respecting stability. We also show that the combinded algorithm is strategy-proof for doctors.
    Keywords: Matching, Interval constraints, Stability, Strategy-proofness, Cumulative offer process
    JEL: C78 D47 D61 D63
    Date: 2022–03
  2. By: P\'eter Bir\'o; Gergely Cs\'aji
    Abstract: In a multiple partners matching problem the agents can have multiple partners up to their capacities. In this paper we consider both the two-sided many-to-many stable matching problem and the one-sided stable fixtures problem under lexicographic preferences. We study strong core and Pareto-optimal solutions for this setting from a computational point of view. First we provide an example to show that the strong core can be empty even under these severe restrictions for many-to-many problems, and that deciding the non-emptiness of the strong core is NP-hard. We also show that for a given matching checking Pareto-optimality and the strong core properties are co-NP-complete problems for the many-to-many problem, and deciding the existence of a complete Pareto-optimal matching is also NP-hard for the fixtures problem. On the positive side, we give efficient algorithms for finding a near feasible strong core solution, where the capacities are only violated by at most one unit for each agent, and also for finding a half-matching in the strong core of fractional matchings. These polynomial time algorithms are based on the Top Trading Cycle algorithm. Finally, we also show that finding a maximum size matching that is Pareto-optimal can be done efficiently for many-to-many problems, which is in contrast with the hardness result for the fixtures problem.
    Date: 2022–02
  3. By: Soumendu Sarkar (Department of Economics, Delhi School of Economics)
    Abstract: Assembly is an exchange problem with one buyer and multiple sellers. The buyer wants to purchase multiple items and sellers hold one item each. In applications like land acquisition, the buyer is required to purchase contiguous land plots to realize a project worth any value. This paper characterizes strategyproof,individually rational and budget balanced mechanisms for the assembly problem when the valuations of the agents are private information. It also examines several mechanisms in this class. JEL Codes: C78, D82
    Date: 2022–02
  4. By: Debasis Mishra; Kolagani Paramahamsa
    Abstract: We analyze a model of selling a single object to a principal-agent pair who want to acquire the object for a firm. The principal and the agent have different assessments of the object's value to the firm. The agent is budget-constrained while the principal is not. The agent participates in the mechanism, but she can (strategically) delegate decision-making to the principal. We derive the revenue-maximizing mechanism in a two-dimensional type space (values of the agent and the principal). We show that below a threshold budget, a mechanism involving two posted prices and three outcomes (one of which involves randomization) is the optimal mechanism for the seller. Otherwise, a single posted price mechanism is optimal.
    Date: 2022–02
  5. By: Lirong Xia
    Abstract: For centuries, it has been widely believed that the influence of a small coalition of voters is negligible in a large election. Consequently, there is a large body of literature on characterizing the asymptotic likelihood for an election to be influence, especially by the manipulation of a single voter, establishing an $O(\frac{1}{\sqrt n})$ upper bound and an $\Omega(\frac{1}{n^{67}})$ lower bound for many commonly studied voting rules under the i.i.d.~uniform distribution, known as Impartial Culture (IC) in social choice, where $n$ is the number is voters. In this paper, we extend previous studies in three aspects: (1) we consider a more general and realistic semi-random model that resembles the model in smoothed analysis, (2) we consider many coalitional influence problems, including coalitional manipulation, margin of victory, and various vote controls and bribery, and (3) we consider arbitrary and variable coalition size $B$. Our main theorem provides asymptotically tight bounds on the semi-random likelihood of the existence of a size-$B$ coalition that can successfully influence the election under a wide range of voting rules. Applications of the main theorem and its proof techniques resolve long-standing open questions about the likelihood of coalitional manipulability under IC, by showing that the likelihood is $\Theta\left(\min\left\{\frac{B}{\sqrt n}, 1\right\}\right)$ for many commonly studied voting rules. The main technical contribution is a characterization of the semi-random likelihood for a Poisson multinomial variable (PMV) to be unstable, which we believe to be a general and useful technique with independent interest.
    Date: 2022–02
  6. By: Rodrigo Carril; Andres Gonzalez-Lira; Michael S. Walker
    Abstract: We study the effects of intensifying competition for contracts in the context of U.S. Defense procurement. Conceptually, opening contracts up to bids by more participants leads to lower awarding prices, but may hinder buyers' control over non-contractible characteristics of prospective contractors. Leveraging a regulation that mandates agencies to publicize certain contract opportunities, we document that expanding the set of bidders reduces award prices, but deteriorates post-award performance, resulting in more cost overruns and delays. To further study the scope of this tension, we develop and estimate a model in which the buyer endogenously chooses the intensity of competition, invited sellers decide on auction participation and bidding, and the winner executes the contract ex-post. Model estimates indicate substantial heterogeneity in ex-post performance across contractors, and show that simple adjustments to the current regulation that account for adverse selection could provide 2 percent of savings in procurement spending, or $104 million annually
    Keywords: Procurement, competition, auctions, incomplete contracts
    JEL: D22 D44 D73 H57 L13 L14
    Date: 2022–03
  7. By: Abdulkadiroglu, Atila (Department of Economics, Duke University); Andersson, Tommy (Department of Economics, Lund University)
    Abstract: School districts in the US and around the world are increasingly moving away from traditional neighborhood school assignment, in which pupils attend closest schools to their homes. Instead, they allow families to choose from schools within district boundaries. This creates a market with parental demand over publicly-supplied school seats. More frequently than ever, this market for school seats is cleared via market design solutions grounded in recent advances in matching and mechanism design theory. The literature on school choice is reviewed with emphasis placed on the trade-offs among policy objectives and best practices in the design of admissions processes. It is concluded with a brief discussion about how data generated by assignment algorithms can be used to answer contemporary empirical questions about school effectiveness and policy interventions.
    Keywords: school choice; market design; policy evaluation; survey article
    JEL: C78 D80 H75 I21 I28
    Date: 2022–02–28

This nep-des issue is ©2022 by Guillaume Haeringer and Alex Teytelboym. It is provided as is without any express or implied warranty. It may be freely redistributed in whole or in part for any purpose. If distributed in part, please include this notice.
General information on the NEP project can be found at For comments please write to the director of NEP, Marco Novarese at <>. Put “NEP” in the subject, otherwise your mail may be rejected.
NEP’s infrastructure is sponsored by the School of Economics and Finance of Massey University in New Zealand.