# Different Games in Dialogue: Combining character and conversational types in
strategic choice

Alafate Abulmiti
Université de Paris, CNRS
Laboratoire de Linguistique Formelle<EMAIL_ADDRESS>
###### Abstract

In this paper, we show that investigating the interaction of _conversational
type_ (often known as language game or speech genre) with the character types
of the interlocutors is worthwhile. We present a method of calculating the
decision making process for selecting dialogue moves that combines character
type and conversational type. We also present a mathematical model that
illustrate these factors’ interactions in a quantitative way.

##  1 Introduction

Wittgenstein (1953); Bakhtin (2010) introduced language games/speech genres as
notions tying diversity of linguistic behaviors to activity. Building on this,
and insights of pragmaticists such as Hymes (1974); Allwood (2000), and
earlier work in AI by (Allen and Perrault, 1980; Cohen and Perrault, 1979)
Larsson (2002); Ginzburg (2012); Wong and Ginzburg (2018) showed how to
associate global structure with conversations in a way that captures the range
of possible topics and idiosyncratic moves. (Larsson, 2002) is also the basis
for an approach to building spoken dialogue systems (SDS) which is essentially
domain general, offers a fine-grained treatment of grounding interaction, and
which was extended to clarification interaction in (Purver, 2004).

This body of work does not address, however the issue of strategic choice in
conversation, which is the core issue underlying work in Game Theory. Asher et
al. (2017) used game theoretic tools to develop a theory of strategic choice
for dialogue. Although there are a variety of interesting insights captured in
this approach, it is based on two assumptions that apply only to a restricted
class of language games—games continue indefinitely and there exists a jury
that assigns winning conditions to participants.

We seek to develop an approach to strategic choice applicable to the general
case of dialogical interaction, where termination is an important
consideration and where assessment is internal to the participants. Strategic
choice is modelled by combining structure from conversational types with
psychological and cognitive notions associated with the players.

Character type as a relatively independent factor abstracted out of the
conversational type is important for dialogue. Although there is some analysis
concerning both character effects and conversational types in the dialogue,
combining them and analyzing their interactions in a quantitative way has not,
to our knowledge, been carried out before. The purposes of this paper is,
hence, to combine character type effect and conversational type analysis to
yield a method that could help to analyse strategic choice in dialogue.

##  2 Background

The starting point of (Asher et al., 2017) is the framework of Banach-
Mazurckiewicz games. They modify this framework to make it more amenable to
analyzing certain kinds of NL dialogue, the emergent framework being _BM
messaging games_. Asher et al. (2017) argued that each dialogue potentially
continues indefinitely and has a winner adjudged by a third party jury. This
is useful for modelling political discourse between rival groups or individual
contenders in the public domain. But clearly this sort of conception is not
appropriate for a variety, arguably most types of dialogue.111Strictly
speaking, Asher et al. (2017) allowed also for finite games, by allowing for
games to consist of a special move from a certain point onwards, but this
would seem to either defeat the purpose of assuming potential extendibility or
to be purely formal. These have beginnings ($InitState$) and a variety of
distinct terminations ($FinState$) Wong (2018), and there is no ‘external
jury’ in most cases.

Burnett (2019) developed a formal model called social meaning games which
explains how social variants affect the linguistic style of dialogue
participants. And conversely, how the speaker’s intrinsic linguistic style
affects dialogue moves. Pennebaker and King (1999) shows that linguistic style
is an independent and meaningful way of exploring personality. There is
evidence that people’s personality traits influence their use of language. For
instance, extroverted individuals are able to deceive others more easily,
while neurotic individuals are less likely to be deceived Riggio et al.
(1988). The charisma of a speaker has been shown to be closely related to an
extroverted character Bono and Judge (2004). There is also a strong relation
between extroversion and conscientiousness and positive influences, as well as
between neuroticism and dissent and various negative influencesWatson and
Clark (1992). Thus, an individual’s personality does affect decision-making
process in dialogue.

Cooperation in dialogue is a widespread phenomenon, and Allwood et al. (2000)
identified four features of cooperation: cognitive consideration, joint
purpose, ethical consideration and trust. When engaging in a collaborative
dialogue, where the interlocutor decides his next move based on the intentions
of the other and a variety of information deriving from the context of the
dialogue, it seems that character has a broad influence on the course of the
dialogue. Thus, it seems natural that a dialogue participant (DP) should also
take into account the other’s character traits in order to choose the
appropriate move.

In the next section, we will explain the method we propose of combining
character type effects and conversational type.

##  3 Methodology

In this section, we wish to explore the interaction between character type and
conversational type, by considering how given a possible range of moves, a
quantitative analysis can be provided for move selection.

###  3.1 Character Type

Researchers have developed a relatively unanimous consensus on personality
description patterns, proposing the Big Five model of personalityGoldberg
(1992). Within this model there are five traits that can be used to capture
many aspects of human personality. The Big Five Personality (OCEAN) can be
assessed by the NEO-PI-RCosta Jr and McCrae (2008). The traits can be
described as follows:

  * •

Openness: the ability to be imaginative, aesthetic, emotional, creative,
intelligent, etc.

  * •

Conscientiousness: displays characteristics such as competence, fairness,
organization, due diligence, achievement, self-discipline, caution, restraint,
etc.

  * •

Extroversion: exhibits qualities such as enthusiasm, sociability,
decisiveness, activity, adventure, optimism, etc.

  * •

Agreeableness: the qualities of trust, altruism, straightforwardness,
compliance, humility, empathy, etc.

  * •

Neuroticism: difficulty balancing emotional traits such as anxiety, hostility,
repression, self-awareness, impulsivity, vulnerability, etc.

Goldberg (1992) gave a pertinent method to quantify character types in terms
of 5 dimensional vector $[o,c,e,a,n]$. We define $\chi_{s}$ for the self
character type scale vector and $\chi_{o}$ represents other character type
scale vector.

In addition, with the development of machine learning and deep learning
methods within NLP, a variety of approaches have been implemented for
automatic recognition of personality in conversation and text Mairesse et al.
(2007). Jiang et al. (2019) used attentive network and contextual embeddings
to detect personality traits from monologues and multiparty dialogues. Given a
text(or utterance), one can calculate the character type scale vector of this
sentence with a robust prediction model. We define $c_{i}$ as $i$th dialogue
move vector prediction.

We note that by calculating the similarity between the $\chi$ and $c_{i}$, we
obtain the extent to which a given dialogue move can fit either the self
character type or the other character type. Note that $\chi_{s}$ is a dialogue
interlocutor’s intrinsic property which does not show great change during
conversation, but considering one’s imperfect information situation,
$\chi_{o}$ will change once new evidence arises and can be modified by
applying Bayes’ rule.

###  3.2 Conversational Type

Pennebaker and King (1999) also indicated that linguistic style gets
influenced by the situation in which the interlocutor find themselves. Wong
and Ginzburg (2018) provided a topological perspective on the space of
conversational types based on the distribution of Non-Sentential Utterances
(NSU) within each type. Wong (2018) developed a model of a conversational type
couched in TTR Cooper (2005). On this view, a conversational type is a 4-tuple
{$ConvRules$, $InitState$, $FinState$, $G$}, here $ConvRules$ represents a set
of conversational rules, transition rules between different dialogue states
(_dialogue gameboards_) of type $DGBType$ (Ginzburg, 2012), $InitState$ and
$FinState$ are the initial and final DGB states.
$DGBType$ $\mapsto$
$\mskip-3.0mu\left[\hskip 0.0pt\vbox{\vskip
1.65761pt\halign{\avmjfont\strut#\unskip\hfil&&\hskip\avmjhskip\avmjvalfont#\unskip\hfil\cr
spkr: Ind \\\ addr: Ind \\\ utt-time: Time \\\ c-utt: adressing(spkr, addr,
utt-time) \\\ FACTS: set(Proposition) \\\ Pending: list(Locutionary
Proposition) \\\ Moves: list(Locutionary Proposition) \\\ QUD: poset(Question)
\\\ }\vskip 1.65761pt}\hskip 0.0pt\right]\mskip-3.0mu$

G is the grammar which serves for the different conversational language use.

##### An Example

Considering a commercial transaction conversational type involving shopping in
a bakery, so that we have:
$Bakery=$
$\mskip-3.0mu\left[\hskip 0.0pt\vbox{\vskip
1.65761pt\halign{\avmjfont\strut#\unskip\hfil&&\hskip\avmjhskip\avmjvalfont#\unskip\hfil\cr
participant: InteractionGroup \framebox{\@text@daccent{$\wedge$}}
$\mskip-3.0mu\left[\hskip 0.0pt\vbox{\vskip
1.65761pt\halign{\avmjfont\strut#\unskip\hfil&&\hskip\avmjhskip\avmjvalfont#\unskip\hfil\cr
c1:customer(A) \\\ c2:baker(B) \\\ }\vskip 1.65761pt}\hskip
0.0pt\right]\mskip-3.0mu$\ignorespaces\\\ qnud-set = QS : poset(question) \\\
c1 : $\mskip-3.0mu\left\\{\hskip 0.0pt\vbox{\vskip
1.65761pt\halign{\avmjfont\strut#\unskip\hfil&&\hskip\avmjhskip\avmjvalfont#\unskip\hfil\cr$\lambda$
x.InShopBuy(A,x), $\lambda$ P.P(A),\\\ $\lambda$ P.P(B), $\lambda$ x.Pay(A,x)
\crcr}\vskip 1.65761pt}\hskip 0.0pt\right\\}\mskip-3.0mu$\ignorespaces$\in$
QS\\\ moves : list(IllocProp) \crcr}\vskip 1.65761pt}\hskip
0.0pt\right]\mskip-3.0mu$

this involves:

  * •

participants: Baker and customer.

  * •

qnud-set: questions to be discussed during the interaction

  * •

moves: Dialogue moves made.

Wong (2018) argued that clarification interactions provide data showing that
interlocutors can be uncertain about the conversational type that classifies
the interaction they are in, as for instance in (3.2):

  * (Context: A is being interviewed by B) A: Hi B: Hi . . . B (1): have you seen Blackklansman yet? A (2): Wait— is this an informal chat or a formal interview? B: A bit of both. (Example (54) from (Wong, 2018).

Thus, the DP has an opaque or uncertain ”guess” as to the conversational type
and this also influences the decision-making process. Following probabilistic
TTR theory Cooper et al. (2014), we assume that the DP has a probabilistic
conversational type in the private part of information state and this can be
updated during dialogue by Bayesian inference. We model the information state
as follows:
$InformationState=$
$\mskip-3.0mu\left[\hskip 0.0pt\vbox{\vskip
1.65761pt\halign{\avmjfont\strut#\unskip\hfil&&\hskip\avmjhskip\avmjvalfont#\unskip\hfil\cr
private = $\mskip-3.0mu\left[\hskip 0.0pt\vbox{\vskip
1.65761pt\halign{\avmjfont\strut#\unskip\hfil&&\hskip\avmjhskip\avmjvalfont#\unskip\hfil\cr
CharacterType:$\mskip-3.0mu\left[\hskip 0.0pt\vbox{\vskip
1.65761pt\halign{\avmjfont\strut#\unskip\hfil&&\hskip\avmjhskip\avmjvalfont#\unskip\hfil\cr
Self: Vector \\\ Other: Vector \\\ }\vskip 1.65761pt}\hskip
0.0pt\right]\mskip-3.0mu$\ignorespaces\\\ Goals: Set(Prop) \\\ Tmp: private
\\\ ConvType : ConvType \\\ Conv-prob : [0, 1] \crcr}\vskip 1.65761pt}\hskip
0.0pt\right]\mskip-3.0mu$\ignorespaces\\\ dgb :DGBType \crcr}\vskip
1.65761pt}\hskip 0.0pt\right]\mskip-3.0mu$

In the private part, we have the CharacterType stores for self and other’s
character type vector; Goals tracks a set of (futurate) propositions that the
DP wants realized; Tmp is a backup of the previous private state. Its use is
for reasoning about the current CharacterType and updating the Conv-prob;
ConvType is the conversational type and here we introduce Conv-prob, which
indicates the probabilistic conjecture concerning the current conversational
type.

###  3.3 Move Space

Individuals choose the moves from different kind of possible options. Ginzburg
et al. (2019) provided a taxonomy of the response space of queries. 14
possible categories are given by the study of English and Polish corpus. The
field of Nature Language Generation has some useful probabilistic methods to
generate the range of potential moves, such as the Sequence-to-Sequence
modelSutskever et al. (2014). See et al. (2019) proposed a new conditional
weight control technique to make the response space more human-like. The
popular pre-training model like BERTDevlin et al. (2018) exemplifies NLG
capability with fine-tuning. We define here $A$ for a dialogue move space
vector composed by $a_{i}$ representing the $i$th move.

In the current work we will not discuss how to specify the possible moves, but
will leave this for future work.

###  3.4 Decision Making

####  3.4.1 Global View

Levelt (1993) proposed that speakers monitors themselves while speaking. In
other words, individuals have a self-criticism mechanism enabling them to
reflect on their behaviors, emotions and speaking. We dub this the
SelfMonitor.

Given our analysis in the first two subsections, a DP’s move choice in the
dialogue is influenced by her character type, the other interlocutor’s
character type, and the conversational type. When a DP tries to respond to the
other party’s dialogue move, she first constructs a dialogue move space, which
yields a set of possible utterances that the DP can use. The DP typically
makes a conjecture about the other’s character type in terms of individual
personality traits, based on her a priori knowledge of that individual and the
current state of the dialogue. In addition, the DP has a probabilistic
assumption about the present conversational type given her cognitive state.
Subsequently, the DP’s SelfMonitor determines which factor is more valuable in
this context. Eventually a move is selected considering each possible move’s
value by comparing the affinity of each move for each factor with the skewness
of each factor as determined by the SelfMonitor.

####  3.4.2 Mathematical Modeling

After the above analysis, we offer a mathematical model to explicate this
process. In evaluating possible moves, we have three important factors: self
character type, other character type, and the conversational type. We want to
provide a real valued function $\rho$ to evaluate each move in the dialogue
move space.

  * •

$a_{i}$: $i$th move.

  * •

$\overrightarrow{\chi_{s}}$: Self character type vector.

  * •

$\overrightarrow{c_{i}}$: character type vector for $i$th move.

  * •

$\alpha$ Weight for the self character type effect.

  * •

$\overrightarrow{\chi_{o}}$: Current other character type vector estimation.

  * •

$\beta$: Weight for the other character effect.

  * •

$p$: Probabilistic conjecture of the conversational type.

  * •

$d_{i}$: $i$th move conformity with the conversational type from -1 to 1.

  * •

$\gamma$ Weight for probabilistic conversational type.

  * •

$W=[\alpha,\beta,\gamma]$.

Conformity represents the degree to which a dialogue move conforms to the
current conversational type. In other words, it can be modeled as the
evaluation score generated by this dialogue move in dialogue context.

In order to calculate the ”affinity” among character type vector
{$\chi_{s}$,$\chi_{o}$} and move vector ($c_{i}$), we use cosine similarity,
defined as follows:

$simi(A,B)=\cos(\theta)=\frac{A\cdot B}{\|A\|\|B\|}$ (1)

Then we define the function $\rho(a_{i})$:

$\rho(a_{i})=\alpha\cdot
simi(\overrightarrow{c_{i}},\overrightarrow{\chi_{s}})+\beta\cdot
simi(\overrightarrow{c^{i}},\overrightarrow{\chi_{o}})+\gamma d_{i}\cdot p\\\
$ (2)

and let $X=[simi(\overrightarrow{c_{i}},\overrightarrow{\chi_{s}}),\
simi(\overrightarrow{c^{i}},\overrightarrow{\chi_{o}}),\ d_{i}\cdot p]^{T}$ as
a decision factor matrix, obtaining:

$\rho(A)=W\cdot X$ (3)

where $\alpha+\beta+\gamma=1$

$\alpha$, $\beta$, $\gamma$ are in fact estimated by the SelfMonitor based on
information deriving from the information state. We believe those weights are
mainly fixed in the beginning of the conversation, because great changes in
strategic choice lead to the suspicion of deception in some cases Riggio et
al. (1988), This estimation process can be back-engineered by observing DP’s
selection of moves in the dialogue.

After the calculation of $\rho$, we get the score for each move. This score
alone cannot determine the final decision—we need to take into account the
features that we have not yet discussed and observed, so here we will
probabilize them, i.e., convert it into a probabilistic distribution space
using the $softmax$ function.

$softmax(a_{i})=\frac{exp(\rho(a_{i}))}{\sum_{j}exp(\rho(a_{j})))}$ (4)

We then obtain a probability estimate for each move, which indicates that the
greater the probability the DP is more inclined to choose this move.

###  3.5 Example

Here we illustrate our proposed approach with an example.

####  3.5.1 Scenario

In a bakery, we observe a customer and baker’s buying and selling process
during the pandemic of COVID-19.

##### Goals

For simplicity we fix the final goals as follows:

  * a.

Customer goal: buy two croissants.

  * b.

Baker goal: sell the two croissants and obtain the desired price.

It is worth noting that both players may have more complex goals or a series
of goals. For example, the customer might want to have appropriate desserts
for dinner. In order to achieve those kind of goals, we often divide into
several specific and simple goals. In such a case, the sub-goal might be:

  1. 1.

what are the best desserts in this bakery?

  2. 2.

From among those best desserts, which one will fit the dishes I prepare
tonight?

For our current purposes, however, we will avoid such complications, despite
their importance in a variety of cases.

####  3.5.2 Move Space

We assess a baker’s possible responses to the customer’s initial utterance: ”2
croissants”. We assume the following possible responses of the baker:

  * client 2 croissants. baker (i) 1.90.
(ii) Get out of the bakery, you’re not wearing a mask.
(iii) Please would be nice.
(iv) 1.90 and please would be nice.

(i) would lead to a quick end that meet their needs. This ”style” is used in
most cases in our life disregarding other conversational factors and attending
only to the baker’s final goals. If the baker considers particularly the
conversational type’s impact, he would choose (i) to advance the conversation,
thereby looking forward to finalizing the conversation early and achieving his
goal.

(ii) would lead to an ”unpleasant” conversation. The baker thinks that the
customer’s behavior is disrespectful (a short demand lacking politeness). He
therefore uses the lack of the mask as a pretext or has in mind a competing
goal for fighting against this disrespect. Finally, neither participants goals
is achieved.

(iii) This choice shows that the baker wants to have a pleasant and respectful
conversation above all. It is clear that baker does not assign much weight to
his final goals or the conversational type. Instead he prioritizes his
psychological needs. The question under discussion would shift to another
topic and the conversation might evolve into a dispute, though with lower
probability than in (ii).

(iv) indicate that the baker wants to persist with the trade without
disturbing his final goals and his psychological needs. This seems to be very
much of a compromise move, but still the final state would depend on the
customer’s interpretation of the dialogue pragmatics.

####  3.5.3 A worked example

For this example, we have a character type vector of [o, c, e, a, n] we assume
that baker character vector is $\chi_{s}$ = [0.0, 0.3, 0.0, 0.0, 0.5] showing
conscientiousness and relatively high neuroticism and Conv-prob is $p$ = 0.98
assuming the baker’s conformity with the bakery conversational type is high.
Following the initial state $S_{0}$, the baker hears ”2 croissants” from
client, after which the baker updates the information state then the
SelfMonitor chooses values for $\alpha,\beta,\gamma$. For example, we assume
$\alpha$ = 0.1, $\beta$ = 0.1 and $\gamma$ = 0.8, we assume, in this
circumstance, that the baker thinks more about the conversational type rule
than self character type and other character type, then:

$CharacterType.Other=\chi_{o}$ $\chi_{o}=\mu(\Uparrow
Tmp.CharacterType.Other,\Uparrow dgb)$

$\mu$ is the other’s character type updating function with parameters: the
previous state’s character type vector and the current DGB. We assume that
after the other’s character type update we have $\chi_{o}$ = [0.0, 0.0, -0.1,
-0.4, 0.2] assuming the customer is not very agreeable (-0.4) and a little
neurotic (0.2).

(i): We assume that ”1.90” shows disagreeableness (-0.4) and slight
neuroticism (0.2) so $c_{1}$ = [0.0, 0.0, -0.1, -0.4, 0.2] and $d_{1}$ = 0.8
shows ”1.90” shows high conformity with the bakery conversational type. Then
according to function (2) we have: $\rho(a_{1})$ = 0.7646

(ii): We assume that ”Get out of the bakery, you’re not wearing a mask” shows
high disagreeableness (-0.7), low conscientiousness (-0.5) and high
neuroticism (0.8) so $c_{2}$ = [0.3, -0.5, 0.0, -0.7, 0.8] and $d_{2}$ = -1.0
shows incongruity with the bakery type. As a result, we obtain $\rho(a_{2})$ =
-0.7080

(iii): We assume that ”Please would be nice” shows high agreeableness (0.7)
and slight extroversion (0.3) $c_{3}$ = [0.2, 0.0, 0.3, 0.7, -0.2] and $d_{3}$
= 0.3 shows low conformity with the conversational type. Consequently, we
obtain $\rho(a_{3})$ = 0.1201

(iv): We assume that ”1.90 and please would be nice” shows relatively high
openness (0.5), conscientiousness (0.6) and extroversion (0.4), high
agreeableness (0.7) and low neuroticism (-0.4) so $c_{4}$ = [0.5, 0.6, 0.4,
0.7, -0.4] and $d_{4}$ = 0.7 shows high conformity with the bakery type. So we
obtain, $\rho(a_{4})$ = 0.4727

We then apply those preference score with the $softmax$ function:
$softmax(\overrightarrow{\rho(a_{i})})$ = [0.3998, 0.0917, 0.2099, 0.2986]

This indicates that the probability that the baker selects (i) is 39.98% (iv)
is the next ranked score. All this assuming that the baker’s character type is
relative high neuroticism and the commitment degree to the conversational type
is high. Given his character type, it is reasonable to conclude that he would
not be extremely polite (option iv) but not rude because of the constraint of
conformity with the conversational type.

Now we want to illustrate that if we change the distribution of certain of the
parameters, things can flip significantly. We change the distribution of
different variables ($\alpha,\beta,\gamma$) to [0.3, 0.1, 0.6] showing that
the baker is concerned a little more about his own character type (0.3 rather
than 0.1) but slightly less than before on conversational type (0.6). And we
assume the baker’s character type vector is [0.5, 0.7, 0.3, 0.8, -0.5] which
shows high conscientiousness (0.7), low neuroticism (-0.5) and high
agreeableness. Then we obtain:$\rho(\overrightarrow{A})$ = [0.3457, -0.7277,
0.3217, 0.6946]. the resulting following with probabilistic distribution is
$softmax(\overrightarrow{\rho(a_{i})})$ = [0.2677, 0.0915, 0.2613, 0.3795]

This indicates that the baker would choose option (iv) for the next move with
38% probability, an option which balances the baker’s final goal and personal
psychological needs (high conscientiousness).

Finally, we modify ($\alpha,\beta,\gamma$) to [0.8, 0.1, 0.1] and assume that
the baker’s character type vector is [0.2, -0.3, 0, -0.5, 0.8] which shows
high neuroticism (0.8), low agreeableness (-0.5). What we obtain is
$\rho(\overrightarrow{A})$ = [0.8007, 0.7652, -0.5229, -0.5032]. From this
what results is the following: $softmax(\overrightarrow{\rho(a_{i})})$ =
[0.3996, 0.3856, 0.1064, 0.1085]

This indicates that the probability of choosing (i) and (ii) is now about the
same. In this scenario the baker focuses more on his own character type. (ii)
shows complete incongruity with the bakery type, which indicates a complete
violation of the baker’s original final goal. Hence, at this point, the baker
is in a dilemma. It is worth noting that this state will lead to a
”breakthrough point”, and if the baker chooses (ii), it means that baker
chooses to change his final goal or conversational type. The consequence of
this is that the $Goals$, $ConvType$ and $Conv-prob$ should be changed in the
private state of information state. How to effect this in a formal way, we
leave to future work.

##  4 Conclusion

Character is a person’s stable attitude towards reality and it also affects
one’s performance in dialogue. Conversational type is, in one way or another,
since the early days of AI work on dialogue, one of the principal notions of
dialogue research. It reflects domain specific interaction, in particular the
move space given to the conversational participants. We have tried to show in
this paper that investigating the interaction of these two factors is
worthwhile. In particular, we present a method of the decision making process
for moves that combines character type and conversational type. We present a
mathematical model that combines these factors after assigning numerical
values to the various parameters that are involved and demonstrate by means of
an example how this works.

##  5 Future Work

In this paper, we have made a preliminary proposal concerning the modelling of
character types and their combination with conversational types. We aim to
refine this in future work in ways that include the following:

  * •

Wong (2018) gave a formal method to classify conversations into types. We
believe that under realistic conditions, there are often multiple
conversational types involved in a single conversation, which may involve
sequential transformations or overlapping phenomena.

  * •

In the approach sketched here, for classifying the conversational type we use
a probabilistic TTR. However, in practice this assessment can change as the
dialogue unfolds. We hope to develops methods that incorporate such dynamism.

  * •

Personality analysis based on the Big Five theory is robust, but inference
about each other’s character types is also in flux during conversations, and
examining the impact of the change process on our approach is worth looking
forward to future work.

  * •

Ginzburg et al. (2019) provided a categorical approach to the response to the
question. We hypothesize that the conversational type has the role of
delimiting the range of possible moves. We aim to characterize this
variability.

  * •

This article introduces the concept of move conformity, which is required for
automatic detection of research based on different types of dialogue in the
future work. This could be achieved by modifying an existing NLG evaluation
model (e.g. BLEU Papineni et al. (2002), ADEM Lowe et al. (2017)).

  * •

This paper discussed several cases in detail, but they are all constructed
examples, so fitting this model on actual conversations (e.g. the British
National Corpus) or scripted dialogues annotated for character types (e.g.
FriendQA Yang and Choi (2019)) with experimental predictions is desirable.

### Acknowledgments

This work was supported by an internship funded by the Institut Universitaire
de France, within Jonathan Ginzburg’s project Unifying Verbal and Non-verbal
Interaction. We also acknowledge the support of the French Investissements
d’Avenir-Labex EFL program (ANR-10-LABX-0083). Thanks to Prof. Ginzburg’s
patient guidance during the internship. Thanks also to three anonymous
reviewers for SemDial for their detailed and perceptive comments.

## References

  * Allen and Perrault (1980) James Allen and Ray Perrault. 1980.  Analyzing intention in utterances.  _Artificial Intelligence_ , 15:143–178.
  * Allwood (2000) Jens Allwood. 2000.  An activity based approach of pragmatics.  In Harry Bunt, editor, _Abduction, Belief and Context in Dialogue; Studies in Computational Pragmatics_. Amsterdam, John Benjamins.
  * Allwood et al. (2000) Jens Allwood, David Traum, and Kristiina Jokinen. 2000.  Cooperation, dialogue and ethics.  _International Journal of Human-Computer Studies_ , 53(6):871–914.
  * Asher et al. (2017) Nicholas Asher, Soumya Paul, and Antoine Venant. 2017.  Message exchange games in strategic contexts.  _Journal of Philosophical Logic_ , 46(4):355–404.
  * Bakhtin (2010) Mikhail Mikhalovich Bakhtin. 2010.  _Speech genres and other late essays_.  University of Texas Press.
  * Bono and Judge (2004) Joyce E Bono and Timothy A Judge. 2004.  Personality and transformational and transactional leadership: a meta-analysis.  _Journal of applied psychology_ , 89(5):901.
  * Burnett (2019) Heather Burnett. 2019.  Signalling games, sociolinguistic variation and the construction of style.  _Linguistics and Philosophy_ , 42(5):419–450.
  * Cohen and Perrault (1979) Philip Cohen and Ray Perrault. 1979.  Elements of a plan-based theory of speech acts.  _Cognitive Science_ , 3:177–212.
  * Cooper (2005) Robin Cooper. 2005.  Records and record types in semantic theory.  _Journal of Logic and Computation_ , 15(2):99–112.
  * Cooper et al. (2014) Robin Cooper, Simon Dobnik, Shalom Lappin, and Staffan Larsson. 2014.  A probabilistic rich type theory for semantic interpretation.  In _Proceedings of the EACL 2014 Workshop on Type Theory and Natural Language Semantics (TTNLS)_ , pages 72–79.
  * Costa Jr and McCrae (2008) Paul T Costa Jr and Robert R McCrae. 2008.  _The Revised NEO Personality Inventory (NEO-PI-R)._ Sage Publications, Inc.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Ginzburg (2012) Jonathan Ginzburg. 2012.  _The interactive stance_.  Oxford University Press.
  * Ginzburg et al. (2019) Jonathan Ginzburg, Zulipiye Yusupujiang, Chuyuan Li, Kexin Ren, and Paweł Łupkowski. 2019.  Characterizing the response space of questions: a corpus study for english and polish.  In _Proceedings of the 20th Annual SIGdial Meeting on Discourse and Dialogue_ , pages 320–330.
  * Goldberg (1992) Lewis R Goldberg. 1992.  The development of markers for the big-five factor structure.  _Psychological assessment_ , 4(1):26.
  * Hymes (1974) Dell Hymes. 1974.  Ways of speaking.  _Explorations in the ethnography of speaking_ , 1:433–451.
  * Jiang et al. (2019) Hang Jiang, Xianzhe Zhang, and Jinho D Choi. 2019.  Automatic text-based personality recognition on monologues and multiparty dialogues using attentive networks and contextual embeddings.  _arXiv preprint arXiv:1911.09304_.
  * Larsson (2002) Staffan Larsson. 2002.  _Issue-based dialogue management_.  Citeseer.
  * Levelt (1993) Willem JM Levelt. 1993.  _Speaking: From intention to articulation_ , volume 1.  MIT press.
  * Lowe et al. (2017) Ryan Lowe, Michael Noseworthy, Iulian V Serban, Nicolas Angelard-Gontier, Yoshua Bengio, and Joelle Pineau. 2017.  Towards an automatic turing test: Learning to evaluate dialogue responses.  _arXiv preprint arXiv:1708.07149_.
  * Mairesse et al. (2007) François Mairesse, Marilyn A Walker, Matthias R Mehl, and Roger K Moore. 2007\.  Using linguistic cues for the automatic recognition of personality in conversation and text.  _Journal of artificial intelligence research_ , 30:457–500.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311–318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
  * Pennebaker and King (1999) James W Pennebaker and Laura A King. 1999.  Linguistic styles: Language use as an individual difference.  _Journal of personality and social psychology_ , 77(6):1296.
  * Purver (2004) Matthew Richard John Purver. 2004.  _The theory and use of clarification requests in dialogue_.  Ph.D. thesis, University of London.
  * Riggio et al. (1988) Ronald E Riggio, Charles Salinas, and Joan Tucker. 1988.  Personality and deception ability.  _Personality and Individual Differences_ , 9(1):189–191.
  * See et al. (2019) Abigail See, Stephen Roller, Douwe Kiela, and Jason Weston. 2019.  What makes a good conversation? how controllable attributes affect human judgments.  _arXiv preprint arXiv:1902.08654_.
  * Sutskever et al. (2014) Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014.  Sequence to sequence learning with neural networks.  In _Advances in neural information processing systems_ , pages 3104–3112.
  * Watson and Clark (1992) David Watson and Lee Anna Clark. 1992.  On traits and temperament: General and specific factors of emotional experience and their relation to the five-factor model.  _Journal of personality_ , 60(2):441–476.
  * Wittgenstein (1953) Ludwig Wittgenstein. 1953.  Philosophical investigations. basil & blackwell.  _OxfordWittgensteinPhilosophical investigations Basil1953_.
  * Wong (2018) Kwong-Cheong Wong. 2018.  _Classifying Conversations_.  Ph.D. thesis, Paris Diderot University.
  * Wong and Ginzburg (2018) Kwong-Cheong Wong and Jonathan Ginzburg. 2018.  Conversational types: a topological perspective.
  * Yang and Choi (2019) Zhengzhe Yang and Jinho D Choi. 2019.  Friendsqa: Open-domain question answering on tv show transcripts.  In _Proceedings of the 20th Annual SIGdial Meeting on Discourse and Dialogue_ , pages 188–197.


# Privacy-Protecting COVID-19 Exposure Notification Based on Cluster
Events111This paper was presented at the _NIST Workshop on Challenges for
Digital Proximity Detection in Pandemics: Privacy, Accuracy, and Impact,
January 28 02021_.
Dates follow conventions of the Long Now Foundation.

Paul Syverson
U.S. Naval Research Laboratory
<EMAIL_ADDRESS>
###### Abstract

We provide a rough sketch of a simple system design for exposure notification
of COVID-19 infections based on copresence at cluster events—locations and
times where a threshold number of tested-positive (TP) individuals were
present. Unlike other designs, such as DP3T or the Apple-Google exposure-
notification system, this design does not track or notify based on detecting
direct proximity to TP individuals.

The design makes use of existing or in-development tests for COVID-19 that are
relatively cheap and return results in less than an hour, and that have high
specificity but may have lower sensitivity. It also uses readily available
location tracking for mobile phones and similar devices. It reports events at
which TP individuals were present but does not link events with individuals or
with other events in an individual’s history. Participating individuals are
notified of detected cluster events. They can then compare these locally to
their own location history. Detected cluster events can be publicized through
public channels. Thus, individuals not participating in the reporting system
can still be notified of exposure.

A proper security analysis is beyond the scope of this design sketch. We do,
however, discuss resistance to various adversaries and attacks on privacy as
well as false-reporting attacks.

The goal of this brief paper is to introduce the idea of, and contextual
motivation for, using mobile phone location data from COVID-19 tested-positive
(TP) individuals to identify cluster events and then to notify people of
potential exposure simply by notifying them of cluster events. A sketch of a
basic design to do this in a privacy-protecting manner is presented. We do not
discuss even high-level particulars of necessary associated system features.

Existing privacy-protecting exposure-notification systems for COVID-19
infection generally do their detection and notification based on detected
proximity to TP individuals [1, 21, 19]. Location information is typically not
recorded by such systems. DP3T intentionally “avoids collecting location data,
which is highly sensitive and very difficult to publish in a privacy-
preserving way” [21]. While SafePaths explores adding GPS location information
to proximity tracing [15], this is considered auxiliary to the primary task of
identifying individuals who have been in close proximity to TP infectious
individuals.

Deployed COVID-19 exposure-notification systems do employ location
information. For example, the National Health Service of the United Kingdom
(NHS) has set up a system whereby venues (pubs, hairdressers, village
libraries, etc.) in England and Wales are required to obtain and post QR codes
for patrons to scan when visiting. If the venue is later determined to be a
COVID-19 hotspot, it is uploaded to a list that patrons can download and check
against visited places scanned into their phones [14]. This is unlike our
approach in multiple respects. It only works for fixed locations, which are
locations of establishments of specific types. It requires participating
locations to create and post QR codes. It only works for locations that
individuals have scanned into their phones. And it identifies locations rather
than events (locations at times).

Safe2 [18] is a mobile phone app that combines self assessment information
about symptoms and proximity contact detection to provide a “Safe Score”
indicating risk of infection ranging from “Healthy” to “Confirmed”. It also
keeps track of location history, but shared in a privacy-protecting way
somewhat similar to what we suggest below. Based on visited locations and
contacts, an individual may be classified as a likely asymptomatic carrier.
Notifications will then be sent to others who have been detected to be in
close proximity to that individual, thus decreasing their Safe Scores.

The approaches and apps mentioned above by no means constitute a complete
list, even ignoring the dynamic state of introduction and development of new
apps. Nor do we provide more than a brief note of the features of the apps
that we do mention as most relevant to or contrasting with our approach. For
example, we have not otherwise mentioned PACT [17] or its incorporation in
SafePaths. Buchanen et al. have produced a survey and analysis of privacy-
preserving COVID-19 contact tracking that was relatively comprehensive at time
of writing [3]. Landau’s recent book provides an introduction to the
technology of contact tracing and its usefulness for public health, in which
she discusses efficacy, equity, and privacy [11].

For Safe2 and the other privacy-protecting systems cited above, close
proximity is determined by detected Bluetooth communication. Dehaye and
Reardon have identified three attacks on Bluetooth-based proximity detection
in the context of COVID-19 contact tracing apps [7]. The attacks require an
adversary capable of placing a software development kit (SDK) in a moderately
successful app, but Dehaye and Reardon argue that this is much easier than is
usually assumed. See the paper for specifics. The good thing is that we need
not accurately determine how hard such attacks are or how hard they are to
counter if our exposure notification system does not depend on phones
broadcasting proximity information. And specifics of COVID-19 infection
patterns and COVID-19 testing technology may permit simplifications of
privacy-protecting notifications based on presence at cluster events rather
than directly detecting proximity to TP individuals.

First, unlike common influenzas and other familiar diseases, COVID-19 appears
to have a high degree of clustering in its dispersion and to be spread more in
events where infected individuals spend time in close proximity to groups of
others. There are other dispersion clustering factors, such as whether
gatherings are indoors and adequacy of ventilation, and clustering also occurs
around some people who are individually linked to high number of infections.
But generally, gatherings play a significant role in infection rates, whether
or not they are exacerbated by other factors [10]. This includes both super-
spreader large gatherings for social or cultural events as well as more
moderate-sized gatherings [4].

Second, most tests for COVID-19 initially rolled out required specialized
equipment to evaluate collected samples, required days or more to return
results, were expensive, or all of the above. But analyses indicate that
faster, cheaper point-of-care tests can be more effective at identification of
infected individuals than more sensitive tests that are slower [13, 9]. And
U.S. Department of Health and Human Services in partnership with the the U.S.
Department of Defense is now providing rapid point-of-care tests to
communities across the United States [8]. Similarly, under the auspices of the
World Health Organization, a global partnership has planned to make 120
million rapid tests available in low- and middle-income countries [23].
Analyses of effectiveness focus on identification and notification of
infectious individuals. But coupled with dispersion patterns, another
advantage of cheap, point-of-care tests emerges.

“[G]iven the huge numbers associated with these clusters, targeting them would
be very effective in getting our transmission numbers down” [22]. Also,
identifying a cluster does not require that everyone who was already infected
at a particular event (location and time) has tested positive or even has been
tested at all. As long as a sufficient _number_ of TP individuals are
associated with a given event, it is not important to identify which
individuals were present, even pseudonymously, in order for the event to
constitute a cluster. Since cluster events are indicators of risk of infection
for all copresent at the event, informing individuals of those clustering
events at which they were present is sufficient to notify them of potential
exposure. And, individuals can make the determination of whether they were
present at a clustering event entirely locally by having their phones compare
clustering events about which they were notified with their location history.

Thus, we only need count the number of distinct TP individuals at an event to
identify it as a cluster event. Like other privacy protecting COVID-19
notification systems, we can make use of anonyms (ephemeral pseudo-random
identifiers) for each individual (where an individual is identified with the
individual’s phone) at a given time. These can be combined with location data
available to the phone, e.g, by GPS and other phone localization inputs, into
an ordered pair,
$(\textit{random\\_ID}_{(i,t)},\textit{location}({\textit{random\\_ID}_{(i,t)}},t)\,)$.

Phones do typically have automatic access to location data but do not
typically store location histories. Location histories are of course
frequently tracked by third parties, and apps to track location history are
readily available for the major mobile platforms. Also, privacy-protecting
tracking and storing of mobile device location data for personal use has been
studied since at least the mid-nineties [16]. As noted above, the Safe2 app
specifically stores and uses location history for COVID-19 exposure
notification. And though Safe2 relies on Bluetooth and GPS, GPS alone can be
effective at detecting useful COVID clustering information [20]. The specific
means of localization is not central to our approach whether GPS, WiFi,
Bluetooth, or other background signals (such as a scanned QR-code, as in the
NHS app) as long as it is decoupled from the reporting of location history. As
with other privacy-protecting aspects not novel in this design, we simply
assume a privacy-protecting location history system and consider particulars
out of scope for this paper.

If an individual tests positive, she submits such pairs for all times within a
critical period, typically covering the maximum past interval during which she
might have become infected. (Note that backward tracing of events appears to
be more effective than forward tracing [10]. Thus it is important to trace
back to the time she might have become infected not merely the shorter period
back to the time she might have become infectious.) Submission can be to a
decentralized repository or to a centralized repository as long as the act of
submission does not reveal association of submitted pairs. Given the limited
goals of this paper, we simply assume such an association-protecting
submission system. As an over-simple, somewhat concrete example of such a
system, assume a centralized repository with submission protected by one or
more mixes [6] such that the output of the mixes is an unordered collection of
all such pairs submitted during a given mix-system firing interval.

If notification of the results of a point-of-care test as well as notification
of exposure are automated in a COVID-19 exposure notification app, and if
adequate privacy protections are incorporated, then individuals have self-
interested incentive to use the app even if its primary goal is to control
spread. Nonetheless, as we shall see, the system can provide useful
notification of exposure even to nonparticipants without an installed app.

#### Malicious reporting of positive tests

Another potential advantage of a cluster-event based approach is that, even
without limiting TP reporting to authorized individuals, it provides automatic
counters to the possibility that “people may falsely report they have been
infected to cause mischief or to keep people home in order to shut down school
or even to disrupt an election” [5]. An individual falsely reporting a
positive test cannot easily create such a result because they are unlikely to
be the one to transition a location and time across the threshold of counting
as a cluster event. And they cannot report at all for a location and time
unless they were present at that event. More significant coordinated
copresence or system hacking of location reporting would be required. And if
coordinated copresence is the mechanism, then it may be that innocents who are
notified because they were present at that cluster event _should_ seek further
testing and curtailing of social interactions.

Our cluster-event design thus automatically prevents, e.g., a student who is
worried about his exam next week and anonymously reports a positive test from
thereby causing his school to shut down or his whole chemistry class to be
forced into quarantine. A fan of one sports team cannot force a rival team
into quarantine, etc.

A more substantial adversary, such as a nation-state, might be able to hack
location histories for a phone, create sybils of phones at a location, etc.
This could support an attack at a larger scale to disrupt a critical operation
or degrade the availability of essential infrastructure or emergency
personnel. Since the proposed design is meant to leverage rapid, point-of-care
tests, it is also conducive to requiring input from authorized testing
personnel at point of care to permit reporting a positive test. For example,
an authorized TP code tied to a unique anonym bound to the identity of the
mobile phone present when an individual is given the test could be sent at the
same time test results are comunicated to that phone, possibly even after the
individual has left the point of care. And reporting of recent location
history for that phone would require this authorization. Specifics of what
capabilities such more significant adversaries might have and how all this
would work is beyond the scope of this paper. We simply note here that the
cluster-event approach remains compatible with requiring authorized parties to
confirm TP status in order for reporting to occur.

Obviously there is a tension between authorization mitigations against more
powerful false reporting attacks and the ease and effectiveness of
participation in the reporting and notification system. For example, without
an authorization requirement, simple tests requiring no expertise to
administer or evaluate can be made available and incorporated in the exposure
notification system without an authorized-testing-personnel bottleneck. And a
powerful adversary might include many other elements beyond our scope, such as
compromising trusted authorization individuals, or the systems used for
authorization, or the physical tests themselves. Lesser adversaries described
above are still countered by the proposed system even without the
authorization component. This is another advantage over any system that
inherently has a trusted-authorization bottleneck.

#### Cluster event criteria

Submitted anonym pairs can be clustered into events according to latest
understanding of what constitutes sufficient proximity in space and time to
indicate risk of exposure likely enough to merit notification. Such clustering
can be based simply on the number of copresent TP individuals. Further privacy
preserving measures exist that would only reveal an uploaded location and time
if a cluster event occurs there. Indeed there are deployed systems for large-
scale gathering of data and release of associated statistics with guarantees
of differential privacy [2].

With small thresholds of cluster events, however, even if the system only
reveals locations if there is a cluster event, there may be a tension between
revealing cluster events in a differentially private way while also not
significantly affecting the rate of false negatives about clusters. This may
not be a significant limitation, however. Without differential privacy, in
principle an adversary could submit a false positive result to enhance
tracking of a TP individual. But this is not trivial. If, for example, the
adversary had a device that could report from the individual’s location,
easier tracking is available. So we would need to assuming knowledge of
suspected trajectories followed by the targeted TP individual, and a hack of
the location reporting system that doesn’t also make more straightforward
tracking possible. In that case, the adversary could report TP locations and
times along the suspected route to look for instances where the adversary’s
report caused a cluster event. If so, and ignoring the entrance of other TP
individuals causing the transition, the target’s presence could have caused
locations-times to be at one less than the cluster-reporting threshold. These
issues are also beyond the scope of this paper.

Exogenous information, if available, could affect clustering classification.
For example, a location may have been separately identified as that of a
salon, restaurant, house of worship, etc. This can affect what constitutes a
notification-worthy cluster: two TP individuals copresent on a street corner
in a city may be too low a threshold to classify this as a cluster event
meriting notification, two TP individuals copresent in a poorly ventilated
small salon might be a reasonable threshold, however.

Conversely, cluster locations that are identified simply by the number of
copresent TP individuals but otherwise unknown and that are also responsible
for large or repeated cluster events might be flagged for public health
officials to investigate what is at that location and what sort of people are
going there for what purposes.

On the other hand, unlike direct contact detecting approaches, since
notification is only of cluster events, this approach cannot detect and
therefore cannot notify people if they are exposed to a single copresent
individual. As noted above, spread of COVID-19 is primarily through such
clustering events, however. And this approach will also provide notification
in a circumstance where an individual might never have come in close contact
to anyone who tested positive (who is also participating in the
detection/notification system) but was present at an event where multiple TP
individuals were detected. So it not clear which approach is more likely to
result in notification. Further, individuals from communities which have
historically experienced disproportionate negative impacts of public health
crises might be disinclined to participate in a contact tracing system [12].
Even if a non-participant, they might nonetheless self-interestedly check a
public website for cluster events and act if they notice a significant cluster
at an event where they (or loved ones) were known to be present. Recall that
in any case, the primary goal is to produce notifications that lead to
significant reduction in spread rather than to guarantee an individual of
notification upon any exposure.

Relatedly, the approach allows different criteria for distance in making a
clustering determination. As an oversimplified illustration, suppose a 2000
$m^{2}$ area is comprised of dozens of TP individuals where all individuals on
the perimeter are within 2 meters of another TP individual for several
minutes. The relevant cluster event for notification should probably cover the
entire area at that time even if portions of the center are 10 meters from the
nearest TP individual—unless there is specific additional information that
would exclude particular subareas. It may be likewise reasonable to include a
larger area than just 2 meters beyond the perimeter for such a large cluster.

Another potential limitation of this approach is that it identifies a cluster
as at one (possibly extended) location in a relatively brief time interval. It
does not directly have a means to distinguish extended presence at a location
of multiple TP individuals with few comings and goings over a period of hours
(for example at a social gathering) versus a roughly persistent total of TP
individuals resulting from regular turnover (for example, at a transit hub or
commercial service establishment). This could matter for time of exposure to a
particular individual as an indicator of infection risk likelihood. On the
other hand, whether a notified individual learns of exposure at multiple
cluster events at the same location based on either of these scenarios may not
matter for the recommended course of action. Notified individuals are also
more likely to know the circumstances of a particular succession of notified
cluster events. And if they know the circumstances, they may be more prepared
to notify others personally known to be associated with those circumstances,
whether or not those others participate in or monitor the notification system.

Relatedly, there is no distinction made by the basic system of multiple
exposures at a succession of locations versus prolonged exposure, e.g., during
a shared ride in a car or mass transit vehicle. Again, it might not make a
practical difference for purposes of the system whether this is identified as
a single prolonged cluster event or succession of many shorter ones.

### High-level Design Summary

  1. 1.

Individual tests positive for COVID-19 and enters this in the notification app
on their phone (alternatively notification of a positive result might be
automated in a phone app and/or require input from a trusted testing
official).

  2. 2.

Individual’s phone app prepares a historical list of locations and times since
the beginning of the critical period based on time of testing, each paired
with a different random identifier.

  3. 3.

Phone submits the list of pairs through a privacy preserving system.

  4. 4.

System receiving these pairs from all reporting phones clusters them into
events at which multiple TP individuals are present.

  5. 5.

System pushes notifications of all cluster events to participants’ phones
and/or posts these to a publicly accessible location, e.g., a website.

  6. 6.

Notified individuals learn of exposures at cluster events.

The purpose of this brief paper is to introduce a novel concept of COVID-19
exposure notification based on creation of clustering events of which
individuals are notified. We have simply assumed adequately privacy preserving
systems for data gathering, processing, and publishing. And there are existing
systems that make this assumption plausible, some of which we have cited.
Details matter, however, to the security, scalability, practicality, and
usability of the overall system. Some of the details we have ignored include
how submission of pairs unlinks submitting individuals from locations and
histories of locations, the number of submitting individuals (in a region,
during an interval), resistance to de-anonymization of location histories from
plausible travel paths given a collection of location-time pairs, how long
various data and information are held, etc. Clustering algorithms and
clustering criteria are central to the cost, basic viability, and properties
provided by this approach, but we have simply assumed these will be selected
to function as needed. Cognizant of these assumptions, we have nonetheless
identified a number of high-level properties of this approach, which we now
summarize.

### Design Features

  * •

Does not depend on TP individual’s phone to have Bluetooth turned on in order
to provide inputs.

  * •

Does not depend on potentially exposed individuals to have Bluetooth on in
order for system to find indications of exposure.

  * •

Does not depend on direct physical interaction (Bluetooth or otherwise)
between phones of TP individuals and exposed individuals.

  * •

Exposure contact distance parameters do not depend on limitations of Bluetooth
communication parameters.

  * •

Does depend on availability of phone location history of reporting TP
individuals.

  * •

Does depend on phone location history (or human memory or…) for individuals to
effectively make use of cluster event notifications or postings.

  * •

Does reveal locations and times of cluster events, even small ones, which may
identify particular households where there are multiple infections or that
some sort of meeting took place at an otherwise nondescript location.

  * •

Leverages fast test results, even if tests have only modest sensitivity.

  * •

Depends on approximate numbers of TP individuals in cluster events rather than
specific contacts with TP individuals.

  * •

Cannot detect exposure to TP individuals outside of cluster events.

  * •

Can notify of exposure even without close contact to a TP individual.

  * •

Can notify of exposure even without participation as reporting individual.

  * •

Counters false TP reporting _and_ tolerates false TP reporting.

  * •

Compatible with using trusted authorizations to counter false TP reporting by
stronger adversaries.

## Acknowledgements

Thanks to Aaron Johnson, Rob Jansen, Matt Traudt, and Ryan Wails for helpful
discussions, and to Paul-Olivier Dehaye and Susan Landau for multiple helpful
comments and discussions.

## References

  * [1] Privacy-preserving contact tracing.  https://covid19.apple.com/contacttracing, 02020.
  * [2] Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld.  Prochlo: Strong privacy for analytics in the crowd.  In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP ’17), pages 441–459, 02017.
  * [3] William J Buchanan, Muhammad Ali Imran, Masood Ur-Rehman, Lei Zhang, Qammer H. Abbasi, Christos Chrysoulas, David Haynes, Nikolaos Pitropakis, and Pavlos Papadopoulos.  Review and critical analysis of privacy-preserving infection tracking and contact tracing.  Frontiers in Communications and Networks, December 8 02020.
  * [4] Muge Cevik, Julia Marcus, Caroline Buckee, and Tara Smith.  SARS-CoV-2 transmission dynamics should inform policy.  https://ssrn.com/abstract=3692807, September 14 02020.
  * [5] Lorrie Faith Cranor.  Digital contact tracing may protect privacy, but it is unlikely to stop the pandemic.  Communications of the ACM, 63(11):22–24, November 02020.
  * [6] George Danezis, Claudia Diaz, and Paul Syverson.  Anonymous communication.  In Burton Rosenberg, editor, Handbook of Financial Cryptography. CRC Press, 02010.
  * [7] Paul-Olivier Dehaye and Joel Reardon.  Proximity tracing in an ecosystem of surveillance capitalism.  In Proc. 19th Workshop on Privacy in the Electronic Society, WPES’20, pages 191–203. ACM, November 9 02020.
  * [8] COVID-19 rapid point-of-care test distribution.
https://www.hhs.gov/coronavirus/testing/rapid-test-distribution/index.html,
October 7 02020.

  * [9] Lee Kennedy-Shaffer, Michael Baym, and William Hanage.  Perfect as the enemy of the good: Using low-sensitivity tests to mitigate SARS-CoV-2 outbreaks.  https://dash.harvard.edu/handle/1/37363184, 02020.
  * [10] Sadamori Kojaku, Laurent Hébert-Dufresne, Enys Mones, Sune Lehmann, and Yong-Yeol Ahn.  The effectiveness of backward contact tracing in networks.  https://arxiv.org/abs/2005.02362, May 5 02020.
  * [11] Susan Landau.  People Count: Contact-Tracing Apps and Public Health.  MIT Press, April 02021.
  * [12] Susan Landau, Christy E. Lopez, and Laura Moy.  The importance of equity in contact tracing.
https://www.lawfareblog.com/importance-equity-contact-tracing,
May 1 02020.

  * [13] Daniel B. Larremore, Bryan Wilder, Evan Lester, Soraya Shehata, James M. Burke, James A. Hay, Milind Tambe, Michael J. Mina, and Roy Parker.  Test sensitivity is secondary to frequency and turnaround time for COVID-19 surveillance.  medRxiv, 02020.  https://www.medrxiv.org/content/early/2020/09/08/2020.06.22.20136309.full.pdf.
  * [14] Create a coronavirus NHS QR code for your venue.  https://www.gov.uk/create-coronavirus-qr-poster, 02020.
  * [15] Ramesh Raskar, Abhishek Singh, and Sam Zimmerman.  Adding Location Context to Apple/Google Exposure Notification Bluetooth API: MIT SafePaths Encryption Proposals for GPS + Bluetooth, version 0.1.  https://docs.google.com/document/d/1uTjdUetEEtnwN-6˙iw3HTZOdAd0kKsK7GR1YbdS10Ss/edit, April 26 02020.
  * [16] Michael G. Reed, Paul F. Syverson, and David M. Goldschlag.  Protocols using anonymous connections: Mobile applications.  In Security Protocols: 5th International Workshop, Paris France, April 7-9 1997, Proceedings, pages 13–23. Springer-Verlag, LNCS 1361, 01998\.
  * [17] Ronald L. Rivest, Daniel J. Weitzner, Louise C. Ivers, Israel Soibelman, and Marc A. Zissman.  PACT: Private automated contact tracing, mission and approach.
https://pact.mit.edu/wp-content/uploads/2020/05/PACT-Mission-and-
Approach-2020-05-19-.pdf, May 19 02020.

  * [18] Safe2: Frequently asked questions.  https://safe2.org/faq/, 02020.
  * [19] SafePaths Alliance.  Private kit: Safe paths; privacy-by-design.
https://safepaths.mit.edu, 02020.

  * [20] Matteo Serafino, Higor S. Monteiro, Shaojun Luo, Saulo D. S. Reis, Carles Igual, Antonio S. Lima Neto, Matías Travizano, José S. Andrade, and Hernán A. Makse.  Superspreading k-cores at the center of COVID-19 pandemic persistence.  medRxiv, 02020.
  * [21] Carmela Troncoso, Mathias Payer, Jean-Pierre Hubaux, Marcel Salathé, James Larus, Edouard Bugnion, Wouter Lueks, Theresa Stadler, Apostolos Pyrgelis, Daniele Antonioli, Ludovic Barman, Sylvain Chatel, Kenneth Paterson, Srdjan Čapkun, David Basin, Jan Beutel, Dennis Jackson, Marc Roeschlin, Patrick Leu, Bart Preneel, Nigel Smart, Aysajan Abidin, Seda Gürses, Michael Veale, Cas Cremers, Michael Backes, Nils Ole Tippenhauer, Reuben Binns, Ciro Cattuto, Alain Barrat, Dario Fiore, Manuel Barbosa, Rui Oliveira, and José Pereira.  Decentralized privacy-preserving proximity tracing.  https://arxiv.org/abs/2005.12273, May 25 02020.
  * [22] Zeynep Tufekci.  This overlooked variable is the key to the pandemic: It’s not R.  The Atlantic, September 30 02020.
https://www.theatlantic.com/health/archive/2020/09/k-overlooked-variable-
driving-pandemic/616548/.

  * [23] Global partnership to make available 120 million affordable, quality COVID-19 rapid tests for low- and middle-income countries.
https://www.who.int/news/item/28-09-2020-global-partnership-to-make-
available-120- million-affordable-quality-covid-19-rapid-tests-for- low--and-
middle-income-countries, September 28 02020.