nep-des New Economics Papers
on Economic Design
Issue of 2020‒10‒05
eight papers chosen by
Alex Teytelboym
University of Oxford

  1. Pareto efficient combinatorial auctions: dichotomous preferences without quasilinearity By Komal Malik; Debasis Mishra
  2. Reforms meet fairness concerns in school and college admissions By Somouaoga Bonkoungou; Alexander Nesterov
  3. The Affiliate Matching Problem: On Labor Markets where Firms are Also Interested in the Placement of Previous Workers By Samuel Dooley; John P. Dickerson
  4. Tiered Random Matching Markets: Rank is Proportional to Popularity By Itai Ashlagi; Mark Braverman; Clayton Thomas; Geng Zhao
  5. Strategy-proof allocation with outside option By Jun Zhang
  6. Mechanisms for a No-Regret Agent: Beyond the Common Prior By Modibo Camara; Jason Hartline; Aleck Johnsen
  7. The Platform Design Problem By Christos Papadimitriou; Kiran Vodrahalli; Mihalis Yannakakis
  8. Trust and Trustworthiness in Procurement Contracts with Retainage By Matthew J. Walker; Elena Katok; Jason Shachat

  1. By: Komal Malik; Debasis Mishra
    Abstract: We consider a combinatorial auction model where preferences of agents over bundles of objects and payments need not be quasilinear. However, we restrict the preferences of agents to be dichotomous. An agent with dichotomous preference partitions the set of bundles of objects as acceptable} and unacceptable, and at the same payment level, she is indifferent between bundles in each class but strictly prefers acceptable to unacceptable bundles. We show that there is no Pareto efficient, dominant strategy incentive compatible (DSIC), individually rational (IR) mechanism satisfying no subsidy if the domain of preferences includes all dichotomous preferences. However, a generalization of the VCG mechanism is Pareto efficient, DSIC, IR and satisfies no subsidy if the domain of preferences contains only positive income effect dichotomous preferences. We show the tightness of this result: adding any non-dichotomous preference (satisfying some natural properties) to the domain of quasilinear dichotomous preferences brings back the impossibility result.
    Date: 2020–09
  2. By: Somouaoga Bonkoungou; Alexander Nesterov
    Abstract: Recently, many matching systems around the world have been reformed. These reforms responded to objections that the matching mechanisms in use were unfair and manipulable. Surprisingly, the mechanisms remained unfair even after the reforms: the new mechanisms may induce an outcome with a blocking student who desires and deserves a school which she did not receive. However, as we show in this paper, the reforms introduced matching mechanisms which are more fair compared to the counterfactuals. First, most of the reforms introduced mechanisms that are more fair by stability: whenever the old mechanism does not have a blocking student, the new mechanism does not have a blocking student either. Second, some reforms introduced mechanisms that are more fair by counting: the old mechanism always has at least as many blocking students as the new mechanism. These findings give a novel rationale to the reforms and complement the recent literature showing that the same reforms have introduced less manipulable matching mechanisms. We further show that the fairness and manipulability of the mechanisms are strongly logically related.
    Date: 2020–09
  3. By: Samuel Dooley; John P. Dickerson
    Abstract: In many labor markets, workers and firms are connected via affiliative relationships. A management consulting firm wishes to both accept the best new workers but also place its current affiliated workers at strong firms. Similarly, a research university wishes to hire strong job market candidates while also placing its own candidates at strong peer universities. We model this affiliate matching problem in a generalization of the classic stable marriage setting by permitting firms to state preferences over not just which workers to whom they are matched, but also to which firms their affiliated workers are matched. Based on results from a human survey, we find that participants (acting as firms) give preference to their own affiliate workers in surprising ways that violate some assumptions of the classical stable marriage problem. This motivates a nuanced discussion of how stability could be defined in affiliate matching problems; we give an example of a marketplace which admits a stable match under one natural definition of stability, and does not for that same marketplace under a different, but still natural, definition. We conclude by setting a research agenda toward the creation of a centralized clearing mechanism in this general setting.
    Date: 2020–09
  4. By: Itai Ashlagi; Mark Braverman; Clayton Thomas; Geng Zhao
    Abstract: We study the stable marriage problem in two-sided markets with randomly generated preferences. We consider agents on each side divided into a constant number of "soft tiers", which intuitively indicate the quality of the agent. Specifically, every agent within a tier has the same public score, and agents on each side have preferences independently generated proportionally to the public scores of the other side. We compute the expected average rank which agents in each tier have for their partners in the men-optimal stable matching, and prove concentration results for the average rank in asymptotically large markets. Furthermore, we show that despite having a significant effect on ranks, public scores do not strongly influence the probability of an agent matching to a given tier of the other side. This generalizes results of [Pittel 1989] which correspond to uniform preferences. The results quantitatively demonstrate the effect of competition due to the heterogeneous attractiveness of agents in the market, and we give the first explicit calculations of rank beyond uniform markets.
    Date: 2020–09
  5. By: Jun Zhang
    Abstract: We consider strategy-proof mechanisms to solve allocation problems where agents can choose outside options if they wish. Mechanisms could return an allocation or a randomization over allocations. We prove two useful theorems, relying on an invariance property of the allocations found by strategy-proof mechanisms when agents vary the ranking of outside options in their preferences. The first theorem proves that, among individually rational and strategy-proof mechanisms, pinning down every agent's probability of choosing outside option in every preference profile is equivalent to pinning down a mechanism. The second theorem provides a sufficient condition for proving equivalence between two strategy-proof mechanisms when the number of possible allocations is finite. The two theorems provide a unified foundation for existing results in several distinct models and imply new results in some models.
    Date: 2020–09
  6. By: Modibo Camara; Jason Hartline; Aleck Johnsen
    Abstract: A rich class of mechanism design problems can be understood as incomplete-information games between a principal who commits to a policy and an agent who responds, with payoffs determined by an unknown state of the world. Traditionally, these models require strong and often-impractical assumptions about beliefs (a common prior over the state). In this paper, we dispense with the common prior. Instead, we consider a repeated interaction where both the principal and the agent may learn over time from the state history. We reformulate mechanism design as a reinforcement learning problem and develop mechanisms that attain natural benchmarks without any assumptions on the state-generating process. Our results make use of novel behavioral assumptions for the agent -- centered around counterfactual internal regret -- that capture the spirit of rationality without relying on beliefs.
    Date: 2020–09
  7. By: Christos Papadimitriou; Kiran Vodrahalli; Mihalis Yannakakis
    Abstract: On-line firms deploy suites of software platforms, where each platform is designed to interact with users during a certain activity, such as browsing, chatting, socializing, emailing, driving, etc. The economic and incentive structure of this exchange, as well as its algorithmic nature, have not been explored to our knowledge; we initiate their study in this paper. We model this interaction as a Stackelberg game between a Designer and one or more Agents. We model an Agent as a Markov chain whose states are activities; we assume that the Agent's utility is a linear function of the steady-state distribution of this chain. The Designer may design a platform for each of these activities/states; if a platform is adopted by the Agent, the transition probabilities of the Markov chain are affected, and so is the objective of the Agent. The Designer's utility is a linear function of the steady state probabilities of the accessible states (that is, the ones for which the platform has been adopted), minus the development cost of the platforms. The underlying optimization problem of the Agent -- that is, how to choose the states for which to adopt the platform -- is an MDP. If this MDP has a simple yet plausible structure (the transition probabilities from one state to another only depend on the target state and the recurrent probability of the current state) the Agent's problem can be solved by a greedy algorithm. The Designer's optimization problem (designing a custom suite for the Agent so as to optimize, through the Agent's optimum reaction, the Designer's revenue), while NP-hard, has an FPTAS. These results generalize, under mild additional assumptions, from a single Agent to a distribution of Agents with finite support. The Designer's optimization problem has abysmal "price of robustness", suggesting that learning the parameters of the problem is crucial for the Designer.
    Date: 2020–09
  8. By: Matthew J. Walker (Durham University Business School); Elena Katok (Naveen Jindal School of Management, University of Texas at Dallas); Jason Shachat (Durham University Business School)
    Abstract: When product quality is unverifiable by third parties, enforceable contracts that condition price upon quality are not feasible. If higher quality is also costly to deliver, moral hazard by sellers flourishes, particularly when procurement is via a competitive auction process. Retainage is a contractual mechanism that presents a solution to the third-party unverifiability problem, by setting aside a portion of the purchase price. After delivery, the buyer has sole discretion over the amount of retainage money that is released to the seller. While generally a feasible contract form to implement, retainage introduces a moral hazard for the buyer. We use laboratory experiments to investigate how and when retainage might be successfully used to facilitate trust and trustworthiness in procurement contracts. We observe that retainage induces a significant improvement in product quality when there are some trustworthy buyers in the population, consistent with a model of fair payment norms that we develop. This improvement is realized at the cost of increased buyer-seller profit inequalities. We also observe that at high levels of retainage, there is a welfaredecreasing market unraveling in which sellers do not bid on contracts. Our results imply that retainage incentives can mitigate the tension between competition and cooperation arising from reverse auctions, but only at appropriate levels of retainage
    Keywords: trust, procurement, reverse auction, retainage, moral hazard
    JEL: C92 L15 D86
    Date: 2020

This nep-des issue is ©2020 by 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.