A Scalable Interdependent Multi-Issue Negotiation Protocol for Energy Exchange

1 Introduction

It is estimated that 1.4 billion people have no access to electricity and a billion more only have access to unreliable electricity networks [IEA, 2010]. This lack of access to electricity is a serious hindrance to their social and economic development and particularly acute in Sub-Saharan Africa and South Asia; where the majority of this population is scattered in small communities over vast areas of land [UNDP 2012]. Recent initiatives have sought to provide these remote communities with off-grid renewable microgeneration infrastructure such as solar panels and electric batteries. 1 At present, these resources (i.e., microgeneration and storage) are operated in isolation for individual home needs. However, recent works show that interconnection and autonomous coordination of such resources could result in their more efficient use. 2

In line with this vision, Alam et al. [2013b] investigates the idea of energy exchange between homes in communities; whereby self-interested autonomous agents (i.e., households) negotiate and reach energy exchange agreements in order to maximise their own utility. Negotiation in this context poses many issues that come from the very nature of communities and realities of life in developing countries: e.g., lack of banking/payment systems, and absence of a centralised infrastructure. Furthermore, negotiation over energy exchange involves multiple issues, as it requires deciding the amount of energy exchanged and, also, how this amount is scheduled across the day. These issues are interdependent as the recipient's utility for any period may depend on the energy received in earlier periods (since energy can be stored). This interdependent multi-issue negotiation, along with the socio-economic limitations of remote communities, make negotiation over energy exchange a very challenging task for agents. To address this challenge, Alam et al. [2013b] presented a protocol to facilitate negotiation over energy exchange. Their protocol restricts the type and number of offers such that negotiation leads to a subgame perfect Nash equilibrium (SPNE). However, their protocol only allows point-to-point communication and relies on a fully connected network topology (i.e., each home is connected to all other homes in the community) whereby the number of connections and messages exchanged; grow quadratically with the number of connected homes. Consequently, their protocol neither scales nor is applicable in communities with more general topologies.

More general work on interdependent multi-issue negotiation is focused on two tracks. The first focuses on settings where interdependence between issues is reducible. For example, Hindriks et al. [2006] and Fujita et al. [2010] attempt to remove dependencies by approximating the utility space. However, they both conclude that their techniques work only when a few (among all) issues are interdependent. This is not the case in energy exchange problems where the battery usage makes all time periods interdependent (e.g., energy drawn at one time period depends on the stored/drawn energy in all prior time periods). The second track (e.g., Hattori et al. [2007] and Ito et al. [2007]) uses a mediator and thus is not suitable to our decentralised settings where there is no centre and agents are required to negotiate directly with each other.

Against this background, we present a novel negotiation protocol to address the issue of negotiation over energy exchange. Our protocol imposes four key restrictions on the offers that agents make and specifies the negotiation process such that it leads to an SPNE and other desirable properties. Our work can be seen to be in line with Alam et al. [2013b] as it enables concurrent, many-to-many negotiation in a similar fashion. However, our protocol is superior as it (i) utilises broadcasting to scale up to communities with 100s of households (ii) is topology-agnostic as it makes no assumption on the underlying topology; and is thus applicable to communities in general. These properties, coupled with no requisite of financial payments or a mediator, bring our protocol closer to applicability in remote communities. More specifically, we extend the state-of-the-art in the following ways:

1 See the Rural Solar Homes (www.tatabpsolar.com) in India and the Solar Homes (www.gshakti.org) in Bangladesh.

2 See [Yasir et al., 2013; Alam et al., 2013a] for examples of works on community-based resource coordination for the efficient use of energy generation, storage and demand satisfaction.

1. We present a novel negotiation protocol for decentralised, concurrent negotiation over energy exchange.
2. We prove that this protocol leads to a subgame perfect Nash equilibrium where outcomes are Pareto-optimal (under certain conditions).
3. We provide empirical evaluation to show that, in this instance, our protocol (i) can be used to reduce the overall battery charging by close to 40% in a community and (ii) scales to communities with 100s of households.

The rest of the paper is as follows. Section 2 and 3 present home and community models. Section 4 to 6 present our protocol; and 7 and 8 discuss its properties. Section 9 concludes.

2 Model of an Individual Home

Here, we provide a model of a home that is similar to the models presented in related works [Alam et al., 2013b; Vytelingum et al., 2011]. We assume that each home has a renewable generation unit, some loads and a battery to store electricity. Let agent a represent a home, with a generation g = (g1, ..., gt) ∈ Rt≥0 denoting the energy it generates over t = (1, ..., t) ∈ Nt time periods and a load h∈Rt≥0 denoting its load requirements. The battery is characterised by four parameters: a storage capacity, qmax∈R≥0, maximum charging and discharging rate, cmax ∈ R≥0 and dmax∈R≥0, and an efficiency e ∈ [0, 1] which describes the loss of energy during charging. The dynamic state of the battery is captured by: the energy flow into the battery (charge) c ∈Rt≥0 | ∀ci ∈ c 0 ≤ ci ≤ cmax, the flow going out (discharge) d∈Rt≥0 | ∀di ∈d 0 ≤ di ≤ dmax and the amount of charge stored in the battery q∈Rt≥0 | ∀qi∈q 0 ≤ qi ≤ qmax. Finally, in some cases an agent may not be able to immediately use or store the available energy due to its limited charging or capacity. We refer to it as the wasted energy, w ∈Rt≥0 .

Using the battery an agent can compute an energy allocation, p = (p1, ..., pt)∈Rt≥0 , allocating the generated energy g to loads h. The utility of agent a at time i is then load pi that is powered at time i. The overall utility ua is given by:

Thus, the goal of an agent is to power as much of its load as possible to maximise its utility. The battery is useful here as it enables the agent to find an optimal energy allocation, p∗ :

This can be transformed to a linear programming (LP) model with the following constraints: Constraint 1: At time i, the allocated power pi depends on the generated power gi, charging ci and discharging di:

Constraint 2: The current battery state qi depends on the last battery state q(i-1), charge c(i-1) and discharge d(i-1). The charge flow ci ∈ c is subjected to the battery efficiency e. Also, the initial battery state q1 is zero.

Constraint 3: Allocated power pi must not exceed load hi:

We now discuss our model of a connected community.

3 Connecting Agents to Build a Community

Given the home model in Section 2, connecting two agents requires a physical link between them to enable them to (i) communicate and (ii) exchange energy. However, the absence of a centralised infrastructure (e.g., the electricity grid) in remote communities makes it challenging to connect homes and this status quo is unlikely to change in the near future due to the infrastructure costs and the lack of demand. We envision that this challenge can be addressed by establishing a light-weight peer-to-peer (P2P) network of homes where each home owns an exchange box that connects it to other homes; forming a network of interconnected agents from the ground-up without any centralised infrastructure. Now, when an agent is connected, the power available to it also includes the flow on the links between it and the agents to which it is connected to. If agent a is connected to agents j ∈ M then its total flow fi is:

Here z ∈ [0, 1] is the efficiency of the physical link. We can modify constraint o1 to include the link flow f as follows:

Now, for a given flow ˆ f = ( ˆ f1, ..., ˆ ft)∈Rt , a can maximise its utility by using Eq (1) and constraint o4 as follows:

Where ua ( ˆ f) denotes the maximum utility that a can get for ˆ f, subjected to constraints {o2, ..., o4}. Similarly, when a needs to compute f ∗ that maximises its utility it can use:

Now that an agent can compute its optimal flow and evaluate its utility for any offered flow, it can negotiate with other agents to reach an agreed flow that increases its utility. Here, the increase in utility comes from the fact that, via exchange, an agent can avoid energy storage losses and utilise energy that will be unused otherwise. To be clear on this, if an agent has a 100% efficient battery and infinite storage, it cannot increase its utility via exchange. Here, the negotiation is challenging for agents as it involves interdependent issues (see Section 1) and it becomes even more complex when an agent needs to negotiate with multiple agents, because reaching an agreement with one agent can affect the ongoing negotiations with the others. To faciliate negotiation in this context, we next present a protocol that reduces this complexity and enables agents to reach agreements more efficiently.

4 Energy Exchange Protocol (EEP)

We now present our energy exchange protocol (EEP) to facilitate negotiation over energy exchange. The core idea here is to divide agents into two power pools that need energy at alternate times, and impose restrictions on the negotiation to reduce complexity. The ingenuity comes from the fact that these restrictions are engineered so that the negotiation ends in outcomes with certain desirable properties (see Section 7).

Before defining the EEP, we define our terminology. We consider exchange over finite time (e.g., a day) which can be divided into exchange periods. An exchange period is an atomic unit of time (e.g., 12 consecutive hours) for energy exchange and consists of at least one time period. The EEP allows only two exchange periods (ex1 and ex2) and divides agents into two exchange types (et1 and et2) where et1 requires energy in ex1 while et2 requires energy in ex2. Only one exchange type (called makers) is allowed to make simultaneous offers to the other exchange type (called receivers). Given these terms, Figure 1 describes the EEP in detail.

Now, we note that an agent a can use Eq (4) to find f ∗ ∈Rt that maximises its utility ua . However, under the EEP only valid flows (VF) can be agreed, and in this sense, the EEP reduces all flows to the set of VFs, SV F ⊂Rt . To find f ∗ ∈ SV F , a can use Eq (4) subjected to r1 and r2; in addition to {o2, ..., o4}. Knowing f ∗ , a can easily infer its exchange type (which exchange period it prefers to receive energy in). Here, we note that r1 and r2 are designed such that SV F is a convex set where all members lie on the same geometric line. More specifically, if f = (f1, f2, f3, f4) ∈ SV F then r1 requires the sum of energy in both exchange periods to be equal (e.g., |f1+f2|=|f3+f4|) while r2 says |f1|=|f2|=|f3|=|f4|. Now, any scalar multiple of f , c×f also meets r1 and r2 and hence all scalar multiples of f are in SV F . This also implies that, if f ∈SV F then all f ′ ∈SV F can be described as c × f 3 . This geometric characteristic of SV F ensures that if f ∗ ∈ SV F maximises ua , then f ∗ is unique and ua is monotonically decreasing over the interval 0≤f≤f ∗ (see Lemma 1).

5 Energy Exchange as a Sequential Game

Negotiation under the EEP can be modelled as a sequential game with an infinite horizon where agents make their moves in a well-defined sequence as specified by the EEP. We next formulate the strategies of all participating agents.

Strategies for Round Zero: Strategy Γ of an agent is to declare an exchange type, i.e., Γ : et → et | et = {et1, et2}. Now, consider a strategy ˆΓ ∈ Γ whereby an agent declares its true exchange type. Theorem 1 (Section 6) shows that the strategy profile where agents play ˆΓ is an NE in round zero.

Energy Exchange Protocol (EEP)

1. Negotiation starts at a specified time with round zero where all agents simultaneously broadcast their exchange type. Only et1 is allowed to make offers from now on, while et2 can only respond to offers.
2. Subsequent offer rounds take place at specified intervals. If there are at least one maker and one receiver, offer rounds continue as follows:
3. All makers make simultaneous offers. Each maker is required to make a valid flow offer f ̸= 0 to all receiver it is connected to. An offer f is valid if:
4. The offer comprises of exactly two exchange periods. Each exchange period consists of an equal number of consecutive time periods. The amount of energy exchanged in each exchange period must be the same.

• The amount of energy in each time period is equal.

• On receiving offers, each receiver simultaneously broadcasts a valid flow f B ̸= 0 to all agents which must not exceed the minimum offer it received. (r3)
• The agreed flow lA in this offer round is the minimum flow in the set of all broadcast flows F B , i.e., lA = min (F B ). (r4)
• All receivers simultaneously broadcast a boolean signal to their respective makers to indicate if they wish to receive offers in the next offer round.
• The current offer round terminates.
• The EEP terminates.

Figure 1: The Energy Exchange Protocol (EEP)

Strategies for Offer Rounds: In an offer round, the strategy Ω of a maker describes how it chooses an offer for each of its intended receivers, i.e., Ω : Rt → Rt×n where n is the number of receivers. The strategy π of a receiver describes its choice of valid flow to broadcast, given the offers it received from n makers and its optimal flow, i.e., π:Rt×n ×Rt → Rt . Now, consider a VF d= f ∗ n of agent a where f ∗ is its optimal VF and n is either the number of its intended receivers (if a is a maker) or makers it received offers from. We call d the optimal divided flow (ODF) of a. The ODF is special in the sense that, when the agreed flow in an offer round equals the ODF of an agent (i.e., lA = f ∗ n ) then the total agreed flow for that agent is lA ×n=f ∗ . Thus, it gets its optimal VF and, consequently, its maximum utility. Now, consider a strategy ˆΩ∈Ω whereby a maker offers f =d to each of its receivers. Also, consider a strategy ˆπ ∈ π whereby a receiver broadcasts the minimum of its ODF and offers Fn it received, i.e., f B =min(d,min(Fn))4,5 . In Section 6, we show that ˆΩ and ˆπ constitute an NE. Now, having defined the strategies of agents, we next discuss their strategic interaction in the EEP.

6 AGame Theoretic Analysis of the EEP

We now present a detailed game-theoretic analysis of the EEP sequential game to prove; via a series of theorems; that a particular strategy profile is an SPNE for this game, as follows.

Theorem 1. In round zero, the strategy profile λ = (ˆΓ1, ...., ˆΓn), for n participating agents is an NE.

Proof. We know that et1 requires energy in ex1 while et2 requires energy in ex2 (see Section 4); thus, energy exchange is possible only between opposite types (i.e., et1 and et2). In λ, when all agents declare truthfully, all et1 agents become makers and et2 become receivers. Now, in the subsequent offer rounds, energy exchange is possible only between any maker and receiver as they are of the opposite types. Hence, no participating agent has an incentive to unilaterally deviate from the strategy profile λ.

Theorem 2. Let ϕ=(ˆΩ1, ..., ˆΩm, ˆπm+1, ..., ˆπm+r) be a profile for an offer round where m makers play ˆΩ and r receivers play ˆπ. Then ϕ leads to an outcome such that the agent with the minimum divided optimal flow, obtains its optimal flow.

Proof. Let D = (d1, ..., dm, dm+1, ..., dm+r) be the set of the ODFs of m makers and r receivers, F be the set of offers made and F B = (f Bm+1 , ..., f Bm+r ) be the set of broadcast flows. We know that r4 dictates lA = min (F B ). Now, let Fi ⊂ F be the offers that receiver i receives. When i plays ˆπi, it broadcasts f Bi = min(di, F i) where di ∈ D is its ODF. Substituting for F B :

Here, Eq (6) states that under ϕ, lA is the minimum of the ODFs of the receivers and all offers by makers. Now, we know that a maker j playing ˆΩj, makes offers Fj ⊂ F | min(Fj) = dj, thus:

Substituting for min(F ).

Clearly, under ϕ, lA equals the minimum ODF among all agents. Now, when an agent i with di = min(D) obtains di, its total agreed flow is di ×n = f ∗ (see Section 5); thus it obtains its optimal flow f ∗ and, consequently, its maximum utility. Hence, proved.

Theorem 3. In profile ϕ = (ˆΩ1, ..., ˆΩm, ˆπm+1, ..., ˆπm+r), no maker has an incentive to unilaterally deviate from ˆΩ.

4 With a slight abuse of notation, min() is defined as an operation that returns the minimum flow in the provided collection(s) of VFs.

5 Suppose a receiver has f ∗ = (4, 4,-4,-4) and it receives offers Fn = {(1, 1,-1,-1), (2, 2,-2,-2)} from two makers, then d = (2, 2,-2,-2). Since min(Fn) = (1, 1,-1,-1) and min(F n) < d, strategy ˆπ dictates f B = d = (1, 1, -1, -1).

Proof. Let D = (d1, ..., dm, dm+1, ..., dm+r) be the set of ODFs and F be the set of offers made. Let maker i that makes offers to x receivers, deviate from ϕ by making offers Fi ⊂ F such that min(Fi) ̸= di, where di ∈ D is its ODF. Since all other makers play ˆΩ, we modify Eq (7) as follows:

Substituting for min(F ) in Eq (6):

Eq (10) states that lA is the minimum of the ODFs of all but maker i, and the offers that i makes. Let Ωi be the set of all strategies for i and suppose that ∃ Ωi ∈ Ωi | ui(Ωi, ϕ/i) > ui(ˆΩi, ϕ/i). We note that strategies in Ωi can be summarised into two cases with respect to di. In each case, we prove by contradiction that ∄ Ωi ∈ Ωi | ui(Ωi, ϕ/i) > ui(ˆΩi, ϕ/i), as follows:

Case 1: min(D/i) ≤ di, whereby all strategies in Ωi can be summarised as Ωi = {Ω1i , ˆΩi,Ω2i } | Ω1i = min(Fi) > di, ˆΩi = min(Fi) = di,Ω2i = min(Fi) < di. Given this, Table 1 shows the outcomes and utilities corresponding to {Ω1i , ˆΩi,Ω2i }. Now, given min(D/i) ≤ di and Table 1, we can establish:

Hence, in Case 1 ∄ Ωi ∈ Ωi | ui(Ωi, ϕ/i) > ui(ˆΩi, ϕ/i).

Case 2:min(D/i)>di It is sufficient to show that ˆΩi=min(Fi)=di leads to lA = min(D/i,Fi) = di where the total agreed flow is di×x=f ∗ which is the optimal VF of i. Hence, ˆΩi provides i with the maximum utility ui(f ∗ ) that no other strategy can improve. Hence for Case 2, ∄ Ωi ∈Ωi |ui(Ωi, ϕ/i)>ui(ˆΩi, ϕ/i).

Taken together, Case 1 and 2 show that ∄ Ωi ∈ Ωi | ui(Ωi, ϕ/i) > ui(ˆΩi, ϕ/i); thus, maker i has no incentive to unilaterally deviate from strategy ˆΩi in profile ϕ. Hence, proved.

Theorem 4. In profile ϕ = (ˆΩ1, ..., ˆΩm, ˆπm+1, ..., ˆπm+r), no receiver has an incentive to unilaterally deviate from ˆπ.

Proof. Let receiver i receive offers Fi and broadcast f Bi . We know that lA =min (F B ) (see r4). Let F B = F B/i ∪ f Bi , then:

Suppose ∃ πi ∈ πi | ui(πi, ϕ/i) > ui(ˆπi, ϕ/i) where πi is the set of all strategies for i. We note that strategies in πi can be summarised into 3 cases according to their respective outcomes. In each case, we prove by contradiction that

Table 3: Utility of receiver i when min(F B/i ) ≤ di ≤ min(F i).

∄ πi ∈ πi | ui(πi, ϕ/i) > ui(ˆπi, ϕ/i), as follows:

Case 1: min(Fi) ≤ di ≤ min(F B/i ), whereby πi can be summarised as: 6 πi = {ˆπi, π′i} | ˆπi = f Bi = min(di,min(Fi)) = min(Fi) (given in Case 1), π′i = f Bi < min(Fi). Table 2 shows the outcomes and utilities, corresponding to {ˆπi, π′i}.

Now, given min(F i) ≤ di ≤ min(F B/i ) and Table 2, we have:

Hence, in Case 1 ∄ πi ∈ πi | ui(πi, ϕ/i) > ui(ˆπi, ϕ/i).

Case 2: min(F B/i ) ≤ di ≤min(Fi): We summarise πi as πi = {π1 i , π2 i , ˆπiπ3 i } | π1 i =min(Fi), π2 i =di <f Bi <min(Fi), ˆπi = f Bi =min(di,min(Fi)) =di (given in Case 2), π3 i =f Bi <di. Table 3 shows the outcomes and utilities for πi. Now, given min(F B/i ) ≤ di ≤ min(F i) and Table 3, we have:

Hence, in Case 2 ∄ πi ∈ πi | ui(πi, ϕ/i) > ui(ˆπi, ϕ/i).

Case 3: di ≤ min(F B/i ) ≤ min(Fi): It is sufficient to show that ˆπi = f Bi = di leads to lA = min(F B/i , f Bi ) = di such that the total agreed flow is di × x = f ∗ which is the optimal VF of i (see Section 5). Hence, ˆΩi provides i with the maximum utility ui(f ∗ ) that no other strategy can improve. Hence, proved in Case 3.

Taken together, Case 1, 2 and 3 show that ∄ πi ∈ πi | ui(πi, ϕ/i) > ui(ˆπi, ϕ/i); thus receiver i has no incentive to unilaterally deviate from ˆπi in strategy profile ϕ. Hence, proved.

Theorem 5. In an offer round, the strategy profile ϕ = (ˆΩ1, ..., ˆΩm, ˆπm+1, ..., ˆπm+r) is a Nash equilibrium.

Proof. This immediately follows from Theorem 3 and 4. In Theorem 3, we showed that no maker has an incentive to unilaterally deviate from ϕ. Similarly, in Theorem 4 we showed that no receiver has an incentive to unilaterally deviate from ϕ. Hence, in strategy profile ϕ, no participating agent has an incentive to unilaterally deviate from ϕ. Hence, ϕ constitute an NE in an offer round.

6 Broadcasting f Bi > min(Fi) is a violation of r3 and easily detectable by the maker(s) that made the minimum offer.

Theorem 6. The strategy profile µ = (λ, ϕ) is a subgame perfect Nash equilibrium of the EEP sequential game.

Proof. This immediately follows from Theorem 1 and 5. In Theorem 1, we proved that strategy profile λ is in NE in round zero. In Theorem 5, we proved that ϕ is in NE in an offer round. Now, any subgame of the EEP sequential game will consist of round zero and zero or more offer rounds. Thus, µ is the strategy profile such that for any given round in a subgame, there is a corresponding profile in µ that is in NE for that round. Hence, µ is an SPNE.

7 Properties of the EquilibriumOutcomes

Having shown the existence of an SPNE in the EEP negotiation, we now discuss some properties of its outcomes.

1. Termination: The termination guarantee for the EEP emerges in a similar fashion to monotonic concession protocols (MCP); as long as there are some agents willing to make and accept offers in offer rounds, exchange agreements will take place and the cumulative need for energy exchange will reduce [Endriss, 2006]. This reduction, much like the utility reduction in rounds in MCPs, guarantees termination.
2. Pareto-optimality Under Strict Monotonicity: The EEP equilibrium outcomes are guaranteed to be Pareto-optimal in cases where the monotonicity in utility function of agents is strict (see Lem 1). While intuition tells us that this may generally be the case, the strict monotonicity may not hold in some cases: in particular, when an agent has abundant wasted energy. To show that strict monotonicity entails Paretooptimality, consider agent a with optimal VF f ∗ . Its total agreed flow when the negotiation ends, can be either (i) equal to f ∗ - now any further change in the agreed flow will decrease its ua , or (ii) less than f ∗ - but no other agent of opposite type is willing to negotiate in further rounds (they already have reached their optimal VFs) and although agreeing to more flow will improve ua , other agents will no longer gain their maximum utilities. Hence, Pareto-optimality ensues.
3. Tractability and Scalability: The EEP restrictions simplify negotiation such that it becomes tractable and scalable. Specifically, r1 and r2 constrain negotiation to SV F where it becomes easier for agents to compute its optimal VF or

Log 10 (Messages)

evaluate offers using an LP solver (see Eq (4) and (3)). Similarly, r3 and r4 ensure that the best responses of agents remain scalable.For example, for a maker, the number of receivers it makes offers to, is simply a number by which it divides its optimal VF (see Theorem 3). While for a receiver, the number of its makers is irrelevant in the sense that it does not need to evaluate each individual offer, or a combination thereof. Instead, its best response is to broadcast a single flow (see Theorem 4). More importantly, these restrictions ensure that the number of overall messages (e.g., offers and broadcasts) required to converge to an SPNE outcome (as well as other properties), has a linear relationship with the number of participants for scalability (see Section 8 for details).

4. Concurrent, Many-to-Many Negotiation: The EEP allows many-to-many concurrent negotiation in the sense that a maker can simultaneously make offers to many receivers. Similarly, a receiver can simultaneously agree to exchange with many makers. Consequently, in an offer round, many agents make offers to many agents who respond to many.

8 Empirical Evaluation

Here, we set up a realistic example to demonstrate (i) the benefit of energy exchange via the EEP and (ii) its comparison to the EEP-A by Alam et al. [2013b] which is the state-of-the-art. To this end, we consider an example of energy exchange in a community where each agent has either a 1.5kW wind turbine or a 1.75kW solar panel with equal probability. The energy generation data for the wind turbine comes from a wind farm near Lugo, Northwest Spain (www.sotaventogalicia.com), while the output of the solar panel is estimated to be directly proportional to the daily radiance for the same region (www.re.jrc.ec.europa.eu/apps/radday.php). We use data for July 2011, estimate the average generation for a day and scale it to match the output of a 1.5kWwind turbine and a 1.75kW solar panel. At present, the load requirements of homes in remote areas are not available, so we use load data recorded and provided by a UK electric company in low-income homes equipped with smart meters. Figure 3 shows this consumption along with the generation (solar and wind). The actual generation and consumption for each agent comes from a distribution over these profiles. More specifically, we model generation/consumption in each time unit as an independent Gaussian distribution (with scaled value as the mean and the variance within 10% of it). We assume that agents have identical batteries [s = 20kWh, c = 4kW, d = -4kW, e = 90%].

Given this setup, we repeatedly (50 times) create a fully connected P2P community of 20 agents and simulate energy exchange via the EEP and EEP-A. We find that agents can reduce their need for overall battery charging by exchanging energy, as shown in Table 4. This is important because electric batteries are expensive (costing as much as 500 USD/kWh) and have a limited number of charging cycles 7 (3000 to 5000). Reducing the battery charging prolongs the battery life and reduces the need for frequent replacements; thus saving maintenance costs. We also note that (i) the reduction in overall charging via the EEP and EEP-A is comparable; this is because both are MCPs (see Section 7) which terminate when no further energy exchange is possible thus leading to similar reductions, and (ii) the number of messages needed to converge to an SPNE outcome (henceforth; convergence) are significantly fewer in the EEP. This is due to the efficient mechanistics of the EEP that rely on a systematic propagation of a single broadcast message from each receiver, unlike the EEPA that requires all offers to be propagated to all receivers. 8

To demonstrate scalability, we use the same experimental setup (no repetition) to simulate exchange in the communities of up to 100 agents (chosen to be close to the number of households (98) in an average Indian village [Govt. of India, 2011]). Figure 2 shows the number of messages needed for convergence in the EEP and EEP-A, as a function of the number of agents. We note that while the EEP-A can be suitable for small (<30) neighbourhoods, the explosion in the number of messages quickly renders it infeasible for larger communities. In contrast, the EEP scales up nicely and needs orders of magnitude fewer messages, compared to that of the EEP-A. 9

7 In Lithium-based batteries, one life cycle means a full charge of the battery, even when the charging is discrete.

8 For r receivers and mmakers, each offer round in the EEP requires ∑Mi=1 (2rmi + r) messages where rmi is the number of receivers of maker i; conversely, the EEP-A requires ∑mi=1 r(r + 1).

9 The time required for convergence depends on factors such as the computational power of each agent, network latency and bandwidth etc. In our case, the EEP-A takes over 8 hours and the EEP takes less than 10 minutes for 100 agents on a 72TFlops (4 nodes

Finally, we note that any quantitative improvement; as the result of energy exchange in a community, is dependent on the nature and degree of diversity (e.g., generation means or load profile, battery specification) among agents. To explore this effect and provide a more balanced interpretation, we create an unstructured (i.e., no specific topology) P2P community where each agent is randomly connected to up to 5 agents (i.e., rmi =U(1, 5)). We then use the same experimental setup to simulate exchange for each day in July, 2011; with the exception of using the power generated from wind on that day. Figure 3 shows the overall battery charging (mWh) with no energy exchange and the EEP, and the similarity (i.e., correlation coefficient) between the wind and solar generation profiles on each day. It is evident that, in general, as the generations from solar and wind become dissimilar (negatively correlated), agents have more opportunities to exchange energy; resulting in more reductions in battery charging. We note that the agents (in Figure 3) differ only in their energy generation, and more diversity in other aspects (e.g., consumption) have the potential to make energy exchange even more useful.

9 Conclusion and FutureWork

The problem of negotiation over energy exchange is a complex interdependent multi-issue negotiation problem. The EEP tackles this complexity by imposing certain restrictions over negotiation and guarantees certain desirable properties. Using real-world data, we empirically evaluate the EEP and show that, in this instance, exchange via the EEP reduces the total battery charging up to 40%. When taken together, these results show that energy exchange via the EEP is useful and scalable in communities to improve the efficient use of energy and storage. Future work will investigate how relaxing the EEP restrictions affects the negotiated outcomes when the energy generation is uncertain and loads are deferrable.

A Appendix

Lemma 1. Let IV F = [f 0 , ˆ f] ⊂ SV F be an interval where f 0 is the zero flow and ˆ f is the optimal flow that gives agent a maximum utility. Then utility is a monotonic function on IV F i.e., f ′ , f ′′ ∈ IV F | f 0 <f ′ <f ′′ < ˆ f =⇒ u(f 0 ) ≤ u(f ′ ) ≤ u(f ′′ ) ≤ u( ˆ f ).

Proof. We first modify our LP model in Section 3 to one where t flow constraints can be replaced by a single inequality constraint; to show that change in t flows equates to change in a single constraint. We then use a general property of LP to prove monotonicity in u(f). Step 1: Equivalent Representation of Valid Flows: We know that the amount of flow in each time period of a VF is the same. Hence, a VF can be described as f = (z, ..., z,-z...,-z) where z ∈ R. Similarly, IV F = [f 0 , ˆ f] can be mapped to IR = [0, ˆ z] ⊂R. Step 2: Equivalent Representation of the Utility Function: For a given f, an agent can compute its utility via Eq. 3. We can reformulate Eq. 3 as per the equivalent representation of f:

each containing an 8-core with each core 2.27 Ghz) supercomputer.

This establishes (i) u(f) = u(z), (ii) evaluating Eq. 3 over IV F equates to evaluating Eq. 11 over IR and (iii) if ˆ f ∈IV F maximises Eq. 3 then ˆ z∈IR maximises Eq. 11.

Step 3: Monotonicity in Eq. 11: To show that u(z) is monotonic over IR, let us evaluate Eq. 11 subjected to

We are given that Eq. 3 attains maxima at ˆ z. Hence, o19 is satisfied at the maximal value which is referred to as a ≤ inequality constraint being strictly satisfied. Now, as we tighten or decrease o19, the change in u(z) (also known as the shadow price or the Lagrangian multiplier) is guaranteed to be monotonically decreasing. Thus, z′ , z′′ ∈ IR | z′ < z′′ < ˆ z =⇒ u(z′ ) ≤ u(z′′ ) ≤ u(ˆ z). Since evaluating Eq. 3 over IV F equates to evaluating Eq. 11 over IR, for f ′ < f ′′ ∈ IV F and their corresponding z′ , z′′ ∈ IR, we have u(z′ ) ≤ u(z′′ ) =⇒ u(f ′ ) ≤ u(f ′′ ). Hence, proved.