(cvpr) Package cvpr Warning: Package ‘hyperref’ is not loaded, but highly
recommended for camera-ready version

# Analyzing Participants’ Engagement during Online Meetings Using Unsupervised
Remote Photoplethysmography with Behavioral Features

Alexander Vedernikov1, Zhaodong Sun1, Virpi-liisa Kykyri2,
Mikko Pohjola2, Miriam Nokia2, and Xiaobai Li1,3
1Center for Machine Vision and Signal Analysis, University of Oulu, Finland
2Department of Psychology, University of Jyväskylä, Finland
3State Key Laboratory of Blockchain and Data Security, Zhejiang University,
China
{aleksandr.vedernikov<EMAIL_ADDRESS><EMAIL_ADDRESS>
{virpi-liisa.kykyri, mikko.j.pohjola<EMAIL_ADDRESS>
###### Abstract

Engagement measurement finds application in healthcare, education,
advertisement, and services. The use of physiological and behavioral features
is viable, but the impracticality of traditional physiological measurement
arises due to the need for contact sensors. We demonstrate the feasibility of
unsupervised remote photoplethysmography (rPPG) as an alternative for contact
sensors in deriving heart rate variability (HRV) features, then fusing these
with behavioral features to measure engagement in online group meetings.
Firstly, a unique Engagement Dataset of online interactions among social
workers is collected with granular engagement labels, offering insight into
virtual meeting dynamics. Secondly, a pre-trained rPPG model is customized to
reconstruct accurate rPPG signals from video meetings in an unsupervised
manner, enabling the calculation of HRV features. Thirdly, the feasibility of
estimating engagement from HRV features using short observation windows, with
a notable enhancement when using longer observation windows of two to four
minutes, is demonstrated. Fourthly, the effectiveness of behavioral cues is
evaluated and fused with physiological data, which further enhances engagement
estimation performance. An accuracy of 94% is achieved when only HRV features
are used, eliminating the need for contact sensors or ground truth signals.
The incorporation of behavioral cues raises the accuracy to 96%. Facial video
analysis offers precise engagement measurement, beneficial for future
applications.

##  1 Introduction

The rapid transition to online communication underlines the importance of
engagement analysis in virtual meetings. With the absence of physical cues and
direct interaction between individuals, assessing engagement becomes more
challenging. Nevertheless, estimating engagement during these interactions
offers key insights into participant behavior, group dynamics, and individual
input, helping meeting organizers promote effective collaboration.

Figure 1: A large Engagement Dataset of realistic online meetings. Facial
videos and cPPG were recorded.

Engagement analysis in virtual meetings often relies on facial and body
language recognition [11, 23], although they can’t gauge direct physiological
responses like heart rate variability (HRV), which is difficult for
individuals to fake [45]. Electrocardiography (ECG) would be ideal but is
limited by its need for direct contact. In contrast, remote
photoplethysmography (rPPG), a computer vision-based technique, assesses
cardiac activity through facial color changes. This makes it suitable for
online engagement estimation as it obviates the need for direct contact and
specialized equipment [37]. Using unsupervised deep learning for rPPG signal
extraction eliminates the need for ground truth signals, labeled datasets, and
expert annotations, enhancing flexibility in engagement estimation.

This article pioneers the application of unsupervised rPPG measurement
technology in estimating engagement during online meetings. It also proposes
an enhancement in engagement estimation by integrating behavioral cues such as
facial expression and motion. This study discusses potential impediments
affecting the performance of rPPG in engagement analysis. A significant
influence on engagement estimation performance arises from the size of the
observation window employed for calculating HRV features from the obtained
rPPG signal. Moreover, a Engagement Dataset of online group meetings (captured
in real-world scenarios) among social workers is collected (Fig. 1), the first
to explore engagement levels in group interactions, especially with many
participants. It contains 1.5-hour videos for in-depth engagement analysis,
unveiling evolving interactions and gradual shifts in group dynamics, and
incorporates heart rate (HR) data from contact PPG (cPPG), a feature absent in
public datasets. By using a continuous engagement range of -10 to +10, the
Engagement Dataset captures nuances that tend to be neglected in other
datasets [19, 24, 27]. The analysis reveals that participant engagement is
linked to work effectiveness and mitigates job stress, underlining the study’s
practical value.

##  2 Related work

Automated engagement analysis research, initiated by Whitehill _et al_. [47]
in 2014, showcased machine learning’s capacity to estimate engagement with
human-like precision. Subsequent studies explored a wide range of applications
[26], including education [39], social media [16], news [20], human-robot [38]
and human-human interaction [10], consumer engagement [16], healthcare [43],
games [12], and film viewing analysis [8]. These studies explored behavioral
features like facial expressions [18], eye gaze [13], and body gestures [25].
There were studies that utilized physiological features, _e.g_., [41] used
features extracted from electroencephalogram (EEG) signals. In addition,
studies also analyzed modalities reliant solely on text [5], reaction time
[35], and response accuracy [35]. Rather than using a single modality,
scientists have investigated multi-modality fusion methods merging facial
expression-related features with speech/audio [22], head and body
pose/gestures/motions [36], physiological signals (such as
electroencephalographic - EEG activity [3], thermal signals [17], and
electrodermal activity - EDA [15]), game events [36], mouse behavior [50], and
contextual information [4]. Past research on engagement estimation is robust,
but fails to leverage the improvements rPPG data can provide. Notably, rPPG
technology has been applied in affective computing, showing promise in
assessing emotional states such as depression [9], stress [37], and
embarrassment [48], indicating unexploited potential for engagement analysis.

Over the past decade, only one study in 2016 by Monkaresi _et al_. [34]
explored HR for engagement estimation, but it faced major constraints.
Firstly, they relied on contact ECG sensors for HR, impractical in real use.
Our approach, however, uses a non-intrusive method, eliminating contact
sensors. Secondly, the video methods of that time [21] confined their research
to lab data, suffering in real HR detection scenarios. Conversely, our method
is tested and effective in real-life conditions. Moreover, using only seven
basic HR statistical features, they failed to fully exploit HR signals’
potential, leading to a high clinical error rate, as the authors acknowledged.
Their experiments showed that HR signals were less effective than facial
expressions in estimating engagement, likely due to unreliable cardiac
information. HRV features, strongly linked to mental states [30], offer
potential as efficient engagement indicators demanding more research, driving
this work’s innovative approach to physiological signals.

As engagement estimation methods advanced, multiple datasets were created.
Real-world e-learning engagement was first examined by the DAiSEE dataset [19]
in 2016. The horizons of student engagement analysis in educational games were
broadened by the Multimodal Affective State Recognition Dataset [36]. Using
the MHHRI dataset [10], engagement in dyadic human and triadic human-human-
robot contexts was explored. In 2017, UE-HRI dataset [7] further expanded the
scope of human-robot interaction and centered around interactions with the
robot Pepper. In the domain of e-learning, the EngageWild dataset [24] and
VRESEE datasets [40] delved deep into students’ engagement patterns. YouTube
gaming videos and facial engagement modalities were uniquely integrated in the
FaceEngage dataset [12]. A predictive direction in the field was signified by
the PAFE dataset [27] in 2022 and the EngageNet dataset [42] in 2023, both
utilizing different contexts. Primarily, all mentioned datasets offer only
visual modality for engagement analysis, with just two exceptions: the MHHRI
dataset [10] includes data from audio, video, depth, electrodermal activity
(EDA), temperature, and 3-axis wrist acceleration, while the UE-HRI dataset
[7] delivers information from a microphone array, cameras, depth sensors,
sonars, lasers, and user feedback captured through the robot’s touchscreen.
The lack of cPPG data in public resources for rPPG engagement methods
underlines the necessity for new datasets and unsupervised approaches.

This paper introduces the application of unsupervised deep learning for
calculating rPPG signals, an unexplored modality in previous automated
engagement analyses, emphasizing its practical, non-contact, and non-intrusive
nature. Furthermore, various behavioral feature sets are also evaluated and
fused with physiological features to further boost the performance. The work
is established on a novel self-collected Engagement Dataset, capturing real-
world online video meetings of social workers with consultant therapists for
the purpose of reducing work-related stress. The Engagement Dataset
construction, the proposed method framework, and experimental results are
explained in the following sections.

##  3 Dataset construction

Figure 2: The diagram depicts engagement estimation based on heart rate
variability (HRV) and behavioral features. HRV features are calculated from
reconstructed rPPG signals, and behavioral features are computed using the
OpenFace library [6]. Feature-level multimodality fusion is employed, followed
by a classifier.

###  3.1 Data collection

The Engagement Dataset, which contains facial videos, cPPG data, and
engagement annotations, was collected (Tab. 1). The Engagement Dataset
comprises recordings from group online video meetings. Serving as a reflection
of participants’ everyday work, each online video meeting was organized using
the Zoom platform and involved the participation of seven to nine individuals
with one consultant. These participants were social services employees working
with individuals facing mental health challenges and substance abuse issues.
Prior to each session, participants were given detailed instructions on how to
set up their recording environment. To stream and record participants’ facial
videos during online meetings, webcams were installed, and OBS Studio was
used. Throughout the sessions, a research assistant provided online guidance
using Zoom Breakout Rooms. Participants were encouraged to freely express
themselves and move, as long as their faces remained visible in the videos.
The cPPG signals were captured using the Beurer 80 pulse oximeter. Following
each online video meeting, the facial videos and cPPG signals were
synchronized based on their timestamps.

Engagement labels | [-10, 10], 2 labels/second
---|---
Engagement classes | 3 (Low / Middle / High)
Participants (male/female) | 25 (3/22)
Consultants (male/female) | 2 (1/1)
Video recordings | 109
cPPG data | 106
Average duration | 1 hr 23 min 58 sec
Total length | 153 hours
Table 1: Engagement Dataset statistics and properties.

###  3.2 Data annotation

Psychology students worked as research assistants to perform engagement
annotation based on the observed behavior of the target subject from face
video. DARMA, a continuous measurement system, was used for engagement
annotation. It synchronizes media playback and continuous recording of
observational measurement conducted with a computer joystick at a sampling
rate of 20Hz. The DARMA software provided a continuous coding time series
consisting of two values per second [28], with 10 (“High Engagement”) and -10
(“Low Engagement”). Research assistants underwent training to familiarize
themselves with distinct engagement levels before starting the coding. Inter-
rater reliability in control sessions was good (correlation coefficient over
0.8).

The scale of -10 to +10 facilitated a detailed understanding of engagement,
allowing for robust and nuanced annotations. This range was chosen over a
binary or three-point scale because human emotional states and levels of
engagement are continuous and nuanced. The chosen range captures these nuances
by providing a more granular scale. It is broad enough to encompass the
extreme ends of the engagement spectrum while being fine-grained enough to
account for slight variations within these extremes. Additionally, this
continuous scale can better account for individual differences in engagement
levels, allowing for the representation of each subject’s unique engagement
signature.

###  3.3 Data statistics and properties

The Engagement Dataset comprises 24 recorded group online video meetings, each
lasting approximately 1.5 hours. The Engagement Dataset contains two
modalities, namely facial video recordings and cPPG signals. Each online video
meeting involved between seven to nine participants and one consultant. The
resolution of 1920 × 1080 and the frame rate of 60 fps were recommended to
optimize video quality, although variations were observed due to different
cameras and recording environments. The Engagement Dataset contains several
unique properties as opposed to previous datasets studying engagement. 1)
Duration of data. With 1.5-hour videos compared to shorter public clips, the
Engagement Dataset enables in-depth engagement analysis, uncovering evolving
interactions, gradual shifts in interactions, and group dynamics. 2) Group
dynamics. Unlike earlier datasets, the Engagement Dataset involves more
participants per session, amplifying group interaction complexities for better
engagement analysis and enhancing group dynamic insights. 3) Recorded cPPG
signals. The presence of cPPG signals in the Engagement Dataset, not presented
in other datasets, underscores its unique importance in advancing engagement
estimation. 4) Granular annotation. The Engagement Dataset uniquely adopts a
-10 to +10 range of engagement, emphasizing the fluidity of human responses.
Such a spectrum effectively captures engagement nuances often overlooked in
other datasets. 5) Real-world setting. Rooted in real-world scenarios, the
Engagement Dataset showcases authentic online meetings of social service
employees. Unlike other datasets in simulated and well-controlled
environments, the Engagement Dataset promises true engagement data pertinent
to real-world situations.

##  4 Method

###  4.1 rPPG curves reconstruction from facial videos

The proposed method is illustrated in Fig. 2. The original videos are pre-
processed to extract frames and acquire facial landmarks using the OpenFace
library [6]. This tool effectively addresses issues related to head motion,
providing precise tracking of facial landmarks. The detected facial landmarks
are employed to determine regions of interest (ROI) on exposed skin areas. The
faces are cropped and then resized to dimensions of 128 × 128, preparing them
for input into the unsupervised Contrast-Phys model [44], a computer vision-
based technique, for the subsequent rPPG curves reconstruction. The Contrast-
Phys approach is based on the principle where the utilization of a 3DCNN model
allows the derivation of multiple rPPG signals from distinct spatiotemporal
locations within each video. Two videos, randomly selected from the Engagement
Dataset, constitute the input of Contrast-Phys. One video yields
spatiotemporal rPPG (ST-rPPG) block $P$, rPPG samples $[p_{1},\dots,p_{N}]$,
and associated power spectrum densities (PSDs) $[f_{1},\dots,f_{N}]$. The
other video provides ST-rPPG block $P^{\prime}$, rPPG samples
$[p^{\prime}_{1},\dots,p^{\prime}_{N}]$, and corresponding PSDs
$[f^{\prime}_{1},\dots,f^{\prime}_{N}]$, following the same procedure. The
contrastive loss pulls together PSDs from the same video while pushing apart
PSDs from distinct ones. Contrast-Phys implies that using rPPG spatiotemporal
similarity, the PSDs from the same ST-rPPG block should resemble each other as
follows $\text{PSD}\big{\\{}P(t_{1}\to t_{1}+\Delta
t,h_{1},w_{1})\big{\\}}\approx\text{PSD}\big{\\{}P(t_{2}\to t_{2}+\Delta
t,h_{2},w_{2})\big{\\}}\implies f_{i}\approx f_{j},i\neq j$ and
$\text{PSD}\big{\\{}P^{\prime}(t_{1}\to t_{1}+\Delta
t,h_{1},w_{1})\big{\\}}\approx\text{PSD}\big{\\{}P^{\prime}(t_{2}\to
t_{2}+\Delta t,h_{2},w_{2})\big{\\}}\implies f^{\prime}_{i}\approx
f^{\prime}_{j},i\neq j$. Subsequently, to bring together PSDs (positive pairs)
from the same video, the mean squared error is suggested to be utilized as the
loss function. When normalized based on the total count of positive pairs, the
positive loss term is:

$L_{p}=\sum_{i=1}^{N}\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{N}\big{(}\parallel f_{i}-f_{j}\parallel^{2}+\parallel
f^{\prime}_{i}-f^{\prime}_{j}\parallel^{2}\big{)}/\big{(}2N(N-1)\big{)}$ (1)

On the other hand, the cross-video rPPG dissimilarity suggests that the PSDs
resulting from spatiotemporal sampling of two separate ST-rPPG blocks will be
distinct. This attribute for the two input videos is described as
$\text{PSD}\big{\\{}P(t_{1}\to t_{1}+\Delta
t,h_{1},w_{1})\big{\\}}\neq\text{PSD}\big{\\{}P^{\prime}(t_{2}\to t_{2}+\Delta
t,h_{2},w_{2})\big{\\}}\implies f_{i}\neq f^{\prime}_{j}$. Next, the task of
distancing PSDs (negative pairs) from two different videos is achieved when
the negative mean squared error is used as the loss function. Then, the
overall quantity of negative pairs is employed to normalize the negative loss
term:

$L_{n}=-\sum_{i=1}^{N}\sum_{j=1}^{N}\parallel
f_{i}-f^{\prime}_{j}\parallel^{2}/N^{2}$ (2)

Finally, the overall loss function combines both positive and negative loss
terms: $L=L_{p}+L_{n}$.

The model is pre-trained on the Oulu Bio-Face database [29]. This approach
enables the reconstruction of rPPG signals in any recorded facial video,
eliminating the need for ground truth data in the future.

###  4.2 Definition of observation window for HRV and behavioral features

The -10 to +10 engagement scale is divided into three classes - Low, Medium,
and High engagement - through a process designed to simplify the complexity of
engagement analysis while retaining a significant level of detail. This
triadic classification approach provides a balance between the -10 to +10
scale’s granularity and a binary scale’s simplicity, serving as a practical
and efficient method for multi-classifying engagement levels. In High
engagement (Score: 10), the participant is either speaking, attempting to take
a turn, speaking over someone else, or, as a listener, actively showing
engagement through minimal vocalizations (such as ’mmm’), nods, and/or facial
expressions. In Medium engagement (Score: 0), the participant either gazes at
the speaker and appears to be listening, or gazes away while still seeming
attentive. Finally, in the Low engagement (Score: -10), the participant gazes
away or has their eyes closed, appearing not to follow the conversation,
possibly engaging in side activities like turning away or opening emails. The
process of converting continuous engagement labels into three classes and
definition of observation windows for HRV and behavioral features (BF) is
detailed below.

Figure 3: Observation windows concept for extracting BF and HRV features in
engagement analysis.

A 5-seconds time period was chosen for detecting intervals of stable
engagement. Reliability risks arise from short, context-lacking clips.
Assessing longer clips is more complex due to mixed engagement levels.
Therefore, video recordings were partitioned into 5-seconds intervals, and the
standard deviations of engagement were computed for each interval. The median
value of calculated standard deviations across the collected Engagement
Dataset was subsequently estimated. This median served as a threshold for
filtering out 5-seconds intervals with higher engagement standard deviations.
This process excluded unstable intervals with significant engagement
fluctuations. The engagement values obtained from the filtered intervals were
classified as follows: -10 to 0 as ’Low engagement’, 0 to 5 as ’Medium
engagement’, and 5 to 10 as ’High engagement’. Example of engagement data of a
specific participant in a particular video meeting after filtering process is
shown in Fig. 6 (see supplementary material). After the filtering process, the
distribution of the samples was as follows: 4001 samples were categorized as
’Low Engagement’, 23069 as ’Medium Engagement’, and 8320 as ’High Engagement’.
Next, the midpoint of each 5-seconds filtered interval becomes the center of
an HRV and behavioral observation window (Fig. 3). Subsequently, HRV features
are computed with a 60-seconds observation window that requires a 30-seconds
step in both directions, while BF is derived using a 2-seconds observation
window following similar logic.

###  4.3 Feature extraction

HRV features. Reconstructed rPPG signals were processed using the Neurokit2
library [32] to identify systolic peaks. This allowed for inter-beat intervals
(IBIs) calculation, yielding HRV features. These included three Poincaré plot
features, 16 time-domain features, and five frequency-domain features, making
a total of 24 HRV features. The impact of HRV observation window size on
engagement estimation performance was investigated by extracting HRV features
from the reconstructed rPPG signals using various observation window sizes
(60, 90, 120, 150, 180, 210, and 240 seconds).

Facial expression features. Action Units (AUs) were used for the computation
of facial expression features [46]. 17 unique AUs were detected and tracked
using the OpenFace library [6] (see supplementary material Tab. 6). AUs were
represented in two ways: as intensity signals (on a scale from 0 to 5) and as
binary classifications for their presence or absence. Hence, 34 features were
obtained, providing a comprehensive insight into engagement-related facial
movements.

Motion features. Four distinct sets of motion features were extracted using
the OpenFace library [6]. These included: six gaze tracking features
illustrating the 3D coordinates of each eye’s gaze direction; two features
representing each eye’s gaze direction; 280 features outlining 2D and 3D
landmarks around each eye; and six features pertaining to the translation and
rotation of the head in 3D space. Collectively, these 294 features provided a
comprehensive examination of facial and eye movements associated with
engagement.

In the following, ’behavioral features’ (BF) denotes motion and facial
expressions. These BF were computed for each frame extracted from the
collected video recordings. To consider the temporal dynamics of these
features, a 2-seconds observation window was adopted, wherein the average
value of each feature was computed.

###  4.4 Engagement classification

Three-class classification of engagement has been conducted in two stages. In
the first stage, classification was done using only 24 HRV features with
various classifiers. These included knn, Random Forest, AdaBoost, CatBoost,
xgboost, lightgbm, Support Vector Machine (with ’poly’, ’rbf’, and ’sigmoid’
kernels), Decision Tree, Gaussian Naive Bayes, Quadratic Discriminant
Analysis, Neural Net, an ensemble of knn and Random Forest, and an ensemble of
xgboost and Random Forest. Out of these, the knn and the ensemble of knn and
Random Forest (knn+RF) proved to be the most effective. In the second stage,
these two most effective classifiers were employed. A feature-level fusion
technique was used to combine 24 HRV and 328 BF features into a single feature
vector for a specific 5-seconds engagement interval, which was then fed into
the classifier.

##  5 Results

###  5.1 Experimental protocol

The Engagement Dataset was split into 80% training and 20% test sets. To
ensure model robustness and generalization, a 5-fold subject dependent cross-
validation was applied to the training data. The trained model predicts
outcomes for the testing set. This protocol reliably measures model
performance while maintaining test set independence [14]. Accuracy and the
Receiver Operating Characteristic Area Under the Curve (ROC AUC) metrics were
initially used to evaluate models. For the best performing models, the F1
score and confusion matrices were additionally calculated to enhance the
comprehensiveness of the assessment.

###  5.2 HR measurement accuracy

For the Engagement Dataset, the HR from the reconstructed rPPG signals was
compared to that of ground truth cPPG using mean absolute error (MAE) and root
mean square error (RMSE) as evaluation metrics. An MAE of 5.15 bpm and an RMSE
of 7.81 bpm were obtained, indicating promising results given the uncontrolled
conditions of the video recordings. The SOTA performance [37] was marked by
MAE values of 3.55, 5.99, and 9.26 bpm in controlled lab settings.

(a) Utilization of HRV features.

(b) Utilization of HRV and Behavioral features.

Figure 4: Ensemble of knn and Random Forest model’s confusion matrices for
engagement estimation (HRV observation window of 240 seconds) based on (a) HRV
features; (b) HRV and Behavioral features.

###  5.3 Short observation window HRV features for engagement estimation

Utilizing a short observation window for HRV features calculation, the
proposed approach’s performance on the DAiSEE [19] dataset (focused on
students’ engagement) and Engagement Dataset is shown in Tab. 2. For the
DAiSEE dataset with 10-seconds snippets, the highest accuracy of 54.49% was
achieved by the Random Forest model. Meanwhile, a 49.40% accuracy was yielded
by the knn model on Engagement Dataset using a 10-seconds observation window.
The performance of the proposed method is constrained by the 10-seconds
snippets of the DAiSEE dataset. Reliable HRV features are not offered by such
a short observation window, a fact also reflected in Engagement Dataset
performance using a 10-seconds observation window. Longer videos are required
for robust HRV and engagement estimation. This study’s video recordings allow
the proposed method’s capability to be fully realized using long HRV
observation windows. In the following subsection, the influence of HRV
observation window size is analyzed in detail.

Method | Accuracy [%]
---|---
DAiSEE [19]
InceptionNet Video Level [19] | 46.40
InceptionNet Frame Level [19] | 47.10
C3D Training [19] | 48.60
Inflated 3D ConvNet [49] | 52.35
ResNet + TCN (weighted loss) [2] | 53.70
HRV + Random Forest | 54.49
C3D FineTune [19] | 56.10
C3D LRCN [19] | 57.90
DFSTN [31] | 58.84
C3D + TCN [2] | 59.97
ResNet + LSTM [2] | 61.15
ResNet + TCN [2] | 63.90
EfficientNet B7 + TCN [40] | 64.67
EfficientNet B7 + Bi-LSTM [40] | 66.39
Ordinal TCN [1] | 67.40
EfficientNet B7 + LSTM [40] | 67.48
Engagement Dataset
HRV + knn | 49.40
Table 2: Proposed method’s performance using short observation window HRV features for engagement estimation based on two datasets: (1) DAiSEE [19]; (2) Engagement Dataset. HRV | Accuracy [-] | ROC AUC [-]
---|---|---
window [sec] | knn | knn+RF | knn | knn+RF
60 | 0.816 | 0.816 | 0.870 | 0.906
90 | 0.882 | 0.880 | 0.923 | 0.947
120 | 0.910 | 0.911 | 0.946 | 0.967
150 | 0.924 | 0.926 | 0.953 | 0.975
180 | 0.931 | 0.936 | 0.955 | 0.977
210 | 0.937 | 0.938 | 0.961 | 0.983
240 | 0.937 | 0.940 | 0.960 | 0.983
Table 3: Evaluation metrics of the knn model and ensemble of knn and Random
Forest model for engagement estimation based on HRV features calculated at
different values of HRV observation window.

###  5.4 Effects of HRV observation window size on the performance of
engagement estimation

| HRV
---
window [sec]
HRV |  | HRV
---
\+ BF (1)
| HRV
---
\+ BF (2)
| HRV
---
\+ BF (3)
| HRV
---
\+ BF (4)
| HRV
---
\+ BF (5)
| HRV
---
\+ BF (1+2)
| HRV
---
\+ BF (4+5)
| HRV
---
\+ BF (all)
60 | 0.816 | 0.864 | 0.855 | 0.861 | 0.896 | 0.919 | 0.856 | 0.928 | 0.930
90 | 0.880 | 0.903 | 0.902 | 0.870 | 0.936 | 0.931 | 0.891 | 0.942 | 0.929
120 | 0.911 | 0.929 | 0.929 | 0.881 | 0.952 | 0.944 | 0.919 | 0.952 | 0.934
150 | 0.926 | 0.934 | 0.936 | 0.884 | 0.953 | 0.944 | 0.927 | 0.954 | 0.940
180 | 0.936 | 0.937 | 0.944 | 0.892 | 0.954 | 0.947 | 0.932 | 0.955 | 0.938
210 | 0.938 | 0.939 | 0.944 | 0.896 | 0.955 | 0.951 | 0.933 | 0.958 | 0.941
240 | 0.940 | 0.943 | 0.949 | 0.899 | 0.956 | 0.956 | 0.934 | 0.960 | 0.940
Table 4: Ensemble of knn and Random Forest model’s accuracy for engagement
estimation based on HRV and various sets of BF at different values of HRV
observation window. (1) stands for gaze tracking, (2) for angle of gaze
direction, (3) for 2D and 3D landmarks of specific points around each eye, (4)
for translation and rotation of the head in 3D space, and (5) for facial
Action Units.

With the constraints of a 10-seconds observation window addressed in the
preceding section, the effects of HRV observation windows of extended lengths
are analyzed. The experiments revealed that knn and knn and Random Forest
ensemble (knn+RF) were the most effective machine learning classifiers.
Models’ performance was assessed across different HRV observation window
values (Tab. 3). As the HRV observation window size increased from 60 seconds
to 240 seconds, significant improvements were observed in the accuracy and ROC
AUC scores for both models. At an HRV observation window size of 60 seconds,
the knn model achieved an accuracy of 0.816 and a ROC AUC score of 0.870,
while the knn+RF model showed slightly better results with an accuracy of
0.816 and a ROC AUC score of 0.906. At the optimal HRV observation window size
of 240 seconds, accuracy of the knn model reached 0.937 and its ROC AUC score
peaked at 0.960, while the knn+RF model outperformed with an accuracy of 0.940
and a ROC AUC of 0.983. The HRV observation window size has a significant
impact on the performance of engagement estimation models and larger
observation window sizes yield better results. With longer observation
windows, finer and more complex HRV patterns in the rPPG signals can be
discerned, thus enabling more accurate and robust predictions based on the
extracted HRV features. Moreover, noise and short-term variability in the
signals, which may confuse or degrade the performance of the classifiers, are
better averaged out over longer observation periods. Table 3 demonstrates that
a 120-seconds HRV observation window is already sufficient for the proposed
method to showcase its capability. The confusion matrix of the model with the
highest performance is shown in Fig. 4(a). A high differentiation is observed
among the three classes, slightly better at detecting Moderate engagement than
Low and High engagement. The F1 scores for Low, Moderate, and High levels of
engagement are 0.92, 0.96, and 0.90, respectively. To improve performance in
Low and High engagement, the model requires more balanced data or better
features for class distinction. All in all, the DAiSEE dataset’s 10-seconds
clips prevent an evaluation of the effects of HRV observation window length on
engagement estimation. Yet, from the Engagement Dataset, it’s evident that HRV
features can robustly measure engagement when given a sufficient observation
window size, such as 2 to 4 minutes.

###  5.5 Effectiveness of BF selection when fusing with HRV for engagement
estimation

While HRV features have established a strong foundation, relying solely on
physiological signals limits prediction accuracy. Adding BF is crucial for
improved metrics as human engagement involves not only physiological but also
subtle behavioral cues. Thus, a model fusing both physiological and behavioral
aspects could enhance prediction.

In Tab. 4, the ensemble of knn and Random Forest model’s accuracy using both
HRV and various BF combinations, including (1) gaze tracking, (2) angle of
gaze direction, (3) 2D and 3D landmarks of specific points around each eye,
(4) translation and rotation of the head in 3D space, and (5) facial Action
Units, is shown. The ROC AUC metric, mirroring the accuracy trend, was
omitted. The model’s performance is significantly influenced by the BF
selection. Set (3) is found to be less efficient with longer HRV observation
windows; however, sets (4) and (5) are shown to boost prediction accuracy. The
highest performance was observed when HRV was paired with (4), indicating
”translation and rotation of the head in 3D space”, and (5), pointing to
”facial Action Units”. Significant metric enhancement is observed when BFs are
incorporated as the model’s accuracy increases from 0.816 to 0.930 for a
60-seconds observation window. Enhanced performance due to BF inclusion is
consistently observed across all data. Yet, the boost is more pronounced at
smaller HRV observation window sizes. In Fig. 4(b), the confusion matrix of
the knn+RF model, incorporating HRV and both (4) and (5) BF, is presented, as
opposed to the HRV-only feature confusion matrix depicted in Fig. 4(a). It
outperforms the singular HRV model, underscoring that the inclusion of BF
yields superior engagement estimation. After fusing with BF, the F1 scores for
Low, Moderate, and High levels of engagement improved to 0.93, 0.97, and 0.94,
respectively. Further refinement through enhanced feature selection or the
exploration of alternate models might offer improved differentiation between
Low and High Engagement.

###  5.6 Combining HRV observation window size and BF set for engagement
estimation

Figure 5: Accuracy of the ensemble of knn and Random Forest model for
engagement estimation based on HRV and both (4) and (5) BF calculated at
different values of HRV observation window. The accuracy of the model, based
solely on BF, remains constant due to its independence from the value of the
HRV window.

The effect of combining BF (4+5) set with different HRV observation window
sizes on the model’s performance is shown in Fig. 5. As the HRV observation
window size increases, the performance metrics of the model tends to improve,
up to a certain point. However, the performance improvement isn’t strictly
linear and plateaus after a certain HRV observation window size. In the knn+RF
model with BF (4+5), accuracy improves from 0.928 (60 seconds) to 0.960 (240
seconds), but the difference between 210 seconds and 240 seconds is marginal.
Thus, while the integration of BF improves the model, gains are notably larger
for smaller HRV observation windows. Nevertheless, with the addition of BF,
the best HRV-only model’s performance was enhanced by 2%. Table 5 demonstrates
the comparison of the proposed method with the method proposed by Mohamad _et
al_. [33] which is publicly available and aimed for engagement estimation. The
Engagement Dataset was processed using their method, following the same
protocol and data split as described in Sec. 5.1.

Method | Accuracy [-] | ROC AUC [-]
---|---|---
Mohamad _et al_. [33] | 0.633 | 0.500
HRV | 0.940 | 0.983
HRV + BF (4+5) | 0.960 | 0.991
Table 5: Comparison of methods’ performances for engagement estimation based
on Engagement Dataset. Ensemble of knn and Random Forest model was used for
”HRV” and ”HRV + BF (4+5)” methods.

##  6 Conclusion

The remote measurement of heart rate variability, along with facial and body
language recognition, is used for engagement analysis in virtual meetings,
which have become increasingly popular over the recent years. This article
pioneers the application of unsupervised rPPG measurement technology in
estimating engagement during online meetings. It first introduces the
Engagement Dataset centered on social workers’ online video meetings. The
Engagement Dataset is accompanied by granular engagement labels that capture
the essence of virtual meeting dynamics. Subsequently, the effect of HRV
observation window size on engagement estimation performance was assessed
using both collected and public datasets. Short HRV observation windows proved
to be unreliable for HRV feature calculation, while longer observation windows
(e.g., 2-4 minutes) provided a robust foundation for engagement estimation.
Further, the significance of selecting the right behavioral features set was
evaluated. Given the crucial importance of the right HRV window choice, a
performance increase from 49.40% through 81.60% to 94% was witnessed when the
HRV observation window size was adjusted from 10 seconds to 60 seconds and
then to 240 seconds. Moreover, when the correct BF set was used, performance
was further boosted by up to 2%.

In future, the proposed method is to be validated using more datasets. With
the formulated method, engagement analysis at the clip level was carried out,
setting the stage for future entire video recording level analysis.
Additionally, exploration of engagement fluctuation on a group level, e.g.,
the analysis of synchrony or interactions of the participants, is planned to
better analyze the online event. Moreover, this method is intended to be
advanced into a deep learning model, trained end-to-end for engagement
estimation.

## Acknowledgments

This work was supported by the Research Council of Finland (former Academy of
Finland) Academy Professor project EmotionAI (grants 336116, 345122), and the
Finnish Work Environment Fund (Project 200414). The authors also acknowledge
CSC-IT Center for Science, Finland, for providing computational resources.

## References

  * Abedi and Khan [2021a] Ali Abedi and Shehroz Khan.  Affect-driven ordinal engagement measurement from video.  _arXiv preprint arXiv:2106.10882_ , 2021a.
  * Abedi and Khan [2021b] Ali Abedi and Shehroz S. Khan.  Improving state-of-the-art in detecting student engagement with resnet and tcn hybrid network.  In _Proceedings - 2021 18th Conference on Robots and Vision, CRV 2021_ , page 151 – 157, 2021b.  Cited by: 15; All Open Access, Green Open Access.
  * Arapakis et al. [2017] Ioannis Arapakis, Miguel Barreda-Angeles, and Alexandre Pereda-Baños.  Interest as a proxy of engagement in news reading: Spectral and entropy analyses of eeg activity patterns.  _IEEE Transactions on Affective Computing_ , 10(1):100–114, 2017.
  * Aslan et al. [2019] Sinem Aslan, Nese Alyuz, Cagri Tanriover, Sinem E Mete, Eda Okur, Sidney K D’Mello, and Asli Arslan Esme.  Investigating the impact of a real-time, multimodal student engagement analytics technology in authentic classrooms.  In _Proceedings of the 2019 chi conference on human factors in computing systems_ , pages 1–12, 2019.
  * Atapattu et al. [2019] Thushari Atapattu, Menasha Thilakaratne, Rebecca Vivian, and Katrina Falkner.  Detecting cognitive engagement using word embeddings within an online teacher professional development community.  _Computers & Education_, 140:103594, 2019.
  * Baltrusaitis et al. [2018] Tadas Baltrusaitis, Amir Zadeh, Yao Chong Lim, and Louis-Philippe Morency.  Openface 2.0: Facial behavior analysis toolkit.  In _2018 13th IEEE international conference on automatic face & gesture recognition (FG 2018)_, pages 59–66. IEEE, 2018.
  * Ben-Youssef et al. [2017] Atef Ben-Youssef, Chloé Clavel, Slim Essid, Miriam Bilac, Marine Chamoux, and Angelica Lim.  Ue-hri: a new dataset for the study of user engagement in spontaneous human-robot interactions.  In _Proceedings of the 19th ACM international conference on multimodal interaction_ , pages 464–472, 2017.
  * Benini et al. [2019] Sergio Benini, Mattia Savardi, Katalin Balint, Andras Balint Kovacs, and Alberto Signoroni.  On the influence of shot scale on film mood and narrative engagement in film viewers.  _IEEE Transactions on Affective Computing_ , 13(2):592–603, 2019.
  * Casado et al. [2023] Constantino Álvarez Casado, Manuel Lage Cañellas, and Miguel Bordallo López.  Depression recognition using remote photoplethysmography from facial videos.  _IEEE Transactions on Affective Computing_ , 14(4):3305–3316, 2023.
  * Celiktutan et al. [2017] Oya Celiktutan, Efstratios Skordos, and Hatice Gunes.  Multimodal human-human-robot interactions (mhhri) dataset for studying personality and engagement.  _IEEE Transactions on Affective Computing_ , 10(4):484–497, 2017.
  * Chen et al. [2023] Haoyu Chen, Henglin Shi, Xin Liu, Xiaobai Li, and Guoying Zhao.  Smg: A micro-gesture dataset towards spontaneous body gestures for emotional stress state analysis.  _International Journal of Computer Vision_ , 131(6):1346 – 1366, 2023.  Cited by: 13; All Open Access, Green Open Access, Hybrid Gold Open Access.
  * Chen et al. [2019] Xu Chen, Li Niu, Ashok Veeraraghavan, and Ashutosh Sabharwal.  Faceengage: robust estimation of gameplay engagement from user-contributed (youtube) videos.  _IEEE Transactions on Affective Computing_ , 13(2):651–665, 2019.
  * Choi et al. [2022] Youjin Choi, JooYeong Kim, and Jin-Hyuk Hong.  Immersion measurement in watching videos using eye-tracking data.  _IEEE Transactions on Affective Computing_ , 13(4):1759–1770, 2022.
  * Cournapeau et al. [2023] David Cournapeau, Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, and Vincent Michel.  scikit-learn: Machine learning in python.  https://scikit-learn.org/stable/modules/cross_validation.html#cross-validation, 2023.  Accessed: 2023-08-29.
  * Dubovi [2022] Ilana Dubovi.  Cognitive and emotional engagement while learning with vr: The perspective of multimodal methodology.  _Computers & Education_, 183:104495, 2022.
  * Eslami et al. [2022] Seyed Pouyan Eslami, Maryam Ghasemaghaei, and Khaled Hassanein.  Understanding consumer engagement in social media: The role of product lifecycle.  _Decision Support Systems_ , 162:113707, 2022.
  * Filippini et al. [2021] Chiara Filippini, Edoardo Spadolini, Daniela Cardone, Domenico Bianchi, Maurizio Preziuso, Christian Sciarretta, Valentina del Cimmuto, Davide Lisciani, and Arcangelo Merla.  Facilitating the child–robot interaction by endowing the robot with the capability of understanding the child engagement: The case of mio amico robot.  _International Journal of Social Robotics_ , 13:677–689, 2021.
  * Gordon et al. [2016] Goren Gordon, Samuel Spaulding, Jacqueline Kory Westlund, Jin Joo Lee, Luke Plummer, Marayna Martinez, Madhurima Das, and Cynthia Breazeal.  Affective personalization of a social robot tutor for children’s second language skills.  In _Proceedings of the AAAI conference on artificial intelligence_ , 2016.
  * Gupta et al. [2016] Abhay Gupta, Arjun D’Cunha, Kamal Awasthi, and Vineeth Balasubramanian.  Daisee: Towards user engagement recognition in the wild.  _arXiv preprint arXiv:1609.01885_ , 2016.
  * Hoque et al. [2022] Misbah Ul Hoque, Kisung Lee, Jessica L Beyer, Sara R Curran, Katie S Gonser, Nina SN Lam, Volodymyr V Mihunov, and Kejin Wang.  Analyzing tweeting patterns and public engagement on twitter during the recognition period of the covid-19 pandemic: A study of two us states.  _IEEE Access_ , 10:72879–72894, 2022.
  * Hsu et al. [2014] YungChien Hsu, Yen-Liang Lin, and Winston Hsu.  Learning-based heart rate detection from remote photoplethysmography features.  In _2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 4433–4437, 2014.
  * Huang et al. [2016] Yuyun Huang, Emer Gilmartin, and Nick Campbell.  Conversational engagement recognition using auditory and visual cues.  In _Proceedings of the Annual Conference of the International Speech Communication Association, INTERSPEECH_ , page 590 – 594, 2016.  Cited by: 11.
  * Kamath et al. [2016] Aditya Kamath, Aradhya Biswas, and Vineeth Balasubramanian.  A crowdsourced approach to student engagement recognition in e-learning environments.  In _2016 IEEE Winter Conference on Applications of Computer Vision (WACV)_ , pages 1–9, 2016.
  * Kaur et al. [2018] Amanjot Kaur, Aamir Mustafa, Love Mehta, and Abhinav Dhall.  Prediction and localization of student engagement in the wild.  In _2018 Digital Image Computing: Techniques and Applications (DICTA)_ , pages 1–8. IEEE, 2018.
  * Khenkar and Jarraya [2022] Shoroog Khenkar and Salma Kammoun Jarraya.  Engagement detection based on analyzing micro body gestures using 3d cnn.  _Computers, Materials & Continua_, 70(2), 2022.
  * Kumar et al. [2024] Puneet Kumar, Alexander Vedernikov, and Xiaobai Li.  Measuring non-typical emotions for mental health: A survey of computational approaches.  _arXiv preprint arXiv:5456274_ , 2024.
  * Lee et al. [2022] Taeckyung Lee, Dain Kim, Sooyoung Park, Dongwhi Kim, and Sung-Ju Lee.  Predicting mind-wandering with facial videos in online lectures.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 2104–2113, 2022.
  * Leite et al. [2015] Iolanda Leite, Marissa McCoy, Daniel Ullman, Nicole Salomons, and Brian Scassellati.  Comparing models of disengagement in individual and group interactions.  In _Proceedings of the Tenth Annual ACM/IEEE International Conference on Human-Robot Interaction_ , page 99–105, New York, NY, USA, 2015. Association for Computing Machinery.
  * Li et al. [2018] Xiaobai Li, Iman Alikhani, Jingang Shi, Tapio Seppanen, Juhani Junttila, Kirsi Majamaa-Voltti, Mikko Tulppo, and Guoying Zhao.  The obf database: A large face video database for remote physiological signal measurement and atrial fibrillation detection.  In _Proceedings - 13th IEEE International Conference on Automatic Face and Gesture Recognition, FG 2018_ , page 242 – 249, 2018.  Cited by: 47; All Open Access, Green Open Access.
  * Liang et al. [2009] Wen Chieh Liang, John Yuan, Deh Chuan Sun, and Ming Han Lin.  Changes in physiological parameters induced by indoor simulated driving: Effect of lower body exercise at mid-term break.  _Sensors_ , 9(9):6913–6933, 2009.
  * Liao et al. [2021] Jiacheng Liao, Yan Liang, and Jiahui Pan.  Deep facial spatiotemporal network for engagement prediction in online learning.  _Applied Intelligence_ , 51:6609–6621, 2021.
  * Makowski et al. [2021] Dominique Makowski, Tam Pham, Zen J. Lau, Jan C. Brammer, François Lespinasse, Hung Pham, Christopher Schölzel, and S. H. Annabel Chen.  Neurokit2: A python toolbox for neurophysiological signal processing.  _Behavior Research Methods_ , 53(4):1689 – 1696, 2021.  Cited by: 205; All Open Access, Bronze Open Access, Green Open Access.
  * Mohamad Nezami et al. [2020] Omid Mohamad Nezami, Mark Dras, Len Hamey, Deborah Richards, Stephen Wan, and Cécile Paris.  Automatic recognition of student engagement using deep learning and facial expression.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pages 273–289. Springer, 2020.
  * Monkaresi et al. [2017] Hamed Monkaresi, Nigel Bosch, Rafael A. Calvo, and Sidney K. D’Mello.  Automated detection of engagement using video-based estimation of facial expressions and heart rate.  _IEEE Transactions on Affective Computing_ , 8(1):15–28, 2017.
  * Ober et al. [2021] Teresa M Ober, Corinne J Brenner, Alvaro Olsen, Bruce D Homer, and Jan L Plass.  Detecting patterns of engagement in a digital cognitive skills training game.  _Computers & Education_, 165:104144, 2021.
  * Psaltis et al. [2017] Athanasios Psaltis, Konstantinos C Apostolakis, Kosmas Dimitropoulos, and Petros Daras.  Multimodal student engagement recognition in prosocial games.  _IEEE Transactions on Games_ , 10(3):292–303, 2017.
  * Sabour et al. [2023] Rita Meziati Sabour, Yannick Benezeth, Pierre De Oliveira, Julien Chappé, and Fan Yang.  Ubfc-phys: A multimodal database for psychophysiological studies of social stress.  _IEEE Transactions on Affective Computing_ , 14(1):622–636, 2023.
  * Salam et al. [2022] Hanan Salam, Oya Celiktutan, Hatice Gunes, and Mohamed Chetouani.  Automatic context-driven inference of engagement in hmi: A survey.  _arXiv preprint arXiv:2209.15370_ , 2022.
  * Savchenko et al. [2022] Andrey V Savchenko, Lyudmila V Savchenko, and Ilya Makarov.  Classifying emotions and engagement in online learning based on a single facial expression recognition neural network.  _IEEE Transactions on Affective Computing_ , 13(4):2132–2143, 2022.
  * Selim et al. [2022] Tasneem Selim, Islam Elkabani, and Mohamed A Abdou.  Students engagement level detection in online e-learning using hybrid efficientnetb7 together with tcn, lstm, and bi-lstm.  _IEEE Access_ , 10:99573–99583, 2022.
  * Shaw et al. [2022] Rabi Shaw, Chinmay Mohanty, Bidyut Kr Patra, and Animesh Pradhan.  1d multi-point local ternary pattern: A novel feature extraction method for analyzing cognitive engagement of students in flipped learning pedagogy.  _Cognitive Computation_ , pages 1–14, 2022.
  * Singh et al. [2023] Monisha Singh, Ximi Hoque, Donghuo Zeng, Yanan Wang, Kazushi Ikeda, and Abhinav Dhall.  Do i have your attention: A large scale engagement prediction dataset and baselines, 2023.
  * Steinert et al. [2021] Lars Steinert, Felix Putze, Dennis Küster, and Tanja Schultz.  Audio-visual recognition of emotional engagement of people with dementia.  In _Interspeech_ , pages 1024–1028, 2021.
  * Sun and Li [2022] Zhaodong Sun and Xiaobai Li.  Contrast-phys: Unsupervised video-based remote physiological measurement via spatiotemporal contrast.  _Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)_ , 13672 LNCS:492 – 510, 2022.  Cited by: 2; All Open Access, Green Open Access.
  * Sun et al. [2023] Zhaodong Sun, Alexander Vedernikov, Virpi-Liisa Kykyri, Mikko Pohjola, Miriam Nokia, and Xiaobai Li.  Estimating stress in online meetings by remote physiological signal and behavioral features.  In _Adjunct Proceedings of the 2022 ACM International Joint Conference on Pervasive and Ubiquitous Computing and the 2022 ACM International Symposium on Wearable Computers_ , page 216–220, New York, NY, USA, 2023. Association for Computing Machinery.
  * Tian et al. [2001] Y-I Tian, Takeo Kanade, and Jeffrey F Cohn.  Recognizing action units for facial expression analysis.  _IEEE Transactions on pattern analysis and machine intelligence_ , 23(2):97–115, 2001.
  * Whitehill et al. [2014] Jacob Whitehill, Zewelanji Serpell, Yi-Ching Lin, Aysha Foster, and Javier R. Movellan.  The faces of engagement: Automatic recognition of student engagement from facial expressions.  _IEEE Transactions on Affective Computing_ , 5(1):86 – 98, 2014.  Cited by: 379.
  * Wu et al. [2023] Yi-Chiao Wu, Li-Wen Chiu, Chun-Chih Lai, Bing-Fei Wu, and Sunny S. J. Lin.  Recognizing, fast and slow: Complex emotion recognition with facial expression detection and remote physiological measurement.  _IEEE Transactions on Affective Computing_ , 14(4):3177–3190, 2023.
  * Zhang et al. [2019] Hao Zhang, Xiaofan Xiao, Tao Huang, Sanya Liu, Yu Xia, and Jia Li.  An novel end-to-end network for automatic student engagement recognition.  In _ICEIEC 2019 - Proceedings of 2019 IEEE 9th International Conference on Electronics Information and Emergency Communication_ , page 342 – 345, 2019.  Cited by: 15.
  * Zhang et al. [2020] Zhaoli Zhang, Zhenhua Li, Hai Liu, Taihe Cao, and Sannyuya Liu.  Data-driven online learning engagement detection via facial expression and mouse behavior recognition technology.  _Journal of Educational Computing Research_ , 58(1):63–86, 2020.

Supplementary Material

Figure 6: Example of engagement data obtained after filtering process. Data on this graph represent the engagement labels of a specific participant during a particular video meeting. Table 6: Description of Action Units used in engagement analysis. AU # | Description | AU # | Description
---|---|---|---
AU1 | inner brow raiser | AU12 | lip corner puller
AU2 | outer brow raiser | AU14 | dimpler
AU4 | brow lowerer | AU15 | lip corner depressor
AU5 | upper lid raiser | AU17 | chin raiser
AU6 | cheek raiser | AU20 | lip stretcher
AU7 | lid tightener | AU23 | lip tightener
AU9 | nose wrinkler | AU25 | lips part
AU10 | upper lip raiser | AU26 | jaw drop
|  | AU45 | blink


11institutetext: UNSW Sydney, Australia
11email<EMAIL_ADDRESS>22institutetext: Data61 CSIRO

# Individually Rational Land and Neighbor Allocation: Impossibility Results

Haris Aziz 1122

###### Abstract

We consider a setting in which agents are allocated land plots and they have
additive preferences over which plot they get and who their neighbor is.
Strategyproofness, Pareto optimality, and individual rationality are three
fundamental properties in economic design. We present two impossibility
results showing that the three properties are incompatible in this context.

##  1 Introduction

We consider an allocation problem in which agents wish to get one of the plots
and have preferences over them. They additionally have preferences over who
their neighbor is. Such a problem was recently studied by Elkind et al. (2020)
who among other results, explored the issue of maximizing social welfare.

The model of Elkind et al. (2020) does not allow the agents to express certain
outcomes as unacceptable due to which individual rationality is a non-issue.
When agents are allowed to express certain plots or neighbors as unacceptable,
individual rationality is a meaningful property. For example, agents should
not be forced to get a plot which does not fit their needs. Another scenario
in which individual rationality is important is when agents already have
default plots (also referred to as initial endowments) and the goal is to
enable mutually beneficial exchanges. In these cases, an agent would want to
get an outcome that is at least as preferred as the default outcome.

We revisit the model of Elkind et al. (2020) while taking into account the
additional issue of individual rationality. We examine the challenge of
designing mechanisms that simultaneously satisfy individual rationality,
Pareto optimality, and strategyproofness. We present two impossibility results
that show that even under severe restrictions, the three properties are
incompatible. The first impossibility result holds when agents are only
allowed to express certain plots as unacceptable. The second impossibility
result holds when agents are only allowed to express certain neighbors as
unacceptable. We then show that the three properties are independent in our
context by proving that any pair of properties can be simultaneously
satisfied.

### Related Work

The problem of allocating indivisible items among agents is well-studied in
economics and computer science. It falls under the umbrella of allocation and
matching problems that take into account the preferences of the agents
(Manlove, 2013). The setting that we consider is based on a paper by Elkind et
al. (2020) that they refer to as ‘land allocation with friends’. The model we
consider is slightly more general as it allows agents to express negative
valuations or at least express certain plots or neighbors as unacceptable.
Elkind et al. (2020) focussed on the complexity of computing welfare
maximizing allocations. They also presented a polynomial-time algorithm that
is Pareto optimal and strategyproof under certain restrictions. They did not
consider the issue of agents expressing certain alternatives as unacceptable.

The aspect of preferences over neigbors makes the problem a strict
generalization of the well-known house allocation problem (see e.g.,
Abdulkadiroğlu and Sönmez (1998), Svensson (1999)). Since agents care about
who their neighbor is, the problem also has connection with hedonic games (see
e.g. Aziz and Savani (2016)). Under particular plot topologies, the model we
study also has connections with room-roommate games (Aziz et al., 2013, Chan
et al., 2016).

##  2 Preliminaries

### Model

The problem we consider involves a set of agents $N=\\{1,\ldots,n\\}$ each of
whom need to be allocated at most one of the $m$ plots in
$\mathcal{V}=\\{v_{1},\ldots,v_{m}\\}$. The goal is to find an allocation
$A:N\rightarrow\mathcal{V}$ that allocated plot $A(i)$ to agent $i$. We allow
an agent to not get any plot.

The layout of the plots is captured by a plot graph
$\mathcal{G}=\langle\mathcal{V},\mathcal{E}\rangle$: which is an undirected
graph where _neighboring_ plots $w$ and $v$ are connected by an edge
$\\{w,v\\}\in\mathcal{E}$. Each agent $i\in N$ has a valuation function
$u_{i}:\mathcal{V}\to{\mathbb{Q}}$: $u_{i}(v)$ is the value $i$ derives from
receiving plot $v$. Agents also care about who they live next to. The
relationship graph $\langle N,F\rangle$, where $(i,j)\in F$ indicates that $i$
and $j$ know each other and the edge weight $\phi_{i,j}\in\mathbb{Q}$ is the
additional utility $i$ obtains for living next to $j$. For a given statement
$b$, we denote with $\mathbb{I}(b)$ the indicator function with input $b$ .
The output takes value $1$ if $b$ is true and $0$ if $b$ is false.

The utility $U_{i}(A)$ of agent $i$ under allocation $A$ is

$u_{i}(A(i))+\sum_{(i,j)\in
F}\phi_{i,j}\times\mathbb{I}\left(\\{A(i),A(j)\\}\in\mathcal{E}\right).$ (1)

We will suppose that the utility of being unmatched is zero.

### Properties

An allocation is _Pareto optimal (PO)_ if there exists no other allocation
that each agent weakly prefers and at least one agent strictly prefers.
Individual rationality (IR) is defined as follows. An allocation $A$ is
_individually rational (IR)_ if $U_{i}(A)\geq 0$ for all $i\in N$. A mechanism
is IR if it returns an allocation that gives utility at least zero to each
agent. Finally, an allocation mechanism is _strategyproof (SP)_ if no agent
has an incentive to misreport her utilities functions to obtain a better
outcome with higher utility. Two restricted forms of IR are as follows (1)
agents express certain plots to be unacceptable ($-\infty$ value) or (2)
agents express certain neighbors to be unacceptable ($-\infty$ value).

##  3 Impossibility of Achieving IR, PO, and SP

We show that even when agents are only allowed to express certain plots/houses
as unacceptable, there exists no IR, PO, and SP mechanism.

######  Theorem 3.1.

If agents are allowed to express plots as unacceptable, then there is no
mechanism that is PO, IR, and SP.

###### Proof.

Consider an instance with agents $1,2,3,4,5$ and plots
$v_{1},v_{2},v_{3},v_{4},v_{5}$, where $\mathcal{E}=\\{\\{v_{1},v_{2}\\}\\}$.
Agents’ plot valuations are shown below, and
$\phi_{1,2}=\phi_{2,3}=\phi_{3,1}=1$ and
$\phi_{1,3}=\phi_{3,2}=\phi_{2,1}=0.2$.

$I_{1}$=  $v_{1}$ $v_{2}$ $v_{3}$ $v_{4}$ $v_{5}$ agent 1 .3 .1 1 0 0 agent 2
.3 .1 1 0 0 agent 3 .3 .1 1 0 0 agent 4 0.1 0.1 0.1 0.1 0.1 agent 5 0.1 0.1
0.1 0.1 0.1

Since the instance is symmetric, without loss of generality, let the outcome
be
$A=\\{\\{1,v_{1}\\},\\{2,v_{2}\\},\\{3,v_{3}\\},\\{4,v_{4}\\},\\{5,v_{5}\\}\\}$.
All other PO outcomes are symmetric in which two of agents $1,2,3$ are paired
up in $v_{1}$ and $v_{2}$ and third gets $v_{3}$. Agent 4 and 5 who are
symmetric then take plots $v_{4}$ and $v_{5}$. Note that $u_{1}(A)=1.3$,
$u_{2}(A)=0.3$ and $u_{3}(A)=1$. Suppose agent $2$ misreports her valuation
under $I_{2}$ as follows by reporting $v_{2}$ as unacceptable. Then SP
requires that agent $2$ should not get utility more than $0.3$ under $I_{2}$.

$I_{2}$=  $v_{1}$ $v_{2}$ $v_{3}$ $v_{4}$ $v_{5}$ agent 1 .3 .1 1 0 0 agent 2
.3 – 1 0 0 agent 3 .3 .1 1 0 0 agent 4 0.1 0.1 0.1 0.1 0.1 agent 5 0.1 0.1 0.1
0.1 0.1

We note the following for instance $I_{2}$.

  1. 1.

If agent 2 gets $v_{2}$, the mechanism is not IR as the agent gets an
unacceptable plot.

  2. 2.

If agent 2 gets $v_{3}$, the mechanism is not SP as agent $2$ can misreport
under instance $I_{1}$.

  3. 3.

If agent 2 gets $v_{1}$, then PO requires that agent 1 or 3 get $v_{2}$.
Therefore, agent 2 gets utility at least $0.5$ which violates SP.

  4. 4.

From the above three cases, it is clear that either 2 is unmatched or gets
$v_{4}$ or $v_{5}$.

  5. 5.

If $1$ and $3$ take $v_{1}$ and $v_{2}$ or $v_{2}$ and $v_{1}$, then PO
requires that agent $2$ gets $v_{3}$ which violates SP.

  6. 6.

Suppose one of agents 1 or 3 gets $v_{3}$. Then the other must get $v_{1}$
because of PO.

    1. (a)

Suppose $1$ gets $v_{1}$, $4$ or $5$ gets $v_{2}$ and 3 gets $v_{3}$. Then,
agent $1$ gets utility $0.3$. We will show that in this case the mechanism is
not PO. Agent $1$ will get utility $1.1$ if she takes $v_{2}$ and agent $2$
gets $v_{1}$ which results in a Pareto improvement hence showing the mechanism
is not PO.

    2. (b)

Suppose $3$ gets $v_{1}$, $4$ or $5$ gets $v_{2}$ and 1 gets $v_{3}$. Then,
agent $3$ gets utility $0.3$. We will show that in this case the mechanism is
not PO. Agent $3$ will get utility $0.3$ if she takes $v_{2}$ and agent $2$
gets $v_{1}$ which results in a Pareto improvement hence showing the mechanism
is not PO.

We have exhausted all the cases and found that in each case, either IR, SP, or
PO is violated. ∎

Next, we show that if agents are allowed to express certain neighbors as
unacceptable, then there is no mechanism that is PO, IR, and SP. Our proof
relies on connecting the problem with marriage markets in particular
exploiting a known impossibility result by Alcalde and Barberà (1994).

######  Theorem 3.2.

If agents are allowed to express certain agents as unacceptable, then there is
no mechanism that is PO, IR, and SP.

###### Proof.

Consider a generic instance with agents $m_{1},m_{2},w_{1},w_{2}$ and plots
$v_{1},\ldots,v_{8}$, where
$\mathcal{E}=\\{\\{v_{1},v_{2}\\},\\{v_{3},v_{4}\\},\\{v_{5},v_{6}\\},\\{v_{7},v_{8}\\}\\}$.
We assume that agents get zero value for each of the plots. For reasons that
will become clear immediately, we refer to $m_{1}$ and $m_{2}$ as men and
$w_{1}$ and $w_{2}$ as women. We suppose that men have a sufficiently large
negative value for men and women have a sufficiently large negative value for
women. Agents have strictly positive value for the members of the opposite
gender unless they express them as unacceptable.

For the input above, an agent only cares about who the agent is paired with or
whether it is alone. We partition the set of possible allocations for the
problem $I$ into classes where each class of outcomes has the same pairing
between agents. Each agent is indifferent between allocation in the same
class. Among the classes of allocations, we call a class IR if the allocations
in the class are IR.

Next, we present a reduction from the problem of land allocation with
neighbors to the marriage market problem as follows. For a generic instance
$I$ of the form above, we can construct a corresponding instance $I^{\prime}$
of a marriage market involving two men and two women in which men have
preferences over women and women have preferences over men. In particular, for
instance $I^{\prime}$ the preferences of men over women and of women over men
is the same as in $I$. In problem instance $I^{\prime}$ there are no plots.
For a marriage market, an outcome is a matching between men and women.

Next, we prove the following claim.

######  Claim.

There is a one-to-one correspondence between IR classes of allocations for $I$
and matchings for $I^{\prime}$.

###### Proof.

For a given IR equivalence class of allocations for instance $I$, there is a
corresponding matching for instance $I^{\prime}$ in which a man and women are
matched for $I^{\prime}$ if they were neighbors for the allocation under $I$.
Coversely, for a matching for $I^{\prime}$, there is a corresponding class of
allocation for $I$ in which matched man-woman pairs are neighbors. We have
established a one-to-one correspondence between IR classes of allocations for
$I$ and matchings for $I^{\prime}$. ∎

We note that in the one-to-one correspondence between IR classes of
allocations for $I$ and matchings for $I^{\prime}$, agents have the same
preferences over the corresponding outcomes. Alcalde and Barberà (1994) in the
proof of their Proposition 1 showed that for marriage problem with two men and
two women, there exists no IR, PO, and strategyproof mechanism. The same
statement also follows for our setting because we have designed a reduction
from $I$ to $I^{\prime}$ for which our claim holds: there is a one-to-one
correspondence between IR classes of allocations for $I$ and matchings for
$I^{\prime}$. If we wish to keep the number of agents the same as the number
of plots, we can create four dummy agents who do not derive or provide value
by being neighbors. ∎

We conclude with three remarks.

######  Remark 1 (Cardinal versus Ordinal Preferences).

We note that we have framed the setting in a manner that is consistent with
that of Elkind et al. (2020). However, the model that we consider as well as
the results do need to assume additive utilities. They also hold if agents
have ordinal preferences over outcomes.

######  Remark 2 (Independence of the axioms).

Each pair of the properties from IR, PO, and SP are compatible. An IR and PO
outcome exists by starting from an IR outcome and repeatedly getting Pareto
improvements until no further Pareto improvement can be achieved. SP and IR
are compatible because there is an option to not allocate any plot. SP and PO
are also compatible via the generalized serial dictatorship mechanism studied
by Aziz et al. (2013).

######  Remark 3 (Computation).

We have not discussed computational issues up till this point. We note that
computing a Pareto optimal outcome is NP-hard even if the plots are in pairs
and agents have additively separable 1-0 utilities over plots and over
neighbors. The argument is as follows. Chan et al. (2016) proved that
maximizing social welfare for room-roommate games is NP-hard even if agents
have additively separable 1-0 utilities over rooms and over roommates. If one
examines the reduction, it also proves that even checking whether each agent
gets a most preferred outcome is NP-complete. It follows then from Lemma 1 of
Aziz et al. (2013) that computing a PO outcome is NP-hard.

## References

  * Abdulkadiroğlu and Sönmez (1998) A. Abdulkadiroğlu and T. Sönmez.  Random serial dictatorship and the core from random endowments in house allocation problems.  _Econometrica_ , 66(3):689–701, 1998.
  * Alcalde and Barberà (1994) J. Alcalde and S. Barberà.  Top dominance and the possibility of strategy-proof stable solutions to matching problems.  _Economic Theory_ , 4(3):417–435, 1994.
  * Aziz and Savani (2016) H. Aziz and R. Savani.  Hedonic games.  In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, _Handbook of Computational Social Choice_ , chapter 15. Cambridge University Press, 2016.
  * Aziz et al. (2013) H. Aziz, F. Brandt, and P. Harrenstein.  Pareto optimality in coalition formation.  _Games and Economic Behavior_ , 82:562–581, 2013.
  * Chan et al. (2016) P. H. Chan, X. Huang, Z. Liu, C. Zhang, and S. Zhang.  Assignment and pricing in roommate market.  In _Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI)_ , pages 446–452. AAAI Press, 2016.
  * Elkind et al. (2020) E. Elkind, N. Patel, A. Tsang, and Y. Zick.  Keeping your friends close: Land allocation with friends.  _CoRR_ , abs/2003.03558, 2020.  URL https://arxiv.org/abs/2003.03558.
  * Manlove (2013) D. F. Manlove.  _Algorithmics of Matching Under Preferences_.  World Scientific Publishing Company, 2013.
  * Svensson (1999) L-G Svensson.  Strategy-proof allocation of indivisible goods.  _Social Choice and Welfare_ , 16(4):557–567, 1999\.