
on Economic Design 
By:  Bos, Olivier; Truyts, Tom 
Abstract:  We study the optimal entry fee in a symmetric private value firstprice 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:  firstprice auction,entry,monotonic signaling,social status 
JEL:  D44 D82 
Date:  2022 
URL:  http://d.repec.org/n?u=RePEc:zbw:zewdip:22016&r= 
By:  Meryem Essaidi; Matheus V. X. Ferreira; S. Matthew Weinberg 
Abstract:  We consider a revenuemaximizing 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 tworound 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 nonMHR distribution. In this work, under the same cryptographic assumptions, we identify a new singleitem auction that is credible, strategyproof, revenue optimal, and terminates in constant rounds in expectation for all distributions with finite monopoly price. 
Date:  2022–05 
URL:  http://d.repec.org/n?u=RePEc:arx:papers:2205.14758&r= 
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 
URL:  http://d.repec.org/n?u=RePEc:cbt:econwp:22/07&r= 
By:  Chinmay Maheshwari; Eric Mazumdar; Shankar Sastry 
Abstract:  We study the problem of online learning in competitive settings in the context of twosided 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 coordinationfree 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 
URL:  http://d.repec.org/n?u=RePEc:arx:papers:2206.02344&r= 
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 wellmotivated 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 expost fairness guarantees can be achieved by weakening universal truthfulness to strategyproofness in expectation. 
Date:  2022–05 
URL:  http://d.repec.org/n?u=RePEc:arx:papers:2205.14798&r= 
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 worstcase 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 unitsum utility functions, and left a small asymptotic gap in the best possible distortion. Using tools from the theory of fair multiwinner elections, we propose the first voting rule which achieves the optimal distortion $\Theta(\sqrt{m})$ for unitsum utilities. Our voting rule also achieves optimum $\Theta(\sqrt{m})$ distortion for unitrange and approval utilities. We then take a similar worstcase 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 
URL:  http://d.repec.org/n?u=RePEc:arx:papers:2205.15760&r= 