|
on Economic Design |
| By: | Dirk Bergemann; Marek Bojko; Paul D\"utting; Renato Paes Leme; Haifeng Xu; Song Zuo |
| Abstract: | We study mechanism design when agents hold private information about both their preferences and a common payoff-relevant state. We show that standard message-driven mechanisms cannot implement socially efficient allocations when agents have multidimensional types, even under favorable conditions. To overcome this limitation, we propose data-driven mechanisms that leverage additional post-allocation information, modeled as an estimator of the payoff-relevant state. Our data-driven mechanisms extend the classic Vickrey-Clarke-Groves class. We show that they achieve exact implementation in posterior equilibrium when the state is either fully revealed or the utility is linear in an unbiased estimator. We also show that they achieve approximate implementation with a consistent estimator, converging to exact implementation as the estimator converges, and present bounds on the convergence rate. We demonstrate applications to digital advertising auctions and large language model (LLM)-based mechanisms, where user engagement naturally reveals relevant information. |
| Date: | 2024–12 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2412.16132 |
| By: | Karen Frilya Celine; Warut Suksompong; Sheung Man Yuen |
| Abstract: | Allocating indivisible goods is a ubiquitous task in fair division. We study additive welfarist rules, an important class of rules which choose an allocation that maximizes the sum of some function of the agents' utilities. Prior work has shown that the maximum Nash welfare (MNW) rule is the unique additive welfarist rule that guarantees envy-freeness up to one good (EF1). We strengthen this result by showing that MNW remains the only additive welfarist rule that ensures EF1 for identical-good instances, two-value instances, as well as normalized instances with three or more agents. On the other hand, if the agents' utilities are integers, we demonstrate that several other rules offer the EF1 guarantee, and provide characterizations of these rules for various classes of instances. |
| Date: | 2024–12 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2412.15472 |
| By: | Yingni Guo; Hao Li; Xianwen Shi |
| Abstract: | A seller of an indivisible good designs a selling mechanism for a buyer whose private information (his type) is the distribution of his value for the good. A selling mechanism includes both a menu of sequential pricing, and a menu of information disclosure about the realized value that the buyer is allowed to learn privately. In a model of two types with an increasing likelihood ratio, we show that under some regularity conditions the disclosure policy in an optimal mechanism has a nested interval structure: the high type is allowed to learn whether his value is greater than the seller's cost, while the low type is allowed to learn whether his value is in an interval above the cost. The interval of the low type may exclude values at the top of the distribution to reduce the information rent of the high type. Information discrimination is in general necessary in an optimal mechanism. |
| Keywords: | Sequential Screening, Dynamic Mechanism Design, Disclosure, Information Design |
| JEL: | D83 D82 |
| Date: | 2025–01–16 |
| URL: | https://d.repec.org/n?u=RePEc:tor:tecipa:tecipa-792 |
| By: | Haris Aziz; Patrick Lederer; Xinhang Lu; Mashbat Suzuki; Jeremy Vollen |
| Abstract: | In approval-based budget division, a budget needs to be distributed to some candidates based on the voters' approval ballots over these candidates. In the pursuit of simple, well-behaved, and approximately fair rules for this setting, we introduce the class of sequential payment rules, where each voter controls a part of the budget and repeatedly spends his share on his approved candidates to determine the final distribution. We show that all sequential payment rules satisfy a demanding population consistency notion and we identify two particularly appealing rules within this class called the maximum payment rule (MP) and the $\frac{1}{3}$-multiplicative sequential payment rule ($\frac{1}{3}$-MP). More specifically, we prove that (i) MP is, apart from one other rule, the only monotonic sequential payment rule and gives a $2$-approximation to a fairness notion called average fair share, and (ii) $\frac{1}{3}$-MP gives a $\frac{3}{2}$-approximation to average fair share, which is optimal among sequential payment rules. |
| Date: | 2024–12 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2412.02435 |
| By: | Mridu Prabal Goswami |
| Abstract: | We consider an economic environment with one buyer and one seller. For a bundle $(t, q)\in [0, \infty[\times [0, 1]=\mathbb{Z}$, $q$ refers to the winning probability of an object, and $t$ denotes the payment that the buyer makes. We consider continuous and monotone preferences on $\mathbb{Z}$ as the primitives of the buyer. These preferences can incorporate both quasilinear and non-quasilinear preferences, and multidimensional pay-off relevant parameters. We define rich single-crossing subsets of this class and characterize strategy-proof mechanisms by using monotonicity of the mechanisms and continuity of the indirect preference correspondences. We also provide a computationally tractable optimization program to compute the optimal mechanism for mechanisms with finite range. We do not use revenue equivalence and virtual valuations as tools in our proofs. Our proof techniques bring out the geometric interaction between the single-crossing property and the positions of bundles $(t, q)$s in the space $\mathbb{Z}$. We also provide an extension of our analysis to an $n-$buyer environment, and to the situation where $q$ is a qualitative variable. |
| Date: | 2024–12 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2412.11113 |
| By: | Daniel Kornbluth; Alexey Kushnir |
| Abstract: | Prevailing methods of course allocation at undergraduate institutions involve reserving seats to give priority to designated groups of students. We introduce a competitive equilibrium-based mechanism that assigns course seats using student preferences and course priorities. This mechanism satisfies approximate notions of stability, efficiency, envy-freeness, and strategy-proofness. We evaluate its performance relative to a mechanism widely used in practice using preferences estimated from university data. Our empirical findings demonstrate an improvement in student satisfaction and allocation fairness. The number of students who envy another student of weakly lower priority declines by 8 percent, or roughly 500 students. |
| Date: | 2024–12 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2412.05691 |
| By: | Ying Xue Li; Burkhard C. Schipper |
| Abstract: | When bidders bid on complex objects, they might be unaware of characteristics effecting their valuations. We assume that each buyer's valuation is a sum of independent random variables, one for each characteristic. When a bidder is unaware of a characteristic, he omits the random variable from the sum. We study the seller's decision to raise bidders' awareness of characteristics before a second-price auction with entry fees. Optimal entry fees capture an additional unawareness rent due to unaware bidders misperceiving their probability of winning and the price to be paid upon winning. When raising a bidder's individual awareness of a characteristic with positive expected value, the seller faces a trade-off between positive effects on the expected first order statistic and unawareness rents of remaining unaware bidders on one hand and the loss of the unawareness rent from the newly aware bidder on the other. We present characterization results on raising public awareness together with no versus full information. We discuss the winner's curse due to unawareness of characteristics. |
| Date: | 2024–12 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2412.12676 |
| By: | Hao Li; Xianwen Shi |
| Abstract: | We study when and how randomization can help improve the seller's revenue in the sequential screening setting. In a model with discrete ex ante types and a continuum of ex post valuations, the standard approach based on solving a relaxed problem that keeps only local downward incentive compatibility constraints often fails. Under a strengthening of first-order stochastic dominance ordering on the valuation distribution functions of ex ante types, we introduce and solve a modified relaxed problem by retaining all local incentive compatibility constraints, provide necessary and sufficient conditions for optimal mechanisms to be stochastic, and characterize optimal stochastic contracts. Our analysis mostly focuses on the case of three ex ante types, but our methodology of solving the modified problem, as well as the necessary and sufficient conditions for randomization to be optimal, can be extended to any finite number of ex ante types. |
| Keywords: | Sequential Screening, Stochastic Mechanism |
| JEL: | D83 D82 |
| Date: | 2025–01–16 |
| URL: | https://d.repec.org/n?u=RePEc:tor:tecipa:tecipa-793 |
| By: | Felix Brandt; Patrick Lederer |
| Abstract: | An important -- but very demanding -- property in collective decision-making is strategyproofness, which requires that voters cannot benefit from submitting insincere preferences. Gibbard (1977) has shown that only rather unattractive rules are strategyproof, even when allowing for randomization. However, Gibbard's theorem is based on a rather strong interpretation of strategyproofness, which deems a manipulation successful if it increases the voter's expected utility for at least one utility function consistent with his ordinal preferences. In this paper, we study weak strategyproofness, which deems a manipulation successful if it increases the voter's expected utility for all utility functions consistent with his ordinal preferences. We show how to systematically design attractive, weakly strategyproof social decision schemes (SDSs) and explore their limitations for both strict and weak preferences. In particular, for strict preferences, we show that there are weakly strategyproof SDSs that are either ex post efficient or Condorcet-consistent, while neither even-chance SDSs nor pairwise SDSs satisfy both properties and weak strategyproofness at the same time. By contrast, for the case of weak preferences, we discuss two sweeping impossibility results that preclude the existence of appealing weakly strategyproof SDSs. |
| Date: | 2024–12 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2412.11977 |
| By: | Mohit Garg; Suneel Sarswat |
| Abstract: | Continuous double auctions are commonly used to match orders at currency, stock, and commodities exchanges. A verified implementation of continuous double auctions is a useful tool for market regulators as they give rise to automated checkers that are guaranteed to detect errors in the trade logs of an existing exchange if they contain trades that violate the matching rules. We provide an efficient and formally verified implementation of continuous double auctions that takes $O(n \log n)$ time to match $n$ orders. This improves an earlier $O(n^2)$ verified implementation. We also prove a matching $\Omega(n\log n)$ lower bound on the running time for continuous double auctions. Our new implementation takes only a couple of minutes to run on ten million randomly generated orders as opposed to a few days taken by the earlier implementation. Our new implementation gives rise to an efficient automatic checker. We use the Coq proof assistant for verifying our implementation and extracting a verified OCaml program. While using Coq's standard library implementation of red-black trees to obtain our improvement, we observed that its specification has serious gaps, which we fill in this work; this might be of independent interest. |
| Date: | 2024–12 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2412.08624 |
| By: | Yanlin Chen; Xianwen Shi; Jun Zhang |
| Abstract: | We study the welfare effects of price discrimination in a duopoly market with both captive and contested consumers. Using a unified information design approach, we characterize the best and worst market segmentations for producer surplus, consumer surplus, and social surplus. The firm-optimal segmentation, which divides the market into two nested segments, consistently harms consumers compared to uniform pricing. The consumer-optimal segmentation, which divides the market into a symmetric segment and a nested segment, sometimes leads to a Pareto improvement. Social surplus, if monotone in firm profit, is often maximized either by the firm-optimal or consumer-optimal segmentation. |
| Keywords: | Information Design, Market Segmentation, Firm-optimal Segmentation, Consumer-optimal Segmentation |
| JEL: | D43 D82 |
| Date: | 2025–01–16 |
| URL: | https://d.repec.org/n?u=RePEc:tor:tecipa:tecipa-790 |
| By: | Ravi Jagadeesan; Alexander Teytelboym |
| Abstract: | This paper develops a theory of competitive equilibrium with indivisible goods based entirely on economic conditions on demand. The key idea is to analyze complementarity and substitutability between bundles of goods, rather than merely between goods themselves. This approach allows us to formulate sufficient, and essentially necessary, conditions for equilibrium existence, which unify settings with complements and settings with substitutes. Our analysis has implications for auction design. |
| Date: | 2024–12 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2412.07946 |
| By: | Yannai A. Gonczarowski; Ella Segev |
| Abstract: | We axiomatically define a cardinal social inefficiency function, which, given a set of alternatives and individuals' vNM preferences over the alternatives, assigns a unique number -- the social inefficiency -- to each alternative. These numbers -- and not only their order -- are uniquely defined by our axioms despite no exogenously given interpersonal comparison, outside option, or disagreement point. We interpret these numbers as per capita losses in endogenously normalized utility. We apply our social inefficiency function to a setting in which interpersonal comparison is notoriously hard to justify -- object allocation without money -- leveraging techniques from computer science to prove an approximate-efficiency result for the Random Serial Dictatorship mechanism. |
| Date: | 2024–12 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2412.11984 |
| By: | Saurab Chhachhi; Fei Teng |
| Abstract: | Data is an increasingly vital component of decision making processes across industries. However, data access raises privacy concerns motivating the need for privacy-preserving techniques such as differential privacy. Data markets provide a means to enable wider access as well as determine the appropriate privacy-utility trade-off. Existing data market frameworks either require a trusted third party to perform computationally expensive valuations or are unable to capture the combinatorial nature of data value and do not endogenously model the effect of differential privacy. This paper addresses these shortcomings by proposing a valuation mechanism based on the Wasserstein distance for differentially-private data, and corresponding procurement mechanisms by leveraging incentive mechanism design theory, for task-agnostic data procurement, and task-specific procurement co-optimisation. The mechanisms are reformulated into tractable mixed-integer second-order cone programs, which are validated with numerical studies. |
| Date: | 2024–12 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2412.02609 |
| By: | Mikhail Drugov; Dmitry Ryvkin; Jun Zhang |
| Abstract: | We study tournaments where winning a rank-dependent prize requires passing a minimum performance standard. We show that, for any prize allocation, the optimal standard is always at a mode of performance that is weakly higher than the global mode and identify a necessary and sufficient condition for it to be at the global mode. When the prize scheme can be designed as well, the winner-take-all prize scheme is optimal for noise distributions with an increasing failure rate; and awarding equal prizes to all qualifying agents is optimal for noise distributions with a decreasing failure rate. For distributions with monotone likelihood ratios -- log-concave and log-convex, respectively -- these pay schemes are also optimal in a larger class of anonymous, monotone contracts that may depend on cardinal performance. |
| Date: | 2024–12 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2412.01139 |
| By: | Anton Kolotilin; Hongyi Li; Andriy Zapechelnyuk |
| Abstract: | We study monotone persuasion in the linear case, where posterior distributions over states are summarized by their mean. We solve the two leading cases where optimal unrestricted signals can be nonmonotone. First, if the objective is s-shaped and the state is discrete, then optimal monotone signals are upper censorship, whereas optimal unrestricted signals may require randomization. Second, if the objective is m-shaped and the state is continuous, then optimal monotone signals are interval disclosure, whereas optimal unrestricted signals may require nonmonotone pooling. We illustrate our results with an application to media censorship. |
| Date: | 2024–12 |
| URL: | https://d.repec.org/n?u=RePEc:arx:papers:2412.14400 |
| By: | Itai Arieli; Yakov Babichenko; Dima Shaiderman; Xianwen Shi |
| Abstract: | We propose a dynamic persuasion model of product adoption, where an impatient, long-lived sender commits to a dynamic disclosure policy to persuade a sequence of short-lived receivers to adopt a new product. The sender privately observes a sequence of signals, one per period, about the product quality, and therefore the sequence of her posteriors forms a discrete-time martingale. The disclosure policy specifies ex ante how the sender's information will be revealed to the receivers in each period. We introduce a new concept called ``Blackwell-preserving kernels'' and show that if the sender's belief martingale possesses these kernels, the family of optimal strategies for the sender takes an interval form; namely, in every period, the set of martingale realizations in which adoption occurs is an interval. Utilizing this, we prove that if the sender is sufficiently impatient, then under a random walk martingale, the optimal policy is fully transparent up to the moment of adoption; namely, the sender reveals all the information she privately holds in every period. |
| Keywords: | Dynamic Information Design, Bayesian Persuasion, Learning |
| JEL: | D83 D82 |
| Date: | 2025–01–16 |
| URL: | https://d.repec.org/n?u=RePEc:tor:tecipa:tecipa-791 |