|
on Economic Design |
|
Issue of 2022‒05‒09
eighteen papers chosen by Guillaume Haeringer, Baruch College and Alex Teytelboym, University of Oxford |
| By: | Zhaohua Chen; Xiaotie Deng; Jicheng Li; Chang Wang; Mingwei Yang |
| Abstract: | In today's online advertising markets, it is common for an advertiser to set a long-period budget. Correspondingly, advertising platforms adopt budget control methods to ensure that any advertiser's payment is within her budget. Most budget control methods rely on value distributions of advertisers. However, due to the complex environment advertisers stand in and privacy issues, the platform hardly learns their true priors. Therefore, it is essential to understand how budget control auction mechanisms perform under unassured priors. This paper gives a two-fold answer. First, we propose a bid-discount method barely studied in the literature. We show that such a method exhibits desirable properties in revenue-maximizing and computation when fitting into first-price auction. Second, we compare this mechanism with another four in the prior manipulation model, where an advertiser can arbitrarily report a value distribution to the platform. These four mechanisms include the optimal mechanism satisfying budget-constrained IC, first-price/second-price mechanisms with the widely-studied pacing method, and an application of bid-discount in second-price mechanism. We consider three settings under the model, depending on whether the reported priors are fixed and advertisers are symmetric or not. We show that under all three cases, the bid-discount first-price auction we introduce dominates the other four mechanisms concerning the platform's revenue. For the advertisers' side, we show a surprising strategic-equivalence result between this mechanism and the optimal auction. Extensive revenue dominance and strategic relationships among these mechanisms are also revealed. Based on these findings, we provide a thorough understanding of prior dependency in repeated auctions with budgets. The bid-discount first-price auction itself may also be of further independent research interest. |
| Date: | 2022–03 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2203.16816&r= |
| By: | Dütting, Paul; Kesselheim, Thomas |
| Abstract: | In a combinatorial auction with item bidding, agents participate in multiple single-item second-price auctions at once. As some items might be substitutes, agents need to strategize in order to maximize their utilities. A number of results indicate that high social welfare can be achieved this way, giving bounds on the welfare at equilibrium. Recently, however, criticism has been raised that equilibria of this game are hard to compute and therefore unlikely to be attained. In this paper, we take a different perspective by studying simple best-response dynamics. Often these dynamics may take exponentially long before they converge or they may not converge at all. However, as we show, convergence is not even necessary for good welfare guarantees. Given that agents’ bid updates are aggressive enough but not too aggressive, the game will reach and remain in states of high welfare after each agent has updated his bid at least once. |
| Keywords: | algorithmic game theory; combinatorial auctions; item bidding; best-response dynamics |
| JEL: | J1 |
| Date: | 2020–10–01 |
| URL: | http://d.repec.org/n?u=RePEc:ehl:lserod:106607&r= |
| By: | Di Feng; Bettina Klaus; Flip Klijn |
| Abstract: | We consider the generalization of the classical Shapley and Scarf housing market model of trading indivisible objects (houses) (Shapley and Scarf, 1974) to so-called multiple-type housing markets (Moulin, 1995). When preferences are separable, the prominent solution for these markets is the coordinate-wise top-trading-cycles (cTTC) mechanism. We first show that on the subdomain of lexicographic preferences, a mechanism is unanimous (or onto), individually rational, strategy-proof, and non-bossy if and only if it is the cTTC mechanism (Theorem 1). Second, using Theorem 1, we obtain a corresponding characterization on the domain of separable preferences (Theorem 2). Finally, we show that on the domain of strict preferences, there is no mechanism satisfying unanimity (or ontoness), individual rationality, strategy-proofness, and non-bossiness (Theorem 3).Our characterization of the cTTC mechanism constitutes the first characterization of an extension of the prominent top-trading-cycles (TTC) mechanism to multiple-type housing markets. |
| Keywords: | : multiple-type housing markets, strategy-proofness, non-bossiness, top-trading-cycles (TTC) mechanism, market design |
| JEL: | C78 D47 |
| Date: | 2022–04 |
| URL: | http://d.repec.org/n?u=RePEc:lau:crdeep:22.06&r= |
| By: | Josue Ortega; Thilo Klein |
| Abstract: | How should students be assigned to schools? Two mechanisms have been suggested and implemented around the world: deferred acceptance (DA) and top trading cycles (TTC). These two mechanisms are widely considered excellent choices owing to their outstanding stability and incentive properties. We show theoretically and empirically that both mechanisms perform poorly with regard to two key desiderata such as efficiency and equality, even in large markets. In contrast, the rank-minimizing mechanism is significantly more efficient and egalitarian. It is also Pareto optimal for the students, unlike DA, and generates less justified envy than TTC. |
| Date: | 2022–04 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2204.07255&r= |
| By: | Mill\'an Guerra Beatriz Alejandra |
| Abstract: | For a many-to-one matching model, we study the matchings obtained through the restabilization of stable matchings that had been disrupted by a change in the population. We include a simple representation of the stable matching obtained in terms of the initial stable matching (i.e., before being disrupted by changes in the population) and the firm-optimal stable matching. (We used Lattice Theory to characterize the outcome of the restabilization process.) We also describe the connection between the original stable matching and the one obtained after the restabilization process in the new market. |
| Date: | 2022–02 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2202.12452&r= |
| By: | Gregory Gutin; Philip R. Neary; Anders Yeo |
| Abstract: | In this paper we consider stable matchings that are subject to assignment constraints. These are matchings that require certain assigned pairs to be included, insist that some other assigned pairs are not, and, importantly, are stable. Our main contribution is an algorithm that determines when assignment constraints are compatible with stability. Whenever a stable matching consistent with the assignment constraints exists, our algorithm will output all of them (in polynomial time per solution). This provides market designers with (i) a tool to test the feasibility of stable matchings with assignment constraints, and (ii) a separate tool to implement them. |
| Date: | 2022–04 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2204.03989&r= |
| By: | Gerard Domènech Gironell (Universitat de Barcelona); Marina Núñez Oliva (Universitat de Barcelona) |
| Abstract: | In the multiple-partners job market, introduced in (Sotomayor, 1992), each firm can hire several workers and each worker can be hired by several firms, up to a given quota. We show that, in contrast to what happens in the simple assignment game, in this extension, the firms-optimal stable rules are neither valuation monotonic nor pairwise monotonic. However, we show that the firms-optimal stable rules satisfy a weaker property, what we call firmcovariance, and that this property characterizes these rules among all stable rules. This property allows us to shed some light on how firms can (and cannot) manipulate the firms-optimal stable rules. In particular, we show that firms cannot manipulate them by constantly over-reporting their valuations. Analogous results hold when focusing on the workers. Finally, we extend to the multiple-partners market a known characterization of the fair-division rules on the domain of simple assignment games. |
| Keywords: | Assignment game, stable rules, fair division. |
| JEL: | C78 D78 |
| Date: | 2022 |
| URL: | http://d.repec.org/n?u=RePEc:ewp:wpaper:419web&r= |
| By: | Uriel Feige; Yehonatan Tahan |
| Abstract: | We consider item allocation to individual agents who have additive valuations, in settings in which there are protected groups, and the allocation needs to give each protected group its "fair" share of the total welfare. Informally, within each protected group we consider the total welfare that the allocation gives the members of the group, and compare it to the maximum possible welfare that an allocation can give to the group members. An allocation is fair towards the group if the ratio between these two values is no worse then the relative size of the group. For divisible items, our formal definition of fairness is based on the proportional share, whereas for indivisible items, it is based on the anyprice share. We present examples in which there are no fair allocations, and even not allocations that approximate the fairness requirement within a constant multiplicative factor. We then attempt to identify sufficient conditions for fair or approximately fair allocations to exist. For example, for indivisible items, when agents have identical valuations and the family of protected groups is laminar, we show that if the items are chores, then an allocation that satisfies every fairness requirement within a multiplicative factor no worse than two exists and can be found efficiently, whereas if the items are goods, no constant approximation can be guaranteed. |
| Date: | 2022–04 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2204.06820&r= |
| By: | Hiroki Shinozaki; Tomoya Kazumura; Shigehiro Serizawa |
| Abstract: | We consider the problem of allocating multiple units of an object and collecting payments. Each agent can receive multiple units, and his (consumption) bundle is a pair consisting of the units he receives and his payment. An agent’s preference over bundles may not be quasi-linear. A class of preferences is rich if it includes all quasi-linear preferences with constant incremental valuations. We show that for an odd number of units, if a class of preferences is rich and includes at least one preference exhibiting both decreasing incremental valuations and either positive or negative income effects, then no rule satisfies efficiency, individual rationality, no subsidy for losers, and strategy-proofness. In contrast, for an even number of units, the existence of a rule satisfying the four properties depends on the size of the income effects. We further show that if a rich class of preferences includes only preferences that exhibit nondecreasing incremental valuations, then the generalized Vickrey rule (Saitoh and Serizawa, 2008; Sakai, 2008) is the only rule satisfying the four properties. Our results suggest that (i) there a rule satisfying the four properties “almost” only when preferences exhibit nondecreasing incremental valuations, and (ii) it depends not only on the properties of preferences such as nondecreasing incremental valuations, but also on other characteristics of the environment such as the number of units. |
| Date: | 2020–08 |
| URL: | http://d.repec.org/n?u=RePEc:dpr:wpaper:1097r&r= |
| By: | Vladimir I. Danilov; Alexander V. Karzanov |
| Abstract: | We consider a hypergraph (I,C), with possible multiple (hyper)edges and loops, in which the vertices $i\in I$ are interpreted as agents, and the edges $c\in C$ as contracts that can be concluded between agents. The preferences of each agent i concerning the contracts where i takes part are given by use of a choice function $f_i$ possessing the so-called path independent property. In this general setup we introduce the notion of stable network of contracts. The paper contains two main results. The first one is that a general problem on stable systems of contracts for (I,C,f) is reduced to a set of special ones in which preferences of agents are described by use of so-called weak orders, or utility functions. However, for a special case of this sort, the stability may not exist. Trying to overcome this trouble when dealing with such special cases, we introduce a weaker notion of metastability for systems of contracts. Our second result is that a metastable system always exists. |
| Date: | 2022–02 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2202.13089&r= |
| By: | Sahm, Marco |
| Abstract: | I characterize the optimal accuracy level r of an unbiased Tullock contest between two players with heterogeneous prize valuations. The designer maximizes the winning probability of the strong player or the winner's expected valuation by choosing a contest with an all-pay auction equilibrium (r ≥ 2). By contrast, if she aims at maximizing the expected aggregate effort or the winner's expected effort, she will choose a contest with a pure-strategy equilibrium, and the optimal accuracy level r |
| Keywords: | Tullock Contest,Heterogeneous Valuations,Accuracy,Discrimination,Optimal Design,All-Pay Auction |
| JEL: | C72 D72 |
| Date: | 2022 |
| URL: | http://d.repec.org/n?u=RePEc:zbw:bamber:175&r= |
| By: | Sylvain Béal (CRESE EA3190, Univ. Bourgogne Franche-Comté, F-25000 Besançon, France); Sylvain Ferrières (Université de Saint-Etienne, CNRS UMR 5824 GATE Lyon Saint-Etienne, France); Adriana Navarro-Ramos (Université de Saint-Etienne, CNRS UMR 5824 GATE Lyon Saint-Etienne, France); Philippe Solal (Université de Saint-Etienne, CNRS UMR 5824 GATE Lyon Saint-Etienne, France) |
| Abstract: | We introduce a new family of values for TU-games with a priority structure. This family both contains the Priority value recently introduced by Béal et al. (2021) and the Weighted Shapley values (Kalai and Samet, 1987). Each value of this family is called a Weighted priority value and is constructed as follows. A strictly positive weight is associated with each agent and the agents are partially ordered according to a binary relation. An agent is a priority agent with respect to a coalition if it is maximal in this coalition with respect to the partial order. A Weighted priority value distributes the dividend of each coalition among the priority agents of this coalition in proportion to their weights. We provide an axiomatic characterization of the family of the Weighted Shapley values without the additivity axiom. To this end, we borrow the Priority agent out axiom from Béal et al. (2021), which is used to axiomatize the Priority value. We also reuse, in our domain, the principle of Super weak differential marginality introduced by Casajus (2018) to axiomatize the Positively weighted Shapley values (Shapley, 1953a). We add a new axiom of Independence of null agent position which indicates that the position of a null agent in the partial order does not affect the payoff of the other agents. Together with Efficiency, the above axioms characterize the Weighted Shapley values. Finally, we show that this axiomatic characterization holds on the subdomain where the partial order is structured by levels. This entails an alternative characterization of the Weighted Shapley values. |
| Keywords: | Differential marginality, Priority value, Shapley value, Superweak differiential marginality, Weighted Shapley value |
| JEL: | C71 |
| Date: | 2022–05 |
| URL: | http://d.repec.org/n?u=RePEc:crb:wpaper:2022-03&r= |
| By: | Felix Brandt; Chris Dong |
| Abstract: | We introduce a new notion of rationalizability where the rationalizing relation may depend on the set of feasible alternatives. More precisely, we say that a choice function is locally rationalizable if it is rationalized by a family of rationalizing relations such that a strict preference between two alternatives in some feasible set is preserved when removing other alternatives. We then show that a choice function is locally rationalizable if and only if it satisfies Sen's $\gamma$ and give similar characterizations for local rationalizability via transitive, PIP-transitive, and quasi-transitive relations. Local rationalizability is realized via families of revealed preference relations that are sandwiched in between the base relation and the revealed preference relation of a choice function. We demonstrate the adequacy of our results for analyzing and constructing consistent social choice functions by giving simple characterizations of the top cycle and the uncovered set using transitive and quasi-transitive local rationalizability. |
| Date: | 2022–04 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2204.05062&r= |
| By: | Warut Suksompong; Nicholas Teh |
| Abstract: | We consider the problem of fairly allocating indivisible goods to agents with weights representing their entitlements. A natural rule in this setting is the maximum weighted Nash welfare (MWNW) rule, which selects an allocation maximizing the weighted product of the agents' utilities. We show that when agents have binary valuations, a specific version of MWNW is resource- and population-monotone, satisfies group-strategyproofness, and can be implemented in polynomial time. |
| Date: | 2022–04 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2204.03803&r= |
| By: | Yann Bramoullé (AMSE - Aix-Marseille Sciences Economiques - EHESS - École des hautes études en sciences sociales - AMU - Aix Marseille Université - ECM - École Centrale de Marseille - CNRS - Centre National de la Recherche Scientifique); Brian Rogers (WUSTL - Washington University in Saint Louis); Erdem Yenerdag (WUSTL - Washington University in Saint Louis) |
| Abstract: | We study a two-period one-to-one dynamic matching environment in which agents meet randomly and decide whether to match early or defer. Crucially, agents can match with either partner in the second period. This "recall" captures situations where, e.g., a firm and worker can conduct additional interviews before contracting. Recall has a profound impact on incentives and on aggregate outcomes. We show that the likelihood to match early is nonmonotonic in type: early matches occur between the good-but-not-best agents. The option value provided by the first-period partner provides a force against unraveling, so that deferrals occur under small participation costs. |
| Keywords: | recall,unraveling,dynamic matching |
| Date: | 2022–02–14 |
| URL: | http://d.repec.org/n?u=RePEc:hal:wpaper:halshs-03602169&r= |
| By: | Bo Li; Lijun Li; Ankang Sun; Chenhao Wang; Yingfan Wang |
| Abstract: | We incorporate group fairness into the algorithmic centroid clustering problem, where $k$ centers are to be located to serve $n$ agents distributed in a metric space. We refine the notion of proportional fairness proposed in [Chen et al., ICML 2019] as {\em core fairness}, and $k$-clustering is in the core if no coalition containing at least $n/k$ agents can strictly decrease their total distance by deviating to a new center together. Our solution concept is motivated by the situation where agents are able to coordinate and utilities are transferable. A string of existence, hardness and approximability results is provided. Particularly, we propose two dimensions to relax core requirements: one is on the degree of distance improvement, and the other is on the size of deviating coalition. For both relaxations and their combination, we study the extent to which relaxed core fairness can be satisfied in metric spaces including line, tree and general metric space, and design approximation algorithms accordingly. |
| Date: | 2022–03 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2203.17146&r= |
| By: | Yusuke Kamishiro; Rajiv Vohra; Roberto Serrano |
| Abstract: | This paper provides a noncooperative approach to core stability in an economy with incomplete information. The analysis covers general exchange economies, although our tightest results hold when effective coalitions consist of at most two players, as in matching. We study the perfect Bayesian equilibria of an extensive form mechanism that extends the one used by Serrano and Vohra (1997) to implement the core of a complete information economy. This leads to a version of the core that we refer to as the sequential core, which allows for information to be transmitted among the agents during the process of coalition formation. Such information flows include proposals that can be viewed as signaling devices and/or screening contracts. The same result is obtained in a model of infinite-horizon coalitional bargaining for stationary PBE. Equilibrium refinements are then used to provide justifications for the coarse core and the fine core. |
| Date: | 2022 |
| URL: | http://d.repec.org/n?u=RePEc:bro:econwp:2022-001&r= |
| By: | Smolin, Alex; Ichihashi, Shota |
| Abstract: | A seller faces a consumer with an uncertain value for the product. The seller has imperfect private information about the value and requests additional data to set the price. The consumer can decline any request. The consumer’s willingness to provide data depends on his belief about the seller’s type which in turn depends on the request. We show that the type uncertainty limits the scope of data collection: All equilibrium payoffs are spanned by fully pooling equilibria in which the seller collects the same data regardless of the type. The seller’s private information lowers efficiency and profits, but benefits the consumer by fueling his skepticism and preventing excessive data collection. Having less private information may enable the seller to collect more data directly from the consumer and may lower the overall consumer welfare. |
| Keywords: | consumer privacy; data collection; information design; mechanism design; price discrimination |
| JEL: | D42 D82 D83 |
| Date: | 2022–04–19 |
| URL: | http://d.repec.org/n?u=RePEc:tse:wpaper:126871&r= |