The integer nucleolus of directed simple games: A characterization and an algorithm

Wolff, Reiner Article The integer nucleolus of directed simple games: A characterization and an algorithm Games Provided in Cooperation with: MDPI – Multidisciplinary Digital Publishing Institute, Basel Suggested Citation: Wolff, Reiner (2017) : The integer nucleolus of directed simple games: A characterization and an algorithm, Games, ISSN 2073-4336, MDPI, Basel, Vol. 8, Iss. 1, pp. 1-12, https://doi.org/10.3390/g8010016 This Version is available at: https://hdl.handle.net/10419/168018 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Article The Integer Nucleolus of Directed Simple Games: A Characterization and an Algorithm Reiner Wolff Department of Economics, University of Fribourg, 1700 Fribourg, Switzerland; [email protected] Academic Editors: Luca Dall’Asta and Paolo Pin Received: 16 November 2016; Accepted: 7 February 2017; Published: 28 February 2017 Abstract: We study the class of directed simple games, assuming that only integer solutions are admitted; i.e., the players share a resource that comes in discrete units. We show that the integer nucleolus—if nonempty—of such a game is composed of the images of a particular payoff vector under all symmetries of the game. This payoff vector belongs to the set of integer imputations that weakly preserve the desirability relation between the players. We propose an algorithm for finding the integer nucleolus of any directed simple game with a nonempty integer imputation set. The algorithm supports the parallel execution of multiple threads in a computer application. We also consider the integer prenucleolus and the class of directed generalized simple games. Keywords: integer nucleolus; integer prenucleolus; desirability relation; simple games JEL Classification: C63; C71; D72 1. Introduction The nucleolus is a popular solution concept for cooperative transferable-utility (TU) games because it is a set of game outcomes that are in a sense most acceptable “... as a compromise between the players” (Schmeidler [1], p. 1163). A cooperative TU game is a pair (N,v) =:Γ, henceforth called a game, with a finite set N:={1, . . . , n}of n(≥2)players and a coalition function v: 2N→R,v(∅) = 0. For every payoff vector x∈Rnand coalition S⊆N, let x(S):=Pi∈Sxi. If S⊂N,S6=∅, we denote the excess of coalition Sat xby e(S,x):=v(S)−x(S). This way, we can associate with each x∈Rnthe vector θ(x)of all 2n−2 excesses e(S,x), arranged in nonincreasing magnitude. The nucleolus of Γwith respect to a set Xof feasible payoff vectors is the set N(Γ,X):=x∈X:θ(x)≤lex θ(z)for all z∈Xof payoff vectors which minimize θ(x) lexicographically over X(cf. Schmeidler [1]), as if they were the outcome of an egalitarian arbitration among player coalitions (cf. Maschler [2], p. 611). Our choice for Xwill be the integer imputation set I(Γ):=x∈Zn:x(N) = v(N),xi≥v({i})for all i∈N, under the condition that v(N)∈Z>0. Thus, we assume that the players face an integer resource allocation problem in that v(N)comes in discrete units that cannot be broken apart. We call ν(Γ):=NΓ,I(Γ)the integer nucleolus of the game Γ. A problem closely related to the integer nucleolus is that of finding minimum (or minimum-sum) integer representations of weighted majority games (cf. Peleg [3], Krohn and Sudhölter [4], Kurz et al. [5]). In Wolff and Karagök [6], the integer nucleolus is used to analyze the apportionment of ministries in the Swiss parliament. Fragnelli and Gastaldi [7] study the bankruptcy problem where the estate and the claims are integer, and compare integer versions of the Talmud solution to this problem with the integer nucleolus of the corresponding pessimistic bankruptcy game when there are two or three agents. It is interesting to note that Fragnelli et al. [8,9] suggest integer solutions to a bankruptcy setting that involves an integer estate, while the claims can be of any positive Games 2017,8, 16; doi:10.3390/g8010016 www.mdpi.com/journal/games Games 2017,8, 16 2 of 12 magnitude. An example is the assignment of emergency intervention units, when the claims are calculated in proportion to the size of the population or area to attend to, which, in turn, means that the characteristic function of an associated bankruptcy game may assume noninteger values. A bankruptcy-based model for the management of capacity-constrained integer resources in mobile radio networks is proposed in Lucas-Esta˜ n et al. [10]. Further examples of integer resources are college places, housing opportunities, livestock, or organs for transplant. Finally, when a sum of money is to be divided among a set of players, each smallest relevant money unit also is a whole object. Since I(Γ)lacks convexity, ν(Γ)may contain multiple elements. The question arises in such a case whether the payoff vectors in ν(Γ)possess some common attributes, beyond the property that they all minimize θlexicographically. A complementary practical question is how to compute ν(Γ). In general, ν(Γ)can be obtained by solving a sequence of integer linear programs, analogous to a suggestion by Maschler [2] (p. 615) that is implemented in most of the studies compiled by Leng and Parlar [11] (p. 669): ILPk: min e,xe s.t. x(S) + e≥v(S)for all S∈2N\{A0, . . . , Ak−1}, x(S) + ei=v(S)for all S∈ Ai,i=1, . . . , k−1, x∈I(Γ), k=1, 2, . . . , (1) where A0:={∅,N}, while Ai,i≥1, is the set of coalitions with excess ei<··· <e1for each optimal solution (ei,x)to ILPi(cf. Guajardo and Jörnsten [12] and Nguyen and Thomas [13]). For some k=κ, eventually 2N\{A0, . . . , Aκ}=∅, in which case ILPκis solved by the set of pairs (eκ,x) with x∈ν(Γ). However, this is only a feasible procedure if nis small, since integer linear programs are usually much harder to solve than their continuous counterparts. The present article provides a characterization of ν(Γ)with respect to the class of directed simple games, and suggests an algorithm to compute ν(Γ)for this game class more efficiently, as long as I(Γ)is not too large. We focus on directed simple games because they have numerous applications—e.g., in economics, in political science, and in threshold logic (cf. Taylor and Zwicker [14] for literature references). A simple game Γtwith t∈Z>0is a monotonic game Γ, whereby v(S)≤v(T)if S⊂T⊆N, that satisfies v(S)∈ {0, t}for each S⊆N, while v(N) = t. We denote by W(Γt):={S⊆N:v(S) = t} the set of winning coalitions of Γt. A simple game Γtis called an ordered (or complete or linear) simple game, if it exhibits a complete desirability relation %Don the players in the set N. It is called a directed simple game, if in addition 1 %D··· %Dn, without loss of generality. Given a game Γ, if i%Djfor two players i,j∈N, then player iis said to be more desirable than player j, in which case v(S∪{i})≥v(S∪{j})for all S⊆N\{i,j}. (2) Player iis said to be strictly more desirable than player j, denoted by iDj, if i%Dj, while not j%Di. The players are called symmetric—denoted by i∼Dj—if both i%Djand j%Di(cf. Maschler and Peleg [15], Sect. 9). The desirability relation may be hidden in the set of winning coalitions, and can then be computed with polynomial-time methods (cf. Aziz [16] and Aziz [17], Ch. 3). It may also be rooted naturally in the setup of the game. For example, consider a simple game Γtthat is a weighted majority game with a quota q∈R>0and the weights w1, . . . , wn∈R≥0of the players, where q≤Pi∈Nwi. Here, W(Γt):=S⊆N:Pi∈Swi≥q. Hence, i%Djfor two players i,j∈Nwhenever wi≥wj. We shall represent such a game by the tuple [q;w1, . . . , wn;t], in brief [q;w;t], where w:= (w1, . . . , wn). Note that the desirability relation of an ordered simple game Γt is strictly preserved by the counting vector c:= (c1, . . . , cn), where ci:= S⊆ W(Γt):i∈S  (cf. Lapidot [18,19]). Note also that the integer nucleolus ν(Γ)of any game Γis nonempty and finite Games 2017,8, 16 3 of 12 whenever I(Γ)6=∅. A characterization of ν(Γt)will now be derived in Section 2. The algorithm and a performance analysis follow in Sections 3and 4. Section 5provides an extension to the integer prenucleolus, and Section 6concludes. 2. A Characterization of ν(Γt) We begin with two general properties of the integer nucleolus: Lemma 1. Let Γbe a game. If i Dj for two players i,j∈N, then xi≥xjfor each x∈ν(Γ). Proof. Take any x∈ν(Γ). Suppose xi≤xj−1, noting that xi≥v({i})by definition of ν(Γ). Assume iDj, so v(S∪{i})≥v(S∪{j})for every S⊆N\{i,j}by definition. In particular, v({i})≥v({j}), and thus xj−1≥xi≥v({i})≥v({j}). Observe that e(S∪ {i},x)≥e(S∪ {j},x) + 1 for each S⊆N\ {i,j}. Since iDjby assumption, there exists a coalition T⊆N\ {i,j}such that v(T∪ {i})>v(T∪ {j}), implying e(T∪{i},x)≥e(T∪{j},x) + 2. Hence, a reallocation at xof one unit of payoff from player jto player iwill result in an integer imputation that improves θ, a contradiction (note that the excesses of all coalitions which contain neither or both of the players iand jare not affected). Therefore, if iDjand x∈ν(Γ), then xi≥xj. Lemma 2. Let Γbe a game. If i ∼Dj for two players i,j∈N, then |xi−xj|∈{0, 1}for each x∈ν(Γ). Proof. Take any x∈ν(Γ). Without loss of generality, suppose xi≤xj−2, noting again that xi≥v({i})by definition of ν(Γ). Assume i∼Dj, so v(S∪{i}) = v(S∪{j})for every S⊆N\{i,j} by definition. In particular, v({i}) = v({j}), and thus xj−2≥xi≥v({i}) = v({j}). At the same time, e(S∪{i},x)≥e(S∪{j},x) + 2 for each S⊆N\{i,j}. Consequently, a reallocation at xof one unit of payoff from player jto player iyields an integer imputation that improves θ, a contradiction. Therefore, if i∼Djand x∈ν(Γ), then |xi−xj|∈{0, 1}. Remark 1. Let Γbe a game, where i ∼Dj for two players i,j∈N. If xi6=xjfor x∈ν(Γ), and payoff vector zdiffers from xonly in that the payoffs of players i and j are permuted, then z∈ν(Γ)by the anonymity (impartiality) of ν(Γ). The following lemma and a subsequent corollary are our main theoretical result: Lemma 3. The integer nucleolus ν(Γt)of a directed simple game Γtwith I(Γt)6=∅has a unique element, henceforth denoted by y, that weakly preserves %D; i.e., y1≥ ··· ≥ yn. Proof. By definition of a directed game, 1 %D··· %Dn. Then, because of Lemmas 1and 2, Remark 1, and the nonemptiness of ν(Γt), a payoff vector like yexists. To prove its uniqueness, suppose for x∈I(Γt)that x6=yand x1≥ ··· ≥ xn. Denote by ithe largest index jfor which xj6=yj. Hence, xj=yjfor j>i. Without loss of generality, suppose xi>yi. Note that x∈ν(Γt)if and only if θ(x) = θ(y): Case 1: {i}/∈ W(Γt); i.e., e({i},y) = −yi. Assume yi=0. Then, xj=0 if and only if j>i, in which case also yj=0. Now consider any coalition S⊂N,S6=∅, with e(S,x) = 0. If S∈ W(Γt), then x(S) = t, and thus xl=0 for every player l∈N\S. Since yl=0 for each such player, y(S) = t and hence e(S,y) = 0. If S/∈ W(Γt), then xk=0, and thus yk=0, for every k∈S, whereby also e(S,y) = 0. However, as e({i},x) = −xi<0, we conclude that θ(x)6=θ(y). Next, assume yi>0. Observe for any coalition S⊂N,S6=∅, with e(S,x) = −yithat S⊆ {i+1, . . . , n}. Hence, e(S,y) = −yi. Consequently, as e({i},x) = −xi<−yi, again θ(x)6=θ(y). In all, x/∈ν(Γt). Games 2017,8, 16 4 of 12 Case 2: {i} ∈ W(Γt), whereby yi=tsince y∈I(Γt). In particular, i=1, as y1≥ ··· ≥ yn. Hence, y= (t, 0, . . . , 0), and therefore x/∈I(Γt), a contradiction. To summarize, it cannot be true that x∈ν(Γt),x6=y, and x1≥ ··· ≥ xn. Remark 2. The proof of Lemma 3does not depend on the assumed monotonicity of simple games, and the desirability relation %Dwas not needed to show the uniqueness of y. We conclude from the latter observation—since we are free to renumber the players—that if Γis a simple game, then ν(Γ)contains at most one payoff vector for every order of the payoffs x1, . . . , xn.1 A permutation πof the player set Nof a game Γsuch that v(π(S)) = v(S)for each S⊆Nis called a symmetry of Γ. Because of Lemma 3and Remark 1: Corollary 1. The integer nucleolus ν(Γt)of a directed simple game Γtwith I(Γt)6=∅is the set of images of yunder all symmetries of Γt. We close this section with three examples and a remark: Example 1. Let Γtbe represented by [33; 15, 15, 10, 10, 4, 4, 4, 2, 1; 30]. Then, y= (7, 7, 4, 4, 3, 2, 2, 1, 0). Additionally, c= (189, 189, 163, 163, 147, 147, 147, 129, 129); i.e., c5=c6=c7and c8=c9. Since y5> y6,y7, and y8>y9, we obtain a set ν(Γt)of six payoff vectors. We provide them in anti-lexicographic order: ν(Γt) = (7, 7, 4, 4, 3, 2, 2, 1, 0),(7, 7, 4, 4, 3, 2, 2, 0, 1),(7, 7, 4, 4, 2, 3, 2, 1, 0), (7, 7, 4, 4, 2, 3, 2, 0, 1),(7, 7, 4, 4, 2, 2, 3, 1, 0),(7, 7, 4, 4, 2, 2, 3, 0, 1). Example 2. Let (the non-proper game) Γtbe represented by [6; 4, 4, 2, 2, 2, 1; 8]. Then, y= (2, 2, 1, 1, 1, 1), while c= (30, 30, 26, 26, 26, 23). Hence, ν(Γt) = {(2, 2, 1, 1, 1, 1)}. Example 3. Consider the game Γwhere n =3and v({1}) = v({2}) = 1, v({3}) = 0, v({1, 2}) = 2, v({1, 3}) = v({2, 3}) = 1, v({1, 2, 3}) = 7. Note that 1∼23, whereas ν(Γ) = (3, 3, 1),(3, 2, 2), (2, 3, 2). Lemma 3and Corollary 1thus cannot be generalized to every directed game Γ. Remark 3. In Example 2, player 6 is a null player, yet y6=1. In general, let Γbe a game, and write as L(Γ):=j∈N:v(S) = v(S∪{j})for all S ⊆N\{j}the set of null players of Γ. Suppose x∈I(Γ) and xi≥2for i ∈L(Γ). Since v(N)>0, there exists a coalition T ∈arg max∅6=S⊂Ne(S,x), such that T∩L(Γ) = ∅, whereby e(Q,x)≤e(T,x)−2for all Q ⊂N, i ∈Q. So, a reallocation at xof one unit of payoff from player i to a player k ∈T improves θ. Hence, xi∈ {0, 1}for each i ∈L(Γ)and every x∈ν(Γ). 3. An Algorithm to Compute ν(Γt) Given a directed simple game Γt, denote by θWthe subvector of θassociated with the coalitions in W(Γt)\N, and by P(Γt):=x∈I(Γt):x1≥ ··· ≥ xn∧|xi−xj| ∈ {0, 1}for all i6=j,i∼Djthe subset of integer imputations in anti-lexicographic order that satisfy Lemmas 1and 2. Let νW(Γt):= x∈P(Γt):θW(x)≤lex θW(z)for all z∈P(Γt). Write as V(Γt):=i∈N:S∈ W(Γt)⇒i∈Sthe set of veto players of Γt, and let r:=|V(Γt)|. If r>0, then V(Γt) = {1, . . . , r}, because Γtis directed. Lemma 4. Let Γtbe a directed simple game with I(Γt)6=∅. If W(Γt)\N6=∅, then νW(Γt) = {y}. Proof. Assume W(Γt)\N6=∅, and note that P(Γt)6=∅due to I(Γt)6=∅. Hence, νW(Γt)6=∅. In particular, y∈νW(Γt). Now suppose r>0, whereby x(V(Γt)) = tfor each x∈νW(Γt). Since i∼Dj 1This conclusion was brought to the author’s attention through a valuable comment by J. Derks. Games 2017,8, 16 5 of 12 for any two players i,j∈V(Γt), only one element of the set P(Γt)assigns the payoff tto coalition V(Γt), this element being y= (y+1, . . . , y+1 | {z } stimes ,y, . . . , y | {z } r−stimes , 0, . . . , 0 | {z } n−rtimes ), (3) where y:=bt rcdenotes the largest integer that does not exceed t r, and s:=t−ry. Thus, νW(Γt) = {y}. Next, suppose r=0; i.e., V(Γt) = ∅. Take any x∈P(Γt),x6=y, and denote by ithe largest index jsuch that xj6=yj. Accordingly, xj=yjfor all j>i. Without loss of generality, assume xi>yi. As i/∈V(Γt), there exists a coalition S∈ W(Γt)\N,i/∈S, and hence N\{i} ∈ W(Γt)by the monotonicity of Γt. Consequently, e(N\{i},y) = yi. This excess may be obtained at xonly by winning coalitions N\Twith T⊆ {i+1, . . . , n}, but then also at y. Since e(N\{i},x) = xi>yi, we obtain θW(x)6=θW(y), and so x/∈νW(Γt).2 The borderline case of a directed simple game Γtwith W(Γt)\N=∅implies that W(Γt) = {N}=V(Γt), and thereby I(Γt)6=∅, as well as ν(Γt) = P(Γt) = {y}because of the symmetry of all players. The associated payoff vector yis determined by (3) for r=n. Thus, if Γtis a directed simple game and I(Γt)6=∅, we may search P(Γt)for ywithout reference to the coalitions not contained in W(Γt). In view of this observation, we now suggest an algorithm to compute the integer nucleolus of any such game. Since the elements of P(Γt)have independent excess vectors θW, our algorithm can make the most of computing machinery that supports the parallel execution of multiple threads in an application program. Note for each x∈P(Γt)with xk>0, xk+1=0, that x1+···+xkis a partition of tinto k(≤min{t,n}) parts in standard form. A fast generator of integer partitions in standard form and in anti-lexicographic order is procedure ZS1 by Zoghbi and Stojmenovi´c [20] (pp. 325–326). To proceed, define the incidence vector 1S∈ {0, 1}nof any coalition S∈ W(Γt)\Nin that 1Si =1 if and only if i∈S, and consider the auxiliary vector aS:= (aS1, . . . , aSn), where aSi :=X j≤i 1Sj ,i=1, . . . , n. (4) Hence, if x∈P(Γt)and xk>0, xk+1=0, then aSk players in coalition Sreceive a positive payoff. These players can be read off the auxiliary vector bS:= (bS1, . . . , bS|S|), where bSi :=index of the ith positive entry of 1S,i=1, . . . , |S|. (5) The total payoff of coalition Sat xthus amounts to Pi≤aSk xbSi . For example, if n=7 and S={2, 3, 6}, we obtain 1S= (0, 1, 1, 0, 0, 1, 0),aS= (0, 1, 2, 2, 2, 3, 3), and bS= (2, 3, 6). Thereby, if t=6 and x= (2, 2, 1, 1, 0, 0, 0)—noting that xresults from a partition of tinto four parts—x({2, 3, 6}) = Pi≤aS4xbSi =x2+x3. For each x∈P(Γt), let D(Γt,x,h):=S∈ W(Γt)\N:e(S,x) = hwith h∈ {0, . . . , t}, and attach to xthe auxiliary vector Θ(x):= (Θ1(x), . . . , Θt+1(x)), where Θt−h+1(x):=|D(Γt,x,h)|,h=t, . . . , 0. (6) This way, Θ(x)holds the number of occurrences of excesses of a size at x, top-down from the largest excess tto the smallest excess 0 of the coalitions in the set W(Γt)\N. Thereby, given any two payoff vectors ˜ x,ˆ x∈P(Γt),˜ xis preferred to ˆ xif and only if Θ(˜ x)<lex Θ(ˆ x). While calculating and counting 2The author thankfully acknowledges a helpful conversation with J. Derks who pointed out to him that, given a simple game Γt, the set x∈I(Γt):θW(x)≤lex θW(z)for all z∈I(Γt)contains at most one element xwith x1≥ ··· ≥ xn, whenever N\{i} ∈ W(Γt)for all i∈N. We add that it also suffices to impose the weaker condition that r≤1. Games 2017,8, 16 6 of 12 excesses hand in hand, we may be able to tell quite early how x∈P(Γt)compares to a current best status quo, say x∗. Let Θ∗:=Θ(x∗), and suppose lis the first index ifor which Θ∗ i>0. Then, payoff vector xcan already be discarded if any of the first l−1 entries of Θ(x)has been detected to take a positive value or once Θl(x)is known to exceed Θ∗ l. Table 1. Lexicographic minimization of θ(x)over P(Γt). Input: Directed simple game Γt(assuming I(Γt)6=∅), p Output: (c,y) PROG LEXMIN GLOBAL W(Γt)\N,P(Γt),x∗(),p,t;GLOBAL aS,bSfor all S∈ W(Γt)\N n← |N|;t←v(N) FOR i=1TO nDO {ci← |{S⊆ W(Γt):i∈S}|} P(Γt)←x∈I(Γt):x1≥ ··· ≥ xn∧|xi−xj|∈{0, 1}for all i6=j,ci=cj FOR each S∈ W(Γt)\NDO {compute (aS,bS)as in (4) and (5)} DIM x∗(1: p) START THREAD LEXMIN1 ; . . . ; START THREAD LEXMINp DO {wait for threads LEXMIN1, . . . , LEXMINpto complete} y←x∗(1);Θ∗←Θ(y) FOR i=2TO pDO {IF Θ(x∗(i)) <lex Θ∗THEN y←x∗(i);Θ∗←Θ(y)} END PROG THREAD FUNCTION LEXMINi x∗(i)←last x∈P(Γt);Θ∗←Θ(x∗(i)) ;l←smallest index jfor which Θ∗ j>0 FOR the ith to the 2nd last x∈P(Γt)STEP pDO  k←number of parts of tin x;Θ←(0, . . . , 0) FOR each S∈ W(Γt)\NDO  h←t−Pj≤aSk xbSj IF t−h+1≥lTHEN Θt−h+1←Θt−h+1+1ELSE EXIT FOR IF Θl>Θ∗ lTHEN EXIT FOR IF Θ<lex Θ∗THEN x∗(i)←x;Θ∗←Θ;l←smallest index jfor which Θ∗ j>0 END FUNCTION This observation has been built into the computer pseudocode in Table 1. The code distributes most of the workload across a user-defined number p(≥1)of threads, in support of machines that can execute multiple threads in parallel (desktop applications will most often benefit from creating as many parallel threads as possible, unless |P(Γt)|is small). On input, Γtand pare passed to the main program LEXMIN that at first generates both nand tas well as the counting vector c, the set P(Γt), and the pairs (aS,bS),S∈ W(Γt)\N. Then, it allocates memory for an array x∗(1: p)of pbest status-quo payoff vectors, before invoking the thread functions LEXMIN1, . . . , LEXMINp. Each of them refers to a separate piece of code, such as the code for thread function LEXMINi. This function initializes x∗(i),Θ∗, and l, in terms of a most equal allocation of tacross the players, and then enters into two nested loops. In an attempt to spread the computational burden evenly across the threads, the outer loop has been designed to pass over every pth element of the (ordered) set P(Γt), starting from element number i. For each resulting payoff vector x∈P(Γt)and underlying number kof parts of t, the inner loop computes the excesses associated with xand populates Θ(x). If in the course of these operations index t−h+1 comes out less than l, or Θ∗ lis exceeded, then xwill be discarded Games 2017,8, 16 7 of 12 by a subsequent exit instruction. In the remaining cases, whenever Θ(x)is lexicographically smaller than Θ∗, the elements of the set {x∗(i),Θ∗,l}are updated. Once all threads are completed, LEXMIN minimizes Θlexicographically over the set of retained payoff vectors {x∗(1), . . . , x∗(p)}in order to obtain the unique argument y, and then the pair (c,y)is returned. Note that all relevant variables are considered as local to LEXMIN and its thread functions unless stated otherwise. Remark 4. A payoff vector x∈P(Γt)can already be discarded if Θlis seen to be no smaller than Θ∗ l, while Θl+1is known to be greater than Θ∗ l+1, etc. This may serve to reject xmore quickly, while the extra comparisons can have the opposite effect. Remark 5. If a reallocation of a unit of payoff between players i and j is unfavorable, another such reallocation can be rejected, everything else being equal. We then do not have to trace Θover the full set P(Γt), at the cost of an extended bookkeeping. Remark 6. One may want to exploit the occurrence of special categories of players (e.g., null players or vetoers), which imposes a search cost (cf. Aziz [16] and Aziz [17], Ch. 3, for the complexity of detecting player types). Remark 7. The coalitions S ∈ W(Γt)\N have independent pairs (aS,bS), which suggests a distributed execution of the second loop in LEXMIN. Once yis known, we conduct a scan of the counting vector cfor all subvectors (ci, . . . , cj), where ci=··· =cjand yi>yj, the range j−ibeing as large as possible. If no such subvector exists, then ν(Γt) = {y}, and we are done. Otherwise, given whichever pair (i,j)of matching indices, we retain all elements of ν(Γt)obtained earlier, as well as every payoff vector that can be derived from these elements by permuting the payoffs of the players i, . . . , j. Table 2. Completion of ν(Γt). Input: Directed simple game Γt(assuming I(Γt)6=∅) and associated pair (c,y) Output: ν(Γt) PROG COMPL n← |N|;y1←y;ν(Γt)← {y1} i←n+1 ; m←1 WHILE i>2DO  j←i−1 ; i←j WHILE i>1 and ci−1=cjDO {i←i−1} IF yi>yjTHEN  l←0 FOR each b∈B(i,j)DO  FOR k=1TO mDO  l←l+1 ; yl←(yk 1, . . . , yk i−1,b,yk j+1, . . . , yk n) m←l;ν(Γt)← {y1, . . . , ym} END PROG The pseudocode program COMPL in Table 2generates a corresponding sequence of approximations {y1, . . . , ym}to ν(Γt). On input, Γtand the pair (c,y)are passed. To begin with, the program determines nand initializes ν(Γt). Then, starting from i=j=n, the program looks for Games 2017,8, 16 8 of 12 the smallest i(<j)for which both ci=cjand yi>yj.3Whenever a matching iis found, the program retrieves all permutations of the payoffs in (yi, . . . , yj)from the respective permutation set, named B(i,j), and updates ν(Γt). In the following iteration, jis set to i−1, and so on. The search ends if i≤2, and then ν(Γt)is returned. Note that for each matching pair (i,j)the respective subvector (yi, . . . , yj) of ytakes the form (a, . . . , a,b, . . . , b), where b=a−1. The set B(i,j)can thus be calculated with ACM Algorithm 152 (Nexcom) by Hopley [21], under the normalization a=1. We end this section with a working example of our algorithm and a generalization. The example is primarily meant to illustrate the functioning of a thread in Table 1. Thus, we assume, for simplicity, that p=1: Example 4. Let Γtbe represented by [9; 5, 4, 3, 2, 1; 6]. In this game, W(Γt)\N={1, 2},{1, 2, 3},{1, 2, 4},{1, 2, 5},{1, 3, 4},{1, 3, 5},{2, 3, 4},{1, 2, 3, 4}, {1, 2, 3, 5},{1, 2, 4, 5},{1, 3, 4, 5},{2, 3, 4, 5}. Thereby, c= (11, 10, 9, 8, 7); i.e., the game exhibits the desirability relation 1D2D3D4D5. Hence, P(Γt) = (6, 0, 0, 0, 0),(5, 1, 0, 0, 0),(4, 2, 0, 0, 0),(4, 1, 1, 0, 0),(3, 3, 0, 0, 0),(3, 2, 1, 0, 0), (3, 1, 1, 1, 0),(2, 2, 2, 0, 0),(2, 2, 1, 1, 0),(2, 1, 1, 1, 1). The sole thread LEXMIN1then proceeds as follows if the elements of W(Γt)\N arrive at the thread’s inner loop in the above order from coalition {1, 2}to coalition {2, 3, 4, 5}: xlast Θin inner loop x∗(1)Θ∗llast S in inner loop — — (2, 1, 1, 1, 1) (0, 0, 0, 2, 6, 4, 0)4— (6, 0, 0, 0, 0) (1, 0, 0, 0, 0, 0, 6) (2, 1, 1, 1, 1) (0, 0, 0, 2, 6, 4, 0)4{2, 3, 4} (5, 1, 0, 0, 0) (0, 1, 0, 0, 0, 2, 4) (2, 1, 1, 1, 1) (0, 0, 0, 2, 6, 4, 0)4{2, 3, 4} (4, 2, 0, 0, 0) (0, 0, 1, 0, 2, 0, 4) (2, 1, 1, 1, 1) (0, 0, 0, 2, 6, 4, 0)4{2, 3, 4} (4, 1, 1, 0, 0) (0, 0, 1, 0, 0, 5, 1) (2, 1, 1, 1, 1) (0, 0, 0, 2, 6, 4, 0)4{2, 3, 4} (3, 3, 0, 0, 0) (0, 0, 0, 3, 0, 0, 4) (2, 1, 1, 1, 1) (0, 0, 0, 2, 6, 4, 0)4{2, 3, 4} (3, 2, 1, 0, 0) (0, 0, 0, 2, 3, 4, 3) (3, 2, 1, 0, 0) (0, 0, 0, 2, 3, 4, 3)4{2, 3, 4, 5} (3, 1, 1, 1, 0) (0, 0, 0, 2, 3, 6, 1) (3, 2, 1, 0, 0) (0, 0, 0, 2, 3, 4, 3)4{2, 3, 4, 5} (2, 2, 2, 0, 0) (0, 0, 0, 0, 9, 0, 3) (2, 2, 2, 0, 0) (0, 0, 0, 0, 9, 0, 3)5{2, 3, 4, 5} (2, 2, 1, 1, 0) (0, 0, 0, 1, 3, 2, 0) (2, 2, 2, 0, 0) (0, 0, 0, 0, 9, 0, 3)5{1, 3, 5} Upon initialization, x∗(1)=(2, 1, 1, 1, 1), whereby θW= (3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1), such that Θ∗= (0, 0, 0, 2, 6, 4, 0)and l =4. The first payoff vector x= (6, 0, 0, 0, 0)in the (ordered) set P(Γt)will be discarded as soon as LEXMIN1has calculated the excess of coalition {2, 3, 4}, since h =e({2, 3, 4},x) = 6, and thus t−h+1=1<4, etc. Eventually, Θ∗can be improved at x= (3, 2, 1, 0, 0), where Θ∗= (0, 0, 0, 2, 3, 4, 3), and again at x= (2, 2, 2, 0, 0), where Θ∗= (0, 0, 0, 0, 9, 0, 3). The latter payoff vector is finally identified as yby the main program LEXMIN, and the pair (c,y)is returned. At last, routine COMPL finds in view of c= (11, 10, 9, 8, 7)that there is no matching pair (i,j). Therefore, on output, ν(Γt) = {(2, 2, 2, 0, 0)}. For a generalized simple game Γt, the monotonicity property is dropped, and it is not maintained that v(∅) = 0 and v(N) = t(cf. Carreras and Freixas [22], p. 153, and Taylor and Zwicker [14], p. 4). The desirability relation of a directed generalized simple game is also strictly preserved by the counting vector c. However, I(Γt)may have to be redefined as denoting the set x∈Zn:x(N) = t, xi≥v({i})for all i∈N. The proof of Lemma 3then remains valid, and hence statements analogous to Lemma 3and Corollary 1apply. The following result replaces Lemma 4: 3As to the inner WHILE/DO loop in Table 2, we assume short-circuit evaluation of relational expressions. This means that the expression ‘i>1 and ci−1=cj’ is marked to be false as soon as i=1. Hence, no attempt will be made to access a nonexistent c0.