Improving Multi-agent Coordination by Learning to Estimate Contention

1 Introduction

One of the most relevant problems in multi-agent systems is finding an optimal allocation between agents, i.e., computing a maximum-weight matching, were edge weights correspond to the utility of each alternative. Many multi-agent coordination problems can be formulated as such. Example applications include role allocation (e.g., team formation [Gunn and Anderson, 2013]), task assignment (e.g., smart factories, or taxi-passenger matching [Danassis et al., 2019b; Varakantham et al., 2012]), resource allocation (e.g., parking/charging spaces for autonomous vehicles [Geng and Cassandras, 2013]), etc. What follows is applicable to any such scenario, but for concreteness we focus on the assignment problem (bipartite matching), one of the most fundamental combinatorial optimization problems [Munkres, 1957].

A significant challenge for any algorithm for the assignment problem emerges from the nature of real-world applications, which is often distributed and information-restrictive. Sharing plans, utilities, or preferences creates high overhead, and there is often a lack of responsiveness and/or communication between the participants [Stone et al., 2010]. Achieving fast convergence and high efficiency in such informationrestrictive settings is extremely challenging.

A recently proposed heuristic (ALMA [Danassis et al., 2019a]) was specifically designed to address the aforementioned challenges. ALMA is decentralized, completely uncoupled (agents are only aware of their own history), and requires no communication between the agents. Instead, agents make decisions locally, based on the contest for resources that they are interested in, and the agents that are interested in the same resources. As a result, in the realistic case where each agent is interested in a subset (of fixed size) of the total resources, ALMA's convergence time is constant in the total problem size. This condition holds by default in many real-world applications (e.g., resource allocation in urban environments), since agents only have a local (partial) knowledge of the world, and there is typically a cost associated with acquiring a resource. This lightweight nature of ALMA coupled with the lack of inter-agent communication, and the highly efficient allocations [Danassis et al., 2019b; Danassis et al., 2019a; Danassis et al., 2020], make it ideal for an on-device solution for large-scale intelligent systems (e.g., IoT devices, smart cities and intelligent infrastructure, industry 4.0, autonomous vehicles, etc.).

Despite ALMA's high performance in a variety of domains, it remains a heuristic; i.e., sub-optimal by nature. In this work, we introduce a learning element (ALMA-Learning)

pared to the optimal solution, while simultaneously increasing the fairness of the allocation. Specifically, in ALMA, while contesting for a resource, each agent will back-off with probability that depends on their own utility loss of switching to some alternative. ALMA-Learning improves upon ALMA by allowing agents to learn the chances that they will actually obtain the alternative option they consider when backing-off, which helps guide their search.

ALMA-Learning is applicable in repeated allocation games (e.g., self organization of intelligent infrastructure, autonomous mobility systems, etc.), but can be also applied as a negotiation protocol in one-shot interactions, where agents can simulate the learning process offline, before making their final decision. A motivating real-world application is presented in Section 3.2, where ALMA-Learning is applied to solve a large-scale meeting scheduling problem.

1.1 Our Contributions

(1) We introduce ALMA-Learning, a distributed algorithm for large-scale multi-agent coordination, focusing on scalability and on-device deployment in real-world applications.

1. We prove that ALMA-Learning converges.

(3) We provide a thorough evaluation in a variety of synthetic benchmarks and a real-world meeting scheduling problem. In all of them ALMA-Learning is able to quickly (as little as 64 training steps) reach allocations of high social welfare (less than 5% loss) and fairness (up to almost 10% lower inequality compared to the best performing baseline).

1.2 Discussion and RelatedWork

Multi-agent coordination can usually be formulated as a matching problem. Finding a maximum weight matching is one of the best-studied combinatorial optimization problems (see [Su, 2015; Lov´asz and Plummer, 2009]). There is a plethora of polynomial time algorithms, with the Hungarian algorithm [Kuhn, 1955] being the most prominent centralized one for the bipartite variant (i.e., the assignment problem). In real-world problems, a centralized coordinator is not always available, and if so, it has to know the utilities of all the participants, which is often not feasible. Decentralized algorithms (e.g., [Giordani et al., 2010]) solve this problem, yet they require polynomial computational time and polynomial number of messages - such as cost matrices [Ismail and Sun, 2017], pricing information [Zavlanos et al., 2008], or a basis of the LP [B¨urger et al., 2012], etc. (see also [Kuhn et al., 2016; Elkin, 2004] for general results in distributed approximability under only local information/computation).

While the problem has been 'solved' from an algorithmic perspective - having both centralized and decentralized polynomial algorithms - it is not so from the perspective of multiagent systems, for two key reasons: (1) complexity, and (2) communication. The proliferation of intelligent systems will give rise to large-scale, multi-agent based technologies. Algorithms for maximum-weight matching, whether centralized or distributed, have runtime that increases with the total problem size, even in the realistic case where agents are interested in a small number of resources. Thus, they can only handle problems of some bounded size. Moreover, they require a significant amount of inter-agent communication. As the number and diversity of autonomous agents continue to rise, differences in origin, communication protocols, or the existence of legacy agents will bring forth the need to collaborate without any form of explicit communication [Stone et al., 2010]. Most importantly though, communication between participants (sharing utility tables, plans, and preferences) creates high overhead. On the other hand, under reasonable assumptions about the preferences of the agents, ALMA's runtime is constant in the total problem size, while requiring no message exchange (i.e., no communication network) between the participating agents. The proposed approach, ALMA-Learning, preserves the aforementioned two properties of ALMA.

From the perspective of Multi-Agent Learning (MAL), the problem at hand falls under the paradigm of multi-agent reinforcement learning, where for example it can be modeled as a Multi-Armed Bandit (MAB) problem [Auer et al., 2002], or as a Markov Decision Process (MDP) and solved using a variant of Q-Learning [Busoniu et al., 2008]. In MAB problems an agent is given a number of arms (resources) and at each time-step has to decide which arm to pull to get the maximum expected reward. In Q-learning agents solve Bellman's optimality equation [Bellman, 2013] using an iterative approximation procedure so as to maximize some notion of expected cumulative reward. Both approaches have arguably been designed to operate in a more challenging setting, thus making them susceptible to many pitfalls inherent in MAL. For example, there is no stationary distribution, in fact, rewards depend on the joint action of the agents and since all agents learn simultaneously, this results in a moving-target problem. Thus, there is an inherent need for coordination in MAL algorithms, stemming from the fact that the effect of an agent's action depends on the actions of the other agents, i.e. actions must be mutually consistent to achieve the desired result. Moreover, the curse of dimensionality makes it difficult to apply such algorithms to large scale problems. ALMALearning solves both of the above challenges by relying on ALMA as a coordination mechanism for each stage of the repeated game. Another fundamental difference is that the aforementioned algorithms are designed to tackle the exploration/exploitation dilemma. A bandit algorithm for example will constantly explore, even if an agent has acquired his most preferred alternative. In matching problems, though, agents know (or have an estimate of) their own utilities. ALMALearning in particular, requires the knowledge of personal preference ordering and pairwise differences of utility (which are far easier to estimate than the exact utility table). The latter gives a great advantage to ALMA-Learning, since agents do not need to continue exploring after successfully claiming a resource, which stabilizes the learning process.

2 Proposed Approach: ALMA-Learning

2.1 The Assignment Problem

The assignment problem refers to finding a maximum weight matching in a weighted bipartite graph, G = {N ∪R, V}. In the studied scenario, N = {1, . . . ,N} agents compete to acquire R = {1, . . . ,R} resources. The weight of an edge (n, r) ∈ V represents the utility (un(r) ∈ [0, 1]) agent n receives by acquiring resource r. Each agent can acquire at most one resource, and each resource can be assigned to at most one agent. The goal is to maximize the social welfare (sum of utilities), i.e., maxx≥0 ∑(n,r)∈V un(r)xn,r, where x = (x1,1, . . . , xN,R), subject to ∑r|(n,r)∈V xn,r = 1, ∀n ∈ N , and ∑n|(n,r)∈V xn,r = 1, ∀r ∈ R.

2.2 Learning Rule

We begin by describing (a slightly modified version of) the ALMA heuristic of [Danassis et al., 2019a], which is used as a subroutine by ALMA-Learning. The pseudo-codes for ALMA and ALMA-Learning are presented in Algorithms 1 and 2, respectively. Both ALMA and ALMA-Learning are run independently and in parallel by all the agents (to improve readability, we have omitted the subscript n).

We make the following two assumptions: First, we assume (possibly noisy) knowledge of personal utilities by each agent. Second, we assume that agents can observe feedback from their environment to inform collisions and detect free resources. It could be achieved by the use of sensors, or by a single bit (0 / 1) feedback from the resource (note that these messages would be between the requesting agent and the resource, not between the participating agents themselves).

Agents Table 1: Motivating adversarial example: Inaccurate loss estimate.

Agent n3 backs-off with high probability when contesting for re-

source r1 assuming a good alternative, only to find resource r2 oc-

cupied.

Resources

r1 r2 r3

n1 1 0 0.5

n2 0 1

0

n3 1 0.9 0

(a)

Resources

r1 r2 r3

Algorithm 2 ALMA-Learning

n1 1 0.9 0

n2 0 1 0.9

2:

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

• for all r ∈ R do 3: rewardHistory[r].add(u(r))

5:

4:

6:

7:

8:

Resources EARNING

▷ Initializati

reward[r] ← rewardHistory[r].getMean()

rstart ← arg maxr reward[r]

loss[r] ← u(r) - u(rnext)

source according to agent n's preferences ≺n.

loss(i) = un(ri) - un(ri+1) and ri+1 is the next best re-

r1 r2 r3

Require: Sort resources (Rn ⊆ R) in decreasing order of utility

Agents

n3 1 0.9 0

(b)

The first example is given in Table 1a. Agent n3 backs-off

n1 1 0 0.5

n2 0 1 0

r0, . . . , rRn-1 under ≺n

9:

for t ∈ [1, . . . , T ] do

▷ T : Time horiz

with high probability (higher than agent n1) when contesting

rwon ← ALMA(rstart, loss[])

rewardHistory[rstart].add(u(rwon))

Require: rewardHistory[R][L], reward[R], loss[R]

1: procedure ALMA-LEARNING

2:

for resource r1 assuming a good alternative, only to find re-

10:

11:

n3 1 0.9 0

rewardHistory[r].add(u(r))

Table 2: Motivating adversarial example: Inaccurate reward expec-

tation. Agents n1 and n3 always start by attempting to acquire re-

ble 1: Motivating adversarial example: Inaccurate loss estimate.

ent n3 backs-off with high probability when contesting for re-

rce r1 assuming a good alternative, only to find resource r2 oc-

ied.

12:

▷ Initialization

source r2 occupied. Thus, n3 ends up matched with resource

r3. The social welfare of the final allocation is 2, which

for all r ∈ R do

Table 1: Adversarial examples: (1a) Inaccurate loss estimate. Agent

3:

source r1, reasoning that it is the most preferred one, yet each of

Table 1: Motivating adversarial example: Inaccurate loss estimate. Agent n3 backs-off with high

13:

▷ Run AL

reward[rstart] ← rewardHistory[rstart].getMea

is 20% worse than the optimal (where agents n1, n2, n3 are

14:

if u(rstart) - u(rwon) > 0 then

matched with resources r3, r2, r1, respectively, achieving a

probability when contesting for resource r1 assuming a good alternative, only to find resource r2

occupied.

n3 backs-off with high probability when contesting for resource r1

4:

assuming a good alternative, only to find resource r2 occupied.

them only wins r1 half of the times.

Resources

r1 r2 r3

5:

6:

loss[r] ← u(r) - u(rnext)

reward[r] ← rewardHistory[r].getMean()

15:

16:

17:

loss[rstart] ←

social welfare of 2.5). ALMA-Learning solves this problem

(1 - α)loss[rstart ] + α (u(rstart) - u(rwon)

if rstart! = rwon then

rstart ← arg maxr reward[r]

Resources

r1 r2 r3

by learning an empirical estimate of the loss an agent will in-

cur if he backs-off from a resource. In this case, agent n3 will

18:

▷ T : Time horizon

learn that his loss is not 1-0.9 = 0.1, but actually 1-0 = 1,

(1b) Inaccurate reward expectation. Agents n1 and n3 always start

by attempting to acquire resource r1, reasoning that it is the most

Resources

Resources

r1 r2 r3

n1 1 0.9 0

n2 0 1 0.9

7:

8:

preferred one, yet each of them only wins r1 half of the times.

Agents

Agents n1 1 0 0.5

r1 r2 r3

n2 0 1 0

n1 1 0 0.5

n2 0 1 0

n3 1 0.9 0

r1 r2 r3

Agents

9:

for t ∈ [1, . . . , T ] do

n1 1 0.9 0

n2 0 1 0.9

Agents

10:

18:

rwon ← ALMA(rstart, loss[])

rstart ← arg maxr reward[r]

▷ Run ALMA

ble 2: Motivating adversarial example: Inaccurate reward expecion. Agents n1 and n3 always start by attempting to acquire rerce r1, reasoning that it is the most preferred one, yet each of m only wins r1 half of the times. Resources n3 1 0.9 0 1: Motivating adversarial example: Inaccurate loss estimate. Agent n3 backs-off with high bility when contesting for resource r1 assuming a good alternative, only to find resource r2 ied. Resources 11: rewardHistory[rstart].add(u(rwon)) 12: reward[rstart] ← rewardHistory[rstart].getMean() 13: if u(rstart) - u(rwon) > 0 then 14: loss[rstart] ← 15: (1 - α)loss[rstart ] + α (u(rstart) - u(rwon)) 16: 17: if rstart! = rwon then n3 1 0.9 0 1: Motivating adversarial example: Inaccurate loss estimate. Agent n3 backs-off with high bility when contesting for resource r1 assuming a good alternative, only to find resource r2 ied. Resources (a) n3 1 0.9 0 Table 2: Motivating adversarial example: Inaccurate reward expectation. Agents n1 and n3 always start by attempting to acquire resource r1, reasoning that it is the most preferred one, yet each of them only wins r1 half of the times. (b) Figure 1: Adversarial examples: 1a Inaccurate loss estimate. Agent n3 backs-off with high probability when contesting for resource r1 assuming a good alternative, only to find resource r2 occupied. 1b where rnext is the next most preferred resource to r, accor ing to agent n's preferences ≺n (see line 5 of Alg. 2). Su sequently, for every stage game, agent n starts by selecti resource rstart, and ends up wining resource rwon. The lo of rstart is then updated according to the following averagi process, where α is the learning rate: For both ALMA, and ALMA-Learning, each agent sorts his available resources (possibly Rn ⊆ R) in decreasing utility (r0, . . . , ri, . . . , rRn-1) under his preference ordering ≺n. ALMA: ALtruistic MAtching Heuristic ALMA converges to a resource through repeated trials. Let and thus will not back-off in subsequent stage games, resulting in an optimal allocation. In another example (Table 1b, agents n1 and n3 always start by attempting to acquire resource r1, reasoning that it is the most preferred one. Yet, in a repeated game, each of them only wins r1 half of the times (for a social welfare 2, which is 28.5% worse than the optimal 2.8), thus, in expectation,

ents Y refers to yielding, and Ar refers to accessing resource r, A = {Y,Ar1 , . . . ,ArRn} denote the set of actions, where Inaccurate reward expectation. Agents n1 and n3 always start by attempting to acquire resource r1, reasoning that it is the most prer1 r2 r3

r1 r2 r3

and let g denote the agent's strategy. As long as an agent has

n1 1 0 0.5

Algorithm 2 ALMA-Learning

n2 0 1 0

n3 1 0.9 0

n1 1 0.9 0

n2 0 1 0.9

n1 1 0.9 0

n2 0 1 0.9

resource r1 has utility 0.5. ALMA-Learning solves this by

learning an empirical estimate of the reward of each resource.

rstart ← arg maxr reward[r]

ferred one, yet each of them only wins r1 half of the times.

n3 1 0.9 0

loss[rstart] ← (1 - α)loss[rstart] + α (u(rstart) - u(rwon)

Finally, the last condition (lines 17-18 of Alg. 2) ensur

where rnext is the next most preferred resource to r, accord-

In this case, after learning, either agent n1 or n3 (or both), will

start from resource r2. Agent n2 will back-off since he has a

Require: Sort resources (Rn ⊆ R) in decreasing order of utility r0, . . . , rRn-1 under ≺n

Agents

Require: rewardHistory[R][L], reward[R], loss[R]

not acquired a resource yet, at every time-step, there are two

Agents

possible scenarios: If g = Ar (strategy points to resource

n3 1 0.9 0

source will decrease, thus in the future the agent will switch

1: procedure ALMA-LEARNING

2:

(a)

(b)

that agents who have acquired resources of high preferen

stop exploring, thus stabilizing the learning process.

2: Motivating adversarial example: Inaccurate reward expectation. Agents n1 and n3 always

ing to agent n's preferences ≺n (see line 5 of Alg. 2). Sub-

r), then agent n attempts to acquire that resource. If there is

mple: Inaccurate loss estimate. Agent n3 backs-off with high

for all r ∈ R do sequently, for every stage game, agent n starts by selecting

2: Motivating adversarial example: Inaccurate reward expectation. Agents n1 and n3 always

good alternative, and the result will be the optimal allocation

where agents n1, n2, n3 are matched with resources r2, r3, r1

to an alternative starting resource, and (2) if an agent backs- Initialization

2.3 Convergence

in decreasing order of utility r0, . . . , rRn-1 under ≺n eward[R], loss[R] rstart ← ar maxr reward[r] for t ∈ [1, . . . , ] do : Time horizon rwon ← ALMA(rstart, loss[]) Run ALMA king him more reluctant to back-off in some future stage me. In more detail, ALMA-Learning learns and maintains following information 1 : (i) rewardHistory[R][L]: A 2D array. For each r ∈ R The final allocation of each stage game is controlled by ALMA, which means that even after convergence there can be contest for a resource, i.e., having more than one agent selecting the same starting resource. As we will demonrstart ← ar maxr reward[r] for t ∈ [1, . . . , ] do : Time horizon rwon ← ALMA(rstart, loss[]) Run ALMA (1-α)loss[rstart] α(u(rstart) -u(rwon)) 16: 17: if rstart = rwon then 18: rstart ← ar maxr reward[r] maintains an empirical estimate on the expected reward received by starting at resource r and continue playing according to Alg. 1. It is computed by averaging the reward history of the resource, i.e., ∀r ∈ R : reward[r] ← Theorem 1. There exists time-step tconv such that ∀t tconv : rn start (t) = rn start (tconv), where rn start (t) denot the starting resource rstart of agent n at the stage game time-step t. aggressiveness (willingness to back-off), and f (loss) = ⎧⎪⎨⎪⎩ 1 - ϵ, if loss ≤ ϵ ϵ, if 1 - loss ≤ ϵ (1) off from contesting resource r expecting low loss, only to find that all his high utility alternatives are already occupied, then his expected loss of resource r (loss[r]) will increase,

ource r1 assuming a good alternative, only to find resource r2 Resources ents r1 r2 r3 n1 1 0.9 0 n2 0 1 0.9 n3 1 0.9 0 ple: Inaccurate reward expectation. Agents n1 and n3 always rce r1, reasoning that it is the most preferred one, yet each of by attempting to acquire resource r1, reasoning that it is the most preferred one, yet each of only wins r1 half of the times. rithm 2 ALMA-Learning ire: Sort resources (Rn ⊆ R) in decreasing order of utility r0, . . . , rRn-1 under ≺n ire: rewardHistory[R][L], reward[R], loss[R] rocedure ALMA-LEARNING for all r ∈ R do Initialization rewardHistory[r].add(u(r)) reward[r] ← rewardHistory[r].getMean() loss[r] ← u(r) - u(rnext) ure 1: Adversarial examples: 1a Inaccurate loss estimate. Agent backs-off with high probability when contesting for resource r1 uming a good alternative, only to find resource r2 occupied. 1b ccurate reward expectation. Agents n1 and n3 always start by empting to acquire resource r1, reasoning that it is the most prered one, yet each of them only wins r1 half of the times. urce will decrease, thus in the future the agent will switch an alternative starting resource, and (2) if an agent backsfrom contesting resource r expecting low loss, only to d that all his high utility alternatives are already occupied, n his expected loss of resource r (loss[r]) will increase, resource rstart, and ends up wining resource rwon. The loss of rstart is then updated according to the following averaging process, where α is the learning rate: loss[rstart] ← (1 - α)loss[rstart] + α (u(rstart) - u(rwon)) Finally, the last condition (lines 17-18 of Alg. 2) ensures that agents who have acquired resources of high preference stop exploring, thus stabilizing the learning process. 2.3 Convergence Convergence of ALMA-Learning does not translate to a fixed allocation at each stage game. The system has converged when agents no longer switch their starting resource, rstart. by attempting to acquire resource r1, reasoning that it is the most preferred one, yet each of only wins r1 half of the times. rithm 2 ALMA-Learning ire: Sort resources (Rn ⊆ R) in decreasing order of utility r0, . . . , rRn-1 under ≺n ire: rewardHistory[R][L], reward[R], loss[R] rocedure ALMA-LEARNING for all r ∈ R do Initialization rewardHistory[r].add(u(r)) reward[r] ← rewardHistory[r].getMean() loss[r] ← u(r) - u(rnext) 3: rewardHistory[r].add(u(r)) 4: reward[r] ← rewardHistory[r].getMean() 5: loss[r] ← u(r) - u(rnext) 6: rstart ← ar maxr reward[r] 7: 8: for t ∈ [1, . . . , ] do : Time horizon 9: rwon ← ALMA(rstart, loss[]) Run ALMA 10: 11: rewardHistory[rstart].add(u(rwon)) 12: reward[rstart] ← rewardHistory[rstart].getMean() 13: if u(rstart) - u(rwon) > 0 then 14: loss[rstart] ← 15: off from contesting resource r expecting low loss, only to find that all his high utility alternatives are already occupied, then his expected loss of resource r (loss[r]) will increase, making him more reluctant to back-off in some future stage game. In more detail, ALMA-Learning learns and maintains the following information 1 : (i) rewardHistory[R][L]: A 2D array. For each r ∈ R it maintains the L most recent reward values received by agent n, i.e., the L most recent un(rwon), where rwon ← ALMA(r, loss[]). See line 11 of Alg. 2. The array is initialized to the utility of each resource (line 3 of Alg. 2). (ii) reward[R]: A 1D array. For each r ∈ R it Convergence of ALMA-Learning does not translate to a fix allocation at each stage game. The system has converg when agents no longer switch their starting resource, rsta The final allocation of each stage game is controlled ALMA, which means that even after convergence there c be contest for a resource, i.e., having more than one age selecting the same starting resource. As we will demo strate later, this translates to fairer allocations, since age with similar preferences can alternate between acquiring th most preferred resource. Due to luck of space we only pr vide a sketch of the proof. Please refer to the supplement. a collision, the colliding parties back-off (set g ← Y ) with some probability. Otherwise, if g = Y , the agent chooses another resource r for monitoring. If the resource is free, he sets g ← Ar. The back-off probability (P(·)) is computed individually and locally based on each agent's expected loss. If more than one agent compete for resource ri (step 8 of Alg. 1), each of them will back-off with probability that depends on their expected utility loss. The expected loss array is computed by ALMA-Learning and provided as input to ALMA. The actual back-off probability can be computed with any monotonically decreasing function on loss (see [Danassis et al., 2019a]). In this work we use P(loss) = f(loss)β , where β controls the (or r1, r3, r2), respectively. ALMA-Learning ALMA-Learning uses ALMA as a sub-routine, specifically as a coordination mechanism for each stage of the repeated game. Over time, ALMA-Learning learns which resource to select first (rstart) when running ALMA, and an accurate empirical estimate on the loss the agent will incur by backing-off (loss[]). By learning these two values agents take more informed decisions, specifically: (1) If an agent often loses the contest of his starting resource, the expected reward of that resource will decrease, thus in the future the agent will switch to an alternative starting resource, and (2) if an agent backs-

Initialization u(r)) istory[r].getMean() xt) [r] : Time horizon rewardHistory[rstart].add(u(rwon)) reward[rstart] ← rewardHistory[rstart].getMean() if u(rstart) - u(rwon) > 0 then loss[rstart] ← (1-α)loss[rstart] α(u(rstart) -u(rwon)) if rstart = rwon then maintains the L most recent reward values received by ent n, i.e., the L most recent un(rwon), where rwon ← MA(r, loss[]). See line 11 of Alg. 2. The array is initiald to the utility of each resource (line 3 of Alg. 2). (ii) reward[R]: A 1D array. For each r ∈ R it intains an empirical estimate on the expected reward reived by starting at resource r and continue playing acrding to Alg. 1. It is computed by averaging the restrate later, this translates to fairer allocations, since agents with similar preferences can alternate between acquiring their most preferred resource. Due to luck of space we only provide a sketch of the proof. Please refer to the supplement. Theorem 1. There exists time-step tconv such that ∀t > tconv : rn start (t) = rn start (tconv), where rn start (t) denotes the starting resource rstart of agent n at the stage game of rewardHistory[rstart].add(u(rwon)) reward[rstart] ← rewardHistory[rstart].getMean() if u(rstart) - u(rwon) > 0 then loss[rstart] ← (1-α)loss[rstart] α(u(rstart) -u(rwon)) if rstart = rwon then Table 2 presents the second example. Agents n1 and n3 always start by attempting to acquire resource 168 r1, reasoning that it is the most preferred one. Yet, in a repeated game, each of them only wins r1 169 half of the times (achieving social welfare 2, 28.5%worse than the optimal 2.8), thus, in expectation, 170 resource r1 has utility 0.5. ALMA-Learning solves this problem by learning an empirical estimate of 171 the reward of each resource. In this case, after learning, either agent n1 or n3 (or both), will start from 172 resource r2. Agent n2 will back-off since he has a good alternative, and the result will be the optimal rewardHistory[r].getMean(). See line 12 of Alg. 2. (iii) loss[R]: A 1D array. For each r ∈ R it maintains an empirical estimate on the loss in utility agent n incurs if he backs-off from the contest of resource r. The loss of each resource r is initialized to loss[r] ← un(r) - un(rnext), 1 We have omitted the subscript n from all the variables and arrays, but every agent maintains their own estimates. Proof. (Sketch) Theorem 2.1 of [Danassis et al., 2019 proves that ALMA (called at line 9 of Alg. 2) converg in polynomial time (in fact, under some assumptions, it co verges in constant time, i.e., each stage game converges constant time). In ALMA-Learning agents switch their sta ing resource only when the expected reward for the curre starting resource drops below the best alternative one, i. 1- loss, otherwise Agents that do not have good alternatives will be less likely to back-off and vice versa. The ones that do back-off select an alternative resource and examine its availability. The resource selection is performed in sequential order, starting from the most preferred resource (see step 3 of Alg. 1). Sources of Inefficiency. ALMA is a heuristic, i.e., submaking him more reluctant to back-off in some future stage game. In more detail, ALMA-Learning learns and maintains the following information 1 : (i) rewardHistory[R][L]: A 2D array. For each r ∈ R it maintains the L most recent reward values received by agent n, i.e., the L most recent un(rwon), where rwon ← ALMA(r, loss[]). See line 11 of Alg. 2. The array is initialized to the utility of each resource (line 3 of Alg. 2).

loss[]) Run ALMA add(u(rwon)) rdHistory[rstart].getMean() 0 then ] α(u(rstart) -u(rwon)) eward[r] rstart ← ar maxr reward[r] 2 presents the second example. Agents n1 and n3 always start by attempting to acquire resource asoning that it is the most preferred one. Yet, in a repeated game, each of them only wins r1 f the times (achieving social welfare 2, 28.5%worse than the optimal 2.8), thus, in expectation, rce r1 has utility 0.5. ALMA-Learning solves this problem by learning an empirical estimate of ward of each resource. In this case, after learning, either agent n1 or n3 (or both), will start from rce r2. Agent n2 will back-off since he has a good alternative, and the result will be the optimal ation where agents n1, n2, n3 are matched with resources r2, r3, r1 (or r1, r3, r2), respectively. rd history of the resource, i.e., ∀r ∈ R : reward[r] ← wardHistory[r].getMean(). See line 12 of Alg. 2. (iii) loss[R]: A 1D array. For each r ∈ R it maintains an pirical estimate on the loss in utility agent n incurs if he cks-off from the contest of resource r. The loss of each ource r is initialized to loss[r] ← un(r) - un(rnext), 1 We have omitted the subscript n from all the variables and ars, but every agent maintains their own estimates. time-step t. Proof. (Sketch) Theorem 2.1 of [Danassis et al., 2019a] proves that ALMA (called at line 9 of Alg. 2) converges in polynomial time (in fact, under some assumptions, it converges in constant time, i.e., each stage game converges in constant time). In ALMA-Learning agents switch their starting resource only when the expected reward for the current starting resource drops below the best alternative one, i.e., rstart ← ar maxr reward[r] 2 presents the second example. Agents n1 and n3 always start by attempting to acquire resource asoning that it is the most preferred one. Yet, in a repeated game, each of them only wins r1 f the times (achieving social welfare 2, 28.5%worse than the optimal 2.8), thus, in expectation, rce r1 has utility 0.5. ALMA-Learning solves this problem by learning an empirical estimate of ward of each resource. In this case, after learning, either agent n1 or n3 (or both), will start from rce r2. Agent n2 will back-off since he has a good alternative, and the result will be the optimal ation where agents n1, n2, n3 are matched with resources r2, r3, r1 (or r1, r3, r2), respectively. 173 allocation where agents n1, n2, n3 are matched with resources r2, r3, r1 (or r1, r3, r2), respectively. 174 2.1.2 ALMA-Learning: AMulti-Agent (Meta-)Learning Algorithm 175 ALMA-Learning uses ALMA as a sub-routine, specifically as a coordination mechanism for each 176 stage of the repeated game. Over time, ALMA-Learning learns which resource to select first (rstart) 177 when running ALMA, and an accurate empirical estimate on the loss it will incur by backing-off 178 (loss[]). By learning these two values, agents take more informed decisions, specifically: (1) If 179 an agent often loses the contest of his starting resource, the expected reward of that resource will 180 optimal by nature. It is worth understanding the sources of inefficiency, which in turn motivated ALMA-Learning. To do so, we provide a couple of adversarial examples. In the original ALMA algorithm, all agents start attempting to claim their most preferred resource, and back-off with probability that depends on their loss of switching to the immediate next best resource. Specifically, in the simplest case, the probability to back-off when contesting resource ri would be given by P(loss(i)) = 1 - loss(i), where (ii) reward[R]: A 1D array. For each r ∈ R it maintains an empirical estimate on the expected reward received by starting at resource r and continue playing according to Alg. 1. It is computed by averaging the reward history of the resource, i.e., ∀r ∈ R : reward[r] ← rewardHistory[r].getMean(). See line 12 of Alg. 2. 1 We have omitted the subscript n from all the variables and arrays, but every agent maintains their own estimates.

ALMA-Learning: A Multi-Agent (Meta-)Learning Algorithm ALMA-Learning: A Multi-Agent (Meta-)Learning Algorithm 5 127

Agents n1 and n3 always start by attempting to acquire resource erred one. Yet, in a repeated game, each of them only wins r1 lfare 2, 28.5%worse than the optimal 2.8), thus, in expectation, earning solves this problem by learning an empirical estimate of A-Learning uses ALMA as a sub-routine, specifically as a coordination mechanism for each of the repeated game. Over time, ALMA-Learning learns which resource to select first (rstart) running ALMA, and an accurate empirical estimate on the loss it will incur by backing-off A-Learning uses ALMA as a sub-routine, specifically as a coordination mechanism for each of the repeated game. Over time, ALMA-Learning learns which resource to select first (rstart) running ALMA, and an accurate empirical estimate on the loss it will incur by backing-off

Agents

Algorithm 1 ALMA: Altruistic Matching Heuristic.

Require: Sort resources (Rn ⊆ R) in decreasing order of utility r0, . . . , rRn-1 under ≺n 1: procedure ALMA(rstart, loss[R]) 2: Initialize g ← Arstart 3: Initialize current ← -1 4: Initialize converged ← F alse 5: while !converged do 6: if g = Ar then 7: Agent n attempts to acquire r 8: if Collision(r) then 9: Back-off (set g ← Y ) with prob. P(loss[r]) 10: else 11: converged ← T rue 12: else (g = Y ) 13: current ← (current + 1) mod R 14: Agent n monitors r ← rcurrent. 15: if Free(r) then set g ← Ar 16: return r, such that g = Ar

(iii) loss[R]: A 1D array. For each r ∈ R it maintains an empirical estimate on the loss in utility agent n incurs if he backs-off from the contest of resource r. The loss of each resource r is initialized to loss[r] ← un(r) - un(rnext), where rnext is the next most preferred resource to r, according to agent n's preferences ≺n (see line 5 of Alg. 2). Subsequently, for every stage game, agent n starts by selecting resource rstart, and ends up winning resource rwon. The loss of rstart is then updated according to the following averaging process, where α is the learning rate:

Finally, the last condition (lines 17-18 of Alg. 2) ensures that agents who have acquired resources of high preference stop exploring, thus stabilizing the learning process.

2.3 Convergence

Convergence of ALMA-Learning does not translate to a fixed allocation at each stage game. The system has converged when agents no longer switch their starting resource, rstart. The final allocation of each stage game is controlled by ALMA, which means that even after convergence there can be contest for a resource, i.e., having more than one agent selecting the same starting resource. As we will demonstrate later, this translates to fairer allocations, since agents with similar preferences can alternate between acquiring their most preferred resource.

Theorem 1. There exists time-step tconv such that ∀t > tconv : rn start (t) = rn start (tconv), where rn start (t) denotes the starting resource rstart of agent n at the stage game of time-step t.

Proof. (Sketch; see [Danassis et al., 2021]) Theorem 2.1 of [Danassis et al., 2019a] proves that ALMA (called at line 9 of Alg. 2) converges in polynomial time (in fact, under some assumptions, it converges in constant time, i.e., each stage game converges in constant time). In ALMA-Learning agents switch their starting resource only when the expected reward for the current starting resource drops below the best alternative one, i.e., for an agent to switch from rstart to r′start , it

Algorithm 2 ALMA-Learning

Require: Sort resources (Rn ⊆ R) in decreasing order of utility r0, . . . , rRn-1 under ≺n Require: rewardHistory[R][L], reward[R], loss[R] 1: procedure ALMA-LEARNING 2: for all r ∈ R do ▷ Initialization 3: rewardHistory[r].add(u(r)) 4: reward[r] ← rewardHistory[r].getMean() 5: loss[r] ← u(r) - u(rnext) 6: rstart ← arg maxr reward[r] 7: 8: for t ∈ [1, . . . , T ] do ▷ T : Time horizon 9: rwon ← ALMA(rstart, loss[]) ▷ Run ALMA 10: 11: rewardHistory[rstart].add(u(rwon)) 12: reward[rstart] ← rewardHistory[rstart].getMean() 13: if u(rstart) - u(rwon) > 0 then 14: loss[rstart] ← 15: (1 - α)loss[rstart ] + α (u(rstart) - u(rwon)) 16: 17: if rstart ̸= rwon then 18: rstart ← arg maxr reward[r]

has to be that reward[rstart] < reward[r′start ]. Given that utilities are bounded in [0, 1], there is a maximum, finite number of switches until rewardn[r] = 0, ∀r ∈ R, ∀n ∈ N. In that case, the problem is equivalent to having N balls thrown randomly and independently into N bins (since R = N). Since both R, N are finite, the process will result in a distinct allocation in finite steps with probability 1.

3 Evaluation

We evaluate ALMA-Learning in a variety of synthetic benchmarks and a meeting scheduling problem based on real data from [Romano and Nunamaker, 2001]. Error bars representing one standard deviation (SD) of uncertainty.

Fairness. The usual predicament of efficient allocations is that they assign the resources only to a fixed subset of agents, which leads to an unfair result. Consider the simple example of Table 2. Both ALMA (with higher probability) and any optimal allocation algorithm will assign the coveted resource r1 to agent n1, while n3 will receive utility 0. But, using ALMA-Learning, agents n1 and n3 will update their expected loss for resource r1 to 1, and randomly acquire it between stage games, increasing fairness. Recall that convergence for ALMA-Learning does not translate to a fixed allocation at each stage game. To capture the fairness of this 'mixed' allocation, we report the average fairness on 32 evaluation time-steps that follow the training period.

To measure fairness, we used the Gini coefficient [Gini, 1912]. An allocation x = (x1, . . . , xN)⊤ is fair iff G(x) = 0, where: G(x) = (∑Nn=1 ∑Nn′=1 |xn - xn′ |)/(2N ∑Nn=1 xn)

3.1 Test Case #1: Synthetic Benchmarks

Setting. We present results on three benchmarks:

• (a) Map: Consider a Cartesian map on which the agents and resources are randomly distributed. The utility of agent n

Agents n3 1 0.75 ϵ → 0

Resources
	r1	r2	r3
n1	1	0.5	0
n2	0	1	0
n3	1	0.75	ϵ 0

Table 2: Adversarial example: Unfair allocation. Both ALMA (with higher probability) and any optimal allocation algorithm will assign the coveted resource r1 to agent n1, while n3 will receive utility 0.

	Greedy	ALMA	ALMA-Learning
(a) Map	1.51%-18.71%	0.00%-9.57%	0.00%-0.89%
(b) Noisy	8.13%-12.86%	2.96%-10.58%	1.34%-2.26%
(c) Binary

(c) Binary 0.10%-14.70% 0.00%-16.88% 0.00%-0.39%

Table 3: Range of the average loss (%) in social welfare compared the the (centralized) optimal for the three different benchmarks.

for acquiring resource r is proportional to the inverse of their distance, i.e., un(r) = 1/dn,r. Let dn,r denote the Manhattan distance. We assume a grid length of size √4 × N.

(c) Binary Utilities: This corresponds to each agent being indifferent to acquiring any resource amongst his set of desired resources, i.e., un(r) is randomly assigned to 0 or 1.

• (b) Noisy Common Utilities: This pertains to an anticoordination scenario, i.e., competition between agents with similar preferences. We model the utilities as: ∀n, n′ ∈ N , |un(r)-un′ (r)| ≤ noise, where the noise is sampled from a zero-mean Gaussian distribution, i.e., noise ∼ N(0, σ2 ).

Baselines. We compare against: (i) the Hungarian algorithm [Kuhn, 1955], which computes a maximum-weight matching in a bipartite graphs, (ii) ALMA [Danassis et al., 2019a], and (iii) the Greedy algorithm, which goes through the agents randomly, and assigns them their most preferred, unassigned resource.

Results. We begin with the loss in social welfare. Figure 1a depicts the results for the Map test-case, while Table 3 aggregates all three test-cases 2 . ALMA-Leaning reaches nearoptimal allocations (less than 2.5% loss), in most cases in just 32-512 training time-steps. The exception is the Noisy Common Utilities test-case, where the training time was slightly higher. Intuitively we believe that this is because ALMA already starts with a near optimal allocation (especially for R > 256), and given the high similarity on the agent's utility tables (especially for σ = 0.1), it requires a lot of fine-tuning to improve the result.

Moving on to fairness, ALMA-Leaning achieves the most fair allocations in all of the test-cases. As an example, Figure 1b depicts the Gini coefficient for the Map test-case. ALMALearning's Gini coefficient is -18% to -90% lower on average (across problem sizes) than ALMA's, -24% to -93% lower than Greedy's, and -0.2% to -7% lower than Hungarian's.

2 For the the Noisy Common Utilities test-case, we report results for σ = 0.1; which is the worst performing scenario for ALMALearning. Similar results were obtained for σ = 0.2 and σ = 0.4.

(a) Relative Difference in SW

• (b) Gini Index (lower is better)

Figure 1: Map test-case. Results for increasing number of resources ([2, 1024], x-axis in log scale), and N = R. ALMA-Learning was trained for 512 time-steps.

3.2 Test Case #2: Meeting Scheduling

Motivation. The problem of scheduling a large number of meetings between multiple participants is ubiquitous in everyday life [Nigam and Srivastava, 2020; Ottens et al., 2017; Zunino and Campo, 2009; Maheswaran et al., 2004; BenHassine and Ho, 2007; Hassine et al., 2004; Crawford and Veloso, 2005; Franzin et al., 2002]. The advent of social media brought forth the need to schedule large-scale events, while the era of globalization and the shift to working-fromhome require business meetings to account for participants with diverse preferences (e.g., different timezones).

Meeting scheduling is an inherently decentralized problem. Traditional approaches (e.g., distributed constraint optimization [Ottens et al., 2017; Maheswaran et al., 2004]) can only handle a bounded, small number of meetings. Interdependences between meetings' participants can drastically increase the complexity. While there are many commercially available electronic calendars (e.g., Doodle, Google calendar, Microsoft Outlook, Apple's Calendar, etc.), none of these products is capable of autonomously scheduling meetings, taking into consideration user preferences and availability.

While the problem is inherently online, meetings can be aggregated and scheduled in batches, similarly to the approach for tackling matchings in ridesharing platforms [Danassis et al., 2019b]. In this test-case, we map meeting scheduling to an allocation problem and solve it using ALMA and ALMA-Learning. This showcases an application were ALMA-Learning can be used as a negotiation protocol.

Modeling. Let E = {E1, . . . ,En} denote the set of events and P = {P1, . . . , Pm} the set of participants. To formulate the participation, let part : E → 2P , where 2P denotes the power set of P. We further define the variables days and slots to denote the number of days and time slots per day of our calendar (e.g., days = 7, slots = 24). In order to add length to each event, we define an additional function len : E → N. Participants' utilities are given by:

Mapping the above to the assignment problem of Section 2.1, we would have the set of (day, slot) tuples to correspond to R, while each event is represented by one event agent (that aggregates the participant preferences), and the set of which would correspond to N .

Baselines. We compare against four baselines: (a) We used the IBM ILOG CP optimizer [Laborie et al., 2018] to formulate and solve the problem as a CSP 3 . An additional benefit of this solver is that it provides an upper bound for the optimal solution (which is infeasible to compute). (b) Amodified version of the MSRAC algorithm [BenHassine and Ho, 2007], and finally, (c) the greedy and (d) ALMA, as before.

Designing Large Test-Cases. As the problem size grows, CPLEX's estimate on the upper bound of the optimal solution becomes too loose (see Figure 2a). To get a more accurate estimate on the loss in social welfare for larger test-cases, we designed a large-instance by combining smaller problem instances, making it easier for CPLEX to solve which in turn allowed for tighter upper bounds as well (see Figure 2b).

We begin by solving two smaller problem instances with a low number of events. We then combine the two in a calendar of twice the length by duplicating the preferences, resulting in an instance of twice the number of events (agents) and calendar slots (resources). Specifically, in this case we generated seven one-day long sub-instances (with 10, 20, 30 and 40 events each), and combined then into a one-week long instance with 70, 140, 210 and 280 events, respectively. The fact that preferences repeat periodically, corresponds to participants being indifferent on the day (yet still have a preference on time).

These instances are depicted in Figure 2b and in the last line of Table 4.

Results. Figures 2a and 2b depict the relative difference in social welfare compared to CPLEX for 100 participants (|P| = 100) and increasing number of events for the regular (|E| ∈ [10, 100]) and larger test-cases (|E| up to 280), respectively. Table 4 aggregates the results for various values of P. ALMA-Learning is able to achieve less than 5% loss compared to CPLEX, and this difference diminishes as the problem instance increases (less than 1.5% loss for |P| = 100). Finally, for the largest hand-crafted instance (|P| = 100, |E| = 280, last line of Table 4 and Figure 2b), ALMA-Learning losses less than 9% compared to the possible upper bound of the optimal solution.

Moving on to fairness, Figure 2c depicts the Gini coeffi-

3 Computation time limit 20 minutes.

	Greedy	MSRAC	ALMA	ALMA-Learning
|P| = 20 |P| = 30 |P| =	6.16%-18.35% 1.72%-14.92% 3.29%-12.52%	0.00%-8.12% 1.47%-10.81% 0.00%-15.74% 0.00%-8.52%	0.59%-8.69% 0.50%-8.40% 0.07%-7.34% 0.15%-4.10%	0.16%-4.84% 0.47%-1.94% 0.05%-1.68% 0.14%-1.43%
50
|P| = 100	0.19%-9.32%
= 280

|E| = 280 0.00%-15.31% 0.00%-22.07% 0.00%-10.81% 0.00%-8.84%

Table 4: Range of the average loss (%) in social welfare compared to the IBM ILOG CP optimizer for increasing number of participants, P (|E| ∈ [10, 100]). The final line corresponds to the loss compared to the upper bound for the optimal solution for the large test-case with |P| = 100, |E| = 280 (Figure 2b).

cient for the large, hand-crafted instances (|P| = 100, |E| up to 280). ALMA-Learning exhibits low inequality, up to -9.5% lower than ALMA in certain cases. It is worth noting, though, that the fairness improvement is not as pronounced as in Section 3.1. In the meeting scheduling problem, all of the employed algorithms exhibit high fairness, due to the nature of the problem. Every participant has multiple meetings to schedule (contrary to only being matched to a single resource), all of which are drawn from the same distribution. Thus, as you increase the number of meetings to be scheduled, the fairness naturally improves.

SupplementaryMaterial. We refer the reader to [Danassis et al., 2021] for a detailed model of the meeting scheduling problem, implementation details and hyper-parameters, and additional results for both Sections 3.1, 3.2.

4 Conclusion

The next technological revolution will be interwoven to the proliferation of intelligent systems. To truly allow for scalable solutions, we need to shift from traditional approaches to multi-agent solutions, ideally run on-device. In this paper, we present a novel learning algorithm (ALMA-Learning), which exhibits such properties, to tackle a central challenge in multiagent systems: finding an optimal allocation between agents, i.e., computing a maximum-weight matching. We prove that ALMA-Learning converges, and provide a thorough empirical evaluation in a variety of synthetic scenarios and a realworld meeting scheduling problem. ALMA-Learning is able to quickly (in as little as 64 training steps) reach allocations of high social welfare (less than 5% loss) and fairness.