
on Economic Design 
By:  Jorge Arenas; Juan Pablo TorresMartinez 
Abstract:  We study incentives in a class of threesided matching problems in which the set of stable outcomes is nonempty and coincides with the core. If U, V, and W denote the sides of the market, it is assumed that agents in U have preferences defined on V, agents in V have preferences defined on W, and agents in W have lexicographic preferences defined on VxU. Although in this context there exists a stable mechanism that is strategyproof for agents in U and V, no stable mechanism is strategyproof for agents in W. This impossibility is related to the incompatibility between stability, onesided strategyproofness, and onesided nonbossiness in twosided markets. Also, unlike what happens in marriage markets, strong restrictions on preferences are needed to ensure that stability and onesided strategyproofness are compatible for every market side. 
Date:  2022–11 
URL:  http://d.repec.org/n?u=RePEc:udc:wpaper:wp538&r=des 
By:  Eduardo Duque; Juan Pablo TorresMartinez 
Abstract:  In classical school choice contexts there exists a centralized assignment procedure that is stable and strategyproof: the GaleShapley studentoptimal stable mechanism. We show that this property is not satisfied when externalities are incorporated into the model, even in scenarios in which students are primarily concerned about their own placement (weak externalities). Indeed, although weak externalities have no effects on stability, there are school choice contexts in which no stable and strategyproof mechanism exists. Furthermore, we show that stability and strategyproofness are compatible if and only if schools' priorities are Erginacyclic. This strong effect of weak externalities on incentives is related to the incompatibility between stability, strategyproofness, and nonbossiness in classical school choice problems. 
Date:  2022–11 
URL:  http://d.repec.org/n?u=RePEc:udc:wpaper:wp542&r=des 
By:  Benjamin Balzer; Antonio Rosato 
Abstract:  We characterize optimal reserve prices in firstprice and secondprice auctions with independent private values when bidders are expectationsbased loss averse. Under ``unacclimating personal equilibrium", the optimal public reserve price can be lower than under risk neutrality or risk aversion. Moreover, secret and random reserve prices raise more revenue than public ones since, by giving every bidder a chance to win, they expose all bidders to the ``attachment effect". In contrast, under ``choiceacclimating personal equilibrium", the optimal reserve price is public and differs across the two auction formats. Furthermore, the seller excludes more types compared to the riskneutral and riskaverse benchmarks. 
Date:  2022–10 
URL:  http://d.repec.org/n?u=RePEc:arx:papers:2210.10938&r=des 
By:  Ran Ben Moshe; Sergiu Hart; Noam Nisan 
Abstract:  Maximizing the revenue from selling two or more goods has been shown to require the use of $nonmonotonic$ mechanisms, where a highervaluation buyer may pay less than a lowervaluation one. Here we show that the restriction to $monotonic$ mechanisms may not just lower the revenue, but may in fact yield only a $negligible$ $fraction$ of the maximal revenue; more precisely, the revenue from monotonic mechanisms is no more than k times the simple revenue obtainable by selling the goods separately, or bundled (where k is the number of goods), whereas the maximal revenue may be arbitrarily larger. We then study the class of monotonic mechanisms and its subclass of allocationmonotonic mechanisms, and obtain useful characterizations and revenue bounds. 
Date:  2022–10 
URL:  http://d.repec.org/n?u=RePEc:arx:papers:2210.17150&r=des 
By:  Florian Brandl (HCM  Hausdorff Center for Mathematics  Rheinische FriedrichWilhelmsUniversität Bonn); Felix Brandt (TUM  Technische Universität Munchen  Université Technique de Munich [Munich, Allemagne]); Matthias Greger (TUM  Technische Universität Munchen  Université Technique de Munich [Munich, Allemagne]); Dominik Peters (LAMSADE  Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision  Université Paris DauphinePSL  PSL  Université Paris sciences et lettres  CNRS  Centre National de la Recherche Scientifique); Christian Stricker (TUM  Technische Universität Munchen  Université Technique de Munich [Munich, Allemagne]); Warut Suksompong (NUS  National University of Singapore) 
Abstract:  We study a mechanism design problem where a community of agents wishes to fund public projects via voluntary monetary contributions by the community members. This serves as a model for public expenditure without an exogenously available budget, such as participatory budgeting or voluntary tax programs, as well as donor coordination when interpreting charities as public projects and donations as contributions. Our aim is to identify a mutually beneficial distribution of the individual contributions. In the preference aggregation problem that we study, agents with linear utility functions over projects report the amount of their contribution, and the mechanism determines a socially optimal distribution of the money. We identify a specific mechanismthe Nash product rulewhich picks the distribution that maximizes the product of the agents' utilities. This rule is Pareto efficient and incentivizes agents to contribute their entire budget while spending each agent's contribution only on projects the agent finds acceptable. 
Date:  2022 
URL:  http://d.repec.org/n?u=RePEc:hal:journl:hal03818329&r=des 
By:  Christopher M. Snyder; Kendall Hoyt; Dimitrios Gouglas 
Abstract:  We derive the optimal funding mechanism to incentivize development and production of vaccines against diseases with epidemic potential. In the model, suppliers' costs are private information and investments are noncontractible, precluding costreimbursement contracts, requiring fixedprice contracts conditioned on delivery of a successful product. The high failure risk for individual vaccines calls for incentivizing multiple entrants, accomplished by the optimal mechanism, a (w+1)price reverse Vickrey auction with reserve. Our analysis determines the optimal number of entrants and required funding level. Based on a distribution of supplier costs estimated from survey data, we simulate the optimal mechanism's performance in scenarios ranging from a small outbreak, causing harm in the millions of dollars, to the Covid19 pandemic, causing harm in the trillions. We assess which mechanism features contribute most to its optimality. 
JEL:  D47 H44 I18 L65 O31 
Date:  2022–11 
URL:  http://d.repec.org/n?u=RePEc:nbr:nberwo:30619&r=des 
By:  Strausz, Roland (HU Berlin) 
Abstract:  A multiproduct monopolist sells sequentially to a buyer who privately learns his valuations. Using big data, the monopolist learns the intertemporal correlation of the buyer’s valuations. Perfect price discrimination is generally unattainable—even when the seller learns the correlation perfectly, has full commitment, and in the limit where the consumption good about which the buyer has ex ante private information becomes insignificant. This impossibility is due to informational externalities which re quires information rents for the buyer’s later consumption. These rents induce upward and downward distortions, violating the generalized no distortion at the top principle of dynamic mechanism design. 
JEL:  D82 L52 
Date:  2022–11–10 
URL:  http://d.repec.org/n?u=RePEc:rco:dpaper:347&r=des 
By:  Soroush Ebadian (DCS  Department of Computer Science [University of Toronto]  University of Toronto); Dominik Peters (LAMSADE  Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision  Université Paris DauphinePSL  PSL  Université Paris sciences et lettres  CNRS  Centre National de la Recherche Scientifique); Nisarg Shah (DCS  Department of Computer Science [University of Toronto]  University of Toronto) 
Abstract:  A major open question in fair allocation of indivisible items is whether there always exists an allocation of chores that is Pareto optimal (PO) and envyfree up to one item (EF1). We answer this question affirmatively for the natural class of bivalued utilities, where each agent partitions the chores into easy and difficult ones, and has cost > 1 for chores that are difficult for her and cost 1 for chores that are easy for her. Such an allocation can be found in polynomial time using an algorithm based on the Fisher market. We also show that for a slightly broader class of utilities, where each agent can have a potentially different integer , an allocation that is maximin share fair (MMS) always exists and can be computed in polynomial time, provided that each is an integer. Our MMS arguments also hold when allocating goods instead of chores, and extend to another natural class of utilities, namely weakly lexicographic utilities. 
Date:  2022–05 
URL:  http://d.repec.org/n?u=RePEc:hal:journl:hal03834514&r=des 
By:  Vittorio Bilò (University of Salento [Lecce]); Ioannis Caragiannis (CTI  Computer Technology Institute  Computer Technology Institute); Michele Flammini (GSSI  Gran Sasso Science Institute  INFN  Istituto Nazionale di Fisica Nucleare); Ayumi Igarashi (NII  National Institute of Informatics); Gianpiero Monaco (DI  Dipartimento di Informatica [Italy]  UNIVAQ  Università degli Studi dell'Aquila); Dominik Peters (LAMSADE  Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision  Université Paris DauphinePSL  PSL  Université Paris sciences et lettres  CNRS  Centre National de la Recherche Scientifique); Cosimo Vinci (UNISA  University of Salerno); William Zwicker (Union College) 
Abstract:  We study the existence of allocations of indivisible goods that are envyfree up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph. If the graph is a path and the utility functions are monotonic over bundles, we show the existence of EF1 allocations for at most four agents, and the existence of EF2 allocations for any number of agents; our proofs involve discrete analogues of the Stromquist's movingknife protocol and the SuSimmons argument based on Sperner's lemma. For identical utilities, we provide a polynomialtime algorithm that computes an EF1 allocation for any number of agents. For the case of two agents, we characterize the class of graphs that guarantee the existence of EF1 allocations as those whose biconnected components are arranged in a path; this property can be checked in linear time. 
Keywords:  Envyfree Division,Cakecutting,Resource Allocation 
Date:  2021–11–26 
URL:  http://d.repec.org/n?u=RePEc:hal:journl:hal03834506&r=des 
By:  Soroush Ebadian (DCS  Department of Computer Science [University of Toronto]  University of Toronto); Anson Kahng (Department of Computer Science [Rochester]  University of Rochester [USA]); Dominik Peters (LAMSADE  Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision  Université Paris DauphinePSL  PSL  Université Paris sciences et lettres  CNRS  Centre National de la Recherche Scientifique); Nisarg Shah (DCS  Department of Computer Science [University of Toronto]  University of Toronto) 
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 social welfare produced by 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 previous literature has studied distortion with unitsum utility functions (which are normalized to sum to 1), 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 Θ(√ m) for unitsum utilities. Our voting rule also achieves optimum Θ(√ m) distortion for a larger class of utilities, including unitrange and approval (0/1) 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, which is 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 the Nash welfare, and selects a distribution that is approximately stable by being an O(log m)approximation to the core, making it interesting for applications in participatory budgeting. 
Date:  2022–07 
URL:  http://d.repec.org/n?u=RePEc:hal:journl:hal03834512&r=des 
By:  Krähmer, Daniel (University of Bonn); Strausz, Roland (HU Berlin) 
Abstract:  We consider a dynamic screening model where the agent may go bankrupt due to, for example, cash constraints. We model bankruptcy as a verifiable event that occurs whenever the agent makes a per period loss. This leads to less stringent truthtelling constraints than those considered in the existing literature. We show that the weaker constraints do not af fect optimal contracting in private values settings but may do so with interdependent values. Moreover, we develop a novel method to study private values settings with continuous types and identify a new regularity condition that ensures that the optimal contract is deterministic. 
Keywords:  dynamic screening; bankruptcy; verifiability; mean preserving spread; 
JEL:  D82 H57 
Date:  2022–11–10 
URL:  http://d.repec.org/n?u=RePEc:rco:dpaper:348&r=des 
By:  Markus Brill (TU  Technische Universität Berlin); Paul Gölz (CMU  Carnegie Mellon University [Pittsburgh]); Dominik Peters (LAMSADE  Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision  Université Paris DauphinePSL  PSL  Université Paris sciences et lettres  CNRS  Centre National de la Recherche Scientifique); Ulrike SchmidtKraepelin (TU  Technische Universität Berlin); Kai Wilker (TU  Technische Universität Berlin) 
Abstract:  In the apportionment problem, a fixed number of seats must be distributed among parties in proportion to the number of voters supporting each party. We study a generalization of this setting, in which voters can support multiple parties by casting approval ballots. This approvalbased apportionment setting generalizes traditional apportionment and is a natural restriction of approvalbased multiwinner elections, where approval ballots range over individual candidates instead of parties. Using techniques from both apportionment and multiwinner elections, we identify rules that generalize the D'Hondt apportionment method and that satisfy strong axioms which are generalizations of properties commonly studied in the apportionment literature. In fact, the rules we discuss provide representation guarantees that are currently out of reach in the general setting of multiwinner elections: First, we show that corestable committees are guaranteed to exist and can be found in polynomial time. Second, we demonstrate that extended justified representation is compatible with committee monotonicity (also known as house monotonicity). 
Date:  2022 
URL:  http://d.repec.org/n?u=RePEc:hal:journl:hal03816043&r=des 
By:  Dominik Peters (LAMSADE  Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision  Université Paris DauphinePSL  PSL  Université Paris sciences et lettres  CNRS  Centre National de la Recherche Scientifique); Lan Yu; Hau Chan (University of Nebraska–Lincoln  University of Nebraska System); Edith Elkind (University of Oxford [Oxford]) 
Abstract:  A preference profile is singlepeaked on a tree if the candidate set can be equipped with a tree structure so that the preferences of each voter are decreasing from their top candidate along all paths in the tree. This notion was introduced by Demange (1982), and subsequently Trick (1989b) described an efficient algorithm for deciding if a given profile is singlepeaked on a tree. We study the complexity of multiwinner elections under several variants of the ChamberlinCourant rule for preferences singlepeaked on trees. We show that in this setting the egalitarian version of this rule admits a polynomialtime winner determination algorithm. For the utilitarian version, we prove that winner determination remains NPhard for the Borda scoring function; indeed, this hardness results extends to a large family of scoring functions. However, a winning committee can be found in polynomial time if either the number of leaves or the number of internal vertices of the underlying tree is bounded by a constant. To benefit from these positive results, we need a procedure that can determine whether a given profile is singlepeaked on a tree that has additional desirable properties (such as, e.g., a small number of leaves). To address this challenge, we develop a structural approach that enables us to compactly represent all trees with respect to which a given profile is singlepeaked. We show how to use this representation to efficiently find the best tree for a given profile for use with our winner determination algorithms: Given a profile, we can efficiently find a tree with the minimum number of leaves, or a tree with the minimum number of internal vertices among trees on which the profile is singlepeaked. We then explore the power and limitations of this framework: we develop polynomialtime algorithms to find trees with the smallest maximum degree, diameter, or pathwidth, but show that it is NPhard to check whether a given profile is singlepeaked on a tree that is isomorphic to a given tree, or on a regular tree. 
Date:  2022–01–12 
URL:  http://d.repec.org/n?u=RePEc:hal:journl:hal03834509&r=des 
By:  Jos\'e Carlos R. Alcantud; Domenico Cantone; Alfio Giarlotta; Stephen Watson 
Abstract:  We describe a model that explains possibly indecisive choice behavior, that is, quasichoices (choice correspondences that may be empty on some menus). The justification is here provided by a proportion of ballots, which are quasichoices rationalizable by an arbitrary binary relation. We call a quasichoice $s$majoritarian if all options selected from a menu are endorsed by a share of ballots larger than $s$. We prove that all forms of majoritarianism are equivalent to a wellknown behavioral property, namely Chernoff axiom. Then we focus on two paradigms of majoritarianism, whereby either a simple majority of ballots justifies a quasichoice, or the endorsement by a single ballot suffices  a liberal justification. These benchmark explanations typically require a different minimum number of ballots. We determine the asymptotic minimum size of a liberal justification. 
Date:  2022–10 
URL:  http://d.repec.org/n?u=RePEc:arx:papers:2210.16885&r=des 
By:  David Bartl; Mikl\'os Pint\'er 
Abstract:  We consider transferable utility cooperative games with infinitely many players. In particular, we generalize the notions of core and balancedness, and also the BondarevaShapley Theorem for infinite TUgames with and without restricted cooperation, to the cases where the core consists of $\kappa$additive set functions. Our generalized BondarevaShapley Theorem extends previous results by Bondareva (1963), Shapley (1967), Schmeidler (1967), Faigle (1989), Kannai (1969), Kannai (1992), Pinter(2011) and Bartl and Pint\'er (2022). 
Date:  2022–11 
URL:  http://d.repec.org/n?u=RePEc:arx:papers:2211.05843&r=des 
By:  Tam\'as Solymosi 
Abstract:  We characterize the assignment games which admit a population monotonic allocation scheme (PMAS) in terms of efficiently verifiable structural properties of the nonnegative matrix that induces the game. We prove that an assignment game is PMASadmissible if and only if the positive elements of the underlying nonnegative matrix form orthogonal submatrices of three special types. In game theoretic terms it means that an assignment game is PMASadmissible if and only if it contains a veto player or a dominant veto mixed pair or is composed of from these two types of special assignment games. We also show that in a PMASadmissible assignment game all core allocations can be extended to a PMAS, and the nucleolus coincides with the tauvalue. 
Date:  2022–10 
URL:  http://d.repec.org/n?u=RePEc:arx:papers:2210.17373&r=des 