Research Questions & Hypotheses

  1. Global optimality
    RQ:Can decentralized agents sharing only aggregates reach a near-optimal result?
    H1:Iterative coordination over a tree, using only aggregated plans, finds solutions close to the brute-force optimum.
  2. Techno-socio-economic trade-offs
    RQ:How can individual comfort be traded against collective cost and fairness?
    H2:A single tunable parameter shifts the balance. More comfort leads to higher global cost and lower fairness, and an intermediate setting gives a good compromise.

Hypotheses are not stated explicitly in the paper; derived from its claims.

Background - Timeline

2013
EPOS
Pournaras,
PhD thesis
COHDA
Hinrichs, Lehnhoff
& Sonnenschein
2013/14
2017
I-EPOS
Pilgerstorfer &
Pournaras, SEAMS
Extended version,
ACM TAAS
Pournaras, Pilgerstorfer
& Asikis, ACM TAAS
2018

I-EPOS = Iterative Economic Planning and Optimized Selections

Background - Problem class

Problem class:
The overall problem can be classified as 0-1 multiple-choice combinatorial optimization problem.
Search space:
$$\mathcal{O}(\mathcal{P}_a, \mathcal{A}) = \prod_{a \in \mathcal{A}} \mathcal{P}_a$$
Objective:
$$\mathbf{o}^{\star} = \operatorname*{arg\,min}_{\mathbf{o} \in \mathcal{O}(\mathcal{P}_a, \mathcal{A})} f_G\left( \sum_{a \in \mathcal{A},\, \mathbf{o}_a \in \mathbf{o}} \mathbf{o}_a \right)$$

Phases of I-EPOS Summarized

The cost never increases since during each iteration, each parent only approves what lowers the global city cost $f_G$.

Introducing comfort $\lambda$

So far every household only cared about the city. In reality, each household has a favourite plan.

$$\mathbf{o}^{\star} = \operatorname*{arg\,min}_{\mathbf{o} \in \mathcal{O}(\mathcal{P}_a, \mathcal{A})} \; (1 - \lambda)\, \underbrace{f_G\Big( \sum_{a \in \mathcal{A}} \mathbf{o}_a \Big)}_{\text{collective cost}} \; + \; \lambda\, \underbrace{\frac{1}{a} \sum_{a \in \mathcal{A}} f_L(\mathbf{o}_a)}_{\text{discomfort}}$$
Same search space $\mathcal{O}(\mathcal{P}_a, \mathcal{A}) = \prod_{a \in \mathcal{A}} \mathcal{P}_a$ as before.

Preferences stay private: parents still only see branch sums and judge by $f_G$.

Results – H1: near-optimal with only aggregates

Paper setup:|1,000 agents in a binary tree|16 plans each|$\lambda = 0$|$f_G$ = variance|50 runs

Paper setup:|10 agents|2, 3 or 4 plans each|$\lambda = 0$|$f_G$ = variance|with 4 plans: $4^{10}$ = 1,048,576 combinations

Learning curve
The city cost falls from 480 to 3.2 without ever increasing and settles after about 15 iterations.
vs. brute force (10 agents)
Out of all 1,048,576 possible solutions, I-EPOS ends in the top 0.035 %.
vs. EPOS, COHDA, Greedy
COHDA reaches the same result only with orders of magnitude more communication.
✓ H1Iterative coordination over a tree, using only aggregated plans, finds solutions close to the brute-force optimum.
1 10 100 1k 0 5 10 15 20 25 30 iteration variance (city cost) (a) Global cost 0 2 4 6 8 10 12 0 5 10 15 20 25 30 iteration agents changing their plan (%) (b) Plan changes
Redrawn from the paper's Fig. 9: (a) global cost per iteration, (b) share of agents changing their plan
2.5 4 6.3 10 15.8 1 10² 10⁴ 10⁶ solution (all possible combinations, sorted by cost) variance (city cost) Brute force [4 plans] Brute force [3 plans] Brute force [2 plans] I-EPOS [4 plans] I-EPOS [3 plans] I-EPOS [2 plans] 33 %
Redrawn from the paper's Fig. 21: all solutions sorted by variance (brute force) and where I-EPOS ends up
10 100 1k 100 1k 10k 100k 1M 10M cost computations variance (city cost) (a) Computation 10 100 1k 1k 1M 1G vectors transmitted variance (city cost) (b) Communication I-EPOS COHDA EPOS Greedy
Redrawn from the paper's Fig. 16: variance vs. (a) computations and (b) messages on the critical path

Results – H2: the $\lambda$ trade-off

Discomfort (avg. rank of the chosen plan) sweet spot 0 2 4 6 8 0 0.2 0.4 0.6 0.8 1 λ City cost (variance) sweet spot 0 3 6 9 12 0 0.2 0.4 0.6 0.8 1 λ ↑ 1,058 at λ = 1
Ring city, 1,000 households (same setup as the paper’s Fig. 15): one I-EPOS run per $\lambda$
The $\lambda$ trade-off ✓ H2
Raising $\lambda$ trades city cost and fairness for comfort, and the compromise is cheap: at $\lambda \approx 0.9$ discomfort is 90 % lower, while the city cost has only doubled.

Summary

Optimality & Efficiency:
Sharing only aggregates is enough to reach near-optimal results at a fraction of the cost of full-information methods.
Convergence:
The cost never increases and settles after about 15 iterations.
Techno-socio-economic trade-offs:
The parameter $\lambda$ tunes how much comfort the households trade for a flatter and fairer city.

Take-Home Message

No central authority.
No full information.
Near-optimal answers
to an NP-hard problem.
You don’t have to choose between privacy and collective efficiency.

Further work

Future work the paper names
  • Self-organizing trees and denser hierarchical structures similar to neural networks.
  • Different $\lambda$ values per agent, and reward mechanisms and the equilibria they produce.
Future work I could see
  • Robustness against strategic agents.

Further reading

EPOS 2013
E. Pournaras: Multi-level Reconfigurable Self-organization in Overlay Services. PhD thesis, Delft University of Technology, 2013. SIKS Dissertation Series No. 2013-11, xvi + 205 pp. ISBN 978-94-6186-098-9. Open access via TU Delft Repository; also available at doi.org/10.12681/eadd/30107.
COHDA 2013/14
C. Hinrichs, S. Lehnhoff, M. Sonnenschein: COHDA: A Combinatorial Optimization Heuristic for Distributed Agents. In: Agents and Artificial Intelligence (ICAART 2013), Springer CCIS vol. 449, pp. 23–39, 2014. doi.org/10.1007/978-3-662-44440-5_2
I-EPOS code
github.com/epournaras/EPOS: the authors’ open-source Java implementation of I-EPOS from this paper (releases “I-EPOS 0.0.x”), with example datasets and a tutorial to run your own experiments.

Discussion

Who runs the tree, and is that a new form of centralization?

Notation (1/2)

NotationMeaning
$\mathcal{A}$Finite set of all agents in the network
$\mathcal{B}_{\mathfrak{a}} = \{0, 1\}$Binary decision for agent $\mathfrak{a}$
$\mathcal{C}_{\mathfrak{a}} \subseteq \mathcal{D}_{\mathfrak{a}}$Set of children for agent $\mathfrak{a}$
$\mathcal{D}_{\mathfrak{a}} \subset \mathcal{A}$Set of descendants for agent $\mathfrak{a}$
$\mathcal{O}(\mathcal{P}_{\mathfrak{a}}, \mathcal{A}) = \prod_{\mathfrak{a} \in \mathcal{A}} \mathcal{P}_{\mathfrak{a}}$All combinations of sets $\mathcal{P}_{\mathfrak{a}}$ for agents in $\mathcal{A}$
$\mathcal{P}_{\mathfrak{a}} \subset \mathbb{R}^d$Possible plans of agent $\mathfrak{a}$
$a = |\mathcal{A}|$Number of agents
$c = \max_{\mathfrak{a} \in \mathcal{A}} |\mathcal{C}_{\mathfrak{a}}|$Maximum number of children per agent
$d \in \mathbb{N}^+$Size of plans
$p = \max_{\mathfrak{a} \in \mathcal{A}} |\mathcal{P}_{\mathfrak{a}}|$Maximum number of plans per agent
$t \in \mathbb{N}^+$Number of iterations
$\mathbf{o} \in \mathcal{O}(\mathcal{P}_{\mathfrak{a}}, \mathcal{A})$A combination
$\mathbf{o}^{\star} \in \mathcal{O}(\mathcal{P}_{\mathfrak{a}}, \mathcal{A})$An optimal combination
$\mathbf{o}_{\mathfrak{a}} \in \mathbf{o}$Plan of agent $\mathfrak{a}$ in combination $\mathbf{o} \in \mathcal{O}(\mathcal{P}_{\mathfrak{a}}, \mathcal{A})$
$o_{\mathfrak{c}} \in o$Delta value that encodes a branch approval or rejection for child $\mathfrak{c}$ in combination $o \in \mathcal{O}(\mathcal{B}_{\mathfrak{c}}, \mathcal{C}_{\mathfrak{a}})$
$\mathfrak{a} \in \mathcal{A}$An agent
$\mathfrak{c} \in \mathcal{C}_{\mathfrak{a}}$A child of agent $\mathfrak{a}$
$\mathfrak{d} \in \mathcal{D}_{\mathfrak{a}}$A descendant of agent $\mathfrak{a}$

Table 1 of Pournaras, Pilgerstorfer & Asikis (2018), p. 10:4.

Notation (2/2)

NotationMeaning
$\mathfrak{r} \in \mathcal{A}$Root agent in the tree
$\tau \in \{1, \dots, t\}$Number of the current iteration
$\mathbf{p}_{i,\mathfrak{a}} \in \mathcal{P}_{\mathfrak{a}}$Possible plan $i$ of agent $\mathfrak{a}$
$\mathbf{s}_{\mathfrak{a}}^{(\tau)} \in \mathcal{P}_{\mathfrak{a}}$Selected plan of agent $\mathfrak{a}$ at iteration $\tau$
$\mathbf{g}^{(\tau)} = \sum_{\mathfrak{a} \in \mathcal{A}} \mathbf{s}_{\mathfrak{a}}^{(\tau)}$Global response of the network at iteration $\tau$
$\mathbf{a}_{\mathfrak{a}}^{(\tau)} = \sum_{\mathfrak{d} \in \mathcal{D}_{\mathfrak{a}}} \mathbf{s}_{\mathfrak{d}}^{(\tau)}$Descendants’ aggregated response of agent $\mathfrak{a}$ at iteration $\tau$
$\mathbf{t}_{\mathfrak{a}}^{(\tau)} = \mathbf{s}_{\mathfrak{a}}^{(\tau)} + \mathbf{a}_{\mathfrak{a}}^{(\tau)}$Aggregated branch response of agent $\mathfrak{a}$ at iteration $\tau$
$\delta_{\mathfrak{a}}^{(\tau)} \in \{0, 1\}$Approval or rejection of branch selection for agent $\mathfrak{a}$ at iteration $\tau$
$\tilde{\mathbf{s}}_{\mathfrak{a}}^{(\tau)}, \tilde{\mathbf{g}}^{(\tau)}, \tilde{\mathbf{a}}_{\mathfrak{a}}^{(\tau)}, \tilde{\mathbf{t}}_{\mathfrak{a}}^{(\tau)}, \tilde{\delta}_{\mathfrak{a}}^{(\tau)}$Preliminary $\mathbf{s}_{\mathfrak{a}}^{(\tau)}, \mathbf{g}^{(\tau)}, \mathbf{a}_{\mathfrak{a}}^{(\tau)}, \mathbf{t}_{\mathfrak{a}}^{(\tau)}$, and $\delta_{\mathfrak{a}}^{(\tau)}$
$\nabla \tilde{\mathbf{x}}^{(\tau)} = \tilde{\mathbf{x}}^{(\tau)} - \mathbf{x}^{(\tau - 1)}$Change of preliminary value from the one of the previous iteration for $\mathbf{x}^{(\tau)} \in \{\mathbf{s}_{\mathfrak{a}}^{(\tau)}, \mathbf{g}^{(\tau)}, \mathbf{a}_{\mathfrak{a}}^{(\tau)}, \mathbf{t}_{\mathfrak{a}}^{(\tau)}\}$
$f_G : \mathbb{R}^d \to \mathbb{R}$Global cost function
$f_L : \mathbb{R}^d \to \mathbb{R}$Local cost function
$E_G^{(\tau)} = f_G(\mathbf{g}^{(\tau)})$Global cost at iteration $\tau$
$E_L^{(\tau)}$Average local cost at iteration $\tau$
$U^{(\tau)}$Unfairness at iteration $\tau$
$w : \mathbb{R}^d \to \mathbb{R}$Preference weight; raises the cost of disliked plans
$\lambda \in \mathbb{R}$Controls the tradeoff between global and local cost
$\rho_{i,\mathfrak{a}} \in \mathbb{R}$Dislike of plan $i$ by agent $\mathfrak{a}$

Table 1 of Pournaras, Pilgerstorfer & Asikis (2018), p. 10:4.

Pseudocode of I-EPOS

ALGORITHM 1: The I-EPOS algorithm.
Input: agent $\mathfrak{a}$, plans $\mathcal{P}_{\mathfrak{a}}$, global cost function $f_G$, local cost function $f_L$, parameter $\lambda$
Result: selected plan $\mathbf{s}_{\mathfrak{a}}^{(t)}$, aggregated response $\mathbf{a}_{\mathfrak{a}}^{(t)}$, global response $\mathbf{g}^{(t)}$
$\mathbf{s}_{\mathfrak{a}}^{(0)} \leftarrow \mathbf{0},\;\; \mathbf{a}_{\mathfrak{a}}^{(0)} \leftarrow \mathbf{0},\;\; \mathbf{g}^{(0)} \leftarrow \mathbf{0},\;\; \mathbf{t}_{\mathfrak{c}}^{(0)} \leftarrow \mathbf{0}\;\; \forall \mathfrak{c} \in \mathcal{C}_{\mathfrak{a}}$;
for $\tau = 1$ to $t$ do
/* BOTTOM-UP PHASE*/
if agent $\mathfrak{a}$ is not a leaf node then
while messages from children are missing do
receive preliminary branch response $\tilde{\mathbf{t}}_{\mathfrak{c}}^{(\tau)}$ from child $\mathfrak{c}$;
end
if $\tau = 1$ then
$\tilde{\delta}_{\mathfrak{c}}^{(\tau)} \leftarrow 1, \;\; \forall \mathfrak{c} \in \mathcal{C}_{\mathfrak{a}}$;
else
compute the preliminary deltas $\tilde{\delta}_{\mathfrak{c}}^{(\tau)} \;\forall \mathfrak{c} \in \mathcal{C}_{\mathfrak{a}}$ from Equation (9);
end
end
compute the preliminary aggregated response $\tilde{\mathbf{a}}_{\mathfrak{a}}^{(\tau)}$ and global response $\tilde{\mathbf{g}}_{\mathfrak{a}}^{(\tau)}$ according to Equation (10);
select preliminary plan $\tilde{\mathbf{s}}_{\mathfrak{a}}^{(\tau)}$ according to Equation (12);
if this agent is not the root node then
send preliminary branch response $\tilde{\mathbf{t}}_{\mathfrak{a}}^{(\tau)} = \tilde{\mathbf{s}}_{\mathfrak{a}}^{(\tau)} + \tilde{\mathbf{a}}_{\mathfrak{a}}^{(\tau)}$ to the parent;
end
/* TOP-DOWN PHASE*/
if this agent is the root node $\mathfrak{r}$ then
$\mathbf{g}^{(\tau)} \leftarrow \tilde{\mathbf{s}}_{\mathfrak{r}}^{(\tau)} + \tilde{\mathbf{a}}_{\mathfrak{r}}^{(\tau)}$;
$\delta_{\mathfrak{r}}^{(\tau)} \leftarrow 1$;
else
receive global response $\mathbf{g}^{(\tau)}$ and delta value $\delta_{\mathfrak{a}}^{(\tau)}$ from the parent;
end
$\delta_{\mathfrak{c}}^{(\tau)} \leftarrow \delta_{\mathfrak{a}}^{(\tau)}\,\tilde{\delta}_{\mathfrak{c}}^{(\tau)}, \;\; \forall \mathfrak{c} \in \mathcal{C}_{\mathfrak{a}}$;
send global response $\mathbf{g}^{(\tau)}$ and delta value $\delta_{\mathfrak{c}}^{(\tau)}$ to each child $\mathfrak{c} \in \mathcal{C}_{\mathfrak{a}}$;
compute selected plan $\mathbf{s}_{\mathfrak{a}}^{(\tau)}$, aggregated response $\mathbf{a}_{\mathfrak{a}}^{(\tau)}$ and branch response $\mathbf{t}_{\mathfrak{c}}^{(\tau)}$ for each child $\mathfrak{c} \in \mathcal{C}_{\mathfrak{a}}$ according to Equation (14);
end

Algorithm 1 of Pournaras, Pilgerstorfer & Asikis (2018), p. 10:7.