A random arrival rule for division problems with multiple references

• DOI: http://doi.org/10.1111/itor.12434
• Author: F.J. Sánchez,D.V. Borrero,M.A. Hinojosa,A.M. Mármol
• Published date: 01 May 2018
• Date: 01 May 2018

Intl. Trans. in Op. Res. 25 (2018) 963–982

DOI: 10.1111/itor.12434

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A random arrival rule for division problems with multiple

references

D.V. Borreroa,F.J.S

´

ancheza, M.A. Hinojosaaand A.M. M´

armolb

aDepartamento de Econom´

ıa, M´

etodos Cuantitativos e Historia Econ´

omica, Universidad Pablo de Olavide, Ctra. de Utrera

Km. 1. 41013, Sevilla, Spain

bDepartamento de Econom´

ıa Aplicada III, Universidad de Sevilla, Avda. Ram´

on y Cajal no. 1. 41018, Sevilla, Spain

E-mail: dvbormol@upo.es [Borrero]; fsansan@upo.es [S´

anchez]; mahinram@upo.es [Hinojosa];

amarmol@us.es [M´

armol]

Received 15 October 2016; receivedin revised form 22 March 2017; accepted 11 May 2017

Abstract

We address the problem of the division of a homogeneous, infinitely divisible good among a set of agents

when several characteristics have to be taken into account. Specifically, we extend the classic random arrival

rule to division problems which do not necessarily represent a bankruptcy situation, and in which several

references are considered for each agent. We establish the links of the extended rule with the classic random

arrival rule and we prove that the outcomes coincide with the Shapley value of an appropriate cooperative

game. The results permit a complete description of the allocations that would be obtained for any value of

the quantity to be divided.

Keywords:division problem; random arrival rule; Shapley value

1. Introduction

In this paper,we deal with the problem of the division of a quantity of a homogeneous and infinitely

divisible good among a set of agents according to certain characteristics associated with the agents.

The simplest case of these problems, and the most studied in the literature, is that each agent is

characterized by a single amount that represents the reference of this agent.This case includes both

bankruptcy problems (Aumann and Maschler, 1985) and surplus sharing problems (Moulin, 1987),

which havebeen widely studied in the literature (for a recent survey,see also Thomson, 2003, 2015).

However, there are many real-life situations where each agentis characterized by several references

related to different characteristics, and a final allocation must be determined on the basis of these

different characteristics. One of these situations could be: the budget of the European Union must

be divided among the member countries by taking into account their needs with respect to different

items, such as agriculture and natural resources, security and justice, citizens programs and foreign

relations. In these situations, the problem becomes a multi-dimensional extension of the division

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

964 D.V. Borrero et al. / Intl. Trans. in Op. Res.25 (2018) 963–982

problem. These problems, introduced in Calleja et al. (2005), are henceforth called division problems

with multiple references.The model has been studied in the literature from two possible approaches.

In a first approach, the total quantity is initially allocated between the different characteristics. The

amount assigned to each characteristic is then allocated among the agents. With this approach,

an allocation is a matrix whose components are the amounts assigned to each agent for each

characteristic. This approach is followed in Lorenzo-Freire et al. (2010), Berganti˜

nos et al. (2010,

2011), and Moreno-Ternero (2009). In the second approach, the different characteristics are also

taken into account, however, an allocation is a vector whose components are the final amounts

assigned to each agent. This second model is investigated in Calleja et al. (2005), Gonz´

alez-Alc´

on

et al. (2007), Ju et al. (2007), and in Hinojosa et al. (2012, 2013).

A primary objective in the study of division problems is to identify well-behavedrules that provide

a single allocation to the agents. One of the most outstanding division rules is the random arrival

rule, introduced by O’Neill (1982) for bankruptcy problems. This rule turns out to be the Shapley

value of the cooperative game that assigns to each coalition the remainder of the estate after the

agents outside the coalition have obtained their claims. We first consider this random arrival rule

in a more general context that includes both bankruptcy problems and surplus sharing problems,

and prove that, for these division problems, the rule also coincides with the Shapley value of the

above-mentioned O’Neill’s game.

The main goal of the present paper is the design of a division rule for problems with multiple

references that is based on the same principle underlying the classic random arrival rule and that

can accommodate the possible multi-dimensionality of the references. Specifically, our extension of

the classic random arrival rule takes into account, for each possible permutation of the agents, the

best aggregated expectations across the characteristics of the predecessors of a given agent, instead

of the sum of the claims (the unique characteristic) of these predecessors, as is considered in the

classic random arrival rule.

It is shown in the paper that our generalization of the random arrival rule also provides the

outcomes proposed by the Shapley value of the appropriate cooperative game. Moreover, there are

several links with the classic random arrival rule and with the extended talmudic rule proposed in

Hinojosa et al. (2012) that are established in the paper.

Finally, we provide a complete description of the allocations obtained with the rule for any value

of the quantity to be divided.

The rest of the paper is organized as follows. In Section 2, the random arrival rule for division

problems is defined and the relationship between the rule in this context and the Shapley value is

proved. In Section 3, we propose a division rule for division problems with multiple references and

analyze its behavior. Section 4 is devoted to setting out the conclusions. The proofs of the results

are contained in the Appendix.

2. The division problem

Let N={1,...,n}be a set of agents. A classic bankruptcy problem (Aumann and Maschler,

1985) consists of the division of a positive amount, E∈IR ++1, of a homogeneous and infinitely

1Denote by IR (IR+,IR

++) the set of all (non-negative, positive) real numbers and by IRN(IRN

+,IR

N

++) the Cartesian

product of |N|copies of IR (IR+,IR

++).

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies