We study a property of procedures for allocating indivisible goods to agents called duplication monotonicity, first proposed by Baumeister et al. (Journal of Autonomous Agents and Multi-Agent Systems31 (2017) 628–655). An allocation procedure satisfies duplication monotonicity if two agents with identical preferences always receive at least as good a share together than one agent would on her own. We study this property first for rules that take cardinal inputs, i.e., the numerical utility of each item to each agent; and secondly for rules that take ordinal inputs, i.e., a ranking of all the items for each agent. In the first case, the rules are parametrized by a social welfare ordering interpolating between utilitarian and egalitarian approaches. In the second case, the rules are additionally parametrized by a scoring vector. We show that in the ordinal setting, only the rule using utilitarian social welfare satisfies duplication monotonicity. In stark contrast, in the ordinal setting we prove that a form of duplication monotonicity holds under a weak assumption on the social welfare function (satisfied by all our examples), answering a question by Baumeister et al. (Journal of Autonomous Agents and Multi-Agent Systems31 (2017) 628–655).
H.Aziz, Y.Bachrach, E.Elkind and M.Paterson, False-name manipulations in weighted voting games, Journal of Artificial Intelligence Research40 (2011), 57–93. doi:10.1613/jair.3166.
2.
H.Aziz, F.Brandt and H.Seedig, Computing desirable partitions in additively separable hedonic games, Artificial Intelligence195 (2013), 316–334. doi:10.1016/j.artint.2012.09.006.
3.
N.Bansal and M.Sviridenko, The Santa Claus problem, in: Proceedings of the 38th ACM Symposium on Theory of Computing, ACM Press, 2006, pp. 31–40.
4.
S.Barberà, W.Bossert and P.Pattanaik, Ranking sets of objects, in: Handbook of Utility Theory, Vol. 2: Extensions, S.Barberà, P.Hammond and C.Seidl, eds, Kluwer Academic Publisher, 2004, pp. 893–977. doi:10.1007/978-1-4020-7964-1_4.
5.
J.BartholdiIII, C.Tovey and M.Trick, How hard is it to control an election?, Mathematical and Computer Modelling16(8/9) (1992), 27–40. doi:10.1016/0895-7177(92)90085-Y.
6.
D.Baumeister, S.Bouveret, J.Lang, N.Nguyen, T.Nguyen, J.Rothe and A.Saffidine, Positional scoring-based allocation of indivisible goods, Journal of Autonomous Agents and Multi-Agent Systems31(3) (2017), 628–655. doi:10.1007/s10458-016-9340-x.
7.
S.Bouveret, Y.Chevaleyre and N.Maudet, Fair allocation of indivisible goods, in: Handbook of Computational Social Choice, F.Brandt, V.Conitzer, U.Endriss, J.Lang and A.Procaccia, eds, Cambridge University Press, 2016, pp. 284–310, Chapter 12. doi:10.1017/CBO9781107446984.013.
8.
S.Bouveret and M.Lemaître, Characterizing conflicts in fair division of indivisible goods using a scale of criteria, Journal of Autonomous Agents and Multi-Agent Systems30(2) (2016), 259–290. doi:10.1007/s10458-015-9287-3.
9.
S.Brams, P.Edelman and P.Fishburn, Fair division of indivisible items, Theory and Decision55(2) (2003), 147–180. doi:10.1023/B:THEO.0000024421.85722.0a.
10.
S.Brams and D.King, Efficient fair division: help the worst off or avoid envy?, Rationality and Society17(4) (2005), 387–421. doi:10.1177/1043463105058317.
11.
F.Brandt, V.Conitzer, U.Endriss, J.Lang and A.Procaccia (eds), Handbook of Computational Social Choice, Cambridge University Press, 2016.
12.
A.Darmann and C.Klamler, Using the borda rule for ranking sets of objects, Social Choice and Welfare (2019), to appear. Online version, https://link.springer.com/article/10.1007/s00355-019-01190-w.
13.
A.Darmann and J.Schauer, Maximizing Nash product social welfare in allocating indivisible goods, European Journal of Operational Research247(2) (2015), 548–559. doi:10.1016/j.ejor.2015.05.071.
14.
E.Elkind, P.Faliszewski and A.Slinko, Cloning in elections: Finding the possible winners, Journal of Artificial Intelligence Research42 (2011), 529–573.
15.
E.Elkind and J.Rothe, Cooperative game theory, in: Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, J.Rothe, ed., Springer Texts in Business and Economics, Springer-Verlag, 2015, pp. 135–193, Chapter 3.
16.
G.H.Hardy, J.E.Littlewood and G.Pólya, Inequalities, Cambridge University Press, 1934.
17.
T.Heinen, N.Nguyen, T.Nguyen and J.Rothe, Approximation and complexity of the optimization and existence problems for maximin share, proportional share, and minimax share allocation of indivisible goods, Journal of Autonomous Agents and Multi-Agent Systems32(6) (2018), 741–778. doi:10.1007/s10458-018-9393-0.
18.
B.Kuckuck and J.Rothe, Sequential allocation rules are separable: refuting a conjecture on scoring-based allocation of indivisible goods, in: Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, IFAAMAS, 2018, pp. 650–658.
19.
J.Lang and J.Rothe, Fair division of indivisible goods, in: Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, J.Rothe, ed., Springer Texts in Business and Economics, Springer-Verlag, 2015, pp. 493–550, Chapter 8.
20.
H.Moulin, Condorcet’s principle implies the no show paradox, Journal of Economic Theory45(1) (1988), 53–64. doi:10.1016/0022-0531(88)90253-0.
21.
H.Moulin, Fair Division and Collective Welfare, MIT Press, 2004.
22.
N.Nguyen, D.Baumeister and J.Rothe, Strategy-proofness of scoring allocation correspondences for indivisible goods, Social Choice and Welfare50(1) (2018), 101–122. doi:10.1007/s00355-017-1075-3.
23.
T.Nguyen, M.Roos and J.Rothe, A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation, Annals of Mathematics and Artificial Intelligence68(1–3) (2013), 65–90. doi:10.1007/s10472-012-9328-4.
24.
A.Rey and J.Rothe, False-name manipulation in weighted voting games is hard for probabilistic polynomial time, Journal of Artificial Intelligence Research50 (2014), 573–601. doi:10.1613/jair.4293.
25.
K.W.S.Roberts, Interpersonal comparability and social choice theory, The Review of Economic Studies47(2) (1980), 421–439, http://www.jstor.org/stable/2297002.
26.
A.Sen, Collective Choice and Social Welfare, Holden Day, 1970.
27.
N.Tideman, Independence of clones as a criterion for voting rules, Social Choice and Welfare4(3) (1987), 185–206. doi:10.1007/BF00433944.
28.
R.Yager, On ordered weighted averaging aggregation operators in multicriteria decisionmaking, IEEE Transactions on Systems, Man, and Cybernetics18(1) (1988), 183–190. doi:10.1109/21.87068.
