|
on Economic Design |
|
Issue of 2022‒12‒05
sixteen papers chosen by Guillaume Haeringer, Baruch College and Alex Teytelboym, University of Oxford |
| By: | Jorge Arenas; Juan Pablo Torres-Martinez |
| Abstract: | We study incentives in a class of three-sided matching problems in which the set of stable outcomes is non-empty 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 strategy-proof for agents in U and V, no stable mechanism is strategy-proof for agents in W. This impossibility is related to the incompatibility between stability, one-sided strategy-proofness, and one-sided non-bossiness in two-sided markets. Also, unlike what happens in marriage markets, strong restrictions on preferences are needed to ensure that stability and one-sided strategy-proofness 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 Torres-Martinez |
| Abstract: | In classical school choice contexts there exists a centralized assignment procedure that is stable and strategy-proof: the Gale-Shapley student-optimal 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 strategy-proof mechanism exists. Furthermore, we show that stability and strategy-proofness are compatible if and only if schools' priorities are Ergin-acyclic. This strong effect of weak externalities on incentives is related to the incompatibility between stability, strategy-proofness, and non-bossiness 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 first-price and second-price auctions with independent private values when bidders are expectations-based 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 ``choice-acclimating personal equilibrium", the optimal reserve price is public and differs across the two auction formats. Furthermore, the seller excludes more types compared to the risk-neutral and risk-averse 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 higher-valuation buyer may pay less than a lower-valuation 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 allocation-monotonic 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 Friedrich-Wilhelms-Universitä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 Dauphine-PSL - 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 mechanism-the Nash product rule-which 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:hal-03818329&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 cost-reimbursement contracts, requiring fixed-price 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 Covid-19 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 multi-product 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 Dauphine-PSL - 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 envy-free 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:hal-03834514&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 Dauphine-PSL - 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 envy-free 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 moving-knife protocol and the Su-Simmons argument based on Sperner's lemma. For identical utilities, we provide a polynomial-time 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: | Envy-free Division,Cake-cutting,Resource Allocation |
| Date: | 2021–11–26 |
| URL: | http://d.repec.org/n?u=RePEc:hal:journl:hal-03834506&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 Dauphine-PSL - 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 worst-case 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 unit-sum 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 multi-winner elections, we propose the first voting rule which achieves the optimal distortion Θ(√ m) for unit-sum utilities. Our voting rule also achieves optimum Θ(√ m) distortion for a larger class of utilities, including unit-range and approval (0/1) utilities. We then take a similar worst-case 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:hal-03834512&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 truth-telling 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 Dauphine-PSL - PSL - Université Paris sciences et lettres - CNRS - Centre National de la Recherche Scientifique); Ulrike Schmidt-Kraepelin (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 approval-based apportionment setting generalizes traditional apportionment and is a natural restriction of approval-based 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 core-stable 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:hal-03816043&r=des |
| By: | Dominik Peters (LAMSADE - Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision - Université Paris Dauphine-PSL - 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 single-peaked 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 single-peaked on a tree. We study the complexity of multiwinner elections under several variants of the Chamberlin-Courant rule for preferences single-peaked on trees. We show that in this setting the egalitarian version of this rule admits a polynomial-time winner determination algorithm. For the utilitarian version, we prove that winner determination remains NP-hard 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 single-peaked 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 single-peaked. 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 single-peaked. We then explore the power and limitations of this framework: we develop polynomial-time algorithms to find trees with the smallest maximum degree, diameter, or pathwidth, but show that it is NP-hard to check whether a given profile is single-peaked 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:hal-03834509&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, quasi-choices (choice correspondences that may be empty on some menus). The justification is here provided by a proportion of ballots, which are quasi-choices rationalizable by an arbitrary binary relation. We call a quasi-choice $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 well-known behavioral property, namely Chernoff axiom. Then we focus on two paradigms of majoritarianism, whereby either a simple majority of ballots justifies a quasi-choice, 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 Bondareva-Shapley Theorem for infinite TU-games with and without restricted cooperation, to the cases where the core consists of $\kappa$-additive set functions. Our generalized Bondareva-Shapley 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 PMAS-admissible 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 PMAS-admissible 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 PMAS-admissible assignment game all core allocations can be extended to a PMAS, and the nucleolus coincides with the tau-value. |
| Date: | 2022–10 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2210.17373&r=des |