|
on Economic Design |
|
Issue of 2023‒02‒27
twelve papers chosen by Guillaume Haeringer, Baruch College and Alex Teytelboym, University of Oxford |
| By: | Alfred Galichon (ECON - Département d'économie (Sciences Po) - Sciences Po - Sciences Po - CNRS - Centre National de la Recherche Scientifique, NYU - NYU System); Octavia Ghelfi (NYU - NYU System); Marc Henry (Penn State - Pennsylvania State University - Penn State System) |
| Abstract: | We highlight the tension between stability and equality in non transferable utility matching. We consider many to one matchings and refer to the two sides of the market as students and schools. The latter have aligned preferences, which in this context means that a school's utility is the sum of its students' utilities. We show that the unique stable allocation displays extreme inequality between matched pairs. |
| Date: | 2021–08–17 |
| URL: | http://d.repec.org/n?u=RePEc:hal:spmain:hal-03936184&r=des |
| By: | Elliott, M.; Galeotti, A.; Koh, A.; Li, W. |
| Abstract: | There are many markets that are networked in these sense that not all consumers have access to (or are aware of) all products, while, at the same time, firms have some information about consumers and can distinguish some consumers from some others (for example, in online markets through cookies). With unit demand and price-setting firms we give a complete characterization of all welfare outcomes achievable in equilibrium (for arbitrary buyer-seller networks and arbitrary information structures), as well as the designs (networks and information structures) which implement them. |
| Date: | 2023–02–04 |
| URL: | http://d.repec.org/n?u=RePEc:cam:camdae:2313&r=des |
| By: | Sophie Bade; Joseph Root |
| Abstract: | We study the set of incentive compatible and efficient two-sided matching mechanisms. We classify all such mechanisms under an additional assumption -- "gender-neutrality" -- which guarantees that the two sides be treated symmetrically. All group strategy-proof, efficient and gender-neutral mechanisms are recursive and the outcome is decided in a sequence of rounds. In each round, two agents are selected, one from each side. These agents are either "matched-by-default" or "unmatched-by-default." In the former case either of the selected agents can unilaterally force the other to match with them while in the latter case they may only match together if both agree. In either case, if this pair of agents is not matched together, each gets their top choice among the set of remaining agents. As an important step in the characterization, we first show that in one-sided matching all group strategy-proof and efficient mechanisms are sequential dictatorships. An immediate corollary is that there are no individually rational, group strategy-proof and efficient one-sided matching mechanisms. |
| Date: | 2023–01 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2301.13037&r=des |
| By: | Rustamdjan Hakimov (WZB Berlin); Madhav Raghavan (University of Lausanne) |
| Abstract: | Students participating in centralized admissions procedures do not typically have access to the information used to determine their matched school, such as other students' preferences or school priorities. This can lead to doubts about whether their matched schools were computed correctly (the `Verifiability Problem') or, at a deeper level, whether the promised admissions procedure was even used (the `Transparency Problem'). In a general centralized admissions model that spans many popular applications, we show how these problems can be addressed by providing appropriate feedback to students, even without disclosing sensitive private information like other students' preferences or school priorities. In particular, we show that the Verifiability Problem can be solved by (1) publicly communicating the minimum scores required to be matched to a school (`cutoffs'); or (2) using `predictable' preference elicitation procedures that convey rich `experiential' information. In our main result, we show that the Transparency Problem can be solved by using cutoffs and predictable procedures together. We find strong support for these solutions in a laboratory experiment, and show how they can be simply implemented for popular school admissions applications involving top trading cycles, and deferred and immediate acceptance. |
| Keywords: | school choice; matching; transparency; cutoffs; dynamic mechanisms; experiment; |
| JEL: | C78 C73 D78 D82 |
| Date: | 2023–01–27 |
| URL: | http://d.repec.org/n?u=RePEc:rco:dpaper:376&r=des |
| By: | Yeganeh Alimohammadi; Aranyak Mehta; Andres Perlroth |
| Abstract: | Auto-bidding has recently become a popular feature in ad auctions. This feature enables advertisers to simply provide high-level constraints and goals to an automated agent, which optimizes their auction bids on their behalf. In this paper, we examine the effect of different auctions on the incentives of advertisers to report their constraints to the auto-bidder intermediaries. More precisely, we study whether canonical auctions such as first price auction (FPA) and second price auction (SPA) are auto-bidding incentive compatible (AIC): whether an advertiser can gain by misreporting their constraints to the autobidder. We consider value-maximizing advertisers in two important settings: when they have a budget constraint and when they have a target cost-per-acquisition constraint. The main result of our work is that for both settings, FPA and SPA are not AIC. This contrasts with FPA being AIC when auto-bidders are constrained to bid using a (sub-optimal) uniform bidding policy. We further extend our main result and show that any (possibly randomized) auction that is truthful (in the classic profit-maximizing sense), scalar invariant and symmetric is not AIC. Finally, to complement our findings, we provide sufficient market conditions for FPA and SPA to become AIC for two advertisers. These conditions require advertisers' valuations to be well-aligned. This suggests that when the competition is intense for all queries, advertisers have less incentive to misreport their constraints. From a methodological standpoint, we develop a novel continuous model of queries. This model provides tractability to study equilibrium with auto-bidders, which contrasts with the standard discrete query model, which is known to be hard. Through the analysis of this model, we uncover a surprising result: in auto-bidding with two advertisers, FPA and SPA are auction equivalent. |
| Date: | 2023–01 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2301.13414&r=des |
| By: | Gagan Aggarwal; Andres Perlroth; Junyao Zhao |
| Abstract: | Over the past few years, more and more Internet advertisers have started using automated bidding for optimizing their advertising campaigns. Such advertisers have an optimization goal (e.g. to maximize conversions), and some constraints (e.g. a budget or an upper bound on average cost per conversion), and the automated bidding system optimizes their auction bids on their behalf. Often, these advertisers participate on multiple advertising channels and try to optimize across these channels. A central question that remains unexplored is how automated bidding affects optimal auction design in the multi-channel setting. In this paper, we study the problem of setting auction reserve prices in the multi-channel setting. In particular, we shed light on the revenue implications of whether each channel optimizes its reserve price locally, or whether the channels optimize them globally to maximize total revenue. Motivated by practice, we consider two models: one in which the channels have full freedom to set reserve prices, and another in which the channels have to respect floor prices set by the publisher. We show that in the first model, welfare and revenue loss from local optimization is bounded by a function of the advertisers' inputs, but is independent of the number of channels and bidders. In stark contrast, we show that the revenue from local optimization could be arbitrarily smaller than those from global optimization in the second model. |
| Date: | 2023–01 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2301.13410&r=des |
| By: | Mallesh Pai; Max Resnick; Elijah Fox |
| Abstract: | Smart contracts offer a way to credibly commit to a mechanism, as long as it can be expressed as an easily computable mapping from inputs, in the form of transactions on-chain, to outputs: allocations and payments. But proposers decide which transactions to include, allowing them to manipulate these mechanisms and extract temporary monopoly rents known as MEV. Motivated by both general interest in running auctions on-chain, and current proposals to conduct MEV auctions on-chain, we study how these manipulations effect the equilibria of auctions. Formally, we consider an independent private value auction where bidders simultaneously submit private bids, and public tips, that are paid to the proposer upon inclusion. A single additional bidder may bribe the proposer to omit competing bids. We show that even if bids are completely sealed, tips reveal bids in equilibrium, which suggests that encrypting bids may not prevent manipulation. Further, we show that collusion at the transaction inclusion step is extremely profitable for the colluding bidder: as the number of bidders increases, the probability that the winner is not colluding and the economic efficiency of the auction both decrease faster than $1/n$. Running the auction over multiple blocks, each with a different proposer, alleviates the problem only if the number of blocks is larger than the number of bidders. We argue that blockchains with more than one concurrent proposer can credibly execute auctions on chain, as long as tips can be conditioned on the number of proposers that include the transaction. |
| Date: | 2023–01 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2301.13321&r=des |
| By: | Andrea Canidio |
| Abstract: | I study mechanism design with blockchain-based tokens, that is, tokens that can be used within a mechanism but can also be saved and traded outside of the mechanism. I do so by considering a repeated, private-value auction, in which the auctioneer accepts payments in a blockchain-based token he creates and initially owns. I show that the present-discounted value of the expected revenues is the same as in a standard auction with dollars, but these revenues accrue earlier and are less variable. I then introduce non-contractible effort and the possibility of misappropriating revenues. I compare the auction with tokens to an auction with dollars in which the auctioneer can also issue financial securities. An auction with tokens is preferred when there are sufficiently severe contracting frictions, while the opposite is true when contracting frictions are low. |
| Date: | 2023–01 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2301.13794&r=des |
| By: | Aadityan Ganesh; Jason Hartline |
| Abstract: | Pen testing is the problem of selecting high capacity resources when the only way to measure the capacity of a resource expends its capacity. We have a set of $n$ pens with unknown amounts of ink and our goal is to select a feasible subset of pens maximizing the total ink in them. We are allowed to gather more information by writing with them, but this uses up ink that was previously in the pens. Algorithms are evaluated against the standard benchmark, i.e, the optimal pen testing algorithm, and the omniscient benchmark, i.e, the optimal selection if the quantity of ink in the pens are known. We identify optimal and near optimal pen testing algorithms by drawing analogues to auction theoretic frameworks of deferred-acceptance auctions and virtual values. Our framework allows the conversion of any near optimal deferred-acceptance mechanism into a pen testing algorithm with an additional overhead of at most $(1+o(1)) \ln n$ in the approximation factor of the omniscient benchmark. We use this framework to give pen testing algorithms for various combinatorial constraints like matroid, knapsack and general downward-closed constraints and also for online environments. |
| Date: | 2023–01 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2301.12462&r=des |
| By: | Dirk Bergemann (Yale University); Tibor Heumann (Yale University); Stephen Morris (Cowles Foundation, Yale University) |
| Abstract: | We consider a nonlinear pricing environment with private information. We provide profit guarantees (and associated mechanisms) that the seller can achieve across all possible distributions of willingness to pay of the buyers. With a constant elasticity cost function, constant markup pricing provides the optimal revenue guarantee across all possible distributions of willingness to pay and the lower bound is attained under a Pareto distribution. We characterize how profits and consumer surplus vary with the distribution of values and show that Pareto distributions are extremal. We also provide a revenue guarantee for general cost functions. We establish equivalent results for optimal procurement policies that support maximal surplus guarantees for the buyer given all possible cost distributions of the sellers. |
| Date: | 2023–01 |
| URL: | http://d.repec.org/n?u=RePEc:cwl:cwldpp:2353&r=des |
| By: | Anna Bogomolnaia; Herve Moulin |
| Abstract: | We propose a fair and efficient solution for assigning agents to m posts subject to congestion, when agents care about both their post and its congestion. Examples include assigning jobs to busy servers, students to crowded schools or crowded classes, commuters to congested routes, workers to crowded office spaces or to team projects etc... Congestion is anonymous (it only depends on the number n of agents in a given post). A canonical interpretation of ex ante fairness allows each agent to choose m post-specific caps on the congestion they tolerate: these requests are mutually feasible if and only if the sum of the caps is n. For ex post fairness we impose a competitive requirement close to envy freeness: taking the congestion profile as given each agent is assigned to one of her best posts. If a competitive assignment exists, it delivers unique congestion and welfare profiles and is also efficient and ex ante fair. In a fractional (randomised or time sharing) version of our model, a unique competitive congestion profile always exists. It is approximately implemented by a mixture of ex post deterministic assignments: with an approxination factor equal to the largest utility loss from one more unit of congestion, the latter deliver identical welfare profiles and are weakly efficient. Our approach to ex ante fairness generalises to the model where each agent's congestion is weighted. Now the caps on posts depend only upon own weight and total congestion, not on the number of other agents contributing to it. Remarkably in both models these caps are feasible if and only if they give to each agent the right to veto all but (1/m) of their feasible allocations. |
| Date: | 2023–01 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2301.12163&r=des |
| By: | Andreas A. Haupt; Nicole Immorlica; Brendan Lucier |
| Abstract: | Motivated by applications such as voluntary carbon markets and educational testing, we consider a market for goods with varying but hidden levels of quality in the presence of a third-party certifier. The certifier can provide informative signals about the quality of products, and can charge for this service. Sellers choose both the quality of the product they produce and a certification. Prices are then determined in a competitive market. Under a single-crossing condition, we show that the levels of certification chosen by producers are uniquely determined at equilibrium. We then show how to reduce a revenue-maximizing certifier's problem to a monopolistic pricing problem with non-linear valuations, and design an FPTAS for computing the optimal slate of certificates and their prices. In general, both the welfare-optimal and revenue-optimal slate of certificates can be arbitrarily large. |
| Date: | 2023–01 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2301.13449&r=des |