# Optimal Preference Satisfaction for Conflict-Free Joint Decisions

Authors: Hiroaki Shinkawa; Nicolas Chauvet; Guillaume Bachelier; André Röhm; Ryoichi Horisaki; Makoto Naruse
Journal: Complexity
 (2023)

---

## Abstract

When presented with multiple choices, we all have a preference; we may suffer loss because of conflicts arising from identical selections made by other people if we insist on satisfying only our preferences. Such a scenario is applicable when a choice cannot be divided into multiple pieces owing to the intrinsic nature of the resource. Earlier studies examined how to conduct fair joint decision-making while avoiding decision conflicts in terms of game theory when multiple players have their own deterministic preference profiles. However, probabilistic preferences appear naturally in relation to the stochastic decision-making of humans, and therefore, we theoretically derive conflict-free joint decision-making that satisfies the probabilistic preferences of all individual players. To this end, we mathematically prove conditions wherein the deviation of the resultant chance of obtaining each choice from the individual preference profile (loss) becomes zero; i.e., the satisfaction of all players is appreciated while avoiding conflicts. Further, even in scenarios where zero-loss conflict-free joint decision-making is unachievable, we present approaches to derive joint decision-making that can accomplish the theoretical minimum loss while ensuring conflict-free choices. Numerical demonstrations are presented with several benchmarks.


---

## Body

## 1. Introduction

Since the industrial revolution, we have witnessed important technological advances; however, we are currently faced with issues such as the finiteness of resources, which has led to the need for developing strategies of competition or resource sharing [1, 2]. We need to consider the choices of other people or any entities and those of ours. In this regard, decision conflicts are a critical issue that needs to be addressed. For example, assume that many people or devices attempt to connect to the same mobile network simultaneously. In this case, the wireless resources available per person or device will become significantly smaller, and it will result in poor communication bandwidth or even zero connectivity attributable to congestion [3]. This example considers a case in which an individual suffers from choice conflict with others. Here, the division of resources among entities is allowed, but in other cases, a separable allocation to multiple entities is not permitted. As another example, we consider a draft in a professional football league. Each club has specific players to pick in the draft; however, in principle, only a single club can sign with one player. Thus, decision-making conflicts must be resolved. These examples highlight the importance of achieving individual satisfaction while avoiding conflict.Sharpley and Scarf proposed the top trading cycle (TTC) allocation algorithm [4] to address this problem. A typical example is a house-allocation problem; each of the n students ranked the houses in which they wanted to live from a list of n houses. In this scenario, the TTC allocates one house to each student. The solution provided by the TTC is known to be game-theoretic core-stable; that is, arbitrary numbers of students can swap houses with each other and still not obtain a better allocation than the current one. There are many other mechanisms that originate in TTC, which include those that allow indifference in preference profiles [5–7] and those where agents can be allocated fractions of houses [8].Although TTC works well when players have deterministic rankings, humans or artificial machines can also have probabilistic preferences. That is, unlike the house-allocation problem, an agent with probabilistic preferences would be unsatisfied by always receiving its top preference. Instead, over repeated allocations, the distribution of outcomes and their probabilistic preferences should be similar. Such probabilistic preferences can appear naturally in relation to the stochastic decision-making of humans. The multiarmed bandit (MAB) problem [9, 10] encompasses probabilistic preferences.In the MAB problem, one player repeatedly selects and draws one of the several slot machines based on a certain policy. The reward for each slot machine is generated stochastically based on a probability distribution that the player does not know a priori. The MAB problem aims to maximize the cumulative reward obtained by a player under such circumstances. First, the player draws machines, which include those that do not generate many rewards, to accurately estimate the probability distribution of the reward that each machine follows; this is referred to as exploration. However, the extensive drawing of the highest reward probability machine increases the cumulative reward after the player is confident in the estimation. This is known as exploitation. To successfully solve the MAB problem, it is necessary to strike a balance between exploration and exploitation, especially in a dynamically changing environment; this is called the exploration-exploitation dilemma [11].An example of probabilistic preferences can be observed in the context of the MAB problem. The softmax algorithm, a well-known stochastic decision-making method, is an efficient method to solve this problem [12]. If the empirical reward for each machine i at time t is μit, the probability that a player selects machine i is(1)sit=eμit/τ∑keμkt/τ.Here, τ represents the temperature, which controls the balance between exploration and exploitation. Thus, the player has a probabilistic preference at each time step about which machine to select and with what percentage.Furthermore, we can extend the MAB problem to a case involving multiple players, which is called the competitive MAB problem [13, 14]. In a competitive MAB problem, when multiple players simultaneously select the same machine and the machine generates a reward, the reward is distributed among the players. The aim is to maximize the collective rewards of players while ensuring equality [15]. Decision conflicts inhibit players from maximizing the total rewards in such scenarios.For example, wireless communications suffer from such difficulties, wherein the simultaneous usage of the same band by multiple devices results in the performance degradation of individual devices, as shown in Figure1. Players make a probabilistic decision to explore and exploit simultaneously because they do not know the speed of each bandwidth in advance (here, we assume that the speed changes probabilistically to reflect an uncertain environment). However, the line is shared if they choose the same bandwidth, and there is a decrease in the transmission speed.Figure 1
Internet connection through relays. Each player makes a probabilistic decision about which bandwidth to connect; however, when both select the same bandwidth, the line is shared, and there is a decrease in the transmission speed.For solving competitive MAB problems, Chauvet et al. theoretically and experimentally demonstrated the usefulness of quantum entanglement to avoid decision conflicts without direct communication [16, 17]. A powerful aspect of entanglement is that the optimization of a reward by one player leads to the optimization of the total rewards for the team; this is not easily achievable because if everyone attempts to draw the best machine, it can lead to decision conflicts that will diminish the total rewards in the competitive MAB problem. Further, Amakasu et al. proposed utilizing quantum interference such that the number of choices can be extended to an arbitrary number while perfectly avoiding decision conflicts [18]. A more general example is multiagent reinforcement learning [19, 20]. In this case, multiple agents can learn individually and make probabilistic choices while balancing exploration and exploitation at each time step. Successfully integrating these agents and making cooperative decisions without selection conflicts can help accelerate learning [21].Given such motivations and backgrounds, it is important to clarify how the probabilistic preferences of individual players can be accommodated while avoiding choice conflicts. The question is whether it is possible to satisfy all player preferences while eliminating decision conflicts; if so, what are the conditions for realizing such requirements?This study theoretically clarifies the condition under which joint decision-making probabilities exist such that the preference profiles of all players are satisfied perfectly. In other words, the condition that provides the loss (the deviation of the selection preference of each player from the resulting chance of obtaining each choice determined via the joint decision probabilities) becomes zero is clearly formulated. In addition, we derive joint decision-making probabilities that minimize the loss, even when such a condition is not satisfied.A related problem of satisfying the needs of multiple players is a type of game theory called satisfaction games [22, 23]. Here, a minimum utility threshold is defined for each player, and a joint strategy is defined as a satisfaction equilibrium if all players obtain utility above the threshold. Like in other game theories, the payoff and reward or utility for each player can be defined by joint actions in the satisfaction games; however, in our study, there is no such external payoff. Instead, we define satisfaction as the correspondence between players’ probabilistic preferences and the selection probability of each choice as a result of joint selection. In addition, players learn the optimal action by observing the outcomes of the environment and updating their actions in satisfaction games. However, in our study, we consider joint selection resulting from deliberation by players cooperating with each other rather than learning over multiple trials.The consensus reaching process is another field that is closely related to our research [24–26]. In this area, consensus reaching is achieved by aggregating the preferences of multiple individual players using simple methods, such as weighted sums, to obtain a collective preference, and then, by calculating the distance between the collective preference and individual preferences and by adjusting the individual preferences through feedback [27]. The players continue this loop until they reach consensus. Meanwhile, our study focuses not on modifying individual preferences but on the aggregation of the preferences of multiple players in this process.


## 2. Theory

### 2.1. Problem Formulation

This section introduces the formulation of the study problem. To begin with, we examine cases where the number of players or agents is two: Player A and Player B. There areN choices for each player; these choices are called arms in the literature on the MAB problem, where N is a natural number greater than or equal to two.Each player selects a choice probabilistically depending on his/her preference probability. Here, the preference of Player A is represented by(2)A=A1A2…AN.Similarly, the preference of player B is given by(3)B=B1B2…BN.These preferences have the typical properties of probabilities:(4)A1+A2+⋯+AN=B1+B2+⋯+BN=1,Ai≥0,Bi≥0i=1,2,…,N.The upper side of Figure2 schematically illustrates a scenario where players A and B each have their own preferences in a four-arm case.Figure 2
Problem settings. The sum of each row should be close to the corresponding preference of player A, and the sum of each column should be close to the corresponding preference of player B.Now, we introduce the joint selection probability matrix, which is given as(5)P=0p1,2⋯p1,Np2,10⋯⋮⋮⋮⋱⋮pN,1⋯⋯0.The nondiagonal elementpi,j, with i≠j, denotes the probability that player A selects arm i and player B selects arm j. The diagonal terms are all zero because we consider nonconflict choices. Here, the summation of pi,j over all is and js is unity and pi,j≥0.(6)∑i,jpi,j=1,pi,j≥0.Our interest is to findP that meets the preferences of both players A and B. We formulate the degree of satisfaction of the players to incorporate this perspective as indicated in the following way. By summing up pi,js row-by-row in the joint selection probability matrix, a preference profile given by(7)πAi=∑jpi,j,is obtained. πAi represents the probability that player A selects arm i as a result of the joint selection probability matrix P. We call πAi “satisfied preference” (the link with preference Ai will be discussed hereafter).(8)∑iπAi=1,holds based on the definition of the joint selection probability matrix. This structure is illustrated by the red-shaded elements in the second row of the joint selection probability matrix shown in Figure 2.Similarly, satisfied preferences along the columns ofP(9)πBj=∑ipi,j,represent the probability that player B selects arm j because of the joint selection probability matrix P.Our aim is to find the optimalpi,j, wherein(10)πAi≈Ai,πBj≈Bj,holds for all i=1,2,…,N and j=1,2,…,N; that is, the players’ preferences Ai,Bj are the same or close to the satisfied preferences πAi,πBj.We define lossL akin to an L2-norm to quantify the degree of satisfaction.(11)L=∑iπAi−Ai2+∑jπBj−Bj2,which comprises the sum of squares of the gap between the preferences and the satisfied preferences of the two players.We consider the scenario shown in Figure2 as an example. The preferences of players A and B are(12)A1=0.1,A2=0.2,A3=0.3,A4=0.4,B1=0.3,B2=0.2,B3=0.2,B4=0.3.Now, we consider the following joint selection probability matrixP.(13)P=0000.1000.10.100.200.10.300.10.By taking the sum of the first row, we can calculate the probability that player A chooses arm 1 as a result of this matrix.(14)πA1=0+0+0+0.1=0.1.Similarly, if we calculate all satisfied preferences, we obtain(15)πA1=0.1,πA2=0.2,πA3=0.3,πA4=0.4,πB1=0.3,πB2=0.2,πB3=0.2,πB4=0.3.All preferences are equal to the original preferences of the players, which implies that lossL is zero. In other words, this joint selection probability matrix P completely satisfies the preferences of the player.In the following sections, we prove that the loss defined previously can be zero; in other words, perfect satisfaction for the players can indeed be realized under certain conditions. In addition, even in cases where zero loss is not achievable, we can systematically derive a joint selection probability matrix that ensures a minimum loss.Now, we define the popularitySi for each arm and propose three theorems and one conjecture based on the values of Si.Definition 1.
PopularitySi is defined as the sum of the preferences of players A and B for arm i.(16)Si≔Ai+Bii=1,2,…,N.
Because preferencesAi and Bi are probabilities, it holds that(17)∑iSi=∑iAi+∑iBi=2.
Hereafter, the minimum loss is denoted byLmin.(18)Lmin=minPL.
Meanwhile, the loss function can be defined in other forms such as the Kullback–Leibler (KL) divergence, which is also known as relative entropy [28]. Extended discussions on such metrics should be considered in future studies; we consider that the fundamental structure of the problem under study will not change significantly.
Key notations adopted in this paper are summarized in Table1.Table 1
Summary of key notations.
NotationDescriptionNNumber of arms/choicesAi,BiPreference of player on armiπAi,πBiSatisfied preference; probability of each player selecting armi as a result of the joint selection probability matrixLLoss to measure the degree of satisfactionSiPopularity; sum of the preferences of players A and B for armiTTotal preference used in Section2.2; sum of the preference of each playerA^i,B^i,p^i,j,…Symbols used in the revised problem in Section2.2Ai†,Bi†,pi,j†,…Symbols used in the general problem in Section2.4


### 2.2. Theorem 1

#### 2.2.1. Statement

Theorem 1.
We assume that all popularitiesSi are smaller than or equal to one. Then, it is possible to construct a joint selection probability matrix that makes the loss L equal to zero.(19)∀i;Si≤1⇒Lmin=0.


#### 2.2.2. Auxiliary Lemma

To prove Theorem 1, we first prove a lemma in which the problem settings are modified slightly. In the original problem, we treated the preference of each player as a probability. In this modified problem, however, their preferences do not have to be probabilities as long as they are nonnegative, and the sum of the preferences for each player is given by a constantT, which we refer to as the total preference. Their preferences are called A^ and B^. We will put a hat over each notation to avoid confusion about which definition we are referring to between the original and modified problems.(20)A^=A^1A^2…A^N,B^=B^1B^2…B^N.(21)A^1+A^2+⋯+A^N=B^1+B^2+⋯+B^N=T,A^i≥0,B^i≥0i=1,2,…,N.We still refer to(22)P^=0p^1,2⋯p^1,Np^2,10⋯⋮⋮⋮⋱⋮p^N,1⋯⋯0.as a joint selection probability matrix, although technically, each p^i,j is no longer a probability but a ratio of each joint selection occurring, and the sum of all entries is T, instead of 1. The other notations are defined in a manner similar to the original problem.(23)Satisfied Preference:π^Ai=∑jp^i,j,π^Bj=∑ip^i,j,Loss:L^=∑i(π^Ai−A^i)2+∑j(π^Bj−B^j)2,L^min=minP^L^,Popularity:S^i=A^i+B^i.Lemma 1.
We assume that all popularitiesS^i are smaller than or equal to the total preference T. Then, it is possible to construct a joint selection probability matrix that makes the loss L^ equal to 0.(24)∀i;S^i≤T⇒L^min=0.Theorem 1 is a special case of Lemma 1 whenT=1.


#### 2.2.3. Outline of the Proof

We prove Lemma1 using mathematical induction. In Section 2.2.4, we show that Lemma 1 holds for N=2 and N=3. In Sections 2.2.5 and 2.2.6, we suppose that Lemma 1 has been proven for N arms, and then, we show that Lemma 1 also holds for N+1 arms. In Sections 2.2.5, we assume the existence of pi,js that satisfy certain conditions and prove that perfect satisfaction for the players is achievable using these pi,js. Then, in Section 2.2.6, we verify their existence.


#### 2.2.4. WhenN=2 and When N=3

WhenN=2,(25)S^1=S^2=T,is the only case in which the assumption of Lemma 1, i.e., ∀i;S^i≤T is fulfilled. Due to the constraint (21),(26)A^2=T−A^1,B^1=T−A^1,B^2=A^1.In this case,(27)P^=0A^1A^20,makes the loss equal to zero.WhenN=3, the loss becomes zero when we set the values in the joint selection probability matrix as(28)P^=0p^1,2−p^1,2+A^1T−p^1,2−A^3−B^30p^1,2−A^1+B^3p^1,2+A^3−B^2−p^1,2+B^20.The satisfied preferences for players A and B viaP^ result in A^1,A^2,A^3 and B^1,B^2,B^3, which perfectly match the preferences of players A and B, respectively.However, all elements inP^ must be nonnegative.(29)p^1,2≥0,−p^1,2+A^1≥0,T−p^1,2−A^3−B^3≥0,p^1,2−A^1+B^3≥0,p^1,2+A^3−B^2≥0,−p^1,2+B^2≥0.To summarize these inequalities, the following inequality holds:(30)max0,A^1−B^3,−A^3+B^2≤p^1,2≤minA^1,B^2,T−A^3−B^3.If a nonnegativep^1,2 that satisfies (30) exists, P^ given in (28) is a valid joint selection probability matrix, which makes the loss zero. In other words, if we can prove that p^1,2, which is in the range of (30), exists, regardless of A^ and B^, Lemma 1 holds for N=3.To prove that a nonnegativep^1,2 that satisfies (30) always exists, we consider the following three cases depending on the value of the left-hand term of (30). In each case, we show that the three candidates for the right-hand term of (30) are greater than the left-hand term.[Case 1] Whenmax0,A^1−B^3,−A^3+B^2=0.0≤A^1,0≤B^2 are evident from the definitions in (21). In addition, 0≤T−A^3−B^3 holds because of the assumption of lemma S^3=A^3+B^3≤T. Thus,(31)0≤minA^1,B^2,T−A^3−B^3.[Case 2] When max0,A^1−B^3,−A^3+B^2=A^1−B^3.First, the definition (21) guarantees the following:(32)A^1−B^3≤A^1.Next, using the assumption S^1=A^1+B^1≤T,(33)A^1−B^3≤T−B^1−B^3=B2.Finally,(34)A^1−B^3=T−A^2−A^3−B^3≤T−A^3−B^3.Therefore,(35)A^1−B^3≤minA^1,B^2,T−A^3−B^3.[Case 3] When max0,A^1−B^3,−A^3+B^2=−A^3+B^2.S^2=A^2+B^2≤T implies the following equation:(36)−A^3+B^2≤−A^3+T−A^2=A1.In addition, definition (21) guarantees −A^3+B^2≤B^2. Finally,(37)−A^3+B^2=−A^3+T−B^1−B^3≤T−A^3−B^3,holds because B^1≥0. Hence,(38)−A^3+B^2≤minA^1,B^2,T−A^3−B^3.From (31), (35), and (38) for any A^,B^,(39)max0,A^1−B^3,−A^3+B^2≤minA^1,B^2,T−A^3−B^3.Therefore, it is evident thatp^1,2 that satisfies (30) exists. Hence, P^ given in (28) is a valid joint selection probability matrix that makes the loss L^ zero.


#### 2.2.5. Induction

In this and the following sections, we suppose that Lemma1 has been proven to hold when there are N arms N≥3. Here, we show that Lemma 1 also holds for N+1 case. In the following argument, the arm with the lowest S^i is denoted as arm K.(40)minS^i=S^K.Now, we make the following assumption, which focuses only on the values in theKth row or Kth column.Assumption 1.
There existp^K,1,p^K,2,…,p^K,N+1,p^1,K,p^2,K,…,p^N+1,K that satisfy all of the following conditions (41)–(45).
The sum of theKth row is equal to A^K.(41)∑j=1N+1p^K,j=A^K.
The sum of theKth column is equal to B^K.(42)∑i=1N+1p^i,K=B^K.
The sum of thejth column without the Kth row is nonnegative.(43)∑i≠Kp^i,j≥0⇔p^K,j≤B^j,j=1,2,…,K−1,K+1,…,N+1.
The sum of theith row without the Kth column is nonnegative.(44)∑j≠Kp^i,j≥0⇔p^i,K≤A^i,i=1,2,…,K−1,K+1,…,N+1.
In the gray-shaded area of the joint selection probability matrix in (48), all remaining popularities are less than or equal to the remaining total preference. We note that S^K=minS^i.(45)A^i−p^i,K+B^i−p^K,i≤T−S^Ki=1,2,…,K−1,K+1,…,N+1.
First, we suppose that Assumption1 is valid and show the way to construct a joint selection probability matrix that makes the loss L^ zero, using these p^i,js. Later, we will prove that Assumption 1 is indeed correct.
Here, we show that, using thep^i,js assumed to exist in Assumption 1, we can make the loss L^ equal to zero. From conditions (41) and (42), πAK−AK2+πBK−BK2, which are terms in the definition of L^ regarding arm K, are zero.(46)πAK−AK2+πBK−BK2=0.
Next, we consider the loss for the remaining part of the joint selection probability matrix in the gray-shaded region described in (48), which is defined as(47)L^rem=L^−π^AK−A^K2+π^BK−B^K2.
(48)
L^rem represents the loss corresponding to a problem in which the preference setting is described in Table 2. A^i∗ and B^i∗ are defined as follows:(49)A^i∗=A^i−p^i,K,B^j∗=B^j−p^K,j.
Now, we prove that the optimalL^rem is zero. Ai∗ and Bi∗ fulfill the requirements for the preference; that is, the preferences need to be nonnegative because pi,Ks and pK,js follow (43) and (44) and the total preferences for both players are the same. In this section, we suppose we have proven that Lemma 1 holds when there are N arms; furthermore, because of (45), all remaining popularities S^i∗≔A^i∗+B^i∗=A^i−p^i,K+B^i−p^K,i are smaller than or equal to the remaining total preference T−S^K. Thus, Lemma 1 in the case of N arms verifies(50)minL^rem=0.
From (46) and (50), with p^K,1,p^K,2,…,p^K,N+1,p^1,K,p^2,K,…,p^N+1,K and the optimal p^i,js for the gray-shaded region,(51)L^min=minL^rem+π^AK−A^K2+π^BK−B^K2=0.
Therefore, if Assumption1 is correct, Lemma 1 holds for N+1 arms.Table 2
Preference setting followed by the remaining part of the joint selection probability matrix in the gray-shaded region.A^i∗=A^i−p^i,K,B^j∗=B^j−p^K,j.
PlayerArm 1Arm 2⋯ArmK−1ArmK+1⋯ArmN+1SumAA^1∗A^2∗⋯A^K−1∗A^K+1∗⋯A^N+1∗T−S^KBB^1∗B^2∗⋯B^K−1∗B^K+1∗⋯B^N+1∗T−S^K


#### 2.2.6. Verification of Assumption1

In this section, we prove that Assumption1 is correct. We refer to the arm with the highest S^i as arm VV≠K.(52)maxS^i=S^V.First, by contradiction, we prove that there is at most one arm that violates(53)S^i≤T−S^K,and if there is such an arm, arm V is the one that breaks (53). Note that all the other arms, which satisfy (53), follow (45).We assume that there are two arms that do not satisfy (53) (we call them arm V1 and arm V2), and we prove that this assumption leads to a contradiction.(54)S^V1>T−S^K,S^V2>T−SK.If we add each side,(55)S^V1+S^V2>2T−2S^K⇔2T<S^V1+S^V2+2S^K.AsminS^i=S^K and N≥3,(56)S^V1+S^V2+2S^K≤∑i=1N+1S^i=2T.Together with (55), we obtain the contradiction(57)2T<2T.Therefore, by contradiction, at most one arm violates (53). Such an arm follows(58)S^i>T−S^K,and has the highest S^i since other popularities are no bigger than T−S^K. We call it arm V so that maxS^i=S^V.Now, we can systematically determinep^i,js in the Kth row or the Kth column to show that Assumption 1 is correct; that is, p^i,js fulfill the conditions (41)–(45). We cannot arbitrarily fill in the values in the Kth row or the Kth column such that their sum is A^K and B^K, respectively; instead, we must consider the preferences of the other arms. (43)–(45) give us boundaries for p^K,js and p^i,Ks to exist. We must not only ensure that p^K,j and p^i,K do not exceed these boundaries, but we must also ensure that a sufficient probability is assigned to the most popular arm V; otherwise, the left-hand side of (45) can sometimes be greater than the right-hand side for arm V. We consider the following three cases depending on the size relation of A^K,B^V,B^K,A^V. For each case, it is possible to construct the optimal p^i,js that satisfy all conditions (41)–(45). Note that these three cases are collectively exhaustive.Case 1.A^K≤B^V and B^K≤A^VCase 2.A^K>B^VCase 3.B^K>A^VAs a reminder, armK represents the arm with the lowest popularity and arm V represents the arm with the highest popularity. For detailed construction procedures, see Appendix A.The previous three cases prove thatp^K,1,p^K,2,…,p^K,N+1,p^1,K,p^2,K,…,p^N+1,K which satisfy (41)–(45) always exist. In other words, Assumption 1 is indeed correct. Therefore, if we assume that Lemma 1 has been proven to hold for N arms, then Lemma 1 holds when there are N+1 arms.Hence, using mathematical induction, Lemma1 holds for any number of arms.


### 2.3. Theorem 2

#### 2.3.1. Statement

Here, we return to the original problem, where the preferences of players are probabilities. PopularitySi can still be greater than one because it is the sum of the preferences for each arm.Theorem 2.
If any value ofSi is greater than one, it is impossible to make the loss L equal to zero, and the minimum loss is given by(59)Lmin=N2N−1⋅SV−12.Note thatSV=maxSi. In a case where the Nth arm is the most popular, i.e., SV=SN>1, the following joint selection probability matrix is one of the matrices that minimize the loss:(60)P˜=00⋯0A1+ϵ00⋯0A2+ϵ⋮⋮⋱⋮⋮00⋯0AN−1+ϵB1+ϵB2+ϵ⋯BN−1+ϵ0,ϵ=SN−12N−1.


#### 2.3.2. Outline of the Proof

We can prove that the loss functionL is convex by showing that its Hessian is semidefinite. Appendix B provides the details of the proof. In Section 2.3.3, we rewrite the problem into an optimization problem with equality and inequality constraints and derive p˜i,js that satisfy the Karush–Kuhn–Tucker conditions [29, 30] (hereinafter, KKT conditions). In a convex optimization problem, where the objective function and all constraints are convex, points that satisfy the KKT conditions provide global optima [31]. Therefore, the optimal joint selection probability matrix comprises the aforementioned p˜i,js.


#### 2.3.3. KKT Conditions

We derive the optimal joint selection probability matrix and calculate the minimum loss. The flattened vector of a joint selection probability matrix is defined as(61)p=p1,2p1,3⋯p1,Np2,1p2,3⋯p2,N⋯pN,N−1T.Functionsh and gi,j are defined as(62)hp=∑i,jpi,j−1,gi,jp=−pi,ji≠j.The problem of minimizing the loss while satisfying the constraints can be written as(63)minpLps.t.hp=0,gi,jp≤0.Here,Lp is the loss corresponding to p. Because the objective function and constraints are all convex, p˜ that satisfies the following KKT conditions yields the global minimum.(64)∇Lp˜+∑i,jλi,j∇gi,jp˜+μ∇hp˜=0,λi,jgi,jp˜=0,λi,j≥0,gi,jp˜≤0,hp˜=0.The following parameters satisfy all conditions described in (64).(65)ϵ=SN−12N−1,μ=2N−2ϵ,λi,j=2Nϵ,i≠N∧j≠N,0,otherwise,p˜i,j=0,i≠N∧j≠N,Ai+ϵ,j=N,Bj+ϵ,i=N.See Appendix C for the verification of each condition.Hence,(66)P˜=00⋯0A1+ϵ00⋯0A2+ϵ⋮⋮⋱⋮⋮00⋯0AN−1+ϵB1+ϵB2+ϵ⋯BN−1+ϵ0,ϵ=SN−12N−1,provides a global optimum. The minimum loss is(67)Lmin=∑iπAi−Ai2+∑jπBj−Bj2=∑i=1N−1πAi−Ai2+∑j=1N−1πBj−Bj2+πAN−AN2+πBj−BN=∑i=1N−1ϵ2+∑j=1N−1ϵ2+−N−1ϵ2+−N−1ϵ2=N−1ϵ2+N−1ϵ2+N−12ϵ2+N−12ϵ2=N2N−1⋅SN−12.Note thatP˜ is an example of the global optima, and there could be other matrices that provide the same minimum loss.Therefore, Theorem2 was proven.


### 2.4. Theorem 3

Thus far, we presented two theorems concerning two players andN arms. In this section, we consider the case where M players exist and where M is greater than two. Let the players be called players A, B, C, etc. Moreover, the preference of player X for arm i is denoted by Xi†. As in the original problem,(68)∑iXi†=1,Xi†≥0,holds. The sum of the preferences for each arm is denoted as popularity:(69)Si†=Ai†+Bi†+Ci†+⋯.We definedx as the arm index selected by the xth player. Then, pd1,d2,…,dM† represents the joint selection probability of the xth player selecting arm dx. The collection of joint selection probabilities is called the joint selection probability tensor. The satisfied preference or resultant selection probability for player X comprises the sum of all probabilities of cases in which the xth player selects arm i:(70)πx†i=∑d1∉i∑d2∉i,d1⋯∑dM∉i,d1,d2,…,dM−1pd1,d2,…,dx=i,…,dM†⏟Summation without thexth player.The lossL† is defined as the sum of the squares of the gap between the preferences and the satisfied preferences.(71)L†=∑x∑iπx†i−Xi†2.Here, thexth player is called player X.


#### 2.4.1. Statement

Theorem 3.
Suppose that there areM players and N arms. If any Si† is greater than one, it is not possible to make the loss L† equal to zero.


#### 2.4.2. Proof by Contradiction

We suppose without loss of generality thatS1†>1. We first assume that it is possible to make the loss L† equal to zero and then prove that this leads to a contradiction. If the loss L† becomes zero, the following are required:(72)A1†=∑d2∉1∑d3∉1,d2⋯∑dM∉1,d2,d3,…,dM−1p1,d2,d3,…,dM†,(73)B1†=∑d1∉1∑d3∉d1,1⋯∑dM∉d1,1,d3,…,dM−1pd1,1,d3,…,dM†,(74)C1†=∑d1∉1∑d2∉d1,1⋯∑dM∉d1,d2,1,…,dM−1pd1,d2,1,…,dM†⋮.Terms that appear on the right-hand side of (72) are not identical to those on the right-hand side of (73) because d1≠1 in (73). Similarly, any term on the right-hand side of (72) is not identical to a variable on the right-hand side of all equations (73) and (74) …. Therefore, if we consider the sum of the right-hand sides of (72)–(74), …, it should be smaller than or equal to the sum of all elements in the joint selection probability tensor, which is 1.In contrast, if we take the sum of the left-hand sides of (72)–(74), …, we get A1†+B1†+C1†+⋯=S1†. Thus, by comparing both sides, we obtain S1†≤1. This result contradicts the assumption that S1†>1.Hence, with a proof by contradiction, Theorem3 holds for any number of players and arms.


### 2.5. Conjecture

The construction method introduced in Theorem1 is expected to be applicable to general M players. Here, we propose the following conjecture.Conjecture 1.
Suppose that there areM players and N arms. If all the values of Si† are less than or equal to one, it is possible to make the loss L† equal to zero.This conjecture seems true; however, thus far, the proof has not been completed in generality and is left for future studies.


## 2.1. Problem Formulation

This section introduces the formulation of the study problem. To begin with, we examine cases where the number of players or agents is two: Player A and Player B. There areN choices for each player; these choices are called arms in the literature on the MAB problem, where N is a natural number greater than or equal to two.Each player selects a choice probabilistically depending on his/her preference probability. Here, the preference of Player A is represented by(2)A=A1A2…AN.Similarly, the preference of player B is given by(3)B=B1B2…BN.These preferences have the typical properties of probabilities:(4)A1+A2+⋯+AN=B1+B2+⋯+BN=1,Ai≥0,Bi≥0i=1,2,…,N.The upper side of Figure2 schematically illustrates a scenario where players A and B each have their own preferences in a four-arm case.Figure 2
Problem settings. The sum of each row should be close to the corresponding preference of player A, and the sum of each column should be close to the corresponding preference of player B.Now, we introduce the joint selection probability matrix, which is given as(5)P=0p1,2⋯p1,Np2,10⋯⋮⋮⋮⋱⋮pN,1⋯⋯0.The nondiagonal elementpi,j, with i≠j, denotes the probability that player A selects arm i and player B selects arm j. The diagonal terms are all zero because we consider nonconflict choices. Here, the summation of pi,j over all is and js is unity and pi,j≥0.(6)∑i,jpi,j=1,pi,j≥0.Our interest is to findP that meets the preferences of both players A and B. We formulate the degree of satisfaction of the players to incorporate this perspective as indicated in the following way. By summing up pi,js row-by-row in the joint selection probability matrix, a preference profile given by(7)πAi=∑jpi,j,is obtained. πAi represents the probability that player A selects arm i as a result of the joint selection probability matrix P. We call πAi “satisfied preference” (the link with preference Ai will be discussed hereafter).(8)∑iπAi=1,holds based on the definition of the joint selection probability matrix. This structure is illustrated by the red-shaded elements in the second row of the joint selection probability matrix shown in Figure 2.Similarly, satisfied preferences along the columns ofP(9)πBj=∑ipi,j,represent the probability that player B selects arm j because of the joint selection probability matrix P.Our aim is to find the optimalpi,j, wherein(10)πAi≈Ai,πBj≈Bj,holds for all i=1,2,…,N and j=1,2,…,N; that is, the players’ preferences Ai,Bj are the same or close to the satisfied preferences πAi,πBj.We define lossL akin to an L2-norm to quantify the degree of satisfaction.(11)L=∑iπAi−Ai2+∑jπBj−Bj2,which comprises the sum of squares of the gap between the preferences and the satisfied preferences of the two players.We consider the scenario shown in Figure2 as an example. The preferences of players A and B are(12)A1=0.1,A2=0.2,A3=0.3,A4=0.4,B1=0.3,B2=0.2,B3=0.2,B4=0.3.Now, we consider the following joint selection probability matrixP.(13)P=0000.1000.10.100.200.10.300.10.By taking the sum of the first row, we can calculate the probability that player A chooses arm 1 as a result of this matrix.(14)πA1=0+0+0+0.1=0.1.Similarly, if we calculate all satisfied preferences, we obtain(15)πA1=0.1,πA2=0.2,πA3=0.3,πA4=0.4,πB1=0.3,πB2=0.2,πB3=0.2,πB4=0.3.All preferences are equal to the original preferences of the players, which implies that lossL is zero. In other words, this joint selection probability matrix P completely satisfies the preferences of the player.In the following sections, we prove that the loss defined previously can be zero; in other words, perfect satisfaction for the players can indeed be realized under certain conditions. In addition, even in cases where zero loss is not achievable, we can systematically derive a joint selection probability matrix that ensures a minimum loss.Now, we define the popularitySi for each arm and propose three theorems and one conjecture based on the values of Si.Definition 1.
PopularitySi is defined as the sum of the preferences of players A and B for arm i.(16)Si≔Ai+Bii=1,2,…,N.
Because preferencesAi and Bi are probabilities, it holds that(17)∑iSi=∑iAi+∑iBi=2.
Hereafter, the minimum loss is denoted byLmin.(18)Lmin=minPL.
Meanwhile, the loss function can be defined in other forms such as the Kullback–Leibler (KL) divergence, which is also known as relative entropy [28]. Extended discussions on such metrics should be considered in future studies; we consider that the fundamental structure of the problem under study will not change significantly.
Key notations adopted in this paper are summarized in Table1.Table 1
Summary of key notations.
NotationDescriptionNNumber of arms/choicesAi,BiPreference of player on armiπAi,πBiSatisfied preference; probability of each player selecting armi as a result of the joint selection probability matrixLLoss to measure the degree of satisfactionSiPopularity; sum of the preferences of players A and B for armiTTotal preference used in Section2.2; sum of the preference of each playerA^i,B^i,p^i,j,…Symbols used in the revised problem in Section2.2Ai†,Bi†,pi,j†,…Symbols used in the general problem in Section2.4


## 2.2. Theorem 1

### 2.2.1. Statement

Theorem 1.
We assume that all popularitiesSi are smaller than or equal to one. Then, it is possible to construct a joint selection probability matrix that makes the loss L equal to zero.(19)∀i;Si≤1⇒Lmin=0.


### 2.2.2. Auxiliary Lemma

To prove Theorem 1, we first prove a lemma in which the problem settings are modified slightly. In the original problem, we treated the preference of each player as a probability. In this modified problem, however, their preferences do not have to be probabilities as long as they are nonnegative, and the sum of the preferences for each player is given by a constantT, which we refer to as the total preference. Their preferences are called A^ and B^. We will put a hat over each notation to avoid confusion about which definition we are referring to between the original and modified problems.(20)A^=A^1A^2…A^N,B^=B^1B^2…B^N.(21)A^1+A^2+⋯+A^N=B^1+B^2+⋯+B^N=T,A^i≥0,B^i≥0i=1,2,…,N.We still refer to(22)P^=0p^1,2⋯p^1,Np^2,10⋯⋮⋮⋮⋱⋮p^N,1⋯⋯0.as a joint selection probability matrix, although technically, each p^i,j is no longer a probability but a ratio of each joint selection occurring, and the sum of all entries is T, instead of 1. The other notations are defined in a manner similar to the original problem.(23)Satisfied Preference:π^Ai=∑jp^i,j,π^Bj=∑ip^i,j,Loss:L^=∑i(π^Ai−A^i)2+∑j(π^Bj−B^j)2,L^min=minP^L^,Popularity:S^i=A^i+B^i.Lemma 1.
We assume that all popularitiesS^i are smaller than or equal to the total preference T. Then, it is possible to construct a joint selection probability matrix that makes the loss L^ equal to 0.(24)∀i;S^i≤T⇒L^min=0.Theorem 1 is a special case of Lemma 1 whenT=1.


### 2.2.3. Outline of the Proof

We prove Lemma1 using mathematical induction. In Section 2.2.4, we show that Lemma 1 holds for N=2 and N=3. In Sections 2.2.5 and 2.2.6, we suppose that Lemma 1 has been proven for N arms, and then, we show that Lemma 1 also holds for N+1 arms. In Sections 2.2.5, we assume the existence of pi,js that satisfy certain conditions and prove that perfect satisfaction for the players is achievable using these pi,js. Then, in Section 2.2.6, we verify their existence.


### 2.2.4. WhenN=2 and When N=3

WhenN=2,(25)S^1=S^2=T,is the only case in which the assumption of Lemma 1, i.e., ∀i;S^i≤T is fulfilled. Due to the constraint (21),(26)A^2=T−A^1,B^1=T−A^1,B^2=A^1.In this case,(27)P^=0A^1A^20,makes the loss equal to zero.WhenN=3, the loss becomes zero when we set the values in the joint selection probability matrix as(28)P^=0p^1,2−p^1,2+A^1T−p^1,2−A^3−B^30p^1,2−A^1+B^3p^1,2+A^3−B^2−p^1,2+B^20.The satisfied preferences for players A and B viaP^ result in A^1,A^2,A^3 and B^1,B^2,B^3, which perfectly match the preferences of players A and B, respectively.However, all elements inP^ must be nonnegative.(29)p^1,2≥0,−p^1,2+A^1≥0,T−p^1,2−A^3−B^3≥0,p^1,2−A^1+B^3≥0,p^1,2+A^3−B^2≥0,−p^1,2+B^2≥0.To summarize these inequalities, the following inequality holds:(30)max0,A^1−B^3,−A^3+B^2≤p^1,2≤minA^1,B^2,T−A^3−B^3.If a nonnegativep^1,2 that satisfies (30) exists, P^ given in (28) is a valid joint selection probability matrix, which makes the loss zero. In other words, if we can prove that p^1,2, which is in the range of (30), exists, regardless of A^ and B^, Lemma 1 holds for N=3.To prove that a nonnegativep^1,2 that satisfies (30) always exists, we consider the following three cases depending on the value of the left-hand term of (30). In each case, we show that the three candidates for the right-hand term of (30) are greater than the left-hand term.[Case 1] Whenmax0,A^1−B^3,−A^3+B^2=0.0≤A^1,0≤B^2 are evident from the definitions in (21). In addition, 0≤T−A^3−B^3 holds because of the assumption of lemma S^3=A^3+B^3≤T. Thus,(31)0≤minA^1,B^2,T−A^3−B^3.[Case 2] When max0,A^1−B^3,−A^3+B^2=A^1−B^3.First, the definition (21) guarantees the following:(32)A^1−B^3≤A^1.Next, using the assumption S^1=A^1+B^1≤T,(33)A^1−B^3≤T−B^1−B^3=B2.Finally,(34)A^1−B^3=T−A^2−A^3−B^3≤T−A^3−B^3.Therefore,(35)A^1−B^3≤minA^1,B^2,T−A^3−B^3.[Case 3] When max0,A^1−B^3,−A^3+B^2=−A^3+B^2.S^2=A^2+B^2≤T implies the following equation:(36)−A^3+B^2≤−A^3+T−A^2=A1.In addition, definition (21) guarantees −A^3+B^2≤B^2. Finally,(37)−A^3+B^2=−A^3+T−B^1−B^3≤T−A^3−B^3,holds because B^1≥0. Hence,(38)−A^3+B^2≤minA^1,B^2,T−A^3−B^3.From (31), (35), and (38) for any A^,B^,(39)max0,A^1−B^3,−A^3+B^2≤minA^1,B^2,T−A^3−B^3.Therefore, it is evident thatp^1,2 that satisfies (30) exists. Hence, P^ given in (28) is a valid joint selection probability matrix that makes the loss L^ zero.


### 2.2.5. Induction

In this and the following sections, we suppose that Lemma1 has been proven to hold when there are N arms N≥3. Here, we show that Lemma 1 also holds for N+1 case. In the following argument, the arm with the lowest S^i is denoted as arm K.(40)minS^i=S^K.Now, we make the following assumption, which focuses only on the values in theKth row or Kth column.Assumption 1.
There existp^K,1,p^K,2,…,p^K,N+1,p^1,K,p^2,K,…,p^N+1,K that satisfy all of the following conditions (41)–(45).
The sum of theKth row is equal to A^K.(41)∑j=1N+1p^K,j=A^K.
The sum of theKth column is equal to B^K.(42)∑i=1N+1p^i,K=B^K.
The sum of thejth column without the Kth row is nonnegative.(43)∑i≠Kp^i,j≥0⇔p^K,j≤B^j,j=1,2,…,K−1,K+1,…,N+1.
The sum of theith row without the Kth column is nonnegative.(44)∑j≠Kp^i,j≥0⇔p^i,K≤A^i,i=1,2,…,K−1,K+1,…,N+1.
In the gray-shaded area of the joint selection probability matrix in (48), all remaining popularities are less than or equal to the remaining total preference. We note that S^K=minS^i.(45)A^i−p^i,K+B^i−p^K,i≤T−S^Ki=1,2,…,K−1,K+1,…,N+1.
First, we suppose that Assumption1 is valid and show the way to construct a joint selection probability matrix that makes the loss L^ zero, using these p^i,js. Later, we will prove that Assumption 1 is indeed correct.
Here, we show that, using thep^i,js assumed to exist in Assumption 1, we can make the loss L^ equal to zero. From conditions (41) and (42), πAK−AK2+πBK−BK2, which are terms in the definition of L^ regarding arm K, are zero.(46)πAK−AK2+πBK−BK2=0.
Next, we consider the loss for the remaining part of the joint selection probability matrix in the gray-shaded region described in (48), which is defined as(47)L^rem=L^−π^AK−A^K2+π^BK−B^K2.
(48)
L^rem represents the loss corresponding to a problem in which the preference setting is described in Table 2. A^i∗ and B^i∗ are defined as follows:(49)A^i∗=A^i−p^i,K,B^j∗=B^j−p^K,j.
Now, we prove that the optimalL^rem is zero. Ai∗ and Bi∗ fulfill the requirements for the preference; that is, the preferences need to be nonnegative because pi,Ks and pK,js follow (43) and (44) and the total preferences for both players are the same. In this section, we suppose we have proven that Lemma 1 holds when there are N arms; furthermore, because of (45), all remaining popularities S^i∗≔A^i∗+B^i∗=A^i−p^i,K+B^i−p^K,i are smaller than or equal to the remaining total preference T−S^K. Thus, Lemma 1 in the case of N arms verifies(50)minL^rem=0.
From (46) and (50), with p^K,1,p^K,2,…,p^K,N+1,p^1,K,p^2,K,…,p^N+1,K and the optimal p^i,js for the gray-shaded region,(51)L^min=minL^rem+π^AK−A^K2+π^BK−B^K2=0.
Therefore, if Assumption1 is correct, Lemma 1 holds for N+1 arms.Table 2
Preference setting followed by the remaining part of the joint selection probability matrix in the gray-shaded region.A^i∗=A^i−p^i,K,B^j∗=B^j−p^K,j.
PlayerArm 1Arm 2⋯ArmK−1ArmK+1⋯ArmN+1SumAA^1∗A^2∗⋯A^K−1∗A^K+1∗⋯A^N+1∗T−S^KBB^1∗B^2∗⋯B^K−1∗B^K+1∗⋯B^N+1∗T−S^K


### 2.2.6. Verification of Assumption1

In this section, we prove that Assumption1 is correct. We refer to the arm with the highest S^i as arm VV≠K.(52)maxS^i=S^V.First, by contradiction, we prove that there is at most one arm that violates(53)S^i≤T−S^K,and if there is such an arm, arm V is the one that breaks (53). Note that all the other arms, which satisfy (53), follow (45).We assume that there are two arms that do not satisfy (53) (we call them arm V1 and arm V2), and we prove that this assumption leads to a contradiction.(54)S^V1>T−S^K,S^V2>T−SK.If we add each side,(55)S^V1+S^V2>2T−2S^K⇔2T<S^V1+S^V2+2S^K.AsminS^i=S^K and N≥3,(56)S^V1+S^V2+2S^K≤∑i=1N+1S^i=2T.Together with (55), we obtain the contradiction(57)2T<2T.Therefore, by contradiction, at most one arm violates (53). Such an arm follows(58)S^i>T−S^K,and has the highest S^i since other popularities are no bigger than T−S^K. We call it arm V so that maxS^i=S^V.Now, we can systematically determinep^i,js in the Kth row or the Kth column to show that Assumption 1 is correct; that is, p^i,js fulfill the conditions (41)–(45). We cannot arbitrarily fill in the values in the Kth row or the Kth column such that their sum is A^K and B^K, respectively; instead, we must consider the preferences of the other arms. (43)–(45) give us boundaries for p^K,js and p^i,Ks to exist. We must not only ensure that p^K,j and p^i,K do not exceed these boundaries, but we must also ensure that a sufficient probability is assigned to the most popular arm V; otherwise, the left-hand side of (45) can sometimes be greater than the right-hand side for arm V. We consider the following three cases depending on the size relation of A^K,B^V,B^K,A^V. For each case, it is possible to construct the optimal p^i,js that satisfy all conditions (41)–(45). Note that these three cases are collectively exhaustive.Case 1.A^K≤B^V and B^K≤A^VCase 2.A^K>B^VCase 3.B^K>A^VAs a reminder, armK represents the arm with the lowest popularity and arm V represents the arm with the highest popularity. For detailed construction procedures, see Appendix A.The previous three cases prove thatp^K,1,p^K,2,…,p^K,N+1,p^1,K,p^2,K,…,p^N+1,K which satisfy (41)–(45) always exist. In other words, Assumption 1 is indeed correct. Therefore, if we assume that Lemma 1 has been proven to hold for N arms, then Lemma 1 holds when there are N+1 arms.Hence, using mathematical induction, Lemma1 holds for any number of arms.


## 2.2.1. Statement

Theorem 1.
We assume that all popularitiesSi are smaller than or equal to one. Then, it is possible to construct a joint selection probability matrix that makes the loss L equal to zero.(19)∀i;Si≤1⇒Lmin=0.


## 2.2.2. Auxiliary Lemma

To prove Theorem 1, we first prove a lemma in which the problem settings are modified slightly. In the original problem, we treated the preference of each player as a probability. In this modified problem, however, their preferences do not have to be probabilities as long as they are nonnegative, and the sum of the preferences for each player is given by a constantT, which we refer to as the total preference. Their preferences are called A^ and B^. We will put a hat over each notation to avoid confusion about which definition we are referring to between the original and modified problems.(20)A^=A^1A^2…A^N,B^=B^1B^2…B^N.(21)A^1+A^2+⋯+A^N=B^1+B^2+⋯+B^N=T,A^i≥0,B^i≥0i=1,2,…,N.We still refer to(22)P^=0p^1,2⋯p^1,Np^2,10⋯⋮⋮⋮⋱⋮p^N,1⋯⋯0.as a joint selection probability matrix, although technically, each p^i,j is no longer a probability but a ratio of each joint selection occurring, and the sum of all entries is T, instead of 1. The other notations are defined in a manner similar to the original problem.(23)Satisfied Preference:π^Ai=∑jp^i,j,π^Bj=∑ip^i,j,Loss:L^=∑i(π^Ai−A^i)2+∑j(π^Bj−B^j)2,L^min=minP^L^,Popularity:S^i=A^i+B^i.Lemma 1.
We assume that all popularitiesS^i are smaller than or equal to the total preference T. Then, it is possible to construct a joint selection probability matrix that makes the loss L^ equal to 0.(24)∀i;S^i≤T⇒L^min=0.Theorem 1 is a special case of Lemma 1 whenT=1.


## 2.2.3. Outline of the Proof

We prove Lemma1 using mathematical induction. In Section 2.2.4, we show that Lemma 1 holds for N=2 and N=3. In Sections 2.2.5 and 2.2.6, we suppose that Lemma 1 has been proven for N arms, and then, we show that Lemma 1 also holds for N+1 arms. In Sections 2.2.5, we assume the existence of pi,js that satisfy certain conditions and prove that perfect satisfaction for the players is achievable using these pi,js. Then, in Section 2.2.6, we verify their existence.


## 2.2.4. WhenN=2 and When N=3

WhenN=2,(25)S^1=S^2=T,is the only case in which the assumption of Lemma 1, i.e., ∀i;S^i≤T is fulfilled. Due to the constraint (21),(26)A^2=T−A^1,B^1=T−A^1,B^2=A^1.In this case,(27)P^=0A^1A^20,makes the loss equal to zero.WhenN=3, the loss becomes zero when we set the values in the joint selection probability matrix as(28)P^=0p^1,2−p^1,2+A^1T−p^1,2−A^3−B^30p^1,2−A^1+B^3p^1,2+A^3−B^2−p^1,2+B^20.The satisfied preferences for players A and B viaP^ result in A^1,A^2,A^3 and B^1,B^2,B^3, which perfectly match the preferences of players A and B, respectively.However, all elements inP^ must be nonnegative.(29)p^1,2≥0,−p^1,2+A^1≥0,T−p^1,2−A^3−B^3≥0,p^1,2−A^1+B^3≥0,p^1,2+A^3−B^2≥0,−p^1,2+B^2≥0.To summarize these inequalities, the following inequality holds:(30)max0,A^1−B^3,−A^3+B^2≤p^1,2≤minA^1,B^2,T−A^3−B^3.If a nonnegativep^1,2 that satisfies (30) exists, P^ given in (28) is a valid joint selection probability matrix, which makes the loss zero. In other words, if we can prove that p^1,2, which is in the range of (30), exists, regardless of A^ and B^, Lemma 1 holds for N=3.To prove that a nonnegativep^1,2 that satisfies (30) always exists, we consider the following three cases depending on the value of the left-hand term of (30). In each case, we show that the three candidates for the right-hand term of (30) are greater than the left-hand term.[Case 1] Whenmax0,A^1−B^3,−A^3+B^2=0.0≤A^1,0≤B^2 are evident from the definitions in (21). In addition, 0≤T−A^3−B^3 holds because of the assumption of lemma S^3=A^3+B^3≤T. Thus,(31)0≤minA^1,B^2,T−A^3−B^3.[Case 2] When max0,A^1−B^3,−A^3+B^2=A^1−B^3.First, the definition (21) guarantees the following:(32)A^1−B^3≤A^1.Next, using the assumption S^1=A^1+B^1≤T,(33)A^1−B^3≤T−B^1−B^3=B2.Finally,(34)A^1−B^3=T−A^2−A^3−B^3≤T−A^3−B^3.Therefore,(35)A^1−B^3≤minA^1,B^2,T−A^3−B^3.[Case 3] When max0,A^1−B^3,−A^3+B^2=−A^3+B^2.S^2=A^2+B^2≤T implies the following equation:(36)−A^3+B^2≤−A^3+T−A^2=A1.In addition, definition (21) guarantees −A^3+B^2≤B^2. Finally,(37)−A^3+B^2=−A^3+T−B^1−B^3≤T−A^3−B^3,holds because B^1≥0. Hence,(38)−A^3+B^2≤minA^1,B^2,T−A^3−B^3.From (31), (35), and (38) for any A^,B^,(39)max0,A^1−B^3,−A^3+B^2≤minA^1,B^2,T−A^3−B^3.Therefore, it is evident thatp^1,2 that satisfies (30) exists. Hence, P^ given in (28) is a valid joint selection probability matrix that makes the loss L^ zero.


## 2.2.5. Induction

In this and the following sections, we suppose that Lemma1 has been proven to hold when there are N arms N≥3. Here, we show that Lemma 1 also holds for N+1 case. In the following argument, the arm with the lowest S^i is denoted as arm K.(40)minS^i=S^K.Now, we make the following assumption, which focuses only on the values in theKth row or Kth column.Assumption 1.
There existp^K,1,p^K,2,…,p^K,N+1,p^1,K,p^2,K,…,p^N+1,K that satisfy all of the following conditions (41)–(45).
The sum of theKth row is equal to A^K.(41)∑j=1N+1p^K,j=A^K.
The sum of theKth column is equal to B^K.(42)∑i=1N+1p^i,K=B^K.
The sum of thejth column without the Kth row is nonnegative.(43)∑i≠Kp^i,j≥0⇔p^K,j≤B^j,j=1,2,…,K−1,K+1,…,N+1.
The sum of theith row without the Kth column is nonnegative.(44)∑j≠Kp^i,j≥0⇔p^i,K≤A^i,i=1,2,…,K−1,K+1,…,N+1.
In the gray-shaded area of the joint selection probability matrix in (48), all remaining popularities are less than or equal to the remaining total preference. We note that S^K=minS^i.(45)A^i−p^i,K+B^i−p^K,i≤T−S^Ki=1,2,…,K−1,K+1,…,N+1.
First, we suppose that Assumption1 is valid and show the way to construct a joint selection probability matrix that makes the loss L^ zero, using these p^i,js. Later, we will prove that Assumption 1 is indeed correct.
Here, we show that, using thep^i,js assumed to exist in Assumption 1, we can make the loss L^ equal to zero. From conditions (41) and (42), πAK−AK2+πBK−BK2, which are terms in the definition of L^ regarding arm K, are zero.(46)πAK−AK2+πBK−BK2=0.
Next, we consider the loss for the remaining part of the joint selection probability matrix in the gray-shaded region described in (48), which is defined as(47)L^rem=L^−π^AK−A^K2+π^BK−B^K2.
(48)
L^rem represents the loss corresponding to a problem in which the preference setting is described in Table 2. A^i∗ and B^i∗ are defined as follows:(49)A^i∗=A^i−p^i,K,B^j∗=B^j−p^K,j.
Now, we prove that the optimalL^rem is zero. Ai∗ and Bi∗ fulfill the requirements for the preference; that is, the preferences need to be nonnegative because pi,Ks and pK,js follow (43) and (44) and the total preferences for both players are the same. In this section, we suppose we have proven that Lemma 1 holds when there are N arms; furthermore, because of (45), all remaining popularities S^i∗≔A^i∗+B^i∗=A^i−p^i,K+B^i−p^K,i are smaller than or equal to the remaining total preference T−S^K. Thus, Lemma 1 in the case of N arms verifies(50)minL^rem=0.
From (46) and (50), with p^K,1,p^K,2,…,p^K,N+1,p^1,K,p^2,K,…,p^N+1,K and the optimal p^i,js for the gray-shaded region,(51)L^min=minL^rem+π^AK−A^K2+π^BK−B^K2=0.
Therefore, if Assumption1 is correct, Lemma 1 holds for N+1 arms.Table 2
Preference setting followed by the remaining part of the joint selection probability matrix in the gray-shaded region.A^i∗=A^i−p^i,K,B^j∗=B^j−p^K,j.
PlayerArm 1Arm 2⋯ArmK−1ArmK+1⋯ArmN+1SumAA^1∗A^2∗⋯A^K−1∗A^K+1∗⋯A^N+1∗T−S^KBB^1∗B^2∗⋯B^K−1∗B^K+1∗⋯B^N+1∗T−S^K


## 2.2.6. Verification of Assumption1

In this section, we prove that Assumption1 is correct. We refer to the arm with the highest S^i as arm VV≠K.(52)maxS^i=S^V.First, by contradiction, we prove that there is at most one arm that violates(53)S^i≤T−S^K,and if there is such an arm, arm V is the one that breaks (53). Note that all the other arms, which satisfy (53), follow (45).We assume that there are two arms that do not satisfy (53) (we call them arm V1 and arm V2), and we prove that this assumption leads to a contradiction.(54)S^V1>T−S^K,S^V2>T−SK.If we add each side,(55)S^V1+S^V2>2T−2S^K⇔2T<S^V1+S^V2+2S^K.AsminS^i=S^K and N≥3,(56)S^V1+S^V2+2S^K≤∑i=1N+1S^i=2T.Together with (55), we obtain the contradiction(57)2T<2T.Therefore, by contradiction, at most one arm violates (53). Such an arm follows(58)S^i>T−S^K,and has the highest S^i since other popularities are no bigger than T−S^K. We call it arm V so that maxS^i=S^V.Now, we can systematically determinep^i,js in the Kth row or the Kth column to show that Assumption 1 is correct; that is, p^i,js fulfill the conditions (41)–(45). We cannot arbitrarily fill in the values in the Kth row or the Kth column such that their sum is A^K and B^K, respectively; instead, we must consider the preferences of the other arms. (43)–(45) give us boundaries for p^K,js and p^i,Ks to exist. We must not only ensure that p^K,j and p^i,K do not exceed these boundaries, but we must also ensure that a sufficient probability is assigned to the most popular arm V; otherwise, the left-hand side of (45) can sometimes be greater than the right-hand side for arm V. We consider the following three cases depending on the size relation of A^K,B^V,B^K,A^V. For each case, it is possible to construct the optimal p^i,js that satisfy all conditions (41)–(45). Note that these three cases are collectively exhaustive.Case 1.A^K≤B^V and B^K≤A^VCase 2.A^K>B^VCase 3.B^K>A^VAs a reminder, armK represents the arm with the lowest popularity and arm V represents the arm with the highest popularity. For detailed construction procedures, see Appendix A.The previous three cases prove thatp^K,1,p^K,2,…,p^K,N+1,p^1,K,p^2,K,…,p^N+1,K which satisfy (41)–(45) always exist. In other words, Assumption 1 is indeed correct. Therefore, if we assume that Lemma 1 has been proven to hold for N arms, then Lemma 1 holds when there are N+1 arms.Hence, using mathematical induction, Lemma1 holds for any number of arms.


## 2.3. Theorem 2

### 2.3.1. Statement

Here, we return to the original problem, where the preferences of players are probabilities. PopularitySi can still be greater than one because it is the sum of the preferences for each arm.Theorem 2.
If any value ofSi is greater than one, it is impossible to make the loss L equal to zero, and the minimum loss is given by(59)Lmin=N2N−1⋅SV−12.Note thatSV=maxSi. In a case where the Nth arm is the most popular, i.e., SV=SN>1, the following joint selection probability matrix is one of the matrices that minimize the loss:(60)P˜=00⋯0A1+ϵ00⋯0A2+ϵ⋮⋮⋱⋮⋮00⋯0AN−1+ϵB1+ϵB2+ϵ⋯BN−1+ϵ0,ϵ=SN−12N−1.


### 2.3.2. Outline of the Proof

We can prove that the loss functionL is convex by showing that its Hessian is semidefinite. Appendix B provides the details of the proof. In Section 2.3.3, we rewrite the problem into an optimization problem with equality and inequality constraints and derive p˜i,js that satisfy the Karush–Kuhn–Tucker conditions [29, 30] (hereinafter, KKT conditions). In a convex optimization problem, where the objective function and all constraints are convex, points that satisfy the KKT conditions provide global optima [31]. Therefore, the optimal joint selection probability matrix comprises the aforementioned p˜i,js.


### 2.3.3. KKT Conditions

We derive the optimal joint selection probability matrix and calculate the minimum loss. The flattened vector of a joint selection probability matrix is defined as(61)p=p1,2p1,3⋯p1,Np2,1p2,3⋯p2,N⋯pN,N−1T.Functionsh and gi,j are defined as(62)hp=∑i,jpi,j−1,gi,jp=−pi,ji≠j.The problem of minimizing the loss while satisfying the constraints can be written as(63)minpLps.t.hp=0,gi,jp≤0.Here,Lp is the loss corresponding to p. Because the objective function and constraints are all convex, p˜ that satisfies the following KKT conditions yields the global minimum.(64)∇Lp˜+∑i,jλi,j∇gi,jp˜+μ∇hp˜=0,λi,jgi,jp˜=0,λi,j≥0,gi,jp˜≤0,hp˜=0.The following parameters satisfy all conditions described in (64).(65)ϵ=SN−12N−1,μ=2N−2ϵ,λi,j=2Nϵ,i≠N∧j≠N,0,otherwise,p˜i,j=0,i≠N∧j≠N,Ai+ϵ,j=N,Bj+ϵ,i=N.See Appendix C for the verification of each condition.Hence,(66)P˜=00⋯0A1+ϵ00⋯0A2+ϵ⋮⋮⋱⋮⋮00⋯0AN−1+ϵB1+ϵB2+ϵ⋯BN−1+ϵ0,ϵ=SN−12N−1,provides a global optimum. The minimum loss is(67)Lmin=∑iπAi−Ai2+∑jπBj−Bj2=∑i=1N−1πAi−Ai2+∑j=1N−1πBj−Bj2+πAN−AN2+πBj−BN=∑i=1N−1ϵ2+∑j=1N−1ϵ2+−N−1ϵ2+−N−1ϵ2=N−1ϵ2+N−1ϵ2+N−12ϵ2+N−12ϵ2=N2N−1⋅SN−12.Note thatP˜ is an example of the global optima, and there could be other matrices that provide the same minimum loss.Therefore, Theorem2 was proven.


## 2.3.1. Statement

Here, we return to the original problem, where the preferences of players are probabilities. PopularitySi can still be greater than one because it is the sum of the preferences for each arm.Theorem 2.
If any value ofSi is greater than one, it is impossible to make the loss L equal to zero, and the minimum loss is given by(59)Lmin=N2N−1⋅SV−12.Note thatSV=maxSi. In a case where the Nth arm is the most popular, i.e., SV=SN>1, the following joint selection probability matrix is one of the matrices that minimize the loss:(60)P˜=00⋯0A1+ϵ00⋯0A2+ϵ⋮⋮⋱⋮⋮00⋯0AN−1+ϵB1+ϵB2+ϵ⋯BN−1+ϵ0,ϵ=SN−12N−1.


## 2.3.2. Outline of the Proof

We can prove that the loss functionL is convex by showing that its Hessian is semidefinite. Appendix B provides the details of the proof. In Section 2.3.3, we rewrite the problem into an optimization problem with equality and inequality constraints and derive p˜i,js that satisfy the Karush–Kuhn–Tucker conditions [29, 30] (hereinafter, KKT conditions). In a convex optimization problem, where the objective function and all constraints are convex, points that satisfy the KKT conditions provide global optima [31]. Therefore, the optimal joint selection probability matrix comprises the aforementioned p˜i,js.


## 2.3.3. KKT Conditions

We derive the optimal joint selection probability matrix and calculate the minimum loss. The flattened vector of a joint selection probability matrix is defined as(61)p=p1,2p1,3⋯p1,Np2,1p2,3⋯p2,N⋯pN,N−1T.Functionsh and gi,j are defined as(62)hp=∑i,jpi,j−1,gi,jp=−pi,ji≠j.The problem of minimizing the loss while satisfying the constraints can be written as(63)minpLps.t.hp=0,gi,jp≤0.Here,Lp is the loss corresponding to p. Because the objective function and constraints are all convex, p˜ that satisfies the following KKT conditions yields the global minimum.(64)∇Lp˜+∑i,jλi,j∇gi,jp˜+μ∇hp˜=0,λi,jgi,jp˜=0,λi,j≥0,gi,jp˜≤0,hp˜=0.The following parameters satisfy all conditions described in (64).(65)ϵ=SN−12N−1,μ=2N−2ϵ,λi,j=2Nϵ,i≠N∧j≠N,0,otherwise,p˜i,j=0,i≠N∧j≠N,Ai+ϵ,j=N,Bj+ϵ,i=N.See Appendix C for the verification of each condition.Hence,(66)P˜=00⋯0A1+ϵ00⋯0A2+ϵ⋮⋮⋱⋮⋮00⋯0AN−1+ϵB1+ϵB2+ϵ⋯BN−1+ϵ0,ϵ=SN−12N−1,provides a global optimum. The minimum loss is(67)Lmin=∑iπAi−Ai2+∑jπBj−Bj2=∑i=1N−1πAi−Ai2+∑j=1N−1πBj−Bj2+πAN−AN2+πBj−BN=∑i=1N−1ϵ2+∑j=1N−1ϵ2+−N−1ϵ2+−N−1ϵ2=N−1ϵ2+N−1ϵ2+N−12ϵ2+N−12ϵ2=N2N−1⋅SN−12.Note thatP˜ is an example of the global optima, and there could be other matrices that provide the same minimum loss.Therefore, Theorem2 was proven.


## 2.4. Theorem 3

Thus far, we presented two theorems concerning two players andN arms. In this section, we consider the case where M players exist and where M is greater than two. Let the players be called players A, B, C, etc. Moreover, the preference of player X for arm i is denoted by Xi†. As in the original problem,(68)∑iXi†=1,Xi†≥0,holds. The sum of the preferences for each arm is denoted as popularity:(69)Si†=Ai†+Bi†+Ci†+⋯.We definedx as the arm index selected by the xth player. Then, pd1,d2,…,dM† represents the joint selection probability of the xth player selecting arm dx. The collection of joint selection probabilities is called the joint selection probability tensor. The satisfied preference or resultant selection probability for player X comprises the sum of all probabilities of cases in which the xth player selects arm i:(70)πx†i=∑d1∉i∑d2∉i,d1⋯∑dM∉i,d1,d2,…,dM−1pd1,d2,…,dx=i,…,dM†⏟Summation without thexth player.The lossL† is defined as the sum of the squares of the gap between the preferences and the satisfied preferences.(71)L†=∑x∑iπx†i−Xi†2.Here, thexth player is called player X.


### 2.4.1. Statement

Theorem 3.
Suppose that there areM players and N arms. If any Si† is greater than one, it is not possible to make the loss L† equal to zero.


### 2.4.2. Proof by Contradiction

We suppose without loss of generality thatS1†>1. We first assume that it is possible to make the loss L† equal to zero and then prove that this leads to a contradiction. If the loss L† becomes zero, the following are required:(72)A1†=∑d2∉1∑d3∉1,d2⋯∑dM∉1,d2,d3,…,dM−1p1,d2,d3,…,dM†,(73)B1†=∑d1∉1∑d3∉d1,1⋯∑dM∉d1,1,d3,…,dM−1pd1,1,d3,…,dM†,(74)C1†=∑d1∉1∑d2∉d1,1⋯∑dM∉d1,d2,1,…,dM−1pd1,d2,1,…,dM†⋮.Terms that appear on the right-hand side of (72) are not identical to those on the right-hand side of (73) because d1≠1 in (73). Similarly, any term on the right-hand side of (72) is not identical to a variable on the right-hand side of all equations (73) and (74) …. Therefore, if we consider the sum of the right-hand sides of (72)–(74), …, it should be smaller than or equal to the sum of all elements in the joint selection probability tensor, which is 1.In contrast, if we take the sum of the left-hand sides of (72)–(74), …, we get A1†+B1†+C1†+⋯=S1†. Thus, by comparing both sides, we obtain S1†≤1. This result contradicts the assumption that S1†>1.Hence, with a proof by contradiction, Theorem3 holds for any number of players and arms.


## 2.4.1. Statement

Theorem 3.
Suppose that there areM players and N arms. If any Si† is greater than one, it is not possible to make the loss L† equal to zero.


## 2.4.2. Proof by Contradiction

We suppose without loss of generality thatS1†>1. We first assume that it is possible to make the loss L† equal to zero and then prove that this leads to a contradiction. If the loss L† becomes zero, the following are required:(72)A1†=∑d2∉1∑d3∉1,d2⋯∑dM∉1,d2,d3,…,dM−1p1,d2,d3,…,dM†,(73)B1†=∑d1∉1∑d3∉d1,1⋯∑dM∉d1,1,d3,…,dM−1pd1,1,d3,…,dM†,(74)C1†=∑d1∉1∑d2∉d1,1⋯∑dM∉d1,d2,1,…,dM−1pd1,d2,1,…,dM†⋮.Terms that appear on the right-hand side of (72) are not identical to those on the right-hand side of (73) because d1≠1 in (73). Similarly, any term on the right-hand side of (72) is not identical to a variable on the right-hand side of all equations (73) and (74) …. Therefore, if we consider the sum of the right-hand sides of (72)–(74), …, it should be smaller than or equal to the sum of all elements in the joint selection probability tensor, which is 1.In contrast, if we take the sum of the left-hand sides of (72)–(74), …, we get A1†+B1†+C1†+⋯=S1†. Thus, by comparing both sides, we obtain S1†≤1. This result contradicts the assumption that S1†>1.Hence, with a proof by contradiction, Theorem3 holds for any number of players and arms.


## 2.5. Conjecture

The construction method introduced in Theorem1 is expected to be applicable to general M players. Here, we propose the following conjecture.Conjecture 1.
Suppose that there areM players and N arms. If all the values of Si† are less than or equal to one, it is possible to make the loss L† equal to zero.This conjecture seems true; however, thus far, the proof has not been completed in generality and is left for future studies.


## 3. Numerical Demonstrations

This section introduces several baseline models that output a joint probability selection matrix for the probabilistic preferences of two players. Then, we show the extent to which the loss can be improved by using the construction method of the optimal joint probability selection matrix introduced in Theorems1 and 2 (henceforth, “the optimal satisfaction matrix”). The definitions of the notations, such as preference and loss, follow those in Section 2.1.


### 3.1. Baselines

#### 3.1.1. Uniform Random

In what we call the “uniform random” method, the resulting joint selection probability matrix is such that all elements are equal except for the diagonals, which are filled with zeros. In other words, decision conflicts never occur; however, the selection is determined completely randomly by the two players. If we consider the preference settings shown in Table3, the output of this method is(75)016161601616160.Table 3
Example of a preference setting.
PlayerArm 1Arm 2Arm 3A0.30.250.45B0.50.20.3


#### 3.1.2. Simultaneous Renormalization

In this method, the product of the preferences of both players is considered first. Then, the diagonals where decision conflicts occur are modified to zero, and finally, the whole joint selection probability matrix is renormalized so that the sum is 1. The formula used is(76)ri,j=Ai⋅Bj,i≠j,0,i=j,pi,j=ri,j∑i,jri,j.The joint selection probability matrix generated by this simultaneous renormalization method for the case in Table3 is(77)00.060.090.12500.0750.2250.090/0.665=00.0900.13530.188000.11280.33830.13530.


#### 3.1.3. Random Order

In what we call the “random order” method, the players first randomly determine in which order they will draw arms. This was inspired by the random priority mechanism proposed by Abdulkadiroğlu and Sönmez where preferences are deterministic [32]. Instead, we consider probabilistic preference profiles. Each player selects an arm based on a predetermined order; however, the arms already drawn by the previous players cannot be selected again. Thus, the selection probabilities for those arms are set to zero. Under the settings in Table 3, if we want to calculate p1,2, two possible orders are considered. In the first case, player A draws first. In this case, the joint selection probability is(78)0.3⋅0.21−0.5=0.12.In the other case, player B draws first, and the probability is(79)0.2⋅0.31−0.25=0.08.Therefore, considering the average,(80)p1,2=0.12+0.082=0.1.Similarly, we can calculate all joint selection probabilities, and the resulting matrix is(81)00.10.17180.167400.11510.32140.12430.


### 3.2. Performance Comparison

We compare the lossL of uniform random, simultaneous renormalization, random order, and the optimal satisfaction matrix. Four preference settings are examined to evaluate the performance of each method. Namely, the degree of satisfaction with the players’ preferences is investigated by comparing the loss L. ci is used as a normalization term to ensure that the sum of the preference is one.(1)
Arithmetic progression and same preference.(82)A1:A2:⋯:AN=B1:B2:⋯:BN=1:2:⋯:Nc1,c1=N+1N2.(2)
Modified geometric progression with common ratio 2 and same preference.(83)A1:A2:⋯:AN=B1:B2:⋯:BN=1:1:2:⋯:2N−2c2,c2=2N−1.(3)
Modified geometric progression with common ratio 2 and reversed preference.(84)A1:A2:⋯:AN=BN:BN−1:⋯:B1=1:1:2:⋯:2N−2c3,c3=2N−1.(4)
Geometric progression with common ratio 3 and same preference.(85)A1:A2:⋯:AN=B1:B2:⋯:BN=1:3:⋯:3N−1c4,c4=3N−12.In cases (1)–(3), the optimal satisfaction matrix achievesL=0 because ∀i;Si≤1, whereas in case (4), it is impossible to achieve L=0 because(86)SN=2⋅3N−1∑i=0N−13i=4⋅3N−13N−1>3N3N−1>1.ForN, the following numbers are used.(87)N=3,4,5,…,50.Figure3 summarizes loss L as a function of the number of arms N accomplished by each method.Figure 3
Loss comparison.Y axes are log scale for cases (1)–(3). Lines for the optimal satisfaction matrix overlap with X axes for these cases to show the loss is zero. (1) Arithmetic progression + same preference, (2) geometric progression with common ratio 2 + same preference, (3) geometric progression with common ratio 2 + reversed preference, and (4) geometric progression with common ratio 3 + same preference. For cases (1)–(3), the minimum loss is zero, while for case (4), it is greater than zero.
(a)(b)(c)(d)In all cases, the optimal satisfaction matrix performs the best, followed by random order, simultaneous renormalization, and uniform random. The result in case (1) shows that loss decreases with an increase in the number of arms for all methods. This trend is because our choice of loss is similar to theL2-norm. The absolute value of each preference Ai,Bi decreases with an increase in the number of arms.In the real world, the ratio of preference settings in case (2) is likely to appear more frequently than in case (1). For uniform random, simultaneous renormalization, and random order, the loss increases with the number of arms when the two players have the same preference. In contrast, the results show that the optimal satisfaction matrix consistently achieves 0-loss, and this underlines the importance of the construction method of the optimal joint selection probability matrix in the real world, where there are a vast number of choices.The result in case (3) shows that simultaneous renormalization and random order exhibit good accuracy together with the optimal satisfaction matrix. This result is due to the fact that the probability of decision conflicts happening is significantly smaller in this case (3), where the players have strong, reversed preferences. The diagonal terms are renormalized in simultaneous renormalization, which perturbs the other terms in the joint selection probability matrix. In case (3), these diagonal terms are smaller than in the other cases; therefore, perturbations to the other terms are reduced. In random order, the second player sets his/her preference for the arm drawn by the first player to zero; however, in the setup of case (3), this preference tends to be small because the first player is more likely to select an arm with a higher preference, which is an unfavored arm for the second player. This implies that the second player can select an arm based on a preference almost equal to his/her original preference.In case (4),SN is greater than 1, and thus, the optimal satisfaction matrix also does not achieve 0-loss. However, at approximately N=50, the loss for random order is approximately 1.2 times smaller than the loss for simultaneous renormalization, whereas the optimal loss is almost twice as small as the loss for random order.


## 3.1. Baselines

### 3.1.1. Uniform Random

In what we call the “uniform random” method, the resulting joint selection probability matrix is such that all elements are equal except for the diagonals, which are filled with zeros. In other words, decision conflicts never occur; however, the selection is determined completely randomly by the two players. If we consider the preference settings shown in Table3, the output of this method is(75)016161601616160.Table 3
Example of a preference setting.
PlayerArm 1Arm 2Arm 3A0.30.250.45B0.50.20.3


### 3.1.2. Simultaneous Renormalization

In this method, the product of the preferences of both players is considered first. Then, the diagonals where decision conflicts occur are modified to zero, and finally, the whole joint selection probability matrix is renormalized so that the sum is 1. The formula used is(76)ri,j=Ai⋅Bj,i≠j,0,i=j,pi,j=ri,j∑i,jri,j.The joint selection probability matrix generated by this simultaneous renormalization method for the case in Table3 is(77)00.060.090.12500.0750.2250.090/0.665=00.0900.13530.188000.11280.33830.13530.


### 3.1.3. Random Order

In what we call the “random order” method, the players first randomly determine in which order they will draw arms. This was inspired by the random priority mechanism proposed by Abdulkadiroğlu and Sönmez where preferences are deterministic [32]. Instead, we consider probabilistic preference profiles. Each player selects an arm based on a predetermined order; however, the arms already drawn by the previous players cannot be selected again. Thus, the selection probabilities for those arms are set to zero. Under the settings in Table 3, if we want to calculate p1,2, two possible orders are considered. In the first case, player A draws first. In this case, the joint selection probability is(78)0.3⋅0.21−0.5=0.12.In the other case, player B draws first, and the probability is(79)0.2⋅0.31−0.25=0.08.Therefore, considering the average,(80)p1,2=0.12+0.082=0.1.Similarly, we can calculate all joint selection probabilities, and the resulting matrix is(81)00.10.17180.167400.11510.32140.12430.


## 3.1.1. Uniform Random

In what we call the “uniform random” method, the resulting joint selection probability matrix is such that all elements are equal except for the diagonals, which are filled with zeros. In other words, decision conflicts never occur; however, the selection is determined completely randomly by the two players. If we consider the preference settings shown in Table3, the output of this method is(75)016161601616160.Table 3
Example of a preference setting.
PlayerArm 1Arm 2Arm 3A0.30.250.45B0.50.20.3


## 3.1.2. Simultaneous Renormalization

In this method, the product of the preferences of both players is considered first. Then, the diagonals where decision conflicts occur are modified to zero, and finally, the whole joint selection probability matrix is renormalized so that the sum is 1. The formula used is(76)ri,j=Ai⋅Bj,i≠j,0,i=j,pi,j=ri,j∑i,jri,j.The joint selection probability matrix generated by this simultaneous renormalization method for the case in Table3 is(77)00.060.090.12500.0750.2250.090/0.665=00.0900.13530.188000.11280.33830.13530.


## 3.1.3. Random Order

In what we call the “random order” method, the players first randomly determine in which order they will draw arms. This was inspired by the random priority mechanism proposed by Abdulkadiroğlu and Sönmez where preferences are deterministic [32]. Instead, we consider probabilistic preference profiles. Each player selects an arm based on a predetermined order; however, the arms already drawn by the previous players cannot be selected again. Thus, the selection probabilities for those arms are set to zero. Under the settings in Table 3, if we want to calculate p1,2, two possible orders are considered. In the first case, player A draws first. In this case, the joint selection probability is(78)0.3⋅0.21−0.5=0.12.In the other case, player B draws first, and the probability is(79)0.2⋅0.31−0.25=0.08.Therefore, considering the average,(80)p1,2=0.12+0.082=0.1.Similarly, we can calculate all joint selection probabilities, and the resulting matrix is(81)00.10.17180.167400.11510.32140.12430.


## 3.2. Performance Comparison

We compare the lossL of uniform random, simultaneous renormalization, random order, and the optimal satisfaction matrix. Four preference settings are examined to evaluate the performance of each method. Namely, the degree of satisfaction with the players’ preferences is investigated by comparing the loss L. ci is used as a normalization term to ensure that the sum of the preference is one.(1)
Arithmetic progression and same preference.(82)A1:A2:⋯:AN=B1:B2:⋯:BN=1:2:⋯:Nc1,c1=N+1N2.(2)
Modified geometric progression with common ratio 2 and same preference.(83)A1:A2:⋯:AN=B1:B2:⋯:BN=1:1:2:⋯:2N−2c2,c2=2N−1.(3)
Modified geometric progression with common ratio 2 and reversed preference.(84)A1:A2:⋯:AN=BN:BN−1:⋯:B1=1:1:2:⋯:2N−2c3,c3=2N−1.(4)
Geometric progression with common ratio 3 and same preference.(85)A1:A2:⋯:AN=B1:B2:⋯:BN=1:3:⋯:3N−1c4,c4=3N−12.In cases (1)–(3), the optimal satisfaction matrix achievesL=0 because ∀i;Si≤1, whereas in case (4), it is impossible to achieve L=0 because(86)SN=2⋅3N−1∑i=0N−13i=4⋅3N−13N−1>3N3N−1>1.ForN, the following numbers are used.(87)N=3,4,5,…,50.Figure3 summarizes loss L as a function of the number of arms N accomplished by each method.Figure 3
Loss comparison.Y axes are log scale for cases (1)–(3). Lines for the optimal satisfaction matrix overlap with X axes for these cases to show the loss is zero. (1) Arithmetic progression + same preference, (2) geometric progression with common ratio 2 + same preference, (3) geometric progression with common ratio 2 + reversed preference, and (4) geometric progression with common ratio 3 + same preference. For cases (1)–(3), the minimum loss is zero, while for case (4), it is greater than zero.
(a)(b)(c)(d)In all cases, the optimal satisfaction matrix performs the best, followed by random order, simultaneous renormalization, and uniform random. The result in case (1) shows that loss decreases with an increase in the number of arms for all methods. This trend is because our choice of loss is similar to theL2-norm. The absolute value of each preference Ai,Bi decreases with an increase in the number of arms.In the real world, the ratio of preference settings in case (2) is likely to appear more frequently than in case (1). For uniform random, simultaneous renormalization, and random order, the loss increases with the number of arms when the two players have the same preference. In contrast, the results show that the optimal satisfaction matrix consistently achieves 0-loss, and this underlines the importance of the construction method of the optimal joint selection probability matrix in the real world, where there are a vast number of choices.The result in case (3) shows that simultaneous renormalization and random order exhibit good accuracy together with the optimal satisfaction matrix. This result is due to the fact that the probability of decision conflicts happening is significantly smaller in this case (3), where the players have strong, reversed preferences. The diagonal terms are renormalized in simultaneous renormalization, which perturbs the other terms in the joint selection probability matrix. In case (3), these diagonal terms are smaller than in the other cases; therefore, perturbations to the other terms are reduced. In random order, the second player sets his/her preference for the arm drawn by the first player to zero; however, in the setup of case (3), this preference tends to be small because the first player is more likely to select an arm with a higher preference, which is an unfavored arm for the second player. This implies that the second player can select an arm based on a preference almost equal to his/her original preference.In case (4),SN is greater than 1, and thus, the optimal satisfaction matrix also does not achieve 0-loss. However, at approximately N=50, the loss for random order is approximately 1.2 times smaller than the loss for simultaneous renormalization, whereas the optimal loss is almost twice as small as the loss for random order.


## 4. Conclusion

In this study, we theoretically examined how to maximize the satisfaction of each player by designing joint selection probabilities properly while avoiding decision conflicts when there are multiple players with probabilistic preferences. The present study demonstrated how to accomplish conflict-free stochastic decision-making among multiple players, wherein the preference of each player is highly appreciated. We clarified the condition when the optimal joint selection probabilities perfectly eliminate the deviation of the resulting choice selection probabilities and the probabilistic preference of the player in two player,N-choice situations, which leads to what we call zero-loss realizations. Furthermore, even under circumstances wherein zero loss is unachievable, we showed how to construct, what we call, the optimal satisfaction matrix, and whose joint selection probabilities minimize the loss. Furthermore, we generalized the theory to M-player situations M≥3 and proved the conditions under which zero-loss joint selection was impossible. In addition, we numerically demonstrated the impact of the optimal satisfaction matrix by comparing several approaches that could provide conflict-free joint decision-making. The situation addressed in this study is very generic and can be widely applied to scenarios such as communication technology, multiagent reinforcement learning, and resource allocation, where multiple players make probabilistic choices, and choosing the same option is detrimental.There are still many interesting future topics, including the mathematical proof of the conjecture shown in this study, which discusses the condition of zero-loss conflict-free joint stochastic selection involving an arbitrary number of players. The detailed analysis of situations when we replace loss with other metrics such as KL divergence also remains to be explored. Furthermore, extending the discussions to external environments and not just player satisfaction will be important for practical applications. This study paves the way for multiagent conflict-free stochastic decision-making.



---

*Source: 2794839-2023-02-17.xml*