nep-des New Economics Papers
on Economic Design
Issue of 2022‒07‒18
six papers chosen by
Alex Teytelboym
University of Oxford

  1. Entry in first-price auctions with signaling By Bos, Olivier; Truyts, Tom
  2. Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for all Distributions By Meryem Essaidi; Matheus V. X. Ferreira; S. Matthew Weinberg
  3. Optimal Reserve Prices By Onur A. Koska; Frank Stähler
  4. Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets By Chinmay Maheshwari; Eric Mazumdar; Shankar Sastry
  5. Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism By Haris Aziz; Alexander Lam; Mashbat Suzuki; Toby Walsh
  6. Optimized Distortion and Proportional Fairness in Voting By Soroush Ebadian; Anson Kahng; Nisarg Shah; Dominik Peters

  1. By: Bos, Olivier; Truyts, Tom
    Abstract: We study the optimal entry fee in a symmetric private value first-price auction with signaling, in which the participation decisions and the auction outcome are used by an outside observer to infer the bidders' types. We show that this auction has a unique fully separating equilibrium bidding function. When the bidders' sensibility for the signaling concern is sufficiently strong, the expected revenue maximizing entry fee is the maximal fee that guarantees full participation. The larger is the bidder's sensibility, the higher is the optimal participation.
    Keywords: first-price auction,entry,monotonic signaling,social status
    JEL: D44 D82
    Date: 2022
  2. By: Meryem Essaidi; Matheus V. X. Ferreira; S. Matthew Weinberg
    Abstract: We consider a revenue-maximizing seller with a single item for sale to multiple buyers with i.i.d. valuations. Akbarpour and Li (2020) show that the only optimal, credible, strategyproof auction is the ascending price auction with reserves which has unbounded communication complexity. Recent work of Ferreira and Weinberg (2020) circumvents their impossibility result assuming the existence of cryptographically secure commitment schemes, and designs a two-round credible, strategyproof, optimal auction. However, their auction is only credible when buyers' valuations are MHR or $\alpha$-strongly regular: they show their auction might not be credible even when there is a single buyer drawn from a non-MHR distribution. In this work, under the same cryptographic assumptions, we identify a new single-item auction that is credible, strategyproof, revenue optimal, and terminates in constant rounds in expectation for all distributions with finite monopoly price.
    Date: 2022–05
  3. By: Onur A. Koska (University of Canterbury); Frank Stähler
    Abstract: This note scrutinizes the optimal reserve price in any ascending bid auction. If the auction may imply outcomes such that the winning bid is below the seller’s reservation utility, the seller will always set an optimal reserve price strictly larger than her reservation utility. The optimal reserve price depends only on two largest order statistics of the distribution of bids.
    Keywords: Auctions; Interdependent values; Optimal reserve prices
    JEL: D44
    Date: 2022–03–01
  4. By: Chinmay Maheshwari; Eric Mazumdar; Shankar Sastry
    Abstract: We study the problem of online learning in competitive settings in the context of two-sided matching markets. In particular, one side of the market, the agents, must learn about their preferences over the other side, the firms, through repeated interaction while competing with other agents for successful matches. We propose a class of decentralized, communication- and coordination-free algorithms that agents can use to reach to their stable match in structured matching markets. In contrast to prior works, the proposed algorithms make decisions based solely on an agent's own history of play and requires no foreknowledge of the firms' preferences. Our algorithms are constructed by splitting up the statistical problem of learning one's preferences, from noisy observations, from the problem of competing for firms. We show that under realistic structural assumptions on the underlying preferences of the agents and firms, the proposed algorithms incur a regret which grows at most logarithmically in the time horizon. Our results show that, in the case of matching markets, competition need not drastically affect the performance of decentralized, communication and coordination free online learning algorithms.
    Date: 2022–06
  5. By: Haris Aziz; Alexander Lam; Mashbat Suzuki; Toby Walsh
    Abstract: Proportionality is an attractive fairness concept that has been applied to a range of problems including the facility location problem, a classic problem in social choice. In our work, we propose a concept called Strong Proportionality, which ensures that when there are two groups of agents at different locations, both groups incur the same total cost. We show that although Strong Proportionality is a well-motivated and basic axiom, there is no deterministic strategyproof mechanism satisfying the property. We then identify a randomized mechanism called Random Rank (which uniformly selects a number $k$ between $1$ to $n$ and locates the facility at the $k$'th highest agent location) which satisfies Strong Proportionality in expectation. Our main theorem characterizes Random Rank as the unique mechanism that achieves universal truthfulness, universal anonymity, and Strong Proportionality in expectation among all randomized mechanisms. Finally, we show via the AverageOrRandomRank mechanism that even stronger ex-post fairness guarantees can be achieved by weakening universal truthfulness to strategyproofness in expectation.
    Date: 2022–05
  6. By: Soroush Ebadian; Anson Kahng; Nisarg Shah; Dominik Peters
    Abstract: A voting rule decides on a probability distribution over a set of $m$ alternatives, based on rankings of those alternatives provided by agents. We assume that agents have cardinal utility functions over the alternatives, but voting rules have access to only the rankings induced by these utilities. We evaluate how well voting rules do on measures of social welfare and of proportional fairness, computed based on the hidden utility functions. In particular, we study the distortion of voting rules, which is a worst-case measure. It is an approximation ratio comparing the utilitarian social welfare of the optimum outcome to the welfare of the outcome selected by the voting rule, in the worst case over possible input profiles and utility functions that are consistent with the input. The literature has studied distortion with unit-sum utility functions, and left a small asymptotic gap in the best possible distortion. Using tools from the theory of fair multi-winner elections, we propose the first voting rule which achieves the optimal distortion $\Theta(\sqrt{m})$ for unit-sum utilities. Our voting rule also achieves optimum $\Theta(\sqrt{m})$ distortion for unit-range and approval utilities. We then take a similar worst-case approach to a quantitative measure of the fairness of a voting rule, called proportional fairness. Informally, it measures whether the influence of cohesive groups of agents on the voting outcome is proportional to the group size. We show that there is a voting rule which, without knowledge of the utilities, can achieve an $O(\log m)$-approximation to proportional fairness, the best possible approximation. As a consequence of its proportional fairness, we show that this voting rule achieves $O(\log m)$ distortion with respect to Nash welfare, and provides an $O(\log m)$-approximation to the core, making it interesting for applications in participatory budgeting.
    Date: 2022–05

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