The vigilant eating rule: a general approach for probabilistic economic design with constraints

DOI10.1016/J.GEB.2022.06.002MaRDI QIDQ2675446zbMATH OpenOpenAlexWikidataFDO

Authors Haris Aziz, Florian Brandl

Publication date 23 September 2022

Published in Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.08991

zbMATH Keywords

algorithmsmarket designmatching under constraintsmatching under preferencesprobabilistic matching

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Matching models (91B68)

Abstract: We consider the problem of probabilistic allocation of objects under ordinal preferences. We devise an allocation mechanism, called the vigilant eating rule (VER), that applies to nearly arbitrary feasibility constraints. It is constrained ordinally efficient, can be computed efficiently for a large class of constraints, and treats agents equally if they have the same preferences and are subject to the same constraints. When the set of feasible allocations is convex, we also present a characterization of our rule based on ordinal egalitarianism. Our results about VER do not just apply to allocation problems but to all collective choice problems in which agents have ordinal preferences over discrete outcomes. As a case study, we assume objects have priorities for agents and apply VER to sets of probabilistic allocations that are constrained by stability. VER coincides with the (extended) probabilistic serial rule when priorities are flat and the agent proposing deterministic deferred acceptance algorithm when preferences and priorities are strict. While VER always returns a stable and constrained efficient allocation, it fails to be strategyproof, unconstrained efficient, and envy-free. We show, however, that each of these three properties is incompatible with stability and constrained efficiency.

Recommendations

• The object allocation problem with random priorities
• Efficient rules for probabilistic assignment
• Probabilistic assignment of objects: characterizing the serial rule
• The probabilistic serial mechanism with private endowments
• Probabilistic allocation rules and single-dipped preferences

Cites work

• A new solution to the random assignment problem.
• A solution to the random assignment problem on the full preference domain
• A strategic model of social and economic networks
• A theory of school-choice lotteries
• Approximate random allocation mechanisms
• Assignment mechanisms under distributional constraints
• Assignment mechanisms under distributional constraints
• Collective choice under dichotomous preferences
• College Admissions and the Stability of Marriage
• Constrained random matching
• Deferred acceptance algorithms: history, theory, practice, and open questions
• Designing matching mechanisms under constraints: an approach from discrete convex analysis
• Efficiency and stability of probabilistic assignments in marriage problems
• Equivalence of efficiency notions for ordinal assignment problems
• House allocation with fractional endowments
• scientific article; zbMATH DE number 48303 (Why is no real title available?)
• scientific article; zbMATH DE number 7657254 (Why is no real title available?)
• Lattice structure of the random stable set in many-to-many matching markets
• Pareto optimality in coalition formation
• Queue allocation of indivisible goods
• Random assignment of multiple indivisible objects
• Random assignment: redefining the serial rule
• Random assignments of bundles
• Random Matching Under Dichotomous Preferences
• Random matching under priorities: stability and no envy concepts
• School Choice with Consent^*
• Stability concepts in matching under distributional constraints
• Stable Matchings, Optimal Assignments, and Linear Programming
• Stable schedule matching under revealed preference.
• Strategy-proof allocation of indivisible goods
• Strategy-proofness and Essentially Single-valued Cores
• The college admissions problem with lower and common quotas
• The Economics of Matching: Stability and Incentives
• The geometry of fractional stable matchings and its applications
• The object allocation problem with random priorities
• The probabilistic serial mechanism with private endowments
• The stability of hedonic coalition structures
• Two-sided matching with indifferences

Cited in

(4)

• Fair division of indivisible goods: recent progress and open questions
• Simultaneous eating algorithm and greedy algorithm in assignment problems
• A theory of fair random allocation under priorities
• Ex-post stability under two-sided matching: complexity and characterization

This page was built for publication: The vigilant eating rule: a general approach for probabilistic economic design with constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2675446)