4in!Logarithmic algorithms for fair division problems]Logarithmic algorithms for fair division problems

A. Grebennikov]Alexandr Grebennikov
A. Grebennikov: Saint-Petersburg State University, Department of Mathematics and Computer Sciences, 14th Line 29B, Vasilyevsky Island, St.Petersburg 199178, Russia

X. Isaeva]Xenia Isaeva
X. Isaeva: HSE University, department of mathematics, Usacheva str. 6,  Moscow, 119048, Russia

A. V. Malyutin]Andrei V. Malyutin

A. V. Malyutin: St. Petersburg Department of Steklov Institute of Mathematics,

Fontanka 27, St. Petersburg 191011, Russia;
St. Petersburg State University

M. Mikhailov]Mikhail Mikhailov
M. Mikhailov: St Petersburg University, department of mathematics and mechanics, University avenue 28, Saint Petersburg, 198504, Russia

O. R. Musin]Oleg R. Musin
O. R. Musin: University of Texas Rio Grande Valley, One West University Boulevard, Brownsville, TX, 78520

We study the algorithmic complexity of fair division problems with a focus on minimizing the number of queries needed
to find an approximate solution with desired accuracy.
We show for several classes of fair division problems that under certain natural conditions on sets of preferences, a logarithmic number of queries with respect to accuracy is sufficient.

Mathematics Subject Classification 91B32 68Q17 52C45

§ INTRODUCTION

The problem of fair division is old and famous, it has many forms and arises in numerous real-world settings. See, e. g.,  [12] and references therein for an introduction to the subject.
Among the many interesting aspects of this problem, the area of algorithmic issues stands out.
The state of art here is well characterized by the following words of [12]:
“The main unresolved issue ... is the general question of finding bounded finite algorithms for envy-free division for any number of players. This is a well-known problem, and any algorithm for envy-free division, even for special small cases ... would be of interest.”

In this paper we investigate fast algorithms for some particular cases of the rental harmony and cake-cutting problems.
To recall the former, suppose a group of friends consider renting a house but they shall first agree on how to allocate its rooms and share the rent. They will rent the house only if they can find a room assignment-rent division which appeals to each of them.
We call this problem the rental harmony problem, following Su [15].
Our investigation of the rental harmony problem starts with the simplest situation when each of the tenants forms for their own opinion  of a fair price for each of the rooms, according to the tenant's own criteria, and is ready to rent a room at this or lower price, regardless (say, not knowing) how the rest of the rent is distributed among other tenants.

In the envy-free cake-cutting problem, a “cake” (a heterogeneous divisible resource) has to be divided among $d$ partners with different preferences over parts of the cake [5, 13, 14, 15].
An alternative interpretation of this problem is as several subcontractors distribute parts of some job among themselves.
In particular, to emphasize the duality with the rental harmony problem, suppose a group of workers discussing renovating a house but they shall first agree on who is in charge of which room and allocate the reward.
The simplest version for this problem is when each of the workers forms their own opinion of a fair price for repairing each of the rooms, according to the worker's own criteria, and is ready to renovate a room for this or greater fee.

A convenient visual-geometric point of view
on the fair division problems is provided by the configuration space approach.
In case of $d$ agents (friends/ tenants/ partners/ subcontractors/ workers) the configuration space of all possible rent/reward allocations is the standard $(d-1)$-dimensional simplex $A=\Delta^{d-1}$, that is, all representations of a positive number as a sum of $d$ nonnegative ones.
The preference sets of agents are then subsets of this simplex, the conditions of existence of a fair division can be formulated as conditions on these sets, and solution existence theorems are related to extensions of the KKM (Knaster–Kuratowski–Mazurkiewicz) lemma.[The existence of a solution to envy-free division problems was discussed in [1, 3, 6, 7, 11, 15]. Gale [7] proved a colorful (rainbow) version of the KKM lemma that can be applied for the existence theorem proved by Su [15].]
The mentioned above simplest versions are the cases where these subsets are intersections of the simplex with half-spaces whose boundaries are parallel to the faces of the simplex.
Another case we consider is of convex preference sets.

In terms of configuration spaces, the fair division problems we study are formulated as follows.
There is a simplex and collections of preference sets (satisfying conditions of solution existence).
We do not know these sets, but we can ask which of these sets contain any chosen point of the simplex.

We are interested in algorithms for finding (approximate) solutions aimed at minimizing the number of queries.

We consider two types of queries.
One of these two means that we choose a preference set and a point and check whether this set contains this point.
For example, for the rental harmony problem this means that a tenant says if a given room suits them under a given rent distribution.
We call this type of query the binary mode.
Another approach, which we refer to as the minimal mode, is when a tenant indicates one of the rooms that suits them (under a given rent distribution).

Another important issue is that we are not looking for a point close to a solution (there is no finite algorithm for finding such a point in general), but a point that is a solution when all preference sets increase by a prescribed $\eps$ (in a natural metric on the simplex). Such a point is called an $\eps$-fair division point.

Taking the configuration space point of view, we immediately see that an $\eps$-fair division point can be found in less than $n^{d-1}$ queries, where $n$ stands for $\ceil{1/\eps}$. Indeed, it is enough to check all the vertices of some triangulation mesh size less than $\eps$.
The main point of the present article is that, under certain natural conditions on preference sets, a logarithmic number of queries with respect to accuracy is sufficient (provided we know in advance that the preference sets satisfy the conditions).

In particular, in the case when all preference sets are intersections of the simplex with half-spaces of a certain kind (motivated by the cake division problem) Theorem <ref> says that $(d-1)^2\ceil{\log_2 (n \cdot (d-1))}$ queries suffice in binary mode, and in the case when all preference sets are intersections with half-spaces of another specific kind (motivated by the rent division problem) Theorem <ref> states that $(d-1)\ceil{\log_{\frac{d}{d-1}} n}$ queries suffice in minimal mode.

If the preference sets are convex and $d=3$, Theorem <ref> says that $O(\log^2(n))$ queries in binary mode are enough for the rental harmony problem.
A similar result concerning the cake-cutting problem is Theorem 6 in [4].

§ STATING THE PROBLEM

Let $d$ be a positive integer[In those situations where the case $d = 1$ is degenerate, we will assume by default that $d\ge 2$.],
let $A$ be a $(d-1)$-dimensional regular simplex with edges of length $1$ in $\R^{d-1}$,
and let $v_1, \ldots, v_d$ be the vertices of $A$.
For $j\in\{1, \ldots, d\}$, we denote the facet $\conv{\{v_k\}_{k \neq j}}$ of $A$ by $F_j$.
For the rental harmony problem, $A$ corresponds to all representations of total price as a sum of $d$ nonnegative numbers; and $F_j$ is precisely the set of price distributions with zero price for the $j$th room.

Assume that for each $i\in\{1, \ldots, d\}$ a covering $\{A_{i1}, \ldots, A_{id}\}$ of $A$ consisting of $d$ closed sets is fixed (these coverings are preferences of our agents):

\bigcup_{j\in\{1,\ldots,d\}} A_{ij} = A,
% \bigcup_{1 \le j \le d} A_{ij} = A,

but the elements of these coverings are not known to us.

We want to find a way to split the total price into $d$ prices of rooms such that every person is “satisfied” with it.
We will denote by $\eps$ the maximum “error” we allow.

For $\eps \ge 0$,
we denote the $\eps$-neighbourhoods of the preference sets as

A^{\eps}_{ij} = \{x \in \R^{d-1}: \dist(x, A_{ij}) \le \eps \}

and the intersections of these $\eps$-neighbourhoods as

I^{\eps}_i = A^{\eps}_{i1} \cap \ldots \cap A^{\eps}_{id}.

We introduce the following definition.

We say that $x$ in $A$ is an

$\eps$-fair division point
if there exists a permutation $\sigma$ of $(1,\ldots,d)$ such that $x \in A^{\eps}_{j\sigma(j)}$ for all $j\in\{1,\ldots,d\}$.
We say that $x$ a fair division point if $x$ is an $\eps$-fair division point for $\eps = 0$.

General theory provides some reasonable sufficient conditions when a fair division point exists.
For example, the rainbow KKM lemma tells it exists whenever

\conv{\{v_j\}_{j \in J}} \subset \bigcup_{j \in J} A_{ij} \text{\; for all\;} i\in \{1, \ldots, d\}, J \subset \{1, \ldots, d\},

and a rainbow generalization of Sperner's lemma implies that it exists whenever

\conv{\{v_j\}_{j \in J}} \cap \bigcup_{j \notin J}A_{ij}  = \emptyset \text{\; for all\;} i\in \{1, \ldots, d\}, J \subset \{1, \ldots, d\}.

Our goal is to find an $\eps$-fair division point using the smallest possible number of queries.

Now we give a formal definition for the two types of queries.
One of these two is as follows: we choose an index $i$ and a point $x \in A$ and receive an index $j$ such that $x \in A_{ij}$ as an answer; we call this type of query the
minimal mode.

Another approach is: we choose indices $i$ and $j$ and a point $x \in A$ and receive “yes” if $x \in A_{ij}$ and “no” otherwise;
this type of query is called the
binary mode.

§ PREFERENCE SETS WITH THE INCLUSION PROPERTY

In this section we prove two auxiliary constructive statements showing that if the collection of preference sets has a specific property (given in  Definition <ref>),
then one can find a solution point (i) in a set of points each of which is found separately for each of the agents according to their preferences, and (ii) without information about (the preferences of) one of the agents.[Of course, to move from a solution point to the corresponding solution itself (for example, to a specific resource allocation between the agents), information about the excluded agent's preferences may also be needed.]
[This is directly related to the results of [1], see also [6], where it is proved that there exists an envy-free rent division that remains so for any change in the preferences of one of the tenants.]
Lemma <ref> is a purely combinatorial statement, and Theorem <ref> applies this combinatorics to our problem.

Let $\{ \le_1,\ldots, \le_d \}$
be $d$ linear orderings of $D = \{1, \ldots, d - 1\}$.
Then $D$ contains an element $i_0$ such that for each $j_0\in \{1, \ldots, d\}$ there exists a bijective map $\pi\colon D \to \{1, \ldots d\} \setminus \{j_0\}$ with the property that for all $i \in D$ we have

i_0 \le_{\pi(i)} i.

We will prove the lemma by induction on $d$.
If $d = 1$, there is nothing to prove, so we may assume $D$ is not empty.
Since there are $d$ orderings and $d-1$ elements, it follows that there exists an element $k \in D$ that is maximal with respect to two distinct orderings $l_1$ and $l_2$.
Now we apply induction hypothesis to the set $D \setminus \{k\}$ and all of the orderings except $l_1$, and get some $i_0 \in D \setminus \{k\} \subset D$.
We claim that $i_0$ has the desired property for the initial problem as well.

Suppose we choose (in $\{1, \ldots, d\}$) some $j_0 \neq l_1$.
By the choice of $i_0$ there exists a map

$$\pi'\colon D \setminus \{k\} \to \{1, \ldots, d\} \setminus \{l_1, j_0\}$$
with the desired property.
Since $k$ is maximal with respect to $l_1$, we can define $\pi$ as

\pi(i) =
\begin{cases}
\pi'(i) & \text{if~~}  i \neq k, \\
l_1 & \text{if~~}  i = k.
%            \pi'(i) & \text{when} \; i \neq k, \\
%            l_1 & \text{when} \; i = k. \\
\end{cases}

In the remaining case with $j_0 = l_1$, by the choice of $i_0$ there exists a map

$$\pi'\colon D \setminus \{k\} \to \{1, \ldots, d\} \setminus \{l_1, l_2\}$$

with the desired property. Since $k$ is maximal with respect to $l_2$, it follows that we can define $\pi$ as

\pi(i) =
\begin{cases}
\pi'(i) & \text{if~~}  i \neq k, \\
l_2 & \text{if~~}  i = k. %\qedhere
%            \pi'(i) & \text{when} \; i \neq k, \\
%            l_2 & \text{when} \; i = k. \\
\end{cases}

Consider a table $A$ of size $(d-1) \times d$ with numbers
$\{a_{ij}\}_{i \in\{1,\ldots,d-1\}, j\in\{1,\ldots,d\}}$.

Then we can choose row $i_0$, such that after deletion of any column $j_0$ we would be able to fix $d-1$ cells in the table (exactly one in each of remaining columns and rows), such that for any fixed cell $(i, j)$ the inequality $a_{ij} \ge a_{i_0 j}$ holds.

Say that a cell $(i, j)$ is large if $a_{ij}$ is maximal in its column. Since there are at least $n$ large cells, there is a row $k$ containing at least two of them. Let $l_1$ and $l_2$ be columns of these large cells.

Consider the table $A'$ obtained from $A$ by removing row $k$ and column $l_1$. By induction hypothesis we can choose row $i_0$ in it. We claim that $i_0$ fits the initial table $A$ as well.

Suppose we delete column $j_0 \neq l_1$. Then we can fix some cells in $A'$ (by induction hypothesis for column $j_0$) and cell $(k, l_1)$, and the inequality holds since $a_{k l_1}$ was maximal in its column. Now suppose we delete column $l_1$. Then we can fix some cells in $A'$ (by induction hypothesis for column $l_1$) and cell $(k, l_2)$. Again, the inequality holds since $a_{k l_2}$ was maximal in its column.

We say that our collection of preference sets
$A_{ij}$ satisfies the inclusion property if for each triplet $(i_1, i_2, j)$ with $i_1, i_2\in \{1, \ldots, d - 1\}$ and $j\in \{1, \ldots, d\}$ we have either $A_{i_1 j} \subset A_{i_2 j}$ or $A_{i_2 j} \subset A_{i_1 j}$.

Suppose the collection of sets $A_{ij}$ satisfies the inclusion property.
Then each sequence of points $x_1, \ldots, x_{d-1}$ with $x_i \in I_i = A_{i1} \cap \ldots \cap A_{id}$ for each $i\in\{1, \ldots, d-1\}$ contains a fair division point.
Moreover, there exists an algorithm that, given such a sequence and the related data about inclusions, finds a fair division point in the sequence.

Inclusion orderings on $A_{ij}$ determine orderings on $\{1, \ldots, d-1\}$ by the rule

i_1 \le_{j} i_2 \; \Leftrightarrow \; A_{i_1j} \subset A_{i_2j}.
%    i_1 \le_{j} i_2 \; \text{if} \; A_{i_1j} \subset A_{i_2j}.

We apply Lemma <ref> to these orderings and obtain some index $i_0\in\{1, \ldots, d - 1\}$ having the property described in Lemma <ref>. We claim that $x_{i_0}$ is a fair division point.

Indeed, $x_{i_0}$ is in $A_{dj_0}$ for some $j_0$ since $\{A_{d1},\ldots, A_{dd}\}$ is a covering of $A$.

Then by the choice of $i_0$ there exists a map

$$\pi\colon \{1, \ldots, d - 1\} \to \{1, \ldots, d\} \setminus \{j_0\}$$
such that $i_0 \le_{\pi(i)} i$. Now we define the desired permutation $\sigma$ as

\sigma(i) =
\begin{cases}
\pi(i) & \text{if~~}  i\in\{1, \ldots, d - 1\}, \\     %1 \le i \le d - 1,
j_0 & \text{if~~} i = d. \\
\end{cases}

The condition $i_0 \le_{\pi(i)} i$ means that $A_{i_0 \pi(i)} \subset A_{i \pi(i)}$. Then for each $i\in\{1, \ldots, d - 1\}$ we have

x_{i_0} \in A_{i_0 \pi(i)} \subset A_{i \pi(i)} = A_{i \sigma(i)},

and $x_{i_0} \in A_{dj_0} = A_{d \sigma(d)}$ straight from the definition of $j_0$.

§ LOGARITHMIC ALGORITHMS FOR THE “LINEAR” PREFERENCE SETS

We use the barycentric coordinate system on our regular simplex $A$ in $\R^{d-1}$.
Namely, recall that $v_1,\ldots, v_d$ are the vertices of $A$ so that each $x\in A$ can be uniquely expressed in the form

with all $\al_i\ge0$ and $\al_1 + \ldots + \al_d = 1$.
We will use the notation $[\al_1, \ldots, \al_d]$ for $x$.

Let $\{A_{ij}\}, \; i=1,...,d, \, j=1,...,d$, as above, be a collection of preference sets.
In this section we consider two kinds of linear preference sets (LPS):

(i) each of $A_{ij}$ has the form $\{[\al_1,\ldots,\al_d] \in A: \al_j \ge a_{ij} \}$;

(ii) each of $A_{ij}$ has the form $\{[\al_1,\ldots,\al_d] \in A: \al_j \le a_{ij} \}$,

where $\{a_{ij}\}$ is a set of real numbers.

Case (i) is a particular case of the cake-cutting problem.
The condition that $\{A_{i1},\ldots,A_{id}\}$ is a covering of $A$ implies that $\sum_{j=1}^{d} a_{ij} \le 1$ for all $i$.
In addition, the standard cake-cutting preferences condition that “players prefer any piece with mass to an empty piece” means here that all $a_{ij}$ are in $(0,1)$.
In (ii) we have a particular case of the rental harmony problem with $\sum_{j=1}^{d} a_{ij} \ge 1$ for all $i$. Note that in both cases $A_{ij}$ is the intersection of $A$ and a half-space that is bounded by the hyperplane $\al_j=a_{ij}$.

The following theorem is our “logarithmic complexity” result for the cake-cutting problem.

Suppose that each of the sets $A_{ij}$, being a proper subset of the simplex $A$, is the intersection of $A$ and a closed half-space with boundary parallel to $F_j$ such that $v_j \in A_{ij}$. Then we can find an $\eps$-fair division point in binary mode using at most
$$(d-1)^2\ceil{\log_2 (n \cdot (d-1))}$$
queries, where $n = \ceil{1/\eps}$.

By assumptions we have LPS case (i).
Fix an index $i\in\{1,\ldots,d-1\}$ and denote $\delta = \frac{\eps}{d-1}$.
Since $A_{ij}$ is a proper subset of $A$, it follows that $0<a_{ij}<1$.
For every $j\in\{1,\ldots,d-1\}$
we can use binary search to find approximations $c_{ij}$ such that

$$\max(a_{ij} - \delta, 0) \le c_{ij} < a_{ij}$$

with $\ceil{\log_2 \frac{1}{\delta}}$ queries.
We claim that $I^{\eps}_i$ contains the point
$$x_i = [c_{i1}, c_{i2}, \ldots, c_{i(d-1)}, 1 - c_{i1} - \ldots - c_{i(d-1)}].$$

Indeed, $x_i$ lies in $A$ since

0 \le \sum_{j=1}^{d-1} c_{ij} < \sum_{j=1}^{d-1} a_{ij} \le 1.
%\sum_{j\in\{1,\ldots,d-1\}} c_{ij} ~~~<~~~ \sum_{j\in\{1,\ldots,d-1\}} a_{ij} ~~~\le~~~ 1.
%\sum_{1 \le j \le d - 1} c_{ij} < \sum_{1 \le j \le d - 1} a_{ij} \le 1.

Then for each $j\in\{1,\ldots,d-1\}$ we have $x_i \notin A_{ij}$

straight from the definition, which means that $x_i \in A_{id}$. Furthermore, we have

y_i = [a_{i1}, a_{i2}, \ldots, a_{i(d-1)}, 1 - a_{i1} - \ldots - a_{i(d-1)}] \in A_{i1} \cap \ldots \cap A_{i(d-1)},

\abs{x_i - y_i} = \abs{\sum_{j = 1}^{d-1} (c_{ij} - a_{ij})(v_j - v_d) } \le \sum_{j = 1}^{d-1} \abs{c_{ij} - a_{ij}} \le (d-1)\delta = \eps.

We spent $(d-1)\ceil{\log_2(n \cdot (d-1))}$ queries on the fixed index $i$. Repeating this for all
$i\in\{1,\ldots,d-1\}$ we obtain $d-1$ points $x_1$, …, $x_{d-1}$ lying in the corresponding intersections.

For $i \in \{1,\ldots,d-1\}$ and $j \in \{1,\ldots,d\}$ we set

A'_{ij} = \{ [\al_1, \ldots, \al_d]\in A : \al_j \ge c_{ij} \}.

These sets satisfy the inclusion property and are known to us, so by Theorem <ref> we can find a fair division point $z$ for them. But $x_i \in I^{\eps}_i$ implies that $A'_{ij} \subset A^{\eps}_{ij}$, so $z$ is also an $\eps$-fair division point for the initial problem.

The following figure illustrates the first two steps of binary search for finding (an approximation for) \(a_{12}\). The blue dashed line shows the boundary of the actual set \(A_{12}\). The point with the question mark is the point about which we ask whether it lies in \(A_{12}\), and then cut off a piece of \(A\) according to the answer.

point/.style = draw, circle,  fill = black, inner sep = 1pt,
dot/.style   = draw, circle,  fill = black, inner sep = .75pt,
use Hobby shortcut

(ptA) at (0, 0);
(ptB) at (3, 0);
(ptC) at (3*, 3*);

[blue, dashed, thick] (1.7*, 1.7*) – (3 - 1.7*, 1.7*);

(A) at (0,0)                                            [dot];
(B) at (+1.000 + 1.000 + 1.000, +0.000 + 0.000 + 0.000) [dot];
(C) at (++ + , ++ + ) [dot];
(Q) at (1.5, 1.5 * ) [dot];
(mark) at (1.7, 1.5*- 0.05) []?;
/→in A/B, B/C, C/A

[line width=0.4mm] () – (→);

(F1) at (2, 1.6) [label = right:$F_{1}$];
(F2) at (1.5, 0) [label = below:$F_{2}$];
(F3) at (1, 1.6) [label = left:$F_{3}$];
\(\to\)
point/.style = draw, circle,  fill = black, inner sep = 1pt,
dot/.style   = draw, circle,  fill = black, inner sep = .75pt,
use Hobby shortcut

(ptA) at (0, 0);
(ptB) at (3, 0);
(ptC) at (3*, 3*);

[blue, dashed, thick] (1.7*, 1.7*) – (3 - 1.7*, 1.7*);

[line width=0.4mm]  (1.5*, 1.5*) – (3 - 1.5*, 1.5*);
[EDR] (0,0) – (3, 0) – (3 - 1.5*, 1.5*) – (1.5*, 1.5*) – cycle;

(A) at (ptA) [dot];
(B) at (ptB) [dot];
(C) at (ptC) [dot];
(Q) at (1.5, 2.25*) [dot];
(mark) at (1.7, 2.25*- 0.05) []?;
/→in A/B, B/C, C/A

[line width=0.4mm] () – (→);

(F1) at (2, 1.6) [label = right:$F_{1}$];
(F2) at (1.5, 0) [label = below:$F_{2}$];
(F3) at (1, 1.6) [label = left:$F_{3}$];
\(\to\)
point/.style = draw, circle,  fill = black, inner sep = 1pt,
dot/.style   = draw, circle,  fill = black, inner sep = .75pt,
use Hobby shortcut

(ptA) at (0, 0);
(ptB) at (3, 0);
(ptC) at (3*, 3*);

[blue, dashed, thick] (1.7*, 1.7*) – (3 - 1.7*, 1.7*);

[line width=0.4mm]  (1.5*, 1.5*) – (3 - 1.5*, 1.5*);
[EDR] (0,0) – (3, 0) – (3 - 1.5*, 1.5*) – (1.5*, 1.5*) – cycle;

[line width=0.4mm]  (2.25*, 2.25*) – (3 - 2.25*, 2.25*);
[EDR] (3*, 3*) – (3 - 2.25*, 2.25*) – (2.25*, 2.25*) – cycle;

(A) at (ptA) [dot];
(B) at (ptB) [dot];
(C) at (ptC) [dot];

(Q) at (1.5, 1.875*) [dot];
(mark) at (1.65, 1.875*+ 0.1) []?;
/→in A/B, B/C, C/A

[line width=0.4mm] () – (→);

(F1) at (2, 1.6) [label = right:$F_{1}$];
(F2) at (1.5, 0) [label = below:$F_{2}$];
(F3) at (1, 1.6) [label = left:$F_{3}$];

Suppose that each of the sets $A_{ij}$ is the intersection of the simplex $A$ and a closed half-space with boundary parallel to $F_j$ such that $F_j\subset A_{ij}$. Then we can find an $\eps$-fair division point in minimal mode using at most $(d-1)\ceil{\log_{\frac{d}{d-1}} n}$ queries, where $n = \ceil{1/\eps}$.

We have LPS case (ii).
We fix an index $i_0\in\{1,\ldots,d-1\}$ and ask which of $A_{i_01}$, …, $A_{i_0d}$ contains the center $c_0$ of $A$.

Some $A_{i_0j_0}$ contains $c_0$, so we draw the hyperplane $H_{j_0}$ parallel to $F_{j_0}$ through $c_0$, and $H_{j_0}\cap A$ also lies in $A_{i_0j_0}$.

Clearly, this reduces the problem to the smaller regular simplex that $H_{j_0}$ cuts off from $A$.
This new simplex is similar to the initial one with coefficient $\frac{d-1}{d}$.
So, after $\ceil{\log_{\frac{d}{d-1}} n}$ queries the resulting regular simplex $A^\dagger$ has edges of length at most $\eps$.

Then $I^{\eps}_{i_0}$ contains $A^\dagger$, and we take any point of $A^\dagger$ as $x_{i_0}$.

Repeating the described procedure for all indices $i\in\{1,\ldots,d-1\}$ and each time using exactly the specified number of queries,
we obtain $d-1$ points lying in the corresponding intersections $I^{\eps}_i$.

Analogously to the proof of <ref>, for $i \in \{1,\ldots,d-1\}$ and $j \in \{1,\ldots,d\}$ we set

A'_{ij} = \{ [\al_1, \ldots, \al_d]\in A : \al_j \le x_{ij} \}, \quad\text{where $x_{ij}$ is defined by $x_i=[x_{i1}, \dots, x_{id}]$}.

These sets satisfy the inclusion property and are known to us, so by Theorem <ref> we can find a fair division point $z$ for them. But $x_i \in I^{\eps}_i$ implies that $A'_{ij} \subset A^{\eps}_{ij}$, so $z$ is also an $\eps$-fair division point for the initial problem.

The following figure illustrates the first two steps of binary search for finding \(x_1 \in I^{\eps}_1\). The blue dashed lines show the boundaries of actual sets $A_{11}$, $A_{12}$, and $A_{13}$.
The point with the question mark is the point about which we ask which of $A_{11}$, $A_{12}$, and $A_{13}$ contains it.

At the first step we find out that the point lies in \(A_{13}\), and then cut off a piece of \(A\) according to the answer. Similarly, at the second step we get \(A_{12}\).

point/.style = draw, circle,  fill = black, inner sep = 1pt,
dot/.style   = draw, circle,  fill = black, inner sep = .75pt,
use Hobby shortcut

(ptA) at (0, 0);
(ptB) at (3, 0);
(ptC) at (3*, 3*);

[blue, dashed, thick] (1.7*, 1.7*) – (3 - 1.7*, 1.7*);
[blue, dashed, thick] (1.4, 0) – (1.4*, 1.4*);
[blue, dashed, thick] (3 - 1.1, 0) – (3 - 1.1*, 1.1*);

(A) at (0,0)                                            [dot];
(B) at (+1.000 + 1.000 + 1.000, +0.000 + 0.000 + 0.000) [dot];
(C) at (++ + , ++ + ) [dot];
(Q) at (1.5, ) [dot];
(mark) at (1.7, - 0.05) []?;
/→in A/B, B/C, C/A

[line width=0.4mm] () – (→);

(F1) at (2, 1.6) [label = right:$F_{1}$];
(F2) at (1.5, 0) [label = below:$F_{2}$];
(F3) at (1, 1.6) [label = left:$F_{3}$];
\(\to\)
point/.style = draw, circle,  fill = black, inner sep = 1pt,
dot/.style   = draw, circle,  fill = black, inner sep = .75pt,
use Hobby shortcut

(ptA) at (0, 0);
(ptB) at (3, 0);
(ptC) at (3*, 3*);

[blue, dashed, thick] (1.7*, 1.7*) – (3 - 1.7*, 1.7*);
[blue, dashed, thick] (1.4, 0) – (1.4*, 1.4*);
[blue, dashed, thick] (3 - 1.1, 0) – (3 - 1.1*, 1.1*);
[line width=0.4mm]  (1, 0) – (2, 2*);
[EDR] (0,0) – (1, 0) – (2, 2*) – (3*, 3*) – cycle;

(A) at (ptA) [dot];
(B) at (ptB) [dot];
(C) at (ptC) [dot];
(Q) at (2, 2*/ 3) [dot];
(mark) at (2.1, 2*/ 3 + 0.2) []?;
/→in A/B, B/C, C/A

[line width=0.4mm] () – (→);

(F1) at (2, 1.6) [label = right:$F_{1}$];
(F2) at (1.5, 0) [label = below:$F_{2}$];
(F3) at (1, 1.6) [label = left:$F_{3}$];
\(\to\)
point/.style = draw, circle,  fill = black, inner sep = 1pt,
dot/.style   = draw, circle,  fill = black, inner sep = .75pt,
use Hobby shortcut

(ptA) at (0, 0);
(ptB) at (3, 0);
(ptC) at (3*, 3*);

[blue, dashed, thick] (1.7*, 1.7*) – (3 - 1.7*, 1.7*);
[blue, dashed, thick] (1.4, 0) – (1.4*, 1.4*);
[blue, dashed, thick] (3 - 1.1, 0) – (3 - 1.1*, 1.1*);

[line width=0.4mm]  (3 - 2*/3, 2*/3) – (1 + 2*/3, 2*/ 3) – (2, 2*);
[EDR]  (3 - 2*/3, 2*/3) – (1 + 2*/3, 2*/ 3) – (2, 2*) – (3*, 3*) – (0, 0) – (3, 0) – cycle;
(A) at (ptA) [dot];
(B) at (ptB) [dot];
(C) at (ptC) [dot];

(Q) at (2, 2*/ 3 + 4*/ 9) [dot];
(mark) at (2.1, 2*/ 3 + 4*/ 9 + 0.2) []?;
/→in A/B, B/C, C/A

[line width=0.4mm] () – (→);

(F1) at (2, 1.6) [label = right:$F_{1}$];
(F2) at (1.5, 0) [label = below:$F_{2}$];
(F3) at (1, 1.6) [label = left:$F_{3}$];

§ CASE OF CONVEX PREFERENCE SETS

In this section we deal with the case where the preference sets $A_{ij}$ in the rental harmony problem are convex.
If $d = 2$ then convex sets containing a fixed vertex of the simplex are intersections of the simplex with half-spaces containing this vertex, which provides a trivial solution with $\ceil{\log_2 n}$ queries (this may be viewed as a trivial case of Theorem $\ref{rent}$).
Here, we focus on the situation with $d = 3$.

First, we prove an analogue of Theorem <ref> for the case where our sets are convex (while do not necessarily have the inclusion property) and we know all $d$ points in intersections (instead of $d-1$).

Suppose all preference sets $A_{ij}$ are convex and $F_j \subset A_{ij}$ for all $i$ and $j$.
Then there exists an algorithm that, given $\eps>0$ and a collection $x_1, \ldots, x_d$ with $x_i \in I^{\eps}_i$ for each $i$, finds an $\eps$-fair division point $x = x(x_1, \ldots, x_d)$.

First of all, observe that $A^{\eps}_{ij}$ are clearly also convex.
Put $A'_{ij} = \conv{F_j, x_i}$. Observe that each $A'_{ij}$ depends only on $x_i$ and $j$, but not on $A_{ij}$.
It can be easily seen that any fixed-point free reindexing for vertex indices in $\{v_1,\dots,v_d\}$
turns $\{A'_{i1}, \ldots, A'_{id}\}$ into a KKM-covering for each $i$ (see Sec. <ref>).

Then the rainbow KKM lemma implies that there exists a point $z$ and a permutation $\sigma$ of $(1,\ldots,d)$ such that $z \in A'_{i\sigma(i)}$ for all $i$.
Moreover, it is clear that there exists an algorithm finding $z$: for example, by checking all permutations of $(1,\ldots,d)$ we can find a permutation $\sigma$ such that

\bigcap_{1 \le i \le d} A'_{i\sigma(i)} \neq \emptyset

and take any point in this intersection.
But $F_j \subset A^{\eps}_{ij}$ and $x_i \in I^{\eps}_i \subset A^{\eps}_{ij}$ imply that $A'_{ij} \subset A^{\eps}_{ij}$.
Thus $z$ is also an $\eps$-fair division point for the initial problem.

point/.style = draw, circle,  fill = black, inner sep = 1pt,
dot/.style   = draw, circle,  fill = black, inner sep = .75pt,
use Hobby shortcut

(ptA) at (0, 0);
(ptB) at (3, 0);
(ptC) at (3*, 3*);

[blue, thick, dashed] ([out angle=50]ptA)  .. (1.3, 1)   .. ([in angle=130]ptB);
[blue, thick, dashed] ([out angle=170]ptB) .. (1.7, 0.4) .. ([in angle=250]ptC);
[blue, thick, dashed] ([out angle=290]ptC) .. (2, 0.9)   .. ([in angle=10]ptA);

(A) at (0,0)                                            [dot];
(B) at (+1.000 + 1.000 + 1.000, +0.000 + 0.000 + 0.000) [dot];
(C) at (++ + , ++ + ) [dot];
(x_1) at (1.5, 0.9) [dot, label=$x_1$];
/→in A/B, B/C, C/A

[line width=0.4mm] () – (→);

(F1) at (2, 1.6) [label = right:$F_{1}$];
(F2) at (1.5, 0) [label = below:$F_{2}$];
(F3) at (1, 1.6) [label = left:$F_{3}$];

point/.style = draw, circle,  fill = black, inner sep = 1pt,
dot/.style   = draw, circle,  fill = black, inner sep = .75pt,
use Hobby shortcut

(ptA) at (0, 0);
(ptB) at (3, 0);
(ptC) at (3*, 3*);

[red, thick, dashed] ([out angle=45]ptA)  .. (0.4, 0.4) .. ([in angle=140]ptB);
[red, thick, dashed] ([out angle=168]ptB) .. (1.2, 0.6) .. ([in angle=246]ptC);
[red, thick, dashed] ([out angle=285]ptC) .. (2.15, 1)  .. ([in angle=3]ptA);
(A) at (ptA) [dot];
(B) at (ptB) [dot];
(C) at (ptC) [dot];
(x_2) at (1.7, 0.5) [dot, label=$x_2$];
/→in A/B, B/C, C/A

[line width=0.4mm] () – (→);

(F1) at (2, 1.6) [label = right:$F_{1}$];
(F2) at (1.5, 0) [label = below:$F_{2}$];
(F3) at (1, 1.6) [label = left:$F_{3}$];

point/.style = draw, circle,  fill = black, inner sep = 1pt,
dot/.style   = draw, circle,  fill = black, inner sep = .75pt,
use Hobby shortcut

(ptA) at (0, 0);
(ptB) at (3, 0);
(ptC) at (3*, 3*);

[green, thick, dashed] ([out angle=50] ptA) .. (0.9, 0.9) .. ([in angle=120]ptB);
[green, thick, dashed] ([out angle=170]ptB) .. (1.2, 0.6) .. ([in angle=250]ptC);
[green, thick, dashed] ([out angle=290]ptC) .. (1.2, 0.8) .. ([in angle=10]ptA);

(A) at (ptA) [dot];
(B) at (ptB) [dot];
(C) at (ptC) [dot];

(x_3) at (1.15, 0.9) [dot, label=$x_3$];

/→in A/B, B/C, C/A

[line width=0.4mm] () – (→);

(F1) at (2, 1.6) [label = right:$F_{1}$];
(F2) at (1.5, 0) [label = below:$F_{2}$];
(F3) at (1, 1.6) [label = left:$F_{3}$];

point/.style = draw, circle,  fill = black, inner sep = 1pt,
dot/.style   = draw, circle,  fill = black, inner sep = .75pt,
use Hobby shortcut

(ptA) at (0, 0);
(ptB) at (3, 0);
(ptC) at (3*, 3*);
(x1c) at (1.5, 0.9);

[blue, thick, dashed] ([out angle=50]ptA)  .. (1.3, 1)   .. ([in angle=130]ptB);
[blue, thick, dashed] ([out angle=170]ptB) .. (1.7, 0.4) .. ([in angle=250]ptC);
[blue, thick, dashed] ([out angle=290]ptC) .. (2, 0.9)   .. ([in angle=10]ptA);
[blue, thick] (ptA) – (x1c);
[blue, thick] (ptB) – (x1c);
[blue, thick] (ptC) – (x1c);

(A) at (0,0)                                            [dot];
(B) at (+1.000 + 1.000 + 1.000, +0.000 + 0.000 + 0.000) [dot];
(C) at (++ + , ++ + ) [dot];
(x_1) at (x1c) [dot, label=[label distance=-0.1cm]70:$x_1$];

/→in A/B, B/C, C/A

[line width=0.4mm] () – (→);

(F1) at (2, 1.6) [label = right:$F_{1}$];
(F2) at (1.5, 0) [label = below:$F_{2}$];
(F3) at (1, 1.6) [label = left:$F_{3}$];

point/.style = draw, circle,  fill = black, inner sep = 1pt,
dot/.style   = draw, circle,  fill = black, inner sep = .75pt,
use Hobby shortcut

(ptA) at (0, 0);
(ptB) at (3, 0);
(ptC) at (3*, 3*);
(x2c) at (1.7, 0.6);

[red, thick, dashed] ([out angle=45]ptA)  .. (0.4, 0.4) .. ([in angle=140]ptB);
[red, thick, dashed] ([out angle=168]ptB) .. (1.2, 0.6) .. ([in angle=246]ptC);
[red, thick, dashed] ([out angle=285]ptC) .. (2.15, 1)  .. ([in angle=3]ptA);
[red, thick] (ptA) – (x2c);
[red, thick] (ptB) – (x2c);
[red, thick] (ptC) – (x2c);
(A) at (ptA) [dot];
(B) at (ptB) [dot];
(C) at (ptC) [dot];
(x_2) at (x2c) [dot, label=[label distance=-0.15cm]380:$x_2$];

/→in A/B, B/C, C/A

[line width=0.4mm] () – (→);

(F1) at (2, 1.6) [label = right:$F_{1}$];
(F2) at (1.5, 0) [label = below:$F_{2}$];
(F3) at (1, 1.6) [label = left:$F_{3}$];

point/.style = draw, circle,  fill = black, inner sep = 1pt,
dot/.style   = draw, circle,  fill = black, inner sep = .75pt,
use Hobby shortcut

(ptA) at (0, 0);
(ptB) at (3, 0);
(ptC) at (3*, 3*);
(x3c) at (1.15, 0.9);

[green, thick, dashed] ([out angle=50] ptA) .. (0.9, 0.9) .. ([in angle=120]ptB);
[green, thick, dashed] ([out angle=170]ptB) .. (1.2, 0.6) .. ([in angle=250]ptC);
[green, thick, dashed] ([out angle=290]ptC) .. (1.2, 0.8) .. ([in angle=10]ptA);
[green, thick] (ptA) – (x3c);
[green, thick] (ptB) – (x3c);
[green, thick] (ptC) – (x3c);

(A) at (ptA) [dot];
(B) at (ptB) [dot];
(C) at (ptC) [dot];

(x_3)  at (x3c) [dot, label=[label distance=-0.1cm]3:$x_3$];

/→in A/B, B/C, C/A

[line width=0.4mm] () – (→);

(F1) at (2, 1.6) [label = right:$F_{1}$];
(F2) at (1.5, 0) [label = below:$F_{2}$];
(F3) at (1, 1.6) [label = left:$F_{3}$];

point/.style = draw, circle,  fill = black, inner sep = 1pt,
dot/.style   = draw, circle,  fill = black, inner sep = .75pt,
use Hobby shortcut

(ptA) at (0, 0);
(ptB) at (3, 0);
(ptC) at (3*, 3*);
(x1c) at (1.5, 0.9);
(x2c) at (1.7, 0.6);
(x3c) at (1.15, 0.9);

[blue, thick]  (ptA) – (x1c);
[blue, thick]  (ptB) – (x1c);
[blue, thick]  (ptC) – (x1c);
[red, thick]   (ptA) – (x2c);
[red, thick]   (ptB) – (x2c);
[red, thick]   (ptC) – (x2c);
[green, thick] (ptA) – (x3c);
[green, thick] (ptB) – (x3c);
[green, thick] (ptC) – (x3c);

(A) at (ptA) [dot];
(B) at (ptB) [dot];
(C) at (ptC) [dot];
/→in A/B, B/C, C/A

[line width=0.4mm] () – (→);

(F1) at (2, 1.6) [label = right:$F_{1}$];
(F2) at (1.5, 0) [label = below:$F_{2}$];
(F3) at (1, 1.6) [label = left:$F_{3}$];
(X) at (1.5, 0.8) [draw, circle,  fill = yellow, inner sep = 1pt];

An example of new covering for Lemma <ref>

Suppose that $d = 3$ and each of the sets $A_{ij}$ is a convex set containing $F_j$.
Then we can find an $\eps$-fair division point in binary mode with at most $6(\ceil{\log_2 n}^2 + \ceil{\log_2 n}) = O(\log^2 n)$ queries, where $n = \ceil{1/\eps}$.

By Lemma <ref> it is sufficient to find a point in each of $I^{\eps}_i$, so we want to do this for an arbitrary fixed $i$ with at most $2(\ceil{\log_2 n}^2 + \ceil{\log_2 n})$ queries.

Based on the barycentric coordinates notation introduced in Sec. <ref>, for the triples of numbers $(a,b,c)$ with nonzero sum $a+b+c$ we use the notation

[a, b, c]_*= [a/(a+b+c), b/(a+b+c), c/(a+b+c)]

and introduce the grid

\{ [a, b, c]_* : a, b, c \in \mathbb{N}_0, a + b + c = n \}.

Our queries will only be about grid points. We define

\begin{gather*}
k_2(a) = \max\{ b \in \mathbb{N}_0 : 0 \le b \le n - a, [a, b, n - a - b]_* \in A_{i2} \},\\
k_3(a) = \min\{ b \in \mathbb{N}_0 : 0 \le b \le n - a, [a, b, n - a - b]_* \in A_{i3}\}.
\end{gather*}

scale= 1,
point/.style = draw, circle,  fill = black, inner sep = 1pt,
covered/.style = draw, circle,  fill = green, inner sep = 1.5pt,
uncovered/.style = draw, circle,  fill = orange, inner sep = 1.5pt,
dot/.style   = draw, circle,  fill = black, inner sep = .5pt,
use Hobby shortcut

(z)  at (0,0);

(z0) at (+1.000, +0.000);
(z1) at (+, +);

(z00) at (+1.000 + 1.000, +0.000 + 0.000);
(z10) at (++ 1.000, ++ 0.000);
(z11) at (++ , ++ );

(z000) at (+1.000 + 1.000 + 1.000, +0.000 + 0.000 + 0.000);
(z100) at (++ 1.000 + 1.000, ++ 0.000 + 0.000);
(z110) at (++ + 1.000, ++ + 0.000);
(z111) at (++ + , ++ + );

(z0000) at (+1.000 + 1.000 + 1.000 + 1.000, +0.000 + 0.000 + 0.000 + 0.000);
(z1000) at (++ 1.000 + 1.000 + 1.000, +0.000 + + 0.000 + 0.000);
(z1100) at (++ + 1.000 + 1.000, +0.000 + + + 0.000);
(z1110) at (++ + + 1.000, ++ + + 0.000);
(z1111) at (++ + + , ++ + + );

(z00000) at (+1.000 + 1.000 + 1.000 + 1.000 + 1.000, +0.000 + 0.000 + 0.000 + 0.000 + 0.000);
(z10000) at (++ 1.000 + 1.000 + 1.000 + 1.000, +0.000 + + 0.000 + 0.000 + 0.000);
(z11000) at (++ + 1.000 + 1.000 + 1.000, +0.000 + + + 0.000 + 0.000);
(z11100) at (++ + + 1.000 + 1.000, ++ + + 0.000 + 0.000);
(z11110) at (++ + + + 1.000, ++ + + + 0.000);
(z11111) at (++ + + + , ++ + + + );

(z000000) at (+1.000 + 1.000 + 1.000 + 1.000 + 1.000 + 1.000, +0.000 + 0.000 + 0.000 + 0.000 + 0.000 + 0.000);
(z100000) at (++ 1.000 + 1.000 + 1.000 + 1.000 + 1.000, +0.000 + + 0.000 + 0.000 + 0.000 + 0.000);
(z110000) at (++ + 1.000 + 1.000 + 1.000 + 1.000, +0.000 + + + 0.000 + 0.000 + 0.000);
(z111000) at (++ + + 1.000 + 1.000 + 1.000, ++ + + 0.000 + 0.000 + 0.000);
(z111100) at (++ + + + 1.000 + 1.000, ++ + + + 0.000 + 0.000);
(z111110) at (++ + + + + 1.000, ++ + + + + 0.000);
(z111111) at (++ + + + + , ++ + + + + );

z1/z10, z10/z100, z100/z1000, z1000/z10000, z10000/z100000,
z11/z110, z110/z1100, z1100/z11000, z11000/z110000,
z111/z1110, z1110/z11100, z11100/z111000,
z1111/z11110, z11110/z111100,
z0/z10, z10/z110, z110/z1110, z1110/z11110, z11110/z111110,
z00/z100, z100/z1100, z1100/z11100, z11100/z111100,
z000/z1000, z1000/z11000, z11000/z111000,
z0000/z10000, z10000/z110000,
z00000/z10000, z10000/z11000, z11000/z11100, z11100/z11110, z11110/z11111,
z0000/z1000, z1000/z1100, z1100/z1110, z1110/z1111,
z000/z100, z100/z110, z110/z111,
z00/z10, z10/z11,

[line width=0.1mm] () – (→);

[color=red, line width=0.25mm] (0, 0) to [out=25,in=130] (z000000);
[color=red, line width=0.25mm] (0, 0) to [out=30,in=300] (z111111);

z/z0, z0/z00, z00/z000, z000/z0000, z0000/z00000, z00000/z000000,
z/z1, z1/z11, z11/z111, z111/z1111, z1111/z11111, z11111/z111111,
z000000/z100000, z100000/z110000, z110000/z111000, z111000/z111100, z111100/z111110, z111110/z111111

[line width=0.4mm] () – (→);

(zz) at (z)  [covered];
(x1) at (z0) [covered];
(y1) at (z1) [covered];
(x2) at (z00) [uncovered];
(y2) at (z11) [uncovered];
(x3) at (z000) [covered];
(y3) at (z111) [covered];
(x4) at (z0000) [uncovered];
(y4) at (z1111) [uncovered];
(x5) at (z00000) [uncovered];
(y5) at (z11111) [uncovered];
(x6) at (z000000) [uncovered];
(y6) at (z111111) [uncovered];

(F1) at (4, 3.2) [label = right:$F_{1}$];
(F2) at (3, 0) [label = below:$F_{2}$];
(F3) at (2, 3.2) [label = left:$F_{3}$];

Green points correspond to covered values and orange points correspond to uncovered ones

Observe that $[a, 0, n - a]_* \in A_{i2}$ and $[a, n - a, 0]_* \in A_{i3}$.
Then convexity of $A_{i2}$ and $A_{i3}$ implies that the values of $k_2(a)$ and $k_3(a)$ for any fixed $a$ can be found with binary search using $2\ceil{\log_2 n}$ queries.

We say that a coordinate $a$ is covered if $k_2(a) + 1 \ge k_3(a)$ and uncovered otherwise. In other words, $a$ is covered if the union $A_{i2} \cup A_{i3}$ contains all points of the grid with the first coordinate $a$. Clearly, $a = n$ is covered.
Then we spend $2 \ceil{\log_2 n}$ queries to calculate $k_2(0)$ and $k_3(0)$ and check whether $a = 0$ is covered.
If it is then $[0, k_2(a), n - k_2(a)]_*$ is the desired point.
Otherwise we can run a binary search through $a$ to obtain a coordinate $a_0$ such that it is uncovered while $a_0 + 1$ is covered (note that this is possible despite the set of covered values has “gaps” in general): each iteration of binary search requires at most $2 \ceil{\log_2 n}$ queries, so the total search takes at most $2 \ceil{\log_2 n}^2$ ones.

After finding $a_0$, we turn to the following sequence $Z$ of $k=k_3(a_0)-k_2(a_0)+2$ points (see Fig. <ref>):

\begin{equation*}
\begin{array}{rlll}
z_1:= & [a_0,     & k_2(a_0),   & n-a_0-k_2(a_0)]_*, \\
z_2:= & {[a_0+1,} & k_2(a_0),   & n-a_0-k_2(a_0)-1]_*, \\
z_3:= & {[a_0+1,} & k_2(a_0)+1, & n-a_0-k_2(a_0)-2]_*, \\
& ... & \\
z_{k-2}:= & {[a_0+1,} & k_3(a_0)-2, & n-a_0-k_3(a_0)+1]_*, \\
z_{k-1}:= & {[a_0+1,} & k_3(a_0)-1, & n-a_0-k_3(a_0)]_*, \\
z_{k}:= & {[a_0,} & k_3(a_0), & n-a_0-k_3(a_0)]_*.
\end{array}
\end{equation*}

scale= 1,
point/.style = draw, circle,  fill = black, inner sep = 1pt,
covered/.style = draw, circle,  fill = green, inner sep = 1.5pt,
uncovered/.style = draw, circle,  fill = orange, inner sep = 1.5pt,
zpoint/.style = draw, circle, blue, fill = blue, inner sep = 1pt,
zpoint_big/.style = draw, circle, blue, fill = blue, inner sep = 2pt,
dot/.style   = draw, circle,  fill = black, inner sep = .5pt,
use Hobby shortcut

(z)  at (0,0);

(z0) at (+1.000, +0.000);
(z1) at (+, +);

(z00) at (+1.000 + 1.000, +0.000 + 0.000);
(z10) at (++ 1.000, ++ 0.000);
(z11) at (++ , ++ );

(z000) at (+1.000 + 1.000 + 1.000, +0.000 + 0.000 + 0.000);
(z100) at (++ 1.000 + 1.000, ++ 0.000 + 0.000);
(z110) at (++ + 1.000, ++ + 0.000);
(z111) at (++ + , ++ + );

(z0000) at (+1.000 + 1.000 + 1.000 + 1.000, +0.000 + 0.000 + 0.000 + 0.000);
(z1000) at (++ 1.000 + 1.000 + 1.000, +0.000 + + 0.000 + 0.000);
(z1100) at (++ + 1.000 + 1.000, +0.000 + + + 0.000);
(z1110) at (++ + + 1.000, ++ + + 0.000);
(z1111) at (++ + + , ++ + + );

(z00000) at (+1.000 + 1.000 + 1.000 + 1.000 + 1.000, +0.000 + 0.000 + 0.000 + 0.000 + 0.000);
(z10000) at (++ 1.000 + 1.000 + 1.000 + 1.000, +0.000 + + 0.000 + 0.000 + 0.000);
(z11000) at (++ + 1.000 + 1.000 + 1.000, +0.000 + + + 0.000 + 0.000);
(z11100) at (++ + + 1.000 + 1.000, ++ + + 0.000 + 0.000);
(z11110) at (++ + + + 1.000, ++ + + + 0.000);
(z11111) at (++ + + + , ++ + + + );

(z000000) at (+1.000 + 1.000 + 1.000 + 1.000 + 1.000 + 1.000, +0.000 + 0.000 + 0.000 + 0.000 + 0.000 + 0.000);
(z100000) at (++ 1.000 + 1.000 + 1.000 + 1.000 + 1.000, +0.000 + + 0.000 + 0.000 + 0.000 + 0.000);
(z110000) at (++ + 1.000 + 1.000 + 1.000 + 1.000, +0.000 + + + 0.000 + 0.000 + 0.000);
(z111000) at (++ + + 1.000 + 1.000 + 1.000, ++ + + 0.000 + 0.000 + 0.000);
(z111100) at (++ + + + 1.000 + 1.000, ++ + + + 0.000 + 0.000);
(z111110) at (++ + + + + 1.000, ++ + + + + 0.000);
(z111111) at (++ + + + + , ++ + + + + );

z1/z10, z10/z100, z100/z1000, z1000/z10000, z10000/z100000,
z11/z110, z110/z1100, z1100/z11000, z11000/z110000,
z111/z1110, z1110/z11100, z11100/z111000,
z1111/z11110, z11110/z111100,
z0/z10, z10/z110, z110/z1110, z1110/z11110, z11110/z111110,
z00/z100, z100/z1100, z1100/z11100, z11100/z111100,
z000/z1000, z1000/z11000, z11000/z111000,
z0000/z10000, z10000/z110000,
z00000/z10000, z10000/z11000, z11000/z11100, z11100/z11110, z11110/z11111,
z0000/z1000, z1000/z1100, z1100/z1110, z1110/z1111,
z000/z100, z100/z110, z110/z111,
z00/z10, z10/z11,

[line width=0.1mm] () – (→);

z/z0, z0/z00, z00/z000, z000/z0000, z0000/z00000, z00000/z000000,
z/z1, z1/z11, z11/z111, z111/z1111, z1111/z11111, z11111/z111111,
z000000/z100000, z100000/z110000, z110000/z111000, z111000/z111100, z111100/z111110, z111110/z111111

[line width=0.4mm] () – (→);

[red, thick] ([out angle=50] z) .. (1.3, 1.3) .. ([in angle=120] z000000);
[red, thick] ([out angle=290] z111111) .. (3, 1.2) .. ([in angle=10]z);

(zp1) at (z10000) [zpoint];
(zp2) at (z1000)  [zpoint];
(zp3) at (z1100)  [zpoint];
(zp4) at (z11100) [zpoint];
[thick, blue, ->] (zp1) – (zp2);
[thick, blue, ->] (zp2) – (zp3);
[thick, blue, ->] (zp3) – (zp4);
(zz) at (z)  [covered];
(x1) at (z0) [covered];
(y1) at (z1) [covered];
(x2) at (z00) [covered];
(y2) at (z11) [covered];
(x3) at (z000) [covered];
(y3) at (z111) [covered];
(x4) at (z0000) [covered];
(y4) at (z1111) [covered];
(x5) at (z00000) [uncovered];
(y5) at (z11111) [uncovered];
(x6) at (z000000) [uncovered];
(y6) at (z111111) [uncovered];

(F1) at (4, 3.2) [label = right:$F_{1}$];
(F2) at (3, 0) [label = below:$F_{2}$];
(F3) at (2, 3.2) [label = left:$F_{3}$];

The sequence $Z$ is highlighted in blue

Observe that by construction we have $z_1\in A_{i2}$ and $z_k\in A_{i3}$ while the union $A_{i2}\cup A_{i3}$ contains $Z$. This implies that for some $m$ we have $z_m\in A_{i2}$ and $z_{m+1}\in A_{i3}$. Besides, observe that each pair of consecutive points in $Z$ is a pair of vertices of a triangle of our grid with its third vertex lying at the level $a_0$ between $z_1$ and $z_k$. Since all of the points of the segment between $z_1$ and $z_k$ are in $A_{i1}$, it follows that $z_m$ and $z_{m+1}$ are in $I^{\eps}_i$. It remains to notice that we can find $z_m$ since we know $k_2(a_0+1)$ and $k_3(a_0+1)$.

Acknowledgements. We wish to thank Florian Frick, Frédéric Meunier, and Hervé Moulin for helpful discussions and comments.

This research project was started during the Summer Research Program for Undergraduates 2021 organized by the Laboratory of Combinatorial and Geometric Structures at MIPT. This program was funded by the Russian Federation Government (Grant number 075-15-2019-1926).

Alexandr Grebennikov is supported by Ministry of Science and Higher Education of the Russian Federation, agreement № 075–15–2019–1619.

Andrei Malyutin is supported by RFBR, research project № 20-01-00070.

[1]
Asada, M., Frick, F., Pisharody, V., Polevy, M., Stoner, D., Tsang, L., Wellner, Z.:
Fair division and generalizations of Sperner- and KKM-type results.
SIAM J. Discrete Math. 32,
591–610 (2018)

[2]
Azrieli, Y., Shmaya, E.:
Rental harmony with roommates.
Journal of Mathematical Economics 46,
303–310 (2014)

[3]
Bapat, R. B.:
A constructive proof of a permutation-based generalization of Sperner's lemma.
Mathematical Programming 44,
113–120 (1989)

[4]
Deng, X., Qi, Q., Saberi, A.:
Algorithmic Solutions for Envy-Free Cake Cutting.
Operations Research 60,
1461–1476 (2012)

[5]
Dubins, L. E., Spanier, E. H.:
How to cut a cake fairly.
Amer. Math. Monthly 68,
1–17 (1961)

[6]
Frick, F., Houston-Edwards, K., Meunier, F.:
Achieving rental harmony with a secretive roommate.
Amer. Math. Monthly 126(1),
18–32 (2019)

[7]
Gale, D.:
Equilibrium in a discrete exchange economy with money.
International Journal of Game Theory 13,
61–64 (1984)

[8]
Knaster, B., Kuratowski C., Mazurkiewicz S.:
Ein Beweis des Fixpunktsatzes für \(n\)-dimensionale Simplexe.
Fundamenta Mathematicae 14,
132–137 (1929)

[9]
Musin, O. R.:
Around Sperner's lemma (2014).

[10]
Musin, O. R.:
Homotopy invariants of covers and KKM-type lemmas.
Algebr. Geom. Topol. 16(3),
1799–1812 (2016)

[11]
Musin, O. R.:
KKM type theorems with boundary conditions.
J. Fixed Point Theory Appl. 19(3),
2037–2049 (2017)

[12]
Robertson, J., Webb, W.:
Cake-Cutting Algorithms: Be Fair if You Can (1st ed.).
A K Peters/CRC Press, Nattick, MA (1998)

[13]
Steinhaus, H.:
Sur las division pragmatique.
Econometrica 17,
315–319 (1949)

[14]
Stromquist, W.:
How to cut a cake fairly.
Amer. Math. Monthly 87,
640–644 (1980)

[15]
Su, F. E.:
Rental harmony: Sperner’s lemma in fair division.
Amer. Math. Monthly 106(10),
930–942 (1999)


Christopher Culver

# Quantum computing for lattice supersymmetry

David Schaich

###### Abstract

Quantum computing promises the possibility of studying the real-time dynamics
of non-perturbative quantum field theories while avoiding the sign problem
that obstructs conventional lattice approaches. Current and near-future
quantum devices are severely limited by noise, making investigations of simple
low-dimensional lattice systems ideal testbeds for algorithm development.
Considering simple supersymmetric systems, such as supersymmetric quantum
mechanics with different superpotentials, allows for the analysis of phenomena
like dynamical supersymmetry breaking. We present ongoing work applying
quantum computing techniques to study such theories, targeting real-time
dynamics and supersymmetry breaking effects.

##  1 Introduction

Supersymmetry is an extension of Poincaré symmetry to include spinor
generators relating bosonic and fermionic fields. Supersymmetric theories have
rich features including appearance in holographic dualities [1] which are a
correspondence between spacetime in quantum gravity and a quantum field theory
on its boundary. The existence of dualities enables the indirect study of
phenomena in quantum gravity, such as the dynamics of evaporating black holes.
Instead of solving the quantum gravity problem it is sufficient to study the
quantum field theory. In this realm lattice regularization provides a non-
perturbative approach via both importance-sampling algorithms in classical
computing as well as the developing frontier of quantum simulation. Here we
study simple supersymmetric systems using quantum computing, which in
principle offers direct access to real-time dynamics of quantum field
theories. Beyond this, quantum computing may enable the investigation of
entanglement generation [2], dynamical supersymmetry breaking (which has a
severe sign problem [3, 4]), and real-time scattering of particles in
supersymmetric extensions of the standard model.

Quantum computing is currently in the Noisy Intermediate Scale Quantum (NISQ)
era [5] of quantum devices with low qubit counts and significant error rates
for the operations on qubits. The solution to an evaporating black hole or
real-time scattering are beyond the capabilities of NISQ devices. Modern
quantum computers are best suited to validating algorithmic advances on simple
test case systems. Here we will study simple supersymmetric quantum mechanics
(SQM) with two supercharges in $0+1$ dimensions. This system was recently
studied with classical-computing lattice methods by Refs. [6, 7, 8], which
explored dynamical supersymmetry breaking for different superpotentials.
Similar supersymmetric matrix models are also under consideration as targets
for quantum computing [9, 10, 11]. In this work we will study dynamical
supersymmetry breaking for three different superpotentials. In Section 2 we
define SQM in more detail and discuss how to test whether supersymmetry is
spontaneously broken. Then in Section 3 we discuss the necessary quantum
computing technology to analyze our supersymmetric system. Our progress is
presented in Section 4 including determinations of supersymmetry breaking and
the feasibility of studying SQM on NISQ devices.

##  2 Supersymmetric Quantum Mechanics

In this section we review SQM with two supercharges in $0+1$ dimensions. We
start by defining the Hamiltonian

$2H_{\text{SQM}}=2i\partial_{t}=\left\\{Q,\overline{Q}\right\\}=Q\overline{Q}+\overline{Q}Q,$
(1)

where $Q$ and $\overline{Q}$ are two independent supercharges with
$Q^{2}=\overline{Q}^{2}=0$ and $[H,Q]=[H,\overline{Q}]=0$. These can be
expressed in terms of bosonic and fermionic operators as

$\displaystyle Q$
$\displaystyle=\hat{b}\left[i\hat{p}+W^{\prime}(\hat{q})\right]$
$\displaystyle\overline{Q}$
$\displaystyle=\hat{b}^{{\dagger}}\left[-i\hat{p}+W^{\prime}(\hat{q})\right],$
(2)

where $\hat{q}$ and $\hat{p}$ are the bosonic coordinate and conjugate
momentum operators respectively. The function $W(\hat{q})$ is the
superpotential, and the prime denotes derivatives with respect to $\hat{q}$.
The fermionic operators $\hat{b}^{\dagger}$ and $\hat{b}$ create and destroy a
fermionic state respectively, with $\hat{b}^{2}=(\hat{b}^{{\dagger}})^{2}=0$
and $\left\\{\hat{b},\hat{b}^{{\dagger}}\right\\}=1$.

Using the above equations it is instructive to write down the Hamiltonian in
terms of bosonic and fermionic operators, for which

$\displaystyle
2H_{\text{SQM}}=\hat{p}^{2}+[W^{\prime}(\hat{q})]^{2}-W^{\prime\prime}(\hat{q})\left[\hat{b}^{{\dagger}},\hat{b}\right].$
(3)

The coupling between the fermion and boson depends entirely on the
superpotential. The Hilbert space of the Hamiltonian is the tensor product of
the Hilbert space of a single boson with that of a single fermion. The
continuous bosonic Hilbert space can be written with the basis
$\left|\phi\right\rangle$ where

$\displaystyle\left\langle\phi^{\prime}\mid\phi\right\rangle$
$\displaystyle=\delta(\phi^{\prime}-\phi),$
$\displaystyle\hat{q}\left|\phi\right\rangle$
$\displaystyle=\phi\left|\phi\right\rangle,$ $\displaystyle
e^{ip\Delta}\left|\phi\right\rangle$
$\displaystyle=\left|\phi+\Delta\right\rangle.$ (4)

The fermionic Hilbert space is a two-dimensional vector space spanned by
$\left|0\right\rangle$ and $\left|1\right\rangle$ with

$\displaystyle\hat{b}\left|1\right\rangle$
$\displaystyle=\left|0\right\rangle$
$\displaystyle\hat{b}^{{\dagger}}\left|1\right\rangle$ $\displaystyle=0$ (5)
$\displaystyle\hat{b}\left|0\right\rangle$ $\displaystyle=0$
$\displaystyle\hat{b}^{{\dagger}}\left|0\right\rangle$
$\displaystyle=\left|1\right\rangle.$ (6)

The bosonic Hilbert space needs to be regulated to map the degrees of freedom
to a finite number of qubits, which we will discuss in Section 3.

In this work we consider superpotentials for which the bosonic part of the
Hamiltonian can be written as a harmonic oscillator plus additional
interactions, $[W^{\prime}]^{2}\supset m^{2}\hat{q}^{2}$, where $m$ is the
mass of the particles. It is thus useful to transform from the
$\hat{q},\hat{p}$ basis to the $\hat{a}^{\dagger},\hat{a}$ creation and
annihilation operator basis of a harmonic oscillator, through the usual
definitions

$\displaystyle\hat{a}$
$\displaystyle=\sqrt{\frac{m}{2}}\hat{q}+\frac{i}{\sqrt{2m}}\hat{p},$
$\displaystyle\hat{a}^{\dagger}$
$\displaystyle=\sqrt{\frac{m}{2}}\hat{q}-\frac{i}{\sqrt{2m}}\hat{p}.$ (7)

The SQM Hamiltonian in Eq. 1 is manifestly supersymmetric, but supersymmetry
may break spontaneously depending on the superpotential. One way to study
dynamical supersymmetry breaking is to compute the Witten index [12]

$\mathcal{W}=\mbox{Tr}\left[(-1)^{F}e^{-iHt}\right]=\mbox{Tr}_{B}\left[e^{-iHt}\right]-\mbox{Tr}_{F}\left[e^{-iHt}\right].$
(8)

Here the first trace over all states of the Hilbert space is split into traces
over the bosonic and fermionic parts of the Hilbert space. A vanishing Witten
index, $\mathcal{W}=0$, is a necessary but insufficient condition for
supersymmetry breaking, and corresponds to a vanishing partition function
$Z=0$ that obstructs classical importance-sampling computations [3, 4].
Turning to quantum computing, a more straightforward approach is to exploit
the fact that supersymmetry is broken only if the ground-state energy is non-
zero. Computing the ground-state energy is a task well suited for the
variational quantum eigensolver (VQE) to be discussed in the next section.

##  3 Quantum Computing

To enable computations on a quantum computer we must regulate the infinite
bosonic degrees of freedom. We impose a hard cutoff $\Lambda$ of the boson by
limiting the number of accessible modes of the harmonic oscillator. While this
explicitly breaks supersymmetry, we expect that these effects will become
negligible for sufficiently large $\Lambda$. The raising and lowering
operators become

$\displaystyle\hat{a}$
$\displaystyle=\sum_{n=0}^{\Lambda-2}\sqrt{n+1}\left|n\right\rangle\left\langle
n+1\right|,$ $\displaystyle\hat{a}^{\dagger}$
$\displaystyle=\sum_{n=0}^{\Lambda-2}\sqrt{n+1}\left|n+1\right\rangle\left\langle
n\right|.$ (9)

Having a Hilbert space with a finite number of degrees of freedom, we can
convert the harmonic oscillator degrees of freedom to qubit ones. The first
step is to write the state $j$ in binary as $j=\sum_{i=0}^{N-1}b_{i}2^{i}$
with $N=\lceil\log_{2}\Lambda\rceil$. We associate one qubit with each binary
digit, and write the state as a tensor product of $N$ qubit states,

$\left|j\right\rangle=\left|b_{0}\right\rangle\left|b_{1}\right\rangle\ldots\left|b_{N-1}\right\rangle.$
(10)

Using this, we can translate the matrix element of any bosonic operator into
its representation in terms of the qubit degrees of freedom,

$\left|n\right\rangle\langle
n^{\prime}\mid=\otimes_{i=0}^{N-1}\left|b_{i}\right\rangle\left\langle
b_{i}^{\prime}\right|.$ (11)

It is useful to write the tensor product on the right hand side in terms of
Pauli matrices using the following four relations,

$\displaystyle\left|0\right\rangle\left\langle 1\right|$
$\displaystyle=\frac{1}{2}\left(X+iY\right),$
$\displaystyle\left|1\right\rangle\left\langle 0\right|$
$\displaystyle=\frac{1}{2}\left(X-iY\right),$ (12)
$\displaystyle\left|0\right\rangle\left\langle 0\right|$
$\displaystyle=\frac{1}{2}\left(1+Z\right),$
$\displaystyle\left|1\right\rangle\left\langle 1\right|$
$\displaystyle=\frac{1}{2}\left(1-Z\right).$ (13)

Any bosonic operator can thus be expressed as a linear combination of products
of Pauli matrices, called a Pauli string.

For the fermionic degrees of freedom we use the Jordan–Wigner transformation
which maps the fermionic occupation to spin degrees of freedom. The creation
and annihilation operators are

$\displaystyle\hat{b}^{{\dagger}}$
$\displaystyle=\frac{1}{2}\left(X-iY\right),$ $\displaystyle\hat{b}$
$\displaystyle=\frac{1}{2}\left(X+iY\right).$ (14)

We will always assign the fermionic degree of freedom to the $N+1$ qubit. The
mapping from bosonic and fermionic degrees of freedom to qubit ones results in
the Hamiltonian as a single Pauli string. This allows us to take advantage of
IBM Qiskit [13] implementations of quantum algorithms such as Trotter
evolution and the VQE algorithm. We conclude this section by briefly reviewing
each of these algorithms in turn.

First, to study real-time dynamics we need a quantum circuit for the operation
$e^{iHt}$ acting on the qubits. This can be done with the Suzuki–Trotter
decomposition which breaks the continuous time $t$ into $N$ ‘Trotter steps’ of
size $\delta\equiv t/N$ via

$e^{-iHt}\left|\psi\right\rangle=\left(\exp\left[-iH\delta\right]\right)^{N}\left|\psi\right\rangle.$
(15)

For a Hamiltonian that is a sum of $M$ terms, $H=\sum_{j=1}^{M}H_{j}$, a
single step becomes

$\left|\psi(t+\delta)\right\rangle\equiv\exp\left[-i\sum_{j=1}^{M}H_{j}\delta\right]\left|\psi(t)\right\rangle.$

In practice $M>1$ and the Baker–Campbell–Hausdorff formula is used to convert
the exponential of the sum $H$ into a product of exponentials involving
individual $H_{j}$. Since these various terms in the Hamiltonian do not
commute in general, this implies a trade-off between the number of gate
operations and the accuracy with which the state
$\left|\psi(t+\delta)\right\rangle$ can be obtained at the end of a single
Trotter step. There is a similar trade-off when we consider that the
Suzuki–Trotter decomposition also introduces errors dependent on $\delta$ and
on the ordering of gate operations within the circuit. A simple evolution step
such as that considered in Ref. [14] reduces gate counts at the cost of larger
errors, while more complicated evolution steps can reduce errors at the cost
of (typically significant) increases in the number of gate operations. In
Section 4 we discuss gate costs for a single Trotter step for SQM with various
superpotentials.

The VQE is a hybrid quantum–classical algorithm that finds the lowest
eigenvalue of a matrix [15]. When the matrix in question is a Hamiltonian,
this provides an approximation to the ground state as the corresponding
eigenvector. The algorithm functions similarly to the variational method.
First a trial wave function $\psi$ for the ground state is created which is
defined with tunable parameters $\theta_{i}$. A quantum circuit is used to
compute the energy of the parameterized wave function, whose parameters are
optimized via classical methods to minimize this energy. Eventually the
algorithm will converge to a value $E_{\text{var}}$ that is an upper bound for
the ground-state energy,

$E_{0}\leq
E_{\text{var}}=\frac{\left\langle\psi(\theta_{i})\left|H\right|\psi(\theta_{i})\right\rangle}{\left\langle\psi(\theta_{i})\,|\psi(\theta_{i})\right\rangle}.$
(16)

In this work we report on simulations of VQE analyses using classical
computing rather than actual quantum hardware. This leaves the performance of
the VQE dependent on the choice of trial wave function and classical
optimizer. For the trial wave function we use the $R_{y}$ variational form
[13], which only involves $y$ rotations and CX gates. For the classical
optimizer we use COBYLA which was shown to work well in Ref. [11]. In the next
section we present results for different superpotentials and cutoffs. Given
that the VQE provides only an upper bound on the ground-state energy, we
perform $100$ runs for each computation and quote the minimum result as the
best approximation to the ground state.

##  4 VQE analyses for various superpotentials

Here we discuss the current status of our studies of SQM with three different
superpotentials, for a range of cutoffs $\Lambda$. For each superpotential we
start by looking at the eigenvalues of the Hamiltonian via exact
diagonalization. Then we compare these exact values to the best result
obtained from $100$ runs of the VQE. Lastly we discuss the cost of attempting
to study the real-time dynamics of such systems in terms of their entangling
gate counts.

###  4.1 Harmonic Oscillator

The supersymmetric harmonic oscillator (HO) is specified by the superpotential

$W(\hat{q})=\frac{1}{2}m\hat{q}^{2},$ (17)

where $m$ is the mass of the boson and fermion. This is one of the simplest
superpotentials to consider since $W^{\prime\prime}(\hat{q})=m$ and the bosons
and fermions do not interact. No dynamical supersymmetry breaking is expected
for this superpotential [7]. The energy spectrum as a function of the cutoff
determined via exact diagonalization is plotted in Fig. 1. To preserve
supersymmetry the ground state-energy must vanish, and for any cutoff the
value is exactly zero. In fact, for this superpotential the only cutoff effect
seems to be the lack of excited states; the energies of all accessible states
are exact even for small cutoffs. The results of the VQE for representative
cutoffs up to $\Lambda\leq 32$ are given in Table 1. For this simple
superpotential the VQE clearly converges to zero energy, confirming that a
sufficiently low-noise quantum simulation would come to the correct conclusion
about supersymmetry breaking. For simulating the real-time evolution of this
system, the entangling (CX) gate counts are given by the green circles in Fig.
4. Notably, if the number of oscillator modes is set to a power of two,
$\Lambda=2^{n}$, no CX gates are required to evolve the system in time. This
makes the HO superpotential a promising benchmark for even today’s quantum
devices.

Table 1: Minimum energy from 100 runs of the VQE for various supersymmetric
superpotentials (with $m=g=\mu=1$). The harmonic and anharmonic oscillator are
expected to preserve supersymmetry and have a ground state energy of zero. The
double well breaks supersymmetry and should have a non-zero ground state
energy. The exact value represents the minimum energy from classical
diagonalization.

$\Lambda$ | Exact | VQE
---|---|---
2 | 0.00e+00 | 5.34e-10
4 | 0.00e+00 | 1.07e-09
8 | 0.00e+00 | 4.06e-09
16 | 0.00e+00 | 1.13e-08
32 | 0.00e+00 | 4.81e-08
(a) Harmonic oscillator.

$\Lambda$ | Exact | VQE
---|---|---
2 | 9.38e-01 | 9.38e-01
4 | 1.27e-01 | 1.27e-01
8 | 2.93e-02 | 2.93e-02
16 | 1.83e-03 | 6.02e-02
32 | 1.83e-05 | 6.63e-01
(b) Anharmonic oscillator.

$\Lambda$ | Exact | VQE
---|---|---
2 | 1.08e+00 | 1.08e+00
4 | 9.15e-01 | 9.15e-01
8 | 8.93e-01 | 8.93e-01
16 | 8.92e-01 | 8.94e-01
32 | 8.92e-01 | 8.95e-01
(c) Double well.

Figure 1: Spectra for different cutoffs of the bosonic degrees of freedom, for
the harmonic oscillator (left) and anharmonic oscillator (right)
superpotentials (with $m=g=1$). For each $\Lambda$ there are $2\Lambda$ states
which are differentiated by color. For the harmonic oscillator, and the large-
cutoff limit of the anharmonic oscillator, all levels except the ground state
and highest-energy state are two-fold degenerate.

###  4.2 Anharmonic Oscillator

The supersymmetric anharmonic oscillator (AHO) is given by the superpotential

$W(\hat{q})=\frac{1}{2}m\hat{q}^{2}+\frac{1}{4}g\hat{q}^{4},$ (18)

where $m$ is the mass of the boson and the coefficient $g$ dictates the
strength of the interaction between the boson and fermion. For any value of
$g$ the AHO is also expected to preserve supersymmetry [7]. In Fig. 1 we plot
the low-lying energy spectrum as a function of the cutoff using exact
diagonalization. Here we see more significant errors induced by the cutoff,
but as $\Lambda$ increases the low-lying energies rapidly converge. In Fig. 2
we plot the ground-state energy on a semi-log scale to show that it is
approaching zero exponentially quickly as $\Lambda$ increases, which confirms
that supersymmetry is preserved for this superpotential. The results for the
VQE in Table 1 show that it becomes difficult to find the expected ground-
state energy for larger cutoffs ($\Lambda>16$). This could be due to the fact
that our wave function is not expressive enough, and we are currently
exploring a greater variety of parameterizations. The entangling gate count
for a Trotter step is shown by the yellow crosses in Fig. 4. Here we can see a
dramatic increase in CX gates as a function of the cutoff compared with the HO
superpotential. There is still a significant decrease in the number of
entangling gates when $\Lambda=2^{n}$, although it is always non-zero. This
system will be very interesting to analyze using future NISQ hardware with
improved error rates.

Figure 2: Semi-log plot of the ground-state energy of the anharmonic
oscillator (with $m=g=1$) as a function of the cutoff. As the cutoff increases
this energy exponentially approaches zero signifying that supersymmetry is
preserved in this model.

###  4.3 Double Well

The supersymmetric double well (DW) is defined by the superpotential

$W(\hat{q})=\frac{1}{2}m\hat{q}^{2}+g(\frac{1}{3}\hat{q}^{3}+\hat{q}\mu^{2}),$
(19)

where $m$ is the mass while the coefficients $g$ and $\mu$ control the
strength of interactions between the boson and fermion. For non-zero values of
$g$ and $\mu$, this system is expected to exhibit dynamical supersymmetry
breaking [7]. In Fig. 3 we plot the spectrum from exact diagonalization as a
function of the cutoff. Similarly to the AHO, cutoff effects are non-
negligible for very small values of $\Lambda$. As the large-cutoff limit is
taken the ground-state energy clearly does not converge to zero, confirming
that supersymmetry is dynamically broken. The VQE results in Table 1
successfully reproduce this non-zero ground-state energy. The entangling gate
count in Fig. 4 scales in a comparable way to the AHO superpotential, with
significant cost reductions for cutoffs equal to a power of two.

Figure 3: Similar to Fig. 1 but for the double-well superpotential (with
$m=g=\mu=1$). As the large-cutoff limit is taken two-fold degeneracy is again
recovered—now also for the ground-state energy, which is non-zero due to
spontaneous supersymmetry breaking. Figure 4: Number of entangling CX gates in
a single Trotter step, as a function of the cutoff for the three
superpotentials (with $m=g=\mu=1$) considered so far: the harmonic oscillator
(green circles), the anharmonic oscillator (yellow crosses), and the double
well (blue stars). When the cutoff is equal to a power of two
($\Lambda=2^{n}$) there are significant reductions in the number of CX gates
required. In particular, this produces zero CX gates for the harmonic
oscillator, which isn’t visible on this semi-log plot.

##  5 Summary

We have presented first results from our work using quantum computing to study
supersymmetric quantum mechanics in $0+1$ dimensions. As a measure of
supersymmetry breaking we compute the ground-state energy using both classical
exact diagonalization and the hybrid quantum–classical VQE. Both methods
confirm that supersymmetry is preserved for the harmonic oscillator and
spontaneously broken for the double-well superpotential. For the anharmonic
oscillator exact diagonalization confirms the expected preservation of
supersymmetry, while the VQE has difficulties that we are currently
investigating by exploring whether different trial wave functions or classical
optimizers can improve its performance. Lastly we discussed the entangling
gate counts for a single Trotter step for each of the three superpotentials,
to illustrate why we consider supersymmetric quantum mechanics a promising
target for quantum computing in the NISQ era.

Acknowledgments: We thank Yannick Meurice and Hank Lamm for encouraging
discussions. This work was supported by UK Research and Innovation Future
Leader Fellowship MR/S015418/1 and STFC grant ST/T000988/1.

## References

  * [1] N. Itzhaki, J.M. Maldacena, J. Sonnenschein and S. Yankielowicz, _Supergravity and the large N limit of theories with sixteen supercharges_ , _Phys. Rev. D_ 58 (1998) 046004 [hep-th/9802042].
  * [2] P.V. Buividovich, M. Hanada and A. Schäfer, _Quantum chaos, thermalization, and entanglement generation in real-time simulations of the Banks–Fischler–Shenker–Susskind matrix model_ , _Phys. Rev. D_ 99 (2019) 046011 [1810.03378].
  * [3] G. Bergner and S. Catterall, _Supersymmetry on the lattice_ , _Int. J. Mod. Phys. A_ 31 (2016) 1643005 [1603.04478].
  * [4] D. Schaich, _Progress and prospects of lattice supersymmetry_ , _Proc. Sci._ LATTICE2018 (2019) 005 [1810.09282].
  * [5] J. Preskill, _Quantum computing in the NISQ era and beyond_ , _Quantum_ 2 (2018) 79 [1801.00862].
  * [6] D. Kadoh and K. Nakayama, _Lattice study of supersymmetry breaking in $\mathcal{N}=2$ supersymmetric quantum mechanics_, _Nucl. Phys. B_ 949 (2019) 114783 [1812.10642].
  * [7] A. Joseph and A. Kumar, _Complex Langevin dynamics and supersymmetric quantum mechanics_ , _JHEP_ 2110 (2021) 186 [2011.08107].
  * [8] N.S. Dhindsa and A. Joseph, _Probing Non-perturbative Supersymmetry Breaking through Lattice Path Integrals_ , 2011.08109.
  * [9] H. Gharibyan, M. Hanada, M. Honda and J. Liu, _Toward simulating Superstring/M-theory on a quantum computer_ , _JHEP_ 2107 (2021) 140 [2011.06573].
  * [10] A.J. Buser, H. Gharibyan, M. Hanada, M. Honda and J. Liu, _Quantum simulation of gauge theory via orbifold lattice_ , _JHEP_ 2109 (2021) 034 [2011.06576].
  * [11] E. Rinaldi, X. Han, M. Hassan, Y. Feng, F. Nori, M. McGuigan et al., _Matrix Model simulations using Quantum Computing, Deep Learning, and Lattice Monte Carlo_ , 2108.02942.
  * [12] E. Witten, _Dynamical Breaking of Supersymmetry_ , _Nucl. Phys. B_ 188 (1981) 513.
  * [13] M. Treinish et al., _Qiskit 0.29.0_ , _Zenodo_ (Aug. 2021) .
  * [14] R.C. Brower, D. Berenstein and H. Kawai, _Lattice Gauge Theory for a Quantum Computer_ , _Proc. Sci._ LATTICE2019 (2020) 112 [2002.10028].
  * [15] J.R. McClean, J. Romero, R. Babbush and A. Aspuru-Guzik, _The theory of variational hybrid quantum–classical algorithms_ , _New Journal of Physics_ 18 (2016) 023023 [1509.04279].


# FACADE: A Framework for Adversarial Circuit Anomaly Detection and
Evaluation

Dhruv Pai  Andres Carranza  Rylan Schaeffer  Arnuv Tandon  Sanmi Koyejo

###### Abstract

We present FACADE, a novel probabilistic and geometric framework designed for
unsupervised mechanistic anomaly detection in deep neural networks. Its
primary goal is advancing the understanding and mitigation of adversarial
attacks. FACADE aims to generate probabilistic distributions over circuits,
which provide critical insights to their contribution to changes in the
manifold properties of pseudo-classes, or high-dimensional modes in activation
space, yielding a powerful tool for uncovering and combating adversarial
attacks. Our approach seeks to improve model robustness, enhance scalable
model oversight, and demonstrates promising applications in real-world
deployment settings.

Machine Learning, ICML

##  1 Introduction

In recent years, the field of machine learning has witnessed significant
advancements propelled by improvements in learning algorithms and increased
access to computational resources. These advancements have led to the
development of larger and more capable models, offering remarkable performance
on various tasks. However, as models grow in size and complexity, their
interpretability diminishes (Gao & Guan, 2023). The sheer scale of modern deep
learning models renders traditional methods of interpretation, such as feature
importance or attribution, inadequate. The opacity of these models hinders our
ability to understand the reasoning behind their predictions and opens the
door to potential adversarial attacks.

Moreover, complex models possess numerous axes along which adversarial attacks
can be targeted, making them more vulnerable. Adversarial attacks exploit
small, carefully crafted perturbations to inputs that can mislead models into
making incorrect predictions (Chakraborty et al., 2021). With the increase in
model complexity, the space of potential adversarial perturbations expands
exponentially, making detection and mitigation increasingly difficult.

Furthermore, as AI capabilities continue to grow, and as the freedoms afforded
to such models continue to expand, the implications of a hijacked model pose
substantial risks to society, for example through damage to critical systems
or infrastructure. Robust mechanisms are needed to detect and prevent the
misuse of models, especially as they become more powerful and potentially
capable of autonomously evolving their behavior. An unsupervised framework for
detecting anomalous behavior in models can serve as a crucial component in
safeguarding against such risks.

In this paper, we propose mechanistic anomaly detection via probabilistic
models for circuit mechanisms within models as a scalable method for model
oversight. Our novel circuit-based framework aims to elucidate complex
mechanistic pathways relevant to robustness and does so in an unsupervised
fashion without any priors as to the nature of an adversarial attack. Our
method develops probabilistic models operating in the geometry of neural
activation space that facilitates the detection of deviations from the
expected behavior, thereby enabling the identification of anomalous model
outputs or adversarial attacks111To understand how our proposal relates to
emerging directions in adversarial machine learning, see Carranza et al.
(2023)..

##  2 Mechanistic Anomaly Detection

###  2.1 Activations

Previously, a detailed analysis of flows in activation space proved
computationally intensive and opaque. Insofar as neural networks apply a
series of nonlinear geometric transformations to high-dimensional data
manifolds, the propagation of data points through these transformations is
computationally irreducible and largely uninterpretable directly (Cohen et
al., 2020). However, understanding the propagation of data points in the high-
dimensional activation space has profound implications for the reliability and
security of our models, and this understanding may hold the key to
investigating adversarial robustness.

Adversarial examples have been demonstrated to exploit the complex, and often
poorly understood, geometry of the decision boundaries within this high-
dimensional space (Gebhart et al., 2019). Thus, developing methods capable of
elucidating these decision boundary structures and understanding the geometry
of high-dimensional modes in activation space would lead to improved
adversarial robustness. Prior literature and preliminary experiments
demonstrate that neural networks in activation space learn pseudo-classes:
intermediate groupings of features learned by the model that resemble high-
density modes (Gebhart et al., 2019). An understanding of the distribution,
composition, and shape of pseudo-classes within a network offers a lens into
the mechanistic behavior of the model.

###  2.2 Circuit Mechanisms

As defined by Wang et al. (2022), a circuit is a subgraph of a neural
network’s overall computational graph. Small circuits have recently been
investigated for their role in interpretability, in particular identifying
circuits corresponding to certain visually meaningful properties of an image,
e.g., orientation, curve-detection, color-detection circuits (Olah et al.,
2020). Circuits have been demonstrated as a valuable intermediate between
single-neuron and whole-model holistic interpretability, as they are well-
conserved across mechanistically similar models and provide valuable insights
into model behavior for a wide variety of architectures and datasets (Elhage
et al., 2021).

Figure 1: The intermediate scale of interpretability is simultaneously the
most poorly understood and the most complex, yet could offer the greatest
insights into MAD.

Problematically, circuit interpretability has focused overwhelmingly on
uncovering circuits responsible for specific adversarially or visually
meaningful features specified a posteriori (Olah et al., 2020; Wang et al.,
2022; Conmy et al., 2023). Such an approach requires a specification of the
features used in an adversarial attack before circuit interpretability is
applied, which is rarely the case in a real-world deployment setting (Carlini
et al., 2019). Supervised circuit interpretability also extrapolates poorly
across mechanistically distinct models. We therefore motivate an unsupervised
circuit interpretability approach with the promise of revealing novel insights
into mechanistic anomalies, while improving model invariance, computational
efficiency, and scalable model oversight.

###  2.3 Blue Sky MAD Approach

To identify adversarial examples, and their corresponding circuits through
mechanistic anomaly detection, we propose a novel probabilistic, geometric
framework for creating unsupervised distributions over circuits in a deep
neural network titled FACADE: A Framework for Adversarial Circuit Anomaly
Detection and Evaluation. Specifically, we envision a four-step approach,
where the hyperparameter $\lambda$ can be interpreted as setting the
resolution of circuit analysis.

  1. 1.

Utilize the probabilistic Dirichlet Process Mixture model (Blei & Jordan,
2006; Kulis & Jordan, 2011) for unsupervised clustering (DP-Means) to identify
”pseudoclass” modes in intermediate activation space for a given density
threshold $\lambda$ (Dinari & Freifeld, 2022)

  2. 2.

Elucidate circuits responsible for pseudoclass formation and propagation
through causal discovery and Automatic Circuit DisCovery (ACDC) (Nauta et al.,
2019) (Conmy et al., 2023)

  3. 3.

Determine manifold and kernel density properties of pseudoclass propagation
through circuits and in relation to final classes through mean-field theoretic
approximation (Cohen et al., 2020)

  4. 4.

Generate a distribution over circuits as they contribute to changes in
manifold properties of pseudoclasses as they propagate through the network,
e.g. effective reduction in radius or dimension

Repeating the above algorithm for a sweep of $\lambda$ values allows for
circuit distribution evaluation across a variety of features and mechanistic
pathways. By analyzing anomalous circuits in the distribution or employing
FACADE to prune circuits, we envision significant gains in adversarial
robustness. Adversarial circuits, identified as probabilistic outliers in
geometric transformations, would stand out on FACADE distributions and could
easily be reverse-engineered to derive how adversarially-susceptible
pseudoclasses can be made more robust by surgical tuning of weights. It is
worth noting that FACADE relies on sufficiently many training examples to
capture meaningful activation flows in an unsupervised fashion. However, if
this condition is met, at test-time FACADE distributions with a simple
probabilistic thresholding approach can identify and prevent mechanistic
anomalies and adversarial attacks autonomously.

## References

  * Blei & Jordan (2006) Blei, D. M. and Jordan, M. I.  Variational inference for dirichlet process mixtures.  2006\.
  * Carlini et al. (2019) Carlini, N., Athalye, A., Papernot, N., Brendel, W., Rauber, J., Tsipras, D., Goodfellow, I., Madry, A., and Kurakin, A.  On evaluating adversarial robustness, 2019.
  * Carranza et al. (2023) Carranza, A., Pai, D., Tandon, A., Schaeffer, R., and Koyejo, S.  Deceptive alignment monitoring, 2023.
  * Chakraborty et al. (2021) Chakraborty, A., Alam, M., Dey, V., Chattopadhyay, A., and Mukhopadhyay, D.  A survey on adversarial attacks and defences.  _CAAI Transactions on Intelligence Technology_ , 6(1):25–45, 2021.  doi: https://doi.org/10.1049/cit2.12028.  URL https://ietresearch.onlinelibrary.wiley.com/doi/abs/10.1049/cit2.12028.
  * Cohen et al. (2020) Cohen, U., Chung, S., Lee, D. D., and Sompolinsky, H.  Separability and geometry of object manifolds in deep neural networks.  _Nature communications_ , 11(1):746, 2020.
  * Conmy et al. (2023) Conmy, A., Mavor-Parker, A. N., Lynch, A., Heimersheim, S., and Garriga-Alonso, A.  Towards automated circuit discovery for mechanistic interpretability, 2023\.
  * Dinari & Freifeld (2022) Dinari, O. and Freifeld, O.  Revisiting dp-means: fast scalable algorithms via parallelism and delayed cluster creation.  In _Uncertainty in Artificial Intelligence_ , pp. 579–588. PMLR, 2022.
  * Elhage et al. (2021) Elhage, N., Nanda, N., Olsson, C., Henighan, T., Joseph, N., Mann, B., Askell, A., Bai, Y., Chen, A., Conerly, T., DasSarma, N., Drain, D., Ganguli, D., Hatfield-Dodds, Z., Hernandez, D., Jones, A., Kernion, J., Lovitt, L., Ndousse, K., Amodei, D., Brown, T., Clark, J., Kaplan, J., McCandlish, S., and Olah, C.  A mathematical framework for transformer circuits.  _Transformer Circuits Thread_ , 2021.  https://transformer-circuits.pub/2021/framework/index.html.
  * Gao & Guan (2023) Gao, L. and Guan, L.  Interpretability of machine learning: Recent advances and future prospects.  _IEEE MultiMedia_ , pp. 1–12, 2023.  doi: 10.1109/MMUL.2023.3272513.
  * Gebhart et al. (2019) Gebhart, T., Schrater, P., and Hylton, A.  Characterizing the shape of activation space in deep neural networks.  In _2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA)_ , pp. 1537–1542. IEEE, 2019.
  * Kulis & Jordan (2011) Kulis, B. and Jordan, M. I.  Revisiting k-means: New algorithms via bayesian nonparametrics.  _arXiv preprint arXiv:1111.0352_ , 2011.
  * Nauta et al. (2019) Nauta, M., Bucur, D., and Seifert, C.  Causal discovery with attention-based convolutional neural networks.  _Machine Learning and Knowledge Extraction_ , 1(1):312–340, 2019.
  * Olah et al. (2020) Olah, C., Cammarata, N., Schubert, L., Goh, G., Petrov, M., and Carter, S.  Zoom in: An introduction to circuits.  _Distill_ , 2020.  doi: 10.23915/distill.00024.001.  https://distill.pub/2020/circuits/zoom-in.
  * Wang et al. (2022) Wang, K., Variengien, A., Conmy, A., Shlegeris, B., and Steinhardt, J.  Interpretability in the wild: a circuit for indirect object identification in gpt-2 small.  _arXiv preprint arXiv:2211.00593_ , 2022.