|
on Economic Design |
|
Issue of 2022‒05‒02
thirteen papers chosen by Guillaume Haeringer, Baruch College and Alex Teytelboym, University of Oxford |
| By: | Alexander Kolesnikov; Fedor Sandomirskiy; Aleh Tsyvinski; Alexander P. Zimin |
| Abstract: | We consider the problem of revenue-maximizing Bayesian auction design with several i.i.d. bidders and several items. We show that the auction-design problem can be reduced to the problem of continuous optimal transportation introduced by Beckmann. We establish the strong duality between the two problems and demonstrate the existence of solutions. We then develop a new numerical approximation scheme that combines multi-to-single-agent reduction and the majorization theory insights to characterize the solution. |
| Date: | 2022–03 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2203.06837&r= |
| By: | Shanglyu Deng |
| Abstract: | A speculator can take advantage of a procurement auction by acquiring items for sale before the auction. The accumulated market power can then be exercised in the auction and may lead to a large enough gain to cover the acquisition costs. I show that speculation always generates a positive expected profit in second-price auctions but could be unprofitable in first-price auctions. In the case where speculation is profitable in first-price auctions, it is more profitable in second-price auctions. This comparison in profitability is driven by different competition patterns in the two auction mechanisms. In terms of welfare, speculation causes private value destruction and harms efficiency. Sellers benefit from the acquisition offer made by the speculator. Therefore, speculation comes at the expense of the auctioneer. |
| Date: | 2022–03 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2203.03044&r= |
| By: | Saeed Alaei; Ali Makhdoumi; Azarakhsh Malekian; Rad Niazadeh |
| Abstract: | We consider descending price auctions for selling $m$ units of a good to unit demand i.i.d. buyers where there is an exogenous bound of $k$ on the number of price levels the auction clock can take. The auctioneer's problem is to choose price levels $p_1 > p_2 > \cdots > p_{k}$ for the auction clock such that auction expected revenue is maximized. The prices levels are announced prior to the auction. We reduce this problem to a new variant of prophet inequality, which we call \emph{batched prophet inequality}, where a decision-maker chooses $k$ (decreasing) thresholds and then sequentially collects rewards (up to $m$) that are above the thresholds with ties broken uniformly at random. For the special case of $m=1$ (i.e., selling a single item), we show that the resulting descending auction with $k$ price levels achieves $1- 1/e^k$ of the unrestricted (without the bound of $k$) optimal revenue. That means a descending auction with just 4 price levels can achieve more than 98\% of the optimal revenue. We then extend our results for $m>1$ and provide a closed-form bound on the competitive ratio of our auction as a function of the number of units $m$ and the number of price levels $k$. |
| Date: | 2022–03 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2203.01384&r= |
| By: | Eibelshäuser, Steffen; Smetak, Fabian |
| Abstract: | We study liquidity provision by competitive high-frequency trading firms (HFTs) in a dynamic trading model with private information. Liquidity providers face adverse selection risk from trading with privately informed investors and from trading with other HFTs that engage in latency arbitrage upon public information. The impact of the two different sources of risk depends on the details of the market design. We determine equilibrium transaction costs in continuous limit order book (CLOB) markets and under frequent batch auctions (FBA). In the absence of informed trading, FBA dominates CLOB just as in Budish et al. (2015). Surprisingly, this result does no longer hold with privately informed investors. We show that FBA allows liquidity providers to charge markups and earn profits - even under risk neutrality and perfect competition. A slight variation of the FBA design removes the inefficiency by allowing traders to submit orders conditional on auction excess demand. |
| Keywords: | market design,market microstructure,liquidity provision,high-frequency trading,continuous limit order book,frequent batch auctions,sniping,latency arbitrage |
| JEL: | G10 D47 |
| Date: | 2022 |
| URL: | http://d.repec.org/n?u=RePEc:zbw:safewp:344&r= |
| By: | Hadi Hosseini; Zhiyi Huang; Ayumi Igarashi; Nisarg Shah |
| Abstract: | In the classical version of online bipartite matching, there is a given set of offline vertices (aka agents) and another set of vertices (aka items) that arrive online. When each item arrives, its incident edges -- the agents who like the item -- are revealed and the algorithm must irrevocably match the item to such agents. We initiate the study of class fairness in this setting, where agents are partitioned into a set of classes and the matching is required to be fair with respect to the classes. We adopt popular fairness notions from the fair division literature such as envy-freeness (up to one item), proportionality, and maximin share fairness to our setting. Our class versions of these notions demand that all classes, regardless of their sizes, receive a fair treatment. We study deterministic and randomized algorithms for matching indivisible items (leading to integral matchings) and for matching divisible items (leading to fractional matchings). We design and analyze three novel algorithms. For matching indivisible items, we propose an adaptive-priority-based algorithm, MATCH-AND-SHIFT, prove that it achieves 1/2-approximation of both class envy-freeness up to one item and class maximin share fairness, and show that each guarantee is tight. For matching divisible items, we design a water-filling-based algorithm, EQUAL-FILLING, that achieves (1-1/e)-approximation of class envy-freeness and class proportionality; we prove (1-1/e) to be tight for class proportionality and establish a 3/4 upper bound on class envy-freeness. Finally, we build upon EQUAL-FILLING to design a randomized algorithm for matching indivisible items, EQAUL-FILLING-OCS, which achieves 0.593-approximation of class proportionality. The algorithm and its analysis crucially leverage the recently introduced technique of online correlated selection (OCS) [Fahrbach et al., 2020]. |
| Date: | 2022–03 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2203.03751&r= |
| By: | Juan Pereyra (Departamento de Economía, Facultad de Ciencias Sociales, Universidad de la República); Francisco Silva |
| Abstract: | Objects of different quality are to be assigned to agents. Agents can be assigned at most one object and there are not enough high-quality objects for every agent. The social planner is unable to use transfers to give incentives for agents to convey their private information; instead, she is able to imperfectly verify their reports. We characterize a mechanism that maximizes welfare, where agents face different lotteries over the various objects, depending on their report. We then apply our main result to the case of college admissions. We find that optimal mechanisms are, in general, ex-post inefficient and do strictly better than the standard mechanisms that are typically studied in the matching literature. |
| Keywords: | imperfect verification, evidence, mechanism design, matching. |
| JEL: | C7 D8 |
| Date: | 2020–09 |
| URL: | http://d.repec.org/n?u=RePEc:ude:wpaper:0420&r= |
| By: | Federico Echenique; Joseph Root; Fedor Sandomirskiy |
| Abstract: | We study efficiency in general collective choice problems when agents have ordinal preferences and randomization is allowed. We establish the equivalence between welfare maximization and ex-ante efficiency for general domains. We relate ex-ante efficiency with ex-post efficiency, characterizing when the two notions coincide. Our results have implications for well-studied mechanisms including random serial dictatorship and a number of specific environments, including the dichotomous, single-peaked, and social choice domains. |
| Date: | 2022–03 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2203.06353&r= |
| By: | Jason Hartline |
| Abstract: | The analysis of online bipartite matching of Eden et al. (2021) is a smoothness proof (Syrgkanis and Tardos, 2013). Moreover, it can be interpreted as combining a $\lambda = 1-1/e$ value covering (which holds for single-dimensional agents and randomized auctions) and $\mu = 1$ revenue covering (Hartline et al., 2014). Note that value covering is a fact about single-dimensional agents and has nothing to do with the underlying feasibility setting. Thus, the essential new result from Eden et al. (2021) is that online bipartite matching is $\mu=1$ revenue covered. |
| Date: | 2022–03 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2203.13140&r= |
| By: | Hadi Hosseini; Sujoy Sikdar; Rohit Vaish; Lirong Xia |
| Abstract: | We study fair allocation of indivisible goods and chores among agents with \emph{lexicographic} preferences -- a subclass of additive valuations. In sharp contrast to the goods-only setting, we show that an allocation satisfying \emph{envy-freeness up to any item} (EFX) could fail to exist for a mixture of \emph{objective} goods and chores. To our knowledge, this negative result provides the \emph{first} counterexample for EFX over (any subdomain of) additive valuations. To complement this non-existence result, we identify a class of instances with (possibly subjective) mixed items where an EFX and Pareto optimal allocation always exists and can be efficiently computed. When the fairness requirement is relaxed to \emph{maximin share} (MMS), we show positive existence and computation for \emph{any} mixed instance. More broadly, our work examines the existence and computation of fair and efficient allocations both for mixed items as well as chores-only instances, and highlights the additional difficulty of these problems vis-{\`a}-vis their goods-only counterparts. |
| Date: | 2022–03 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2203.07279&r= |
| By: | Yuri Faenza; Swati Gupta; Xuan Zhang |
| Abstract: | Discovery program (DISC) is an affirmative action policy used by the New York City Department of Education (NYC DOE). It has been instrumental in increasing the number of admissions for disadvantaged students at specialized high schools. However, our empirical analysis of the student-school matches shows that about 950 in-group blocking pairs were created each year amongst the disadvantaged group of students, impacting about 650 disadvantaged students. Moreover, we find that this program usually benefits lower-performing disadvantaged students more than the top-performing ones, thus unintentionally creating an incentive to under-perform. In this work, we explore two affirmative action policies that can be used to minimally modify and improve the discovery program: minority reserve (MR) and joint-seat allocation (JSA). We show that (i) both MR and JSA result in no in-group blocking pairs, and (ii) JSA is weakly group strategy-proof, ensures that at least one disadvantaged is not worse off, and when reservation quotas are carefully chosen then no disadvantaged student is worse-off. In the general setting, we show that there is no clear winner in terms of the matchings provided by DISC, JSA and MR, from the perspective of disadvantaged students. We however characterize a condition for markets, that we term high competitiveness, where JSA dominates MR for disadvantaged students. This condition is verified in markets when there is a higher demand for seats than supply, and the performances of disadvantaged students are significantly lower than that of advantaged students. Data from NYC DOE satisfy the high competitiveness condition, and for this dataset our empirical results corroborate our theoretical predictions, showing the superiority of JSA. We believe that the discovery program, and more generally affirmative action mechanisms, can be changed for the better by implementing JSA. |
| Date: | 2022–03 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2203.00544&r= |
| By: | Tayfun Sonmez; M. Bumin Yenmez |
| Abstract: | India is home to a comprehensive affirmative action program that reserves a fraction of positions at governmental institutions for various disadvantaged groups. While there is a Supreme Court-endorsed mechanism to implement these reservation policies when all positions are identical, courts have refrained from endorsing explicit mechanisms when positions are heterogeneous. This lacunae has resulted in widespread adoption of unconstitutional mechanisms, countless lawsuits, and inconsistent court rulings. Formulating mandates in the landmark Supreme Court judgment Saurav Yadav (2020) as technical axioms, we show that the 2SMH-DA mechanism is uniquely suited to overcome these challenges. |
| Date: | 2022–03 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2203.01483&r= |
| By: | Zo\"e Hitzig; Benjamin Niswonger |
| Abstract: | This paper defines and analyzes default delegation, an indirect mechanism that describes how the government influences bilateral contracts to maximize social welfare. In default delegation, the government chooses the default contract and a possibly-limited set of contract terms it is willing to enforce. Our analysis of this mechanism provides a theoretical foundation for immutable and default rules in contract law: immutable rules mitigate externalities, while default rules achieve particular distributions of surplus in non-contractible states of the world. We derive conditions under which default delegation implements the entire set of first-best contracts. We then characterize how optimal default delegation responds to changes in the underlying contracting environment and in the social welfare function's weighting of efficiency, externalities and distributional concerns. |
| Date: | 2022–03 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2203.01233&r= |
| By: | Gregorio Curello; Ludvig Sinander |
| Abstract: | In the canonical persuasion model, comparative statics has been an open question. We answer it, delineating which shifts of the sender's interim payoff lead her optimally to choose a more informative signal. Our first theorem identifies an ordinal notion of 'increased convexity' that we show characterises those shifts of the sender's interim payoff that lead her optimally to choose no less informative signals. To strengthen this conclusion to 'more informative' requires further assumptions: our second theorem identifies the necessary and sufficient condition on the sender's interim payoff, which strictly generalises the 'S'-shape commonly imposed in the literature. (Note: preliminary and incomplete.) |
| Date: | 2022–04 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2204.07474&r= |