FVS PairedFVS VC 3-SAT

# Cutting cycles of rods in space is FPT

Mitchell Jones Department of Computer Science; University of Illinois; 201 N.
Goodwin Avenue; Urbana, IL, 61801, USA<EMAIL_ADDRESS>http://mfjones2.web.engr.illinois.edu/.

###### Abstract

In this short note, we show that cutting cycles of rods is fixed-parameter
tractable by reducing the problem to computing a feedback vertex set in a
mixed graph.

##  1 Introduction

Let $S$ be a collection of $n$ non-vertical segments in $\mathbb{R}^{3}$. For
two segments $s,s^{\prime}\in S$, we say that $s\succ s^{\prime}$ if and only
if $s$ _lies above_ $s^{\prime}$. Formally, if $\ell$ is the vertical line
that meets $s$ and $s^{\prime}$, then $s\succ s^{\prime}$ if and only if the
$z$-coordinate of the point $\ell\cap s$ is larger than the $z$-coordinate of
the point $\ell\cap s^{\prime}$. This induces a relation $\succ$ on the
segments in $S$ (which may not be transitive). In general, this relation may
contain what we call _depth cycles_. By _cutting_ the segments of $S$ into
multiple smaller segments, we obtain a new collection of segments
$S^{\prime}$. The goal is to cut the segments of $S$ such that the relation
for the segments $S^{\prime}$ is a partial ordering (i.e., there are no depth
cycles). The minimum number of such cuts needed is called the _cutting number_
of $S$. See Figure 1. Often segments are referred to as rods, and we use these
terms interchangeably.

Figure 1: A set of segments inducing a depth cycle (left) and the resulting
depth ordering after making a single cut (right).

To summarize, the problem is to make as few cuts as possible to the rods (each
rod may be cut in multiple different places) such that the resulting depth
ordering is acyclic. In this note, we study the parameterized version of the
problem.

######  Problem 1.

Given a set $S$ of $n$ non-vertical segments in $\mathbb{R}^{3}$ and a
parameter $k$, is there an algorithm running in time $f(k)n^{O(1)}$ (where $f$
is some computable function) which decides if all depth cycles can be
eliminated using at most $k$ cuts?

This is equivalent to asking if the above problem is _fixed-parameter
tractable_ ($\FPT$) by the solution size. See [FG06, CFK+15] for a reference
on parameterized algorithms and complexity.

###  1.1 Previous work

Cutting cycles of rods has applications in hidden surface removal and computer
graphics (see discussions in [AKS05] and [dBCvKO08, Chapter 12]). The problem
has been studied from both a combinatorial [AKS05, AS18] and computational
[Sol98, HS01, AdBGM08] viewpoint. Here, we focus on the computational aspect
of the problem.

For a given collection of segments $S$ in $\mathbb{R}^{3}$ with cutting number
$\mu$, Solan [Sol98] was the first to develop an output sensitive algorithm
for the problem, producing a set of $O(n^{1+\varepsilon}\mu^{1/2})$ cuts in
time $O(n^{4/3+\varepsilon}\mu^{1/3})$, for any given $\varepsilon>0$. One can
think of this as a $O(n^{1+\varepsilon}\mu^{-1/2})$-approximation algorithm.
This was further improved to a $O(n\alpha(n)\mu^{-1/2}\log
n)$-approximation111$\alpha(n)$ is the inverse Ackermann function. algorithm
with expected running time $O(n^{4/3+\varepsilon}\mu^{1/3})$ [HS01]. Aronov et
al. [AdBGM08] obtain a $O(\log\mu\log\log\mu)$-approximation algorithm in
$O(n^{4+2\omega}\log^{2}n)$ time222Here, $\omega<2.37$ is the matrix
multiplication constant for multiplying two $n\times n$ matrices., by reducing
the problem to computing a feedback vertex set in a directed graph.

As far as the author is aware, the problem of cutting cycles of rods has not
been studied from a parameterized perspective.

#### Relation to feedback vertex set.

Let $G=(V,A)$ be a directed graph with $n$ vertices $V$ and arc set $A$.
Recall that a subset of vertices $U\subseteq V$ form a _feedback vertex set_
($\FVS$) if $G-U$ is acyclic. It is known that $\FVS\in\FPT$ when
parameterized by the solution size $k$ [CLL+08], running in
$O(4^{k}k!k^{4}n^{3})$ time.

In [AdBGM08], Aronov et al. reduce the problem to computing the feedback
vertex set in a directed graph $G$. In particular, the authors show that if
all depth cycles in $S$ can be eliminated with $k$ cuts, then $G$ admits a FVS
of size at most $2k$. Unfortunately the reverse implication does not hold in
their reduction. Since $\FVS\in\FPT$, the best one can hope for is a
2-approximation algorithm to Problem 1 running in $O(4^{k}k!k^{4}n^{3})$ time,
using their reduction and the result of Chen et al. [CLL+08].

###  1.2 Our results

We prove that Problem 1 is fixed-parameter tractable by the solution size $k$.

######  Theorem 1.

Let $S$ be a collection of $n$ non-vertical segments in $\mathbb{R}^{3}$.
Given an integer parameter $k$, there is an algorithm which decides if all
depth cycles of $S$ can be eliminated with at most $k$ cuts, and runs in time
$O(47.5^{k}k!n^{8})$.

##  2 Proof of Theorem 1

###  2.1 Mixed graphs

A mixed graph $G$ is defined by the tuple $(V,E,A)$, where $V$ is a collection
of $n$ vertices, $E$ is a collection of undirected edges, and $A$ is a
collection of directed arcs. For each edge $e\in E$ with endpoints $u,v\in V$,
we denote $e$ by $\left\\{u,v\right\\}$. Each arc $a\in A$ with tail $u\in V$
and head $v\in V$ is denoted by $(u,v)$. The _total degree_ of a vertex $v$ is
the number of edges and arcs adjacent to $v$. A _cycle_ in $G$ consists of a
sequence of distinct vertices $v_{1},\ldots,v_{\ell}$ in $G$, where
$v_{\ell}=v_{1}$ and for each $1\leq i\leq\ell-1$ either
$\left\\{v_{i},v_{i+1}\right\\}\in E$ or $(v_{i},v_{i+1})\in A$. A subset of
vertices $S\subseteq V$ is a feedback vertex set for $G$ if and only if $G-S$
is acyclic. We will use the following result of [BL11].

######  Theorem 2 ([BL11]).

Let $G$ be a mixed graph on $n$ vertices. Given an integer parameter $k$,
there is an algorithm which decides if $G$ contains a feedback vertex set of
size at most $k$, and runs in time $O(47.5^{k}k!n^{4})$.

###  2.2 Reducing cutting cycles to $\FVS$ in mixed graphs

For a segment $s$ in $\mathbb{R}^{3}$, let $\overline{s}$ be the projection of
$s$ onto the $xy$-plane. Similarly, let
$\overline{S}=\left\\{{\overline{s}}\mid{s\in S}\right\\}$ for our collection
of segments $S$. Given $s\in S$, let $I(s)$ be the set of intersection points
in the arrangement $\mathcal{A}\left({\overline{S}}\right)$ along the segment
$\overline{s}$. We order these intersection points $I(s)$ along $\overline{s}$
arbitrarily and label them $p^{s}_{1},\ldots,p^{s}_{\ell}\in\mathbb{R}^{2}$,
where $\ell=\left|{I(s)}\right|$.

Observe that by cutting each segment $s$ at each of its intersection points
(with the appropriate $z$-coordinate in $\mathbb{R}^{3}$), we remove all depth
cycles (and make $O(n^{2})$ cuts). In particular, it suffices to focus on
cutting segments _only_ at intersection points in order to remove depth
cycles. Indeed, any solution which cuts a segment $s$ at a point which is a
non-intersection can be shifted along $s$ until it meets an intersection, and
remains a valid solution.

Equipped with these observations, we define the following mixed graph
$G_{S}=(V,E,A)$ (see also Figure 2):

  1. (i)

for each $s\in S$, define the vertex set
$V_{s}=\\{v^{s}_{1},\ldots,v^{s}_{\left|{I(s)}\right|}\\}$, where the vertex
$v^{s}_{i}$ represents the $i$th intersection point $p^{s}_{i}$ in $I(s)$. We
set $V=\bigcup_{s\in S}V_{s}$;

  2. (ii)

for each $s\in S$, add the undirected edges
$\left\\{v^{s}_{i},v^{s}_{i+1}\right\\}$ for $1\leq
i\leq\left|{I(s)}\right|-1$ to $E$;

  3. (iii)

for two segments $s\succ t$ for which
$\overline{s}\cap\overline{t}\neq\varnothing$, suppose that
$p^{s}_{i}=p^{t}_{j}$ for some integers $i,j$ (i.e.,
$\overline{s}\cap\overline{t}$ is the $i$th intersection point along
$\overline{s}$, and $\overline{s}\cap\overline{t}$ is the $j$th intersection
point along $\overline{t}$). Then we add the directed arc
$(v^{s}_{i},v^{t}_{j})$ to $A$.

Figure 2: A set of four segments $S$ and the corresponding mixed graph
$G_{S}$.

######  Lemma 3.

All cycles in $S$ can be eliminated with at most $k$ cuts if and only if the
mixed graph $G_{S}$ admits a feedback vertex set of size at most $k$.

###### Proof:

Let $U\subseteq V$ be a feedback vertex set for $G_{S}$. Since each vertex in
$U$ corresponds to an intersection point $p^{s}_{i}$ along some segment $s\in
S$, we cut $s$ at the point with $xy$-coordinates $p^{s}_{i}$ and the
appropriate $z$-coordinate. Let $C$ denote the resulting collection of cuts.
Clearly, the number of cuts we make is $\left|{C}\right|=\left|{U}\right|\leq
k$. We claim that $C$ eliminates all depth cycles. Suppose not, then there is
a cycle consisting of (potentially cut) segments $s_{1}\succ
s_{2}\succ\ldots\succ s_{p}$, where $s_{p}=s_{1}$. Since $s_{i}\succ s_{i+1}$
for $1\leq i\leq p-1$, there is a directed edge
$(v^{s_{i}}_{j(i)},v^{s_{i+1}}_{j^{\prime}(i+1)})$ for each $i$ and indices
$1\leq j(i),j^{\prime}(i)\leq\left|{I(s_{i})}\right|$. Here, the index $j(i)$
(resp. $j^{\prime}(i)$) is chosen such that
$\overline{s_{i}}\cap\overline{s_{i+1}}$ (resp.
$\overline{s_{i}}\cap\overline{s_{i-1}}$) is the $j(i)$th (resp.
$j^{\prime}(i)$th) intersection point along $\overline{s_{i}}$. Since the
vertices of $V_{s_{i+1}}$ are connected by an undirected path, we can travel
from the vertex $v^{s_{i+1}}_{j^{\prime}(i+1)}$ to the vertex
$v^{s_{i+1}}_{j(i+1)}$ along an undirected path $P_{i}$. This corresponds to
moving along the segment $s_{i+1}$. Note that since each vertex in $V$ is
adjacent to exactly one arc, we have that $v^{s_{i}}_{j^{\prime}(i)}\neq
v^{s_{i}}_{j(i)}$ for all $i$. Next, we can take another directed edge
$(v^{s_{i+1}}_{j(i+1)},v^{s_{i+2}}_{j^{\prime}(i+2)})$. Continuing in this
fashion, we can stitch together a cycle which concatenates the directed edge
$(v^{s_{i}}_{j(i)},v^{s_{i+1}}_{j^{\prime}(i+1)})$ followed by the undirected
path $P_{i+1}$ from $v^{s_{i+1}}_{j^{\prime}(i+1)}$ to $v^{s_{i+1}}_{j(i+1)}$,
for $i=1,\ldots,p-1$, to obtain a cycle in $G_{S}-U$. A contradiction.

Conversely, let $C$ be a collection of cuts which eliminates all depth cycles
in $S$. By the above discussion, without loss of generality we can assume that
$C$ cuts the segments of $S$ at intersection points. Since each intersection
point is associated to a vertex in $G_{S}$, we add the vertex $v^{s}_{i}$ to
$U$ if and only if segment $s$ was cut at the intersection point $p^{s}_{i}$.
Clearly, this collection of vertices $U$ satisfies
$\left|{U}\right|=\left|{C}\right|\leq k$. The argument that $U$ is a feedback
vertex set for $G_{S}$ is similar to above. If $U$ is a not a solution, then
there is a cycle in $G_{S}$ which corresponds to a depth cycle in $S$ after
making the cuts in $C$, a contradiction.

Restatement of Theorem 1. Let $S$ be a collection of $n$ non-vertical segments
in $\mathbb{R}^{3}$. Given an integer parameter $k$, there is an algorithm
which decides if all depth cycles of $S$ can be eliminated with at most $k$
cuts, and runs in time $O(47.5^{k}k!n^{8})$.

###### Proof:

The algorithm is straightforward. Given $S$, apply the above reduction to
obtain a mixed graph $G_{S}$. Note that $G_{S}$ has size $O(n^{2})$ (there are
$O(n^{2})$ vertices, and each vertex has total degree at most three), and can
be easily computed in $O(n^{2})$ time. Next, run the algorithm of Theorem 2 on
$G_{S}$ to obtain a feedback vertex set $U$. One can map this set $U$ back to
a cut set $C$ for $S$ by Lemma 3. The total running time of the algorithm is
$O(47.5^{k}k!\left|{G_{S}}\right|^{4})=O(47.5^{k}k!n^{8})$.

#### Acknowledgements.

Thanks to Sariel Har-Peled for suggesting the problem and subsequent
discussions. Thanks also to Chandra Chekuri for discussions on feedback vertex
set and its variants.

## References

  * [AdBGM08] Boris Aronov, Mark de Berg, Chris Gray, and Elena Mumford.  Cutting cycles of rods in space: hardness and approximation.  In Shang-Hua Teng, editor, Proc. 19th ACM-SIAM Sympos. Discrete Alg. (SODA), pages 1241–1248. SIAM, 2008.
  * [AKS05] Boris Aronov, Vladlen Koltun, and Micha Sharir.  Cutting triangular cycles of lines in space.  Discrete Comput. Geom., 33(2):231–247, 2005.
  * [AS18] Boris Aronov and Micha Sharir.  Almost tight bounds for eliminating depth cycles in three dimensions.  Discrete Comput. Geom., 59(3):725–741, 2018.
  * [BL11] Paul S. Bonsma and Daniel Lokshtanov.  Feedback vertex set in mixed graphs.  In Proc. 12th Workshop Alg. Data Struct. (WADS), volume 6844 of Lecture Notes in Computer Science, pages 122–133. Springer, 2011\.
  * [CFK+15] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [CLL+08] Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, and Igor Razgon.  A fixed-parameter algorithm for the directed feedback vertex set problem.  J. ACM, 55(5):21:1–21:19, 2008.
  * [dBCvKO08] Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars.  Computational geometry: algorithms and applications, 3rd Edition.  Springer, 2008.
  * [FG06] Jörg Flum and Martin Grohe.  Parameterized Complexity Theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006\.
  * [HS01] Sariel Har-Peled and Micha Sharir.  Online point location in planar arrangements and its applications.  Discrete Comput. Geom., 26(1):19–40, 2001.
  * [Sol98] Alexandra Solan.  Cutting cylces of rods in space.  In Proc. 14th Int. Annu. Sympos. Comput. Geom. (SoCG), pages 135–142, 1998.


# The Pixel Charging-up effect in Gas Micro-Pixel Detectors

Di-Fan Yi  Qian Liu  Hong-Bang Liu  Fei Xie  Huan-Bo Feng  Zu-ke Feng  Yang-
Heng Zheng

###### Abstract

This study investigates the charging-up effect on the Topmetal-II- chip in Gas
Micro-Pixel Detectors(GMPD). It is found that this effect differs from the
charging-up typically observed in gas detector multiplier devices and
increases the effective gain of the detector. The research indicates that this
effect originates from the accumulation of charges on the insulating layer of
the chip’s pixel surface and is unlikely to dissipate naturally. Iterative
simulations using COMSOL and GARFIELD++ were employed to model the variation
of detector effective gain with the charging-up effect, and a simple yet
effective model was proposed, which aligns well with experimental data. The
study suggests that to ensure stable detector gain and reduce residual
modulation in polarization detection, charging-up to near saturation state is
required before operating the GMPD.

###### keywords:

Charging-up , Gaseous X-ray polarimetry

††journal: NIM-A

[label1]School of Physical Science, University of Chinese Academy of Sciences,
Beijing, 100049, China [label2]School of Physical Science and Technology,
Guangxi University, Nanning 530004, China

##  1 Introduction

Topmetal-II- is a charge-sensitive pixel chip widely used in particle track
detection applications[1]. GMPD is a soft X-ray polarimeter developed by
Guangxi University[2], in which Topmetal-II- is utilized as the photoelectron
track imaging component. With the accumulation of working time, charging-up
occurs on certain components of the detector, forming an electric field
opposite to the drift or avalanche multiplication electric field, thereby
affecting the instrument’s performance. Charging-up effects have been
extensively studied in charge multiplication devices such as gas electron
multiplier (GEM)[3], thick gas electron multipliers (THGEM)[4], gas
microchannel plate (GMCP)[5], and MicroMigas[6], which lead to a decrease in
the electric field strength in the multiplication region, resulting in a
reduction in detector gain. Numerous studies have indicated that the gain of
gas detectors exhibits time evolution when bias is applied. Research has also
shown that the gain of GEM increases over time[7, 8, 9], while the gain of
THGEM initially decreases and then increases over time[10, 11, 12]. The charge
accumulation effect is commonly considered to be a significant factor
influencing gain.

However, for GMPD, the charging-up effect also occurs on the pixels of the
Topmetal-II- chip. The charging-up effect on GMPD has many significant
differences compared to the charging-up effects occurring on the
aforementioned multiplication devices: the charging-up effect on Topmetal-II-
increases the effective gain of the detector, and unless artificial measures
are taken, the charge on Topmetal-II- will hardly dissipate on its own. This
charging-up effect affects the energy resolution of the detector. More
importantly, if the intensity of the incident source has a non-zero gradient,
causing the charging-up effect to occur non-uniformly across the entire chip
surface, it leads to inconsistent gains in different regions, ultimately
affecting the reconstruction of the incident photon’s polarization angle and
resulting in significant residual modulation[13, 14].

This paper investigates the charging-up mechanism of Topmetal-II- and proposes
a simple and experimentally consistent charging-up model through comparisons
and validations with experimental and simulated data. Section 2 of this paper
introduces the polarization detection principles of GMPD, the working
principles, and performance indicators of Topmetal-II-. Section 3 presents the
algorithm for simulating charging-up in Topmetal-II-. Section 4 compares
experimental data with simulation results. Section 5 discusses the impact of
charging-up effects on residual modulation in polarization detection. The
final section 6 provides a summary and outlook.

##  2 Detector structure

The prototype of the GMPD detector is shown in in Figure 1. The entire
detection unit is sealed in an aluminum flow gas chamber, with a constant
pressure mixture of 30% He and 70% dimethyl ether (DME) flowing into the
chamber at a rate of 30 mL/min. The top layer of the detection unit is a
titanium metal thin film cathode; in the middle is a drift region supported by
a 1.4 cm ceramic cylinder structure, with a 300um thick GMCP fixed at the
bottom of the ceramic cylinder, serving as the electron multiplication region.
The Topmetal-II- chip is fixed on the base of the chamber, with a height of
3.4 mm above the chip for the induction region.

Figure 1: (a) GMPD exploded view. (b) GMPD physical top view.

As shown in Figure 2, soft X-rays pass through the cathode window of the
detector unit, and there is a certain probability of photoelectric effect
occurring in the drift region, generating photoelectrons carrying the
polarization information of the incident photons. These photoelectrons deposit
ionization energy in the gas, producing secondary ionization electrons, until
they come to a complete stop. In the induction region, an upward electric
field is applied, causing some of the secondary ionization electrons to drift
downward towards the surface of the GMCP. Some of these electrons enter the
microchannels and undergo avalanche multiplication. The multiplied electrons
then appear from the bottom surface of the GMCP, with some being absorbed,
generating pulse signals. The remaining multiplied electrons continue to drift
towards the Topmetal chip, inducing signals at the corresponding pixel
positions. This process projects the track of the photoelectrons onto the two-
dimensional plane of the Topmetal chip.

Figure 2: Polarization detection principle of GMPD.

The Topmetal-II- is a pixel sensor manufactured using standard 0.35 $\mu$m
complementary metal-oxide-semiconductor (CMOS) technology. The pixel array is
designed in a 72x72 pixel matrix pattern with a pixel pitch of 83 $\mu$m, and
features a 6x6 mm charge-sensitive area. The sensor measures 8x9 mm in size,
with each pixel’s top metal measuring 25x25 $\mu$m. The area of the exposed
top metal electrode designed for direct charge induction is 15x15 $\mu$m.
Figure 3(a) shows a photograph of the sensor bonded to a printed circuit board
(PCB) base through wire bonding, as well as an enlarged view of the pixel
matrix. Figure 3(b) shows the pixel structure of the Topmetal-II-. Each top
metal electrode is surrounded by a protective ring, all of which are connected
together for performance testing. Gaps and coupling capacitance between the
top metal electrode and the protective ring are 3.5 $\mu$m and 5.5 fF,
respectively. Each exposed electrode is directly connected to a low-noise
charge-sensitive amplifier (CSA). When the pixel collects charge, the CSA
immediately converts it into an analog output signal, which can then be output
through analog or digital readout channels. Analog and testing indicate a
charge conversion gain of approximately 196 mV/fC[15].

Figure 3: (a) Top view of the Topmetal-II-. (b) Topmetal-II- pixel CSA
structure. The green portion represents the top metal, which is used to induce
the drift charge signal. C${}_{\text{f}}$ denotes the feedback capacitor.
V${}_{\text{g}}$ represents the gate voltage, V${}_{\text{d}}$ represents the
drain voltage, and V${}_{\text{ref}}$ represents the amplifier’s reference
voltage.

##  3 Charging-up effect and simulation

The mechanism behind the charging-up effect in Topmetal-II- is the
accumulation of electrons on the surface of the charge induction chip. The
surface of the Topmetal-II- chip has a grid-like insulating layer, which only
has 15x15 $\mu$m windows above the top metal. If the charge falls in the
window area, it will be conducted away by the top metal, while electrons that
fall outside the window area on the insulating layer can hardly move.
Therefore, as the number of accumulated events increases during the operation
of the detector, the number of charges falling on the insulating layer outside
the window area gradually increases, forming an increasingly enhanced electric
field in the reverse direction of the induction area as shown in Figure 4(a).
At the same time, since the potential of the window area remains unchanged as
the potential of the top metal, the electric field lines above this area
gradually change from parallel to funnel-shaped, as shown in the figure. The
deformed electric field will attract more electrons from outside the window
area towards the top metal, ultimately increasing the charge collection
efficiency, leading to an effective gain increase in the detector.

To quantitatively understand the impact and variation of charging-up on
collection efficiency, we conducted a combined simulation using COMSOL and
GARFIELD++ to simulate the change in collection efficiency during the process
of charging-up. To simulate the process of charging-up, we followed the
following iterative logic:

  * 1.

Use COMSOL to model the electric field and potential distribution within the
pixel array and detector. As shown in Figure 4(b),(c), to simulate the
accumulation of charge at different positions on the pixel surface, we divided
the insulating layer surface of a single pixel into 3×3 $\mu$m patches,
initialized the charge on each patch, and calculated and solved for the
electric field distribution near the pixel based on the imported surface
charge and potential distribution.

  * 2.

Import the electric field and geometric model obtained from COMSOL into
GARFIELD++. In each iteration, 500 randomly generated electron positions were
created at the height below the GMCP, and the process of these electrons
drifting in the electric field was simulated in GARFIELD++. The positions
where these electrons drifted onto the pixel surface were recorded to simulate
the drift of charge and its distribution on the insulating layer of the pixel.

  * 3.

Based on the distribution of drifting charge on the pixel, update the
accumulated charge on each element. The surface charge density on each element
was updated one by one, and the updated results were input into COMSOL to
solve for the updated electric field distribution above the pixel array, and
steps 2 and 3 are repeated.

Figure 4: (a) Charge Accumulation Schematic: Electrons accumulate on the
insulating layer, forming a low potential region around the top metal. This
leads to the formation of a funnel-shaped electric field above the top metal,
thereby enhancing the charge collection efficiency of the pixel. (b) Front
view structure of a single pixel, where grey represents the insulating layer
where charge accumulates, and blue represents the metal. (c) Back view
structure of a single pixel.

An automated script was developed to facilitate the iterative process of
conversion and updating between COMSOL and GARFIELD++. Following each
iteration, we were able to calculate the charge collection efficiency of the
pixel under the corresponding charging-up state based on the distribution of
the final positions of the electrons.

##  4 Modeling and Comparison

We compared the simulation results of the variation in collection efficiency
$G(n)$ with experimental measurements. The X-ray source used in the experiment
is a 4.51 keV monochromatic source. For each collected set of photoelectron
events, the peak ADC value is obtained by fitting the SumADC distribution
induced on the Topmetal-II- using a crystal ball function. Due to the good
linear relationship between the induced voltage on the chip and the output ADC
value, the measured variation in peak ADC for the monochromatic source can
characterize the change in charge collection efficiency of the pixel.

We considered a more simplified charging-up model that describes the
relationship between the accumulated event count and the accumulated charge in
equation1. Where $n$ is the number of events, $q$ is the accumulated charge on
the chip, and $q_{\text{max}}$ is the maximum saturated accumulated charge,
and $a_{c}$ is the charge adsorption coefficient. Since the surface of
Topmetal-II- is an insulating layer, the charge dissipation rate is extremely
slow, hence we have neglected the charge decay term. The general solution for
$q(n)$ is given by equation 2.The charge collection efficiency $G(n)$ is
proportional to the accumulated charge $q(n)$, but due to the irregular
surface structure of the pixel chip and the interconnected circuits with
different potentials, the relationship between $G(n)$ and $q(n)$ is difficult
to determine analytically. After several attempts, we found that within a
certain range of accumulated charge, $G(n)\propto g(n)^{2}$, as shown by the
fitted red line in Figure 5. The experimental and simulated results exhibited
good consistency. Through the experiments and simulations, we observed that
the change in gain due to charging-up effects gradually saturates as the
accumulation events increase. As the accumulated charges in the insulating
layer are difficult to dissipate, we found that after placing the detector for
a month, the gain remained unchanged within the margin of error.

$\frac{dq(n)}{dn}=\alpha_{c}\left(1-\frac{q(n)}{q_{\max}}\right).$ (1)

$q(n)=x_{0}+x_{1}\exp(x_{2}(n+x_{3})).$ (2)

Figure 5: The variation of chip collection efficiency with the accumulation of
events. The orange points represent experimental data results of 4.51 keV
photoelectron track energy deposition, characterized by fitting the peak ADC
of the data spectrum to represent the variation in chip charge collection
efficiency. The blue points represent the trend of collection efficiency
variation obtained from the joint simulation using COMSOL and GARFIELD++.

##  5 Impact on polarization detection

Figure 6 illustrates the residual modulation caused by the charging-up effect.
Initially, a ferrous strip was used to partially obstruct a section of the
detector’s field of view, leaving a gap of approximately 3 mm. Following a
2-hour exposure to an X-ray flat source, the obstruction was removed, and a
5.9keV unpolarized Fe55 source was used to irradiate and collect the
photoelectron tracks. Upon reconstruction, it was observed in Figure 6(a) that
the signal gain at the previous narrow gap position was significantly higher
than the shaded area, and the residual modulation in the narrow gap area was
higher than in the shaded area, with the modulation direction parallel to the
gap. Subsequently, without any obstruction, the X-ray flat source was used
again for 4 hours to accumulate charges on the entire surface of the chip to
near saturation. The detector was then irradiated with the 5.9keV unpolarized
Fe55, and the tracks were reconstructed in Figure 6(b). Comparing the results
of the Fe55 measurements before and after charging-up reached saturation, it
was found that the residual modulation caused by the uneven gain due to
charging-up significantly decreased. Therefore, it is possible to mitigate the
impact of the charging-up effect by calibrating or measuring the detector
after saturating the charging-up before conducting experiments. Since the
accumulated charge is unlikely to naturally dissipate, once the detector is
encapsulated, only one thorough charging-up is required.

Figure 6: (a) The residual modulation distribution of 5.9keV Fe55 tracks after
uneven charging-up due to narrow gap obstruction. (b) The residual modulation
distribution of 5.9keV Fe55 tracks after uniform charging-up following the
removal of the narrow gap obstruction. The heatmap represents the distribution
of the reconstructed photoelectron emission positions of the tracks, with the
direction of the red lines indicating the direction of residual modulation.
The length of the line and the adjacent number represent the value of the
residual modulation.

##  6 Conclusion

This study investigates the charging-up effect on the Topmetal-II- chip in
GMPD detectors. We found that this effect differs from the charging-up
typically observed in gas detector multiplier devices, and it leads to an
increase in the effective gain of the detector. Our research indicates that
this effect originates from the accumulation of charges on the insulating
layer of the chip’s pixel surface. We simulated the process of charging-up on
the Topmetal-II- chip surface and the evolution of pixel charge collection
efficiency during the charging-up process. The simulated results align well
with the gain variation curve obtained from experimental measurements. By
combining experimental data and physical mechanisms, we have proposed a simple
model to describe the charging-up effect and the variation in detector gain.
This model allows us to calculate the gain under different charging-up states
and estimate the magnitude of the saturated gain.

The charging-up effect of Topmetal-II- can enhance the effective gain of the
detector. We also observed that the charges accumulated on the chip’s surface
are unlikely to dissipate naturally and require the use of metal materials in
contact with the chip surface to dissipate the charges, or the use of positive
ion wind guns to neutralize the surface charges in order to restore the
detector’s gain performance to its pre-charging-up state. Therefore, the
charging-up effect contributes to the improvement of the detector’s
performance and stability. However, uneven charging-up effects can cause
variations in gain across different regions of the chip, and polarization
measurements require the pixel array of the detector to maintain good
consistency and stability. Thus, our research results indicate that prior to
conducting polarization detection in GMPD, the detector needs to undergo a
period of charging-up to ensure stable detector performance and minimize
residual modulation in polarization detection.

## References

  * [1] Z. Li et al., “Preliminary test of topmetal-ii- sensor for x-ray polarization measurements,” Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, vol. 1008, p. 165430, 2021.
  * [2] H.-B. Feng et al., “Spectral and polarimetric characterization of the gas microchannel plate pixel detector,” Journal of Instrumentation, vol. 18, p. P08012, aug 2023.
  * [3] M. Alfonsi et al., “Simulation of the dielectric charging-up effect in a gem detector,” Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, vol. 671, pp. 6–9, 2012.
  * [4] G. Song et al., “A fast simulation method for thgem charging-up study,” Journal of Instrumentation, vol. 15, p. P04015, apr 2020.
  * [5] H. Feng et al., “Charging-up effects for gas microchannel plate detector,” Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, vol. 1055, p. 168499, 2023.
  * [6] M. Chefdeville et al., “Development of micromegas detectors with resistive anode pads,” Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, vol. 1003, p. 165268, 2021.
  * [7] B. Azmoun et al., “A study of gain stability and charging effects in gem foils,” in 2006 IEEE Nuclear Science Symposium Conference Record, vol. 6, pp. 3847–3851, IEEE, 2006.
  * [8] P. Hauer et al., “Measurements of the charging-up effect in gas electron multipliers,” Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, vol. 976, p. 164205, 2020.
  * [9] M. Alfonsi et al., “Simulation of the dielectric charging-up effect in a gem detector,” Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, vol. 671, pp. 6–9, 2012.
  * [10] M. Alexeev et al., “The gain in thick gem multipliers and its time-evolution,” Journal of Instrumentation, vol. 10, no. 03, p. P03026, 2015.
  * [11] P. Correia et al., “Simulation of gain stability of thgem gas-avalanche particle detectors,” Journal of Instrumentation, vol. 13, no. 01, p. P01015, 2018.
  * [12] M. Pitt et al., “Measurements of charging-up processes in thgem-based particle detectors,” Journal of Instrumentation, vol. 13, no. 03, p. P03009, 2018.
  * [13] L. Baldini et al., “Design, construction, and test of the gas pixel detectors for the ixpe mission,” Astroparticle Physics, vol. 133, p. 102628, 2021.
  * [14] J. Rankin et al., “An algorithm to calibrate and correct the response to unpolarized radiation of the x-ray polarimeter onboard ixpe,” The Astronomical Journal, vol. 163, p. 39, jan 2022.
  * [15] C. Gao, G. Huang, and X. Sun, “Topmetal-ii-: a direct charge sensor for high energy physics and imaging applications,” Journal of Instrumentation, vol. 11, p. C01053, jan 2016.


# Revisiting MAB based approaches to recursive delegation

Nir Oren

(2 November 2023)

###### Abstract

In this paper we examine the effectiveness of several multi-arm bandit
algorithms when used as a trust system to select agents to delegate tasks to.
In contrast to existing work, we allow for recursive delegation to occur. That
is, a task delegated to one agent can be delegated onwards by that agent, with
further delegation possible until some agent finally executes the task. We
show that modifications to the standard multi-arm bandit algorithms can
provide improvements in performance in such recursive delegation settings.

##  1 Introduction

Open multi-agent systems (MAS) are composed of agents under different
organisational control, and whose internal goals and mental states cannot be
observed. In such systems, agents often have differing capabilities, and must
rely on each other when pursuing their goals, making task delegation
commonplace. This delegation occurs when one agent (the _delegator_) requests
that another (the _delegatee_), execute a task. A fundamental problem faced by
the delegator involves selecting the most appropriate delegatee to whom the
task should be delegated, and a significant body of work centred around trust
and reputation systems has examined how such a delegation decision should take
place [6, 12, 13].

At their heart, trust and reputation systems associate a rating with each
potential delegatee, and select who to delegate a task to based on this
rating. Following task execution, the rating is updated based on how well the
task was completed. Different systems compute the ratings differently, for
example incorporating indirect information from other agents in the system [8,
14], or utilising social and cognitive concepts as part of the computation
process [4]. Trust and reputation systems can also differ in the way they
select a delegatee, for example by using the rating to weigh the likelihood of
selection. While trust and reputation systems seek to satisfy many properties
including resistance to different types of attacks by malicious agents [7], at
their heart, they balance the exploration of delegatee behaviour with the
exploitation of high quality delagatees. Balancing exploration versus
exploitation also lies at the heart of multi-arm bandit (MAB) problems [9],
and several approaches to trust and reputation have been proposed which build
on MAB algorithms [15].

With few exceptions [2, 3], trust and reputation systems assume that
delegation is non-recursive. That is, once a delegator passes a task onto a
delegatee, it is executed by the latter. However, in many settings, a
delegatee could delegate the task on to another agent, who in turn could
delegate it further. Such _recursive delegation_ naturally arises in the real
world. For example, outsourcing is commonplace in the hydrocarbon exploration
domain, where a company wishing to search for oil may task another company
with finding a ship, and this company outsources crew selection to another
company, etc. Failure in one part of this _delegation chain_ requires the
first company to decide how to ascribe blame down the chain, affecting its
future decisions about who to interact with.

While delegated tasks may be decomposed in different ways with various complex
interrelationships (c.f., HTN planning [5]), in this paper we consider the
recursive delegation of an atomic task. Our main contributions are as follows.

  * •

We demonstrate the importance of considering delegation in the context of the
exploration versus exploitation problem.

  * •

We propose and evaluate several algorithms for recursive delegation,
demonstrating differences in performance between these and non-delegation
aware algorithms.

The next section of the paper describes the recursive delegation problem and
introduces the algorithms which we evaluate in Section 3. We discuss related
and future work in Section 4 before concluding.

##  2 Recursive Delegation in a MAB setting

Consider the system of agents shown in Figure 1. Here, we assume that agent
$a$ will delegate a task to either agent $b$ or agent $c$. If $b$ is delegated
to, they can delegate the task to $d$ or $e$, while if $c$ is delegated to,
they can delegate the task onwards to $f$. Once the task reaches $d,e$ or $f$,
it will be executed.

Figure 1: Left: a simple delegation scenario. Right: the same scenario with
the addition of virtual agents.

Now assume that $a$ is unaware of the possibility of recursive delegation, and
that they delegate a task to $b$, who delegates it onto $d$, with $d$
unsuccessfully completing the task. $a$ then delegates another task to $c$
(and thus onto $f$), with the task now successfully completed. In such an
instance, $a$ will trust $c$ more than $b$, unaware that $b$ may next delegate
onto $e$. If $e$ is more likely to successfully complete a task than $f$ (who
in turn is more likely to succeed in the task than $d$), then $a$’s delegation
strategy is sub-optimal. Instead, $a$ should recognise that agent $e$ has not
yet been delegated to, and its success rate is unknown, and therefore again
delegate a task to $b$. It is this intuition that we attempt to capture in our
MAB-based delegation algorithms. While the standard MAB based algorithms we
build on consider delegation to a single node, the algorithms we propose must
consider the various ways delegation can occur passing through a given agent.

Note that in this paper, we assume that only agents at the leaves of our
delegation graph can execute tasks. This is not a significant restriction as
any agent which can delegate or execute a task can be modified through the
introduction of a virtual agent to which it can delegate as a leaf (c.f., the
right side of Figure 1, where agents labelled with a prime represent such
virtual agents); this virtual agent represents the agent taking an execution
action.

In the rest of this section we consider several widely used MAB algorithms,
namely $\epsilon$-greedy; UCB1; Bayesian (Beta) UCB; and Thompson sampling.
The standard (i.e., non-delegation aware) variant of these algorithms treats
each delegation action as a single instance of a MAB. Returning to Figure 2,
$a$ would select between $a^{\prime}$,$b$ and $c$ by treating it as a single
MAB problem based on the historic success of $a^{\prime}$, $b$ and $c$ and any
other parameters relevant to the algorithm. If (for example) $b$ is then
selected, that agent would choose to delegate to $b^{\prime}$, $d$ or $e$
again based on the historic success of these agents, ignoring future
delegation possibilities.

Our delegation-aware variant of the algorithms instead considers possible
delegation paths. In general, loops are possible in arbitrary delegation
structures, and we assume that an agent will not delegate to an agent already
appearing in the delegation chain. Our primary modification of the standard
MAB algorithms therefore involves changing how the expected utility of
potential delegatees is calculated, which we describe next.

It is worth noting that we make one assumption across all our delegation
algorithms, namely that the result of a delegation is binary; either the task
succeeds, or fails. Integrating different possible levels of task success is
one important avenue of future work.

###  2.1 $\epsilon$-greedy

The standard $\epsilon$-greedy algorithm selects a random agent to delegate to
with likelihood $\epsilon$, and selects the agent with the highest historic
success rate with likelihood $1-\epsilon$. After every interaction, the
success rate of the executing agent is updated. In a recursive delegation
setting, success rates are updated for all delegating agents too.

Our adaptation of this basic algorithm involves the delegating agent
considering how onwards delegation may occur, based on the expected utility of
a delegation. The pseudo-code for calculating this utility is shown in
Algorithm 1.

1:A value $\epsilon$

2:function Calculate-utility($a,chain$)

3: $poss\\_del\leftarrow$ neighbors($a$) $\backslash chain$

4: if $poss\\_del=\emptyset$ then

5: return succ($a$)/(succ($a$)+fail($a$))

6: end if

7: $util\leftarrow 0$

8: $best\leftarrow 0$

9: for all $c\in poss\\_del$ do

10: $uc\leftarrow$ Calculate-utility($c,chain+[a]$)

11: if $uc>best$ then

12: $best\leftarrow uc$

13: end if

14: $util\leftarrow\epsilon\frac{uc}{|poss\\_del|}$

15: end for

16: return $util+(1-\epsilon)best$

17:end function

Algorithm 1

This algorithm takes an agent and the chain of delegations until that agent as
input, and identifies the set of possible delegations that that agent can
delegate to (assuming that an agent cannot be delegated the same task twice).
If no possible delegators exist, then the agent must execute the task, and we
return the expected likelihood of successfully doing so (succ($a$) and
fail($a$) denote the number of times the agent has successfully, or
unsuccessfully, executed a task respectively).

Otherwise, the utility of every possible delegation is (recursively)
calculated, recognising that each such delegation is equally likely to be
selected based on $\epsilon$. The utility of the optimal delegation is also
calculated, allowing us to determine the net expected utility of delegating a
task to agent $a$.

Once the expected utility for a delegation has been computed, we can apply the
standard $\epsilon$-greedy algorithm to undertake the delegation, selecting
the agent with highest (expected) utility with likelihood $1-\epsilon$, and a
random agent with likelihood $\epsilon$.

###  2.2 UCB

In the delegation context, the UCB algorithm selects a delegatee based on the
_upper confidence bound_ associated with the delegatee. With no information
about the probability distribution underlying the delegatee’s behaviour, this
bound is computed as the mean reward received so far plus an additional term
$\sqrt{\frac{2\log n}{n_{0}}}$ where $n$ is the total number of delegations
performed so far across the system, and $n_{0}$ is the total number of times a
task has been delegated to the delegatee under consideration.

Our adaptation of the basic UCB algorithm involves us considering the UCB of
the node at which execution takes place. The UCB value of a parent node is
then the maximal UCB value of all its child nodes, with a delegator delegating
to the delegatee with the maximum UCB value. This calculation of the UCB value
is formalised in Algorithm 2 where $C$ (in line 4) is a constant which helps
control the level of exploration of the algorithm.

1:function Calculate-UCB-utility($a,chain$)

2: $poss\\_del\leftarrow$ neighbors($a$) $\backslash chain$

3: if $poss\\_del=\emptyset$ then

4: return
$\frac{succ(a)}{succ(a)+fail(a)}+C\sqrt{\frac{2\log{n}}{succ(a)+fail(a)}}$

5: end if

6: return $\max_{c\in poss\\_del}$ Calculate-UCB-utility($c,chain+[a]$)

7:end function

Algorithm 2

The difference between the mean and upper confidence bound in our system is a
measure of the uncertainty in the estimate of the performance of a delegatee.
By modeling this uncertainty using a Beta distribution, we can change the UCB
term in line 4 to the standard deviation of the distribution. We refer to this
variant of the UCB algorithm as the Beta-UCB algorithm. As will be shown in
the next section, doing so significantly improves the performance of the
algorithm.

###  2.3 Thompson Sampling

Another popular, and very effective, algorithm used in the multi-arm bandit
literature is Thompson sampling. Here, the value associated with a delegatee
is computed by randomly sampling from a probability distribution representing
the delegatee (which in our case is the Beta distribution.

In the recursive delegation situation, we are now faced with a choice. When
two possible paths reach the same task executor, we can either sample this
executor twice, propagating the value upwards, or sample once, and propagate
the same value up. Sampling only once provides significant performance
improvements (as it facilitates caching), and was thus the approach we used.
Algorithm 3 summarises the utility computation under this approach.

1:function Calculate-TS-utility($a,chain$)

2: $poss\\_del\leftarrow$ neighbors($a$) $\backslash chain$

3: if $poss\\_del=\emptyset$ then

4: return sample from Beta($succ(a),fail(a)$)

5: end if

6: return $\max_{c\in poss\\_del}$ Calculate-TS-utility($c,chain+[a]$)

7:end function

Algorithm 3

##  3 Evaluation

We evaluated the four algorithms described above against their “standard”
counterparts in a variety of scenarios111Source code is available at
https://github.com/jhudsy/RecursiveDelegationMAB and examined the average
resultant cumulative regret over multiple runs.

Figure 2 illustrates the performance of the four algorithms averaged over 100
different binomial graphs (with the probability of edge creation set to 0.3).
In this figure, the UCB constant for both standard and Beta-UCB approaches was
set to 3. Outwith the standard UCB algorithm, the modified, delegation-aware
variants of the algorithms outperform their standard counterparts. However,
for Epsilon-greedy, the performance of the two algorithms is very close, while
for the Beta-UCB variant, the delegation-aware variant initially does not
perform as well as it undertakes more exploration around possible delegations
than the standard version of the algorithm. We believe that for the UCB case,
the poor performance of the delegation-aware variant occurs as exploration
dominates due to the way in which UCB is calculated.

Figure 2:  Evaluation of the four algorithms with 20 agents using a binomial
graph topology. Exploration parameters for both UCB algorithms were set to 3.

Figure 3 shows how the UCB variants performed when their associated constant
was reduced from 3 to 1. As can be seen, the reduction in exploration allowed
both standard UCB variants to reduce their cumulative regret, though the
classic version of the algorithm still outperformed the delegation aware
variant. Turning to Beta-UCB, we can see that while the delegation-aware
variant still performed better, its regret was much worse than the case with a
higher exploration constant. These results indicate that the fine-tuning of
this constant is therefore of critical importance to the performance of these
algorithms.

Figure 3:  Evaluation of the UCB algorithms with exploration parameters set to
1.

We also considered the impact of changing the number of agents in the system.
An increased number of agents would potentially allow more possible
delegations to occur, increasing the need for exploration. The results of this
experiment are shown in Figures 4 (for 10 agents) and 5 (for 50 agents). As
can be seen, with fewer agents, the performance of Beta-UCB improves. For 50
agents, after 20000 iterations, the standard version of Beta-UCB still
outperforms the delegation-aware variant (though the gap is closing). For
Thompson sampling, the delegation-aware version of the algorithm consistently
outperforms the standard version across different numbers of agents.

Figure 4:  Evaluation of the four algorithms with 10 agents using a binomial
graph topology. Figure 5:  Evaluation of the four algorithms with 50 agents
using a binomial graph topology.

Turning our attention to the level of connectedness of the graph, Figure 6
illustrates the case where the probability of agent connection increases from
0.3 to 0.6. These results again illustrate that as the number of possible
paths increases, the UCB algorithms struggle to cope with the additional
exploration, while Thompson sampling still continues to perform well. We
believe that this is due to the manner in which we propagate the results of
Thompson sampling up the delegation chain which reduces the amount of
exploration needed by the system.

Figure 6:  Evaluation of the four algorithms with 20 agents using a binomial
graph topology with connectedness set to 0.6.

Finally, we examined the impact of graph topology. Figure 7 shows the results
when the algorithms are evaluated over a directed scale-free network. Here,
the performance of the standard and variant algorithms is near-identical due
to the low number of delegation choices available to the agents; this result
shows how (unsurprisingly) our variant algorithms operate in a way similar to
the classic algorithms in simple settings.

Figure 7:  Evaluation of the four algorithms over a small world topology.

##  4 Related and Future Work

As mentioned above, while there has been a significant amount of work in the
area of trust and reputation systems, relatively little research has
considered the problem of recursive delegation. Afanador et al. [2, 1] tackled
the problem through the use of _delegation games_. Afanador et al. also
considered another multi-arm bandit based approach to recursive delegation,
namely through an approximation of the Gittens index, to determine which agent
to delegate to.

Another examination of recursive delegation was undertaken by Burnett and Oren
[3]. In this work, the authors examined how rewards and punishments (in the
form of increasing/decreasing trust values) should be apportioned to agents
depending on their position in a delegation chain.

The goal of this paper was to highlight the recursive delegation problem
noting that standard algorithms often work poorly in this domain, and to
encourage additional research in the area. While one important avenue of
future work is to identify additional effective algorithms to cater for
recursive delegation, multiple additional pathways for future research exist,
which we intend to pursue. For example, we note that in the current
formalisation, agents have full visibility of the system. In realistic
scenarios, delegators and delegatees may have partial information about
different parts of the domain. This could include knowledge of the topology of
the delegation graph and partial information about who was delegated to. An
example of the latter is that when a task is executed successfully, a
delegatee may wish to claim credit without informing the delegator about who
executed the task, while if failure happens, the delegatee may wish to blame
who they delegated to for the failure, introducing mitigating circumstances
[11]. Other variants of the problem could involve new agents entering and
exiting the system; agents being busy with other tasks; costs associated with
delegations (which would potentially relate the problem to principal agent
theory [10]); the incorporation of indirect trust information into the system;
and so on. In addition, the large body of work covering trust and reputation
systems has considered many different facets of the (single) delegation
problem, and many of these could need reconsideration in the context of
recursive delegation.

##  5 Conclusions

In this paper we considered the problem of recursive delegation, modelling it
as a (recursive) multi-arm bandit problem. We modified the $\epsilon$-greedy;
Thompson sampling and two versions of the UCB algorithms to cater for
recursive delegation, and evaluated these modified version against their
standard counterparts across different hyperparameters; number of agents and
graph topologies. Our results indicate that in many situations the recursive
delegation aware variants (particularly Thompson sampling) outperform the
standard techniques, though the additional exploration inherent in the
recursive delegation case can significantly affect algorithm performance.

Our work seeks to highlight the recursive delegation problem and its
importance to real-world settings while aiming to spur additional research in
the area. This paper serves as a first step to investigations in the domain,
and we have highlighted several important avenues for future work.

## References

  * [1] J. Afanador.  Recursive Delegation and a Trust-Measuring Algorithm.  PhD thesis, University of Aberdeen, 2019.
  * [2] J. Afanador, M. S. Baptista, and N. Oren.  Algorithms for recursive delegation.  AI Communications, 32(4):303–317, 2019.
  * [3] C. Burnett and N. Oren.  Sub-delegation and trust.  In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, pages 1359–1360, 2012.
  * [4] R. Falcone and C. Castelfranchi.  Social trust: A cognitive approach.  Trust and deception in virtual societies, pages 55–90, 2001.
  * [5] I. Georgievski and M. Aiello.  HTN planning: Overview, comparison, and beyond.  Artificial Intelligence, 222:124–156, 2015.
  * [6] J. Granatyr, V. Botelho, O. R. Lessing, E. E. Scalabrin, J.-P. Barthès, and F. Enembreck.  Trust and reputation models for multiagent systems.  ACM Computing Surveys (CSUR), 48(2):1–42, 2015.
  * [7] A. Jøsang and J. Golbeck.  Challenges for robust trust and reputation systems.  In Proceedings of the 5th International Workshop on Security and Trust Management (SMT 2009), Saint Malo, France, 2009.
  * [8] S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina.  The eigentrust algorithm for reputation management in P2P networks.  In Proceedings of the 12th International Conference on World Wide Web, WWW ’03, page 640–651, 2003.
  * [9] V. Kuleshov and D. Precup.  Algorithms for multi-armed bandit problems.  arXiv preprint arXiv:1402.6028, 2014.
  * [10] J.-J. Laffont and D. Martimort.  The Theory of Incentives: The Principal-Agent Model.  Princeton University Press, Princeton, NJ, USA, 2001.
  * [11] S. Miles and N. Griffiths.  Incorporating mitigating circumstances into reputation assessment.  In CARE/MFSC@AAMAS, volume 541 of Communications in Computer and Information Science, pages 77–93. Springer, 2015.
  * [12] I. Pinyol and J. Sabater-Mir.  Computational trust and reputation models for open multi-agent systems: a review.  Artificial Intelligence Review, 40(1):1–25, 2013.
  * [13] M. Sievers.  Modeling trust and reputation in multiagent systems.  In Handbook of Model-Based Systems Engineering, pages 1–36. Springer, 2022.
  * [14] W. L. Teacy, M. Luck, A. Rogers, and N. R. Jennings.  An efficient and versatile approach to trust and reputation using hierarchical bayesian modelling.  Artificial Intelligence, 193:149–185, 2012.
  * [15] T. Vallée, G. Bonnet, and F. Bourdon.  Multi-armed bandit policies for reputation systems.  In Proceedings of the 12th International Conference on Practical Applications of Multi-Agent Systems, pages 279–290. Springer, 2014.