|
on Economic Design |
| By: | Ran Canetti; Amos Fiat; Yannai A. Gonczarowski |
| Abstract: | A powerful feature in mechanism design is the ability to irrevocably commit to the rules of a mechanism. Commitment is achieved by public declaration, which enables players to verify incentive properties in advance and the outcome in retrospect. However, public declaration can reveal superfluous information that the mechanism designer might prefer not to disclose, such as her target function or private costs. Avoiding this may be possible via a trusted mediator; however, the availability of a trusted mediator, especially if mechanism secrecy must be maintained for years, might be unrealistic. We propose a new approach to commitment, and show how to commit to, and run, any given mechanism without disclosing it, while enabling the verification of incentive properties and the outcome -- all without the need for any mediators. Our framework is based on zero-knowledge proofs -- a cornerstone of modern cryptographic theory. Applications include non-mediated bargaining with hidden yet binding offers. |
| Date: | 2023–02 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2302.05590&r=des |
| By: | Yinghua He (TSE-R - Toulouse School of Economics - UT1 - Université Toulouse 1 Capitole - Université Fédérale Toulouse Midi-Pyrénées - EHESS - École des hautes études en sciences sociales - CNRS - Centre National de la Recherche Scientifique - INRAE - Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement); Thierry Magnac (TSE-R - Toulouse School of Economics - UT1 - Université Toulouse 1 Capitole - Université Fédérale Toulouse Midi-Pyrénées - EHESS - École des hautes études en sciences sociales - CNRS - Centre National de la Recherche Scientifique - INRAE - Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement) |
| Abstract: | A matching market often requires recruiting agents, or ‘programmes', to costly screen ‘applicants', and congestion increases with the number of applicants to be screened. We investigate the role of application costs : higher costs reduce congestion by discouraging applicants from applying to certain programmes; however, they may harm match quality. In a multiple-elicitation experiment conducted in a real-life matching market, we implement variants of the Gale-Shapley deferred-acceptance mechanism with different application costs. Our experimental and structural estimates show that a (low) application cost effectively reduces congestion without harming match quality. |
| Keywords: | Gale-Shapley Deferred Acceptance Mechanism, Costly Preference Formation, Screening, Stable Matching, Congestion, Matching Market Design |
| Date: | 2022 |
| URL: | http://d.repec.org/n?u=RePEc:hal:journl:hal-03979233&r=des |
| By: | Kirneva Margarita; N\'u\~nez Mat\'ias |
| Abstract: | We design a mechanism, Majority voting with random checks, that fully implements the majority rule for binary social decisions. After a simultaneous vote over the two options, the winner must be confirmed by at least one agent from a random sample of agents voting sequentially. The mechanism incentivizes agents to act truthfully as a lottery is held if no agent confirms the outcome. Our mechanism also reduces by almost half the number of stages required for implementation. Furthermore, we extend our results to incomplete information and abstention and introduce additional implementation mechanisms based on the concept of network formation |
| Date: | 2023–02 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2302.09548&r=des |
| By: | Agustín G. Bonifacio; R. Pablo Arribillaga; Marcelo Fernández |
| Abstract: | We study the ability of different classes of voting rules to induce agents to report their preferences truthfully, if agents want to avoid regret. First, we show that regret-free truth-telling is equivalent to strategy-proofness among tops-only rules. Then, we focus on three important families of (non-tops-only) voting methods: maxmin, scoring, and Condorcet consistent ones. We prove positive and negative results for both neutral and anonymous versions of maxmin and scoring rules. In several instances we provide necessary and sufficient conditions. We also show that Condorcet consistent rules that satisfy a mild monotonicity requirement are not regret-free truth-telling. Successive elimination rules fail to be regret-free truth-telling despite not satisfying the monotonicity condition. Lastly, we provide two characterizations for the case of three alternatives and two agents. |
| JEL: | D7 |
| Date: | 2022–11 |
| URL: | http://d.repec.org/n?u=RePEc:aep:anales:4543&r=des |
| By: | Yingkai Li; Xiaoyun Qiu |
| Abstract: | We study the distribution of multiple homogeneous items to multiple agents with unit demand. Monetary transfer is not allowed and the allocation of the items can only depend on the informative signals that are manipulable by costly and wasteful efforts. Examples of such scenarios include grant allocation, college admission, lobbying and affordable housing. We show that the welfare-maximizing mechanism takes the form of a contest and characterize it. We apply our characterizations to study large contests. When the number of agents is large compared to item(s), the format of the optimal contest converges to winner-takes-all, but principal's payoff does not. When both the number of items and agents are large, allocation is randomized to middle types to induce no effort under optimal contest, which weakly decreases effort for all higher types. |
| Date: | 2023–02 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2302.09168&r=des |
| By: | Jorge Alcalde-Unzu; Oihane Gallo; Elena Inarra; Juan D. Moreno-Ternero |
| Abstract: | Agents may form coalitions. Each coalition shares its endowment among its agents by applying a sharing rule. The sharing rule induces a coalition formation problem by assuming that agents rank coalitions according to the allocation they obtain in the corresponding sharing problem. We characterize the sharing rules that induce a class of stable coalition formation problems as those that satisfy a natural axiom that formalizes the principle of solidarity. Thus, solidarity becomes a sufficient condition to achieve stability. |
| Date: | 2023–02 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2302.07618&r=des |
| By: | Pablo Arribillaga; Agustín Bonifacio |
| Abstract: | In a classical voting problem with a finite set of (at least three) alternatives to choose from, we study the manipulation of tops-only and unanimous rules. Since strategy-proofness is impossible to obtain on the universal domain of (strict) preferences, we investigate the weaker concept of non-obvious manipulability (NOM). First, we show that NOM is equivalent to every veto from any agent being a strong veto. Second, we focus on two classes of tops-only rules: (i) (generalized) median voter schemes, and (ii) voting by committees. For each class, we identify which rules satisfy NOM on the universal domain of preferences. |
| JEL: | D71 |
| Date: | 2022–11 |
| URL: | http://d.repec.org/n?u=RePEc:aep:anales:4536&r=des |
| By: | Chris Dong; Patrick Lederer |
| Abstract: | Approval-based committee (ABC) voting rules elect a fixed size subset of the candidates, a so-called committee, based on the voters' approval ballots over the candidates. While these rules have recently attracted significant attention, axiomatic characterizations are largely missing so far. We address this problem by characterizing ABC voting rules within the broad and intuitive class of sequential valuation rules. These rules compute the winning committees by sequentially adding candidates that increase the score of the chosen committee the most. In more detail, we first characterize almost the full class of sequential valuation rules based on mild standard conditions and a new axiom called consistent committee monotonicity. This axiom postulates that the winning committees of size k can be derived from those of size k-1 by only adding candidates and that these new candidates are chosen consistently. By requiring additional conditions, we derive from this result also a characterization of the prominent class of sequential Thiele rules. Finally, we refine our results to characterize three well-known ABC voting rules, namely sequential approval voting, sequential proportional approval voting, and sequential Chamberlin-Courant approval voting. |
| Date: | 2023–02 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2302.11890&r=des |
| By: | Haris Aziz; Xinhang Lu; Mashbat Suzuki; Jeremy Vollen; Toby Walsh |
| Abstract: | The paradigm of best-of-both-worlds advocates an approach that achieves desirable properties both ex-ante and ex-post. We initiate a best-of-both-worlds fairness perspective for the important social choice setting of approval-based committee voting. To this end, we formalize a hierarchy of ex-ante properties including Individual Fair Share (IFS) and its strengthening Group Fair Share (GFS). We establish their relations with well-studied ex-post concepts such as extended justified representation (EJR) and proportional justified representation (PJR). Our central result is a polynomial-time algorithm that simultaneously satisfies ex-post EJR and ex-ante GFS. Our algorithm uses as a subroutine the first phase of the well-known Method of Equal Shares class of rules. |
| Date: | 2023–03 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2303.03642&r=des |
| By: | Ni Yan; WenTing Tao |
| Abstract: | We study the partial and full set-asides and their implication for changes in bidding behavior in first-price sealed-bid auctions in the context of United States Department of Agriculture (USDA) food procurement auctions. Using five years of bid data on different beef products, we implement weighted least squares regression models to show that partial set-aside predicts decreases in both offer prices and winning prices among large and small business bidders. Full set-aside predicts a small increase in offer prices and winning prices among small businesses. With these predictions, we infer that net profit of small businesses is unlikely to increase when set-asides are present. |
| Date: | 2023–02 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2302.05772&r=des |
| By: | Vijay V. Vazirani |
| Abstract: | LP-duality theory has played a central role in the study of the core, right from its early days to the present time. The 1971 paper of Shapley and Shubik, which gave a characterization of the core of the assignment game, has been a paradigm-setting work in this regard. However, despite extensive follow-up work, basic gaps still remain. We address these gaps using the following building blocks from LP-duality theory: 1). Total unimodularity (TUM). 2). Complementary slackness conditions and strict complementarity. TUM plays a vital role in the Shapley-Shubik theorem. We define several generalizations of the assignment game whose LP-formulations admit TUM; using the latter, we characterize their cores. The Hoffman-Kruskal game is the most general of these. Its applications include matching students to schools and medical residents to hospitals, and its core imputations provide a way of enforcing constraints arising naturally in these applications: encouraging diversity and discouraging over-representation. Complementarity enables us to prove new properties of core imputations of the assignment game and its generalizations. |
| Date: | 2023–02 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2302.07627&r=des |