A Simple Characterization of Assignment Mechanisms on Set Constraints

Operations Research Forum
Ping Zhan1
1Department of Communication and Business, Edogawa University, Nagareyama, Japan

Tóm tắt

AbstractWe consider the problem of allocating divisible/indivisible goods to agents according to agents’ ordinal preferences. Hashimoto et al. [15] provided a nonalgorithmic and axiomatic characterization of well-studied probabilistic serial (PS) mechanism. Recently, Fujishige et al. [12] generalized the PS mechanism where goods are enlarged from a fixed set to a family of sets which is a polytope defined by a system of linear inequalities associated with submodular functions. The above extended PS (EPS) greatly improved the flexibility of allocations. Based on these two results, in this paper, we investigate the nonalgorithmic and axiomatic characterization of EPS. We show that the EPS rule is the only mechanism satisfying the ordinal fairness and a newly defined non-wastefulness. The submodularity plays a crucial role in our arguments.

Từ khóa


Tài liệu tham khảo

Amanatidis G, Aziz H, Birmpas G, Filos-Ratsikas A, Li B, Moulin H, Voudouris A, Wu X (2022) Fair division of indivisible goods: a survey. Preprint at https://arxiv.org/abs/2202.07551

Aziz H, Brandl F (2021) The vigilant eating rule: a general approach for probabilistic economic design with constraints. http://arxiv-export-lb.library.cornell.edu/pdf/2008.08991

Balbuzanov I (2022) Constrained random matching. J Econ The 203:105472

Bogomolnaia A (2015) Random assignment: redefining the serial rule. J Econ The 158:308–318

Bogomolnaia A, Heo EJ (2012) Probabilistic assignment of objects: characterizing the serial rule. J Econ The 147:2072–2082

Bogomolnaia A, Moulin H (2001) A new solution to the random assignment problem. J Econ The 100:295–328

Budish Che YK, Kojima K, Milgrom P (2013) Designing random allocation mechanisms: theory and applications. Amer Econ Rev 103:178–200

Chatterji S, Liu P (2020) Random assignments of bundles. J Math Econ 87:15–30

Doğan B, Doğan S, Yildiz K (2018) A new ex-ante efficiency criterion and implications for the probabilistic serial mechanism. J Econ The 175:178–200

Fujishige S (2005) Submodular functions and optimization, 2nd edn. Elsevier, Amsterdam

Fujishige S, Sano Y, Zhan P (2016) A solution to the random assignment problem with a matroidal family of goods. RIMS Preprint, RIMS-1852, Kyoto Univ

Fujishige S, Sano Y, Zhan P (2018) The random assignment problem with submodular constraints on goods. ACM Trans Econ Comput 6:28. https://doi.org/10.1145/3175496

Fujishige S, Sano Y, Zhan P (2019) Submodular optimization views on the random assignment problem. Math Program 178(1–2):585–501

Guo X, Sikdar S, Wang H, Xia L, Cao Y, Wang H (2021) Probabilistic serial mechanism for multi-type resource allocation. Autonomous Agents and Multi-Agent Systems (35) article 15

Hashimoto T, Hirata D, Kesten O, Kurino M, Ünver MU (2014) Two axiomatic approaches to the probabilistic serial mechanism. The Econ 9:253–277

Heo EJ (2014) Probabilistic assignment problem with multi-unit demands: a generalization of the serial rule and its characterization. J Math Econ 54:40–47

Heo EJ, Yilmaz Ö (2015) A characterization of the extended serial correspondence. J Math Econ 59:102–110

Sano Y, Zhan P (2021) Extended random assignment mechanisms on a family of good sets. SN Oper Res Forum 2:52

Thông tin
Thông tin xuất bản

Operations Research Forum

Thông tin tác giả