# A Parallel Dynamic Epistemic Perspective over
Muddy Children Puzzle

Bogdan Macovei Department of Computer Science
Faculty of Mathematics and Computer Science
University of Bucharest, Academiei 14, 010014 Bucharest, Romania

Research Center for Logic, Optimization and Security (LOS)
Department of Computer Science, Faculty of Mathematics and Computer Science,
University of Bucharest, Academiei 14, 010014 Bucharest, Romania
los.cs.unibuc.ro<EMAIL_ADDRESS>
###### Abstract

Epistemic protocols represents a current field of interest, with numerous
approaches still being studied. In this paper we formalize parallel sessions
of the The Muddy Children Puzzle using Public Observation Logic, a system that
allows epistemic update. We consider agents with roles in multiple sessions
and the information update in all parallel sessions as new information is
discovered in any particular session.

##  1 Introduction

In this article, we introduce a formalism to analyze the parallel execution of
actions in the epistemic protocol of the Muddy Children Puzzle, previously
modeled using public announcement logic in [5]. We consider agents with roles
in multiple sessions and the information update in all parallel sessions as
new information is discovered in any particular session. Although the
formalism is specifically tailored to model this protocol, it can be
generalized since its theoretical framework is based on [6], where a logical
system starting from generic actions is defined. Our goal is to investigate
how parallel sessions interact and how agents’ information is modified not
only within a single session but also in a parallel setting.

In the second section, we introduce the public observation logic system, based
on [6]; in the third section, we model the Muddy Children Puzzle protocol
using this formalism, starting from the description in [5]; in the fourth
section, we construct the parallel sessions and define a method of information
propagation between these sessions to maintain consistency in the main
parallel model; in the fifth section, we provide an example of such a parallel
framework where we study the speed of information propagation and how the
number of actions required to reach a result decreases with this update.
Finally, we present some conclusions and future directions for further
research.

##  2 Preliminaries

In this preliminary section, we will present the main results from [6], where
a new logical system, public observation logic, is defined. This system is
built upon notions such as observations and expectation models, which are
based on epistemic models. These concepts will be used in the formalism we
will propose later to define a modeling for the Muddy Children Puzzle.

Let AGENT be a finite set of agents, $\Phi$ be a set of formulas, with
$\Phi_{0}\subseteq\Phi$ the set of atomic propositions.

######  Definition 2.1 (Epistemic model).

An epistemic model $\mathcal{M}$ is $\mathcal{M}=(W,R,V)$, where $W$ is a non-
empty set of worlds, $R\subseteq W^{2}$ is a binary accessibility relation,
$R=\\{R_{a}\mid a\in\text{\footnotesize AGENT}\\}$, and
$V:\Phi\to\mathcal{P}(W)$ is the valuation function, assigning to each formula
the set of worlds where formula is true.

Additionally, the authors of [6] introduce observation expressions, as regular
expressions over a finite set of actions, named $\Sigma$.

######  Definition 2.2 (Observation expressions).

Given a finite set of action symbols $\Sigma$, the language
$\mathcal{L}_{obs}$ of observation expressions is defined by:

$\displaystyle\pi::=\delta\mid\varepsilon\mid\pi\cdot\pi\mid\pi+\pi\mid\pi^{*}$
(1)

where $\delta$ is the empty action, with a corresponding empty set $\emptyset$
of observations, the constant $\varepsilon$ represents the empty string, and
$a\in\Sigma$.

######  Definition 2.3 (Observations).

Given an observation expression $\pi$, the corresponding set of observations,
that is denoted by $\mathcal{L}(\pi)$ is the set of finite string over
$\Sigma$, defined as follows:

$\mathcal{L}(\delta)=\emptyset$ | $\mathcal{L}(\pi_{1}\cdot\pi_{2})=\\{vw\mid v\in\mathcal{L}(\pi_{1})\text{ and }w\in\mathcal{L}(\pi_{2})\\}$
---|---
$\mathcal{L}(\varepsilon)=\\{\epsilon\\}$ | $\mathcal{L}(\pi_{1}\cup\pi_{2})=\mathcal{L}(\pi_{1})+\mathcal{L}(\pi_{2})$
$\mathcal{L}(a)=\\{a\\}$ | $\mathcal{L}(\pi^{*})=\\{\varepsilon\\}\cup\bigcup_{n>0}\mathcal{L}(\underbrace{\pi;\pi;\dots;\pi}_{n\text{ times}})$

######  Definition 2.4 (Epistemic expectation model).

An epistemic expectation model $\mathcal{M}_{exp}$ is a quadruple
$\mathcal{M}_{exp}=(W,R,V,Exp)$, where $(W,R,V)$ is an epistemic model, also
named the epistemic skeleton of $\mathcal{M}_{exp}$, and
$Exp:W\to\mathcal{L}_{obs}$ is an expected observation function, assigning to
each state an observation expression $\pi$, such that
$\mathcal{L}(\pi)\neq\emptyset$.

With these notions defined, there is introduced a new formalism, named Public
observation logic, that is a dynamic logic with knowledge operators, made to
reason about knowledge via the matching of observations and expectations.

######  Definition 2.5 (Update by observation).

Let $\alpha$ be an observation over $\Sigma$, and let
$\mathcal{M}=(W,R,V,Exp)$ be an epistemic expectation model. The updated model
$\mathcal{M}|_{\alpha}$ is defined as
$\mathcal{M}|_{\alpha}=(W^{\prime},R^{\prime},V^{\prime},Exp^{\prime})$, where
$W^{\prime}:=\\{w\mid\mathcal{L}(Exp(w)-\alpha)\neq\emptyset\\}$,
$R^{\prime}=R|_{W^{\prime 2}}$, $V^{\prime}=V|_{W^{\prime}}$, and
$Exp^{\prime}(w)=Exp(w)-\alpha$. Here, $\pi-\alpha$ is defined as
$\pi-\alpha=\\{\beta\mid\alpha\beta\in\mathcal{L}(\pi)\\}$, the right
residuation with respect to the monoid $(\Sigma^{*},\cdot,\varepsilon)$.

######  Definition 2.6 (Public observation logic).

The formula $\varphi$ of POL (Public Observation Logic) are given by the
following BNF:

$\displaystyle\varphi::=\top\mid p\mid\neg\varphi\mid\varphi\land\varphi\mid
K_{a}\varphi\mid[\pi]\varphi$ (2)

where $p\in\Phi_{0}$ and for any $a\in\text{\footnotesize AGENT}$, $K_{a}$ is
the knowledge operator corresponding to agent $a$.

######  Definition 2.7 (Truth definition for POL).

Given an epistemic expectation model $\mathcal{M}=(W,R,V,Exp)$, a state $w\in
W$ and a POL-formula $\varphi$, the truth of $\varphi$ at $w$, denoted by
$\mathcal{M},w\models\varphi$ is defined as follows:

$\displaystyle\mathcal{M},w$ $\displaystyle\models p\iff w\in V(p)$ (3)
$\displaystyle\mathcal{M},w$
$\displaystyle\models\varphi\land\psi\iff\mathcal{M},w\models\varphi\text{ and
}\mathcal{M},w\models\psi$ (4) $\displaystyle\mathcal{M},w$
$\displaystyle\models\neg\varphi\iff\mathcal{M},w\not\models\varphi$ (5)
$\displaystyle\mathcal{M},w$ $\displaystyle\models K_{i}\varphi\iff\text{for
all }v\text{ such that }(w,v)\in R_{i}\text{ it holds
}\mathcal{M},v\models\varphi$ (6) $\displaystyle\mathcal{M},w$
$\displaystyle\models[\pi]\varphi\iff\text{for all
}\alpha\in\mathcal{L}(\pi),\text{ if }\alpha\in\text{init}(Exp(w)),\text{ then
}\mathcal{M}|_{\alpha},w\models\varphi$ (7)

where $\alpha\in\text{init}(\pi)$ if and only if there is a
$\beta\in\Sigma^{*}$ such that $\alpha\beta\in\mathcal{L}(\pi)$.

##  3 Muddy Children Puzzle: formalization in POL

The Muddy Children Puzzle represents a scenario where a group of children who
have been playing outside is called into their house by their father. Some of
the children have mud on their foreheads, others don’t, and none of them know
their own state. Knowing that they can all see each other, but don’t know
anything about their own situation, the father initially announces them that
at least one child is muddy, then asks them who is certain that they have mud
on their forehead. In this scenario, we assume that the children reason
correctly from a logical point of view and know how to update their
information based on their father’s question. If a solution has not been
reached yet, the father does nothing else but repeat the request until a final
resolution is achieved, where all the muddy children are aware of their own
state, so the ones who are not muddy will also know this fact.

We will model the Muddy Children Puzzle starting from the description in [5]
(where the problem was modeled using Public announcement logic), but using the
formalism of Public observation logic. In this case, instead of updating the
model based on formulas, we will update it based on certain actions, and the
main action consists of the successive questions that the father addresses.

Let AGENT be a finite set of agents, with $|\text{\footnotesize
AGENT}|=n_{a}$, that we will denote with the first letters of the alphabet,
$a$, $b$, $c$, $\dots$ during the specification of our protocols. In order to
formalize the Muddy Children Puzzle, we will define one set of formulas
$\Phi$, where $\Phi_{0}\subseteq\Phi$ is the set of atomic propositions, and
one set of actions $\Pi$, with $\Pi_{0}\subseteq\Pi$ contains one atomic
action, QF, the father’s question. Each time when the action is performed, the
general knowledge is changed and the agents enrich their individual knowledge.
We will number the father’s questions to be able to update the model
sequentially based on the information obtained at each step.

For any $a\in\text{\footnotesize AGENT}$, $\Phi_{0}$ contains one atomic
proposition $m_{a}$, that is true if $a$ is muddy, and false otherwise.

######  Definition 3.1.

Given a finite set of atomic actions, $\Pi_{0}=\\{\text{QF}\\}$, we define the
$\mathcal{L}_{\Pi}$ language by the following BNF grammar:

$\displaystyle\pi::=\lambda\mid\text{QF}\mid\pi;\pi\mid\pi\cup\pi\mid\pi^{*}$
(8)

where $\lambda$ stands for the empty action, with a corresponding empty set of
actions.

We introduce the notation
$\text{QF}_{i}:=\underbrace{\text{QF};\dots;\text{QF}}_{i\text{ times}}$

######  Definition 3.2.

Given an action $\pi$, we define the corresponding set of actions
$\mathcal{L}(\pi)$ as follows:

$\mathcal{L}(\lambda)=\emptyset$ | $\mathcal{L}(\pi_{1};\pi_{2})=\\{vw\mid v\in\mathcal{L}(\pi_{1})\text{ and }w\in\mathcal{L}(\pi_{2})\\}$
---|---
$\mathcal{L}(\text{QF})=\\{\text{QF}\\}$ | $\mathcal{L}(\pi_{1}\cup\pi_{2})=\mathcal{L}(\pi_{1})\cup\mathcal{L}(\pi_{2})$
|
$\mathcal{L}(\pi^{*})=\\{\lambda\\}\cup\bigcup_{n>0}\mathcal{L}(\underbrace{\pi;\pi;\dots;\pi}_{n\text{
times}})$

In the following, let $\mathcal{M}=(W,R,V,Exp)$ be an epistemic expectations
model, where the set of possible worlds $W$ consists of ordered pairs
$(w_{a_{1}},\dots,w_{n_{a}})\in\\{0,1\\}^{n_{a}}$. Each $w_{a_{i}}$ for
$a_{i}\in\text{\footnotesize AGENT}$ describe either if $a_{i}$ is muddy or
not. We denote that property by the predicate muddy, defined as, for every
agent $a$ and for every pair $w$, $\textbf{muddy}(a,w)=0$ if $a$ is not muddy
and $\textbf{muddy}(a,w)=1$ if $a$ is muddy.

######  Definition 3.3 (State property).

Let $a\in\text{\footnotesize AGENT}$ and let $w\in W$, where
$\text{\footnotesize AGENT}=\\{a_{1},\dots,a,\dots,a_{n_{a}}\\}$, where $a$ is
on the $p$-th position, $0<p\leq N$. Then
$\textbf{muddy}(a,w)=\textbf{proj}_{p}(w)$, where proj is the projection
function: for a pair $x=(x_{1},\dots,x_{n})$, $\textbf{proj}_{i}(x)$ returns
the value of the $i$-th component $x_{i}$, $0<i\leq n$.

######  Definition 3.4 (Model property).

Let $a\in\text{\footnotesize AGENT}$. We define $\textbf{muddy}(a)$ as:

$\displaystyle\textbf{muddy}(a)=\left\\{\begin{array}[]{ll}0,&\text{ if
}\bigcap\\{\textbf{muddy}(a,w)\mid w\in W\\}=\\{0\\}\\\ 1,&\text{ if
}\bigcap\\{\textbf{muddy}(a,w)\mid w\in W\\}=\\{1\\}\\\
\text{undefined},&\text{ if }\bigcap\\{\textbf{muddy}(a,w)\mid w\in
W\\}=\emptyset\end{array}\right.$ (12)

By abuse of notation, when $\textbf{muddy}(a)$ is defined and there is no risk
for confusion, we will use muddy as a predicate.

This predicate can also be defined as:

$\displaystyle\textbf{muddy}(a)=1$ $\displaystyle\iff\text{for all }w\in
W,\mathcal{M},w\models K_{a}m_{a}$ (13) $\displaystyle\textbf{muddy}(a)=0$
$\displaystyle\iff\text{for all }w\in W,\mathcal{M},w\models K_{a}\neg m_{a}$
(14) $\displaystyle\textbf{muddy}(a)=\text{undefined}$
$\displaystyle\iff\text{otherwise }$ (15)

######  Definition 3.5.

Let $\mathcal{M}=(W,R,V)$ be an epistemic (Kripke) model, and
$Exp:W\to\mathcal{L}_{\Pi}$ an expectation function that assigns to each state
an action $\pi$ such that $\mathcal{L}(\pi)\neq\emptyset$. Then,
$\mathcal{M}_{exp}=(\mathcal{M},Exp)$ is an epistemic expectations model.

######  Definition 3.6.

Let $w$ be an action over $\Pi$ and let $\mathcal{M}_{Exp}=(W,R,V,Exp)$ be an
expectation model. The updated model is
$\mathcal{M}|_{\alpha}=(W^{\prime},R^{\prime},V^{\prime},Exp^{\prime})$, where
$W^{\prime}=\\{v\mid\mathcal{L}(Exp(v)-\alpha)\neq\emptyset\\}$,
$R^{\prime}=R\cap W^{\prime 2}$, $V^{\prime}=V|_{W^{\prime}}$ and for any
$v\in W$, $Exp^{\prime}(v)=Exp(v)-\alpha$.

Each action $\text{QF}_{i}$, $i\geq 0$, corresponds to the $i$-th question of
the father. For $i=0$, we have $\mathcal{M}|_{\text{QF}_{0}}:=\mathcal{M}$.
Starting from $i=1$, the states are eliminated sequentially. For $i=1$, the
state $(0,\dots,0)\in W^{n_{a}}$ is eliminated, as $\text{QF}_{1}$ is the
question that announces the existence of at least one muddy child, so
$\bigcup_{a\in\text{\footnotesize AGENT}}m_{a}$ is true:
$\mathcal{M}|_{QF_{1}}=(W^{\prime}:=W-\\{0^{n_{a}}\\},R|_{W^{\prime
2}},V|_{W^{\prime}},Exp)$, so after the first questions, we have states that
contains at least one component that is $1$. If we continue this process, we
obtain that for $\mathcal{M}|_{QF_{2}}$ there are removed all the states
containing just one muddy agent. In general, for $\mathcal{M}|_{QF_{i}}$ a set
of corresponding worlds with pairs $w\in W_{i}$ such that $w$ contain at least
$i$ values of $1$: $\sum_{j}\textbf{proj}_{j}(w)\geq i$. This fact is
supported by what happens during the father’s questions: he repeats the
questions because the agents knows whether the other agents are muddy or not,
while none knows their own state, which means that each new question confirms
to the agents that there is at least one more muddy agent they must take into
account during the inference process. At this point, we have that

$\displaystyle\mathcal{M}|_{\text{QF}_{i}}=(W^{\prime}:=W-\\{v\in
W\mid\sum_{j}\textbf{proj}_{j}(v)<i\\},R|_{W^{\prime
2}},V|_{W^{\prime}},Exp^{\prime})$ (16)

Formulas are defined by the following BNF grammar:

$\displaystyle\varphi::=p\mid\neg\varphi\mid\varphi\lor\varphi\mid
K_{a}\varphi\mid[\pi]\varphi$ (17)

where $p\in\Phi_{0}$ is an atomic formula, and $a\in\text{\footnotesize
AGENT}$.

The interpretation of formulas is as follows:

$\displaystyle\mathcal{M},w$ $\displaystyle\models p\iff w\in V(p)$ (18)
$\displaystyle\mathcal{M},w$
$\displaystyle\models\varphi\land\psi\iff\mathcal{M},w\models\varphi\text{ and
}\mathcal{M},w\models\psi$ (19) $\displaystyle\mathcal{M},w$
$\displaystyle\models\neg\varphi\iff\mathcal{M},w\not\models\varphi$ (20)
$\displaystyle\mathcal{M},w$ $\displaystyle\models K_{i}\varphi\iff\text{for
all }v\text{ such that }(w,v)\in R_{i}\text{ it holds
}\mathcal{M},v\models\varphi$ (21) $\displaystyle\mathcal{M},w$
$\displaystyle\models[\pi]\varphi\iff\text{for all
}\alpha\in\mathcal{L}(\pi),\text{ if exists }v\text{ such that
}Exp(v)=\alpha;\pi_{1};\dots;\pi_{n},$ (22) $\displaystyle\ \ \ \ \ \text{
then }\mathcal{M}|_{\alpha},w\models\varphi$

The deductive system contains all instances of propositional tautologies, to
which are added the following axioms ([5], [3]):

$(A_{1})$ | $K_{a}(\varphi\to\psi)\to(K_{a}\varphi\to K_{a}\psi)$ | distributivity of K
---|---|---
$(A_{2})$ | $K_{a}\varphi\to\varphi$ | truth
$(A_{3})$ | $K_{a}\varphi\to K_{a}K_{a}\varphi$ | positive introspection
$(A_{4})$ | $\neg K_{a}\varphi\to K_{a}\neg K_{a}\varphi$ | negative introspection
$(A_{5})$ | $[\pi](\varphi\to\psi)\to([\pi]\varphi\to[\pi]\psi)$ | distributivity of $\pi$
$(A_{6})$ | $[\pi](\varphi\land\psi)\leftrightarrow[\pi]\varphi\land[\pi]\psi$ | distributivity over conjunction
$(A_{7})$ | $[\pi_{1};\pi_{2}]\varphi\leftrightarrow[\pi_{1}][\pi_{2}]\varphi$ | sequential operator
$(A_{8})$ | $[\pi_{1}\cup\pi_{2}]\varphi\leftrightarrow[\pi_{1}]\varphi\land[\pi_{2}]\psi$ | choice
$(A_{9})$ | $\varphi\land[\pi][\pi^{*}]\varphi\leftrightarrow[\pi^{*}]\varphi$ | Kleene star
$(A_{10})$ | $\varphi\land[\pi^{*}](\varphi\to[\pi]\varphi)\to[\pi^{*}]\varphi$ | induction axiom

The deduction rules are:  $\text{\footnotesize MP }\frac{\varphi\hskip
5.69046pt\varphi\to\psi}{\psi}$ $\text{\footnotesize NEC
}\frac{\varphi}{K_{a}\varphi}$ $\text{\footnotesize GEN
}\frac{\varphi}{[\pi]\varphi}$

######  Theorem 1.

For $n>1$, there are $n+1$ questions needed to discover $n$ muddy children.

###### Proof.

The proof for this theorem is well-known [2], but we will sketch it for our
system.

Let $\mathcal{M}=(W,R,V,Exp)$ be an epistemic model for Muddy Children Puzzle
and let $n$ be the number of muddy agents. We want to prove that, after $n+1$
questions, every agent knows either if it is muddy or not:

$\mathcal{M}|_{\text{QF}_{n+1}}\models\bigwedge_{\begin{subarray}{c}a\in\text{\footnotesize
AGENT}\end{subarray}}K_{a}m_{a}$

We will prove that by induction over $n$.

  * •

$\textit{base case }(n=1)\Rightarrow$ there are 2 father’s questions QF needed
to discover one muddy agent. After the first one, the state $0^{n}$ is
removed. After the second question, there is just one muddy agent $a_{m}$ that
sees $n-1$ non-muddy other agents, and with the $0^{n}$ state removed, this
agent knows that is muddy:

$\bigwedge_{\begin{subarray}{c}a\in\text{\footnotesize AGENT}\\\ a\neq
a_{m}\end{subarray}}K_{a_{m}}\neg m_{a}\land K_{a}m_{a_{m}}$

  * •

$\textit{induction step}\Rightarrow$ there are already $n$ asked questions
and, based on that, $n-1$ identified muddy agents. We want to prove that if we
add a new muddy agent, there will be one additional question. In this
$\mathcal{M}|_{\text{QF}_{n}}$ model, where is just one world left, $w\in
W_{n}$, such that there are $n-1$ values of $1$. If we have an additional
agent, which we will represent as the last component of the pair, without
losing generality, then we will not be able to distinguish between states
$(w,0)$ and $(w,1)$. With a new question, the agent is able to make the
inference and to figure wheter it is muddy or not.

∎

##  4 Muddy Children Puzzle with parallel sessions

In the parallel setup, we consider that the puzzle unfolds simultaneously in
multiple sessions. Each session is just a regular sequence of actions, so for
each group, there is a father who addresses the questions, and the model
updates based on these actions. However, there are agents who can be
simultaneously present in multiple such groups, which makes them agents
playing in multiple sessions simultaneously. In this case, instead of just
having a number of independent parallel sessions, the sessions interact with
each other through the knowledge of agents who play simultaneously in at least
two sessions. If an agent finds out from one session that they are muddy (or
not), they actually possess this information in all other sessions as well.

Let SESSION be a finite set of sessions. For every session
$s\in\text{\footnotesize SESSION}$, we have a finite set of agents
$\text{\footnotesize AGENT}_{s}$. Given a finite set of atomic actions on
sessions, $\Pi_{0}=\\{\text{QF}^{s}\\}|_{s\in\text{\footnotesize SESSION}}$,
we define the $\mathcal{L}_{\Pi}$ language by the following BNF grammar:

$\displaystyle\pi::=\lambda\mid\text{QF}^{s}\mid\pi;\pi\mid\pi\cup\pi\mid\pi^{*}$
(23)

where $\lambda$ stands for the empty action, $s\in\text{\footnotesize
SESSION}$ and $a\in\text{\footnotesize AGENT}_{s}$.

######  Definition 4.1 (Session model).

A session model $\mathcal{M}_{s}$ is defined as an expectation model
$\mathcal{M}_{s}$, where $\mathcal{M}_{s}=(W_{s},R_{s},V_{s},Exp_{s})$ and
$s\in\text{\footnotesize SESSION}$ is a session; $W_{s}$ is a finite set of
worlds on the session $s$, $R_{s}\subseteq W_{s}\times W_{s}$ is the binary
accessibility relation between worlds, $V_{s}:\Phi\to W_{s}$ is the valuation
function and $Exp_{s}:W_{s}\to\mathcal{L}_{\Pi}$ the expectation assignment
for states.

######  Definition 4.2 (Parallel model).

A parallel model $\mathcal{M}$ is defined as
$\mathcal{M}=\mathcal{M}_{s_{1}}\times\mathcal{M}_{s_{2}}\times\dots\times\mathcal{M}_{s_{n_{s}}}=\bigtimes_{i=1}^{n_{s}}\mathcal{M}_{s_{i}}$,
where $\text{\footnotesize SESSION}=\\{s_{1},s_{2},\dots,s_{n_{s}}\\}$, and
for an arbitrary $s\in\text{\footnotesize SESSION}$,
$\mathcal{M}_{s}=(W_{s},R_{s},V_{s},Exp_{s})$ is a session model.

Suppose that we have a parallel model $\mathcal{M}$ that consists of $n_{s}$
session models, so $\mathcal{M}=\bigtimes_{i}\mathcal{M}_{i}$. We know that,
for every model, we have an initial set of worlds
$W_{s}=\\{0,1\\}^{|\text{\footnotesize AGENT}_{s}|}$, where $0$ means that the
property doesn’t hold (for an agent $a$, we have that $a$ is not muddy), and
$1$ means that the property holds (for an agent $a$, we have that $a$ is
muddy). The $(\text{\footnotesize AGENT}_{s})_{s\in\text{\footnotesize
SESSION}}$ sets are not mutual disjunctive: for
$s_{i},s_{j}\in\text{\footnotesize SESSION}$, $s_{i}\neq s_{j}$, is it
possible that $\text{\footnotesize AGENT}_{s_{i}}\cap\text{\footnotesize
AGENT}_{s_{j}}\neq\emptyset$. In that case, imagine that an action
$\alpha_{s_{i}}$ occurs in the $i$-th model, $0<i\leq|\text{\footnotesize
SESSION}|$ (so we have a formula
$[\beta_{1};\beta_{2};\dots;\alpha_{s_{i}};\dots;\beta_{n}]\varphi$, where
$\beta_{1},\dots,\beta_{n}\in\Pi$ are also actions that occurs in the $i$-th
model, and $\varphi\in\Phi$), that changes the model with respect to updated
model definition; we will have that model updated, so
$\mathcal{M}_{i}:=\mathcal{M}|_{\alpha_{s_{i}}}$. But there is the following
problem: imagine that in the new $\mathcal{M}_{i}$ model, we obtained a new
set of worlds $W_{i}$ that, for an arbitrary agent $a$, we know whether
$\textbf{muddy}(a)$ is either 0 or 1, and that agent also appears in other
session models
$\mathcal{M}_{k_{1}},\mathcal{M}_{k_{2}},\dots,\mathcal{M}_{k_{p}}$. In that
case, we have to also update these models with respect to the new
restrictions.

We define
$\textbf{propagate}(\alpha_{s_{i}},\mathcal{M}_{s_{j}})=(W^{\prime}_{j},R_{j}|_{W^{\prime
2}_{j}},V_{j}|_{W^{\prime}_{j}},Exp_{j})$, where $W^{\prime}_{j}$ contains all
the worlds from $W_{j}$, but without the worlds that doesn’t have the same
value of the property for the agent $a$ as in
$\mathcal{M}_{i}|_{\alpha_{s_{i}}}$. If the position for the agent $a$ is
$i_{a}$ and the property value is 0 (1), we will remove from $W_{j}$ all the
worlds that have 1 (0) on the $i_{a}$-th position.

######  Definition 4.3 (Propagate actions).

Let $s_{i}\in\text{\footnotesize SESSION}$ and let $\alpha_{s_{i}}$ be an
action that occurs on the $i$-th session. We define the propagation on the
$\mathcal{M}_{s_{j}}$ models, ($s_{i}\neq s_{j}$ and for any $j$ in this case,
$s_{j}\in\text{\footnotesize SESSION}$) by:

$\displaystyle\textbf{propagate}(\alpha_{s_{i}},\mathcal{M}_{s_{j}})=(W^{\prime}_{j},R_{j}|_{W^{\prime
2}_{j}},V_{j}|_{W^{\prime}_{j}},Exp_{j})$ (24)

where $W^{\prime}_{j}$ is defined as:

$\displaystyle
W^{\prime}_{j}:=W_{j}-\bigcup_{\begin{subarray}{c}a\in\text{\footnotesize
AGENT}_{s_{i}}\cap\text{\footnotesize AGENT}_{s_{j}}\\\
\textbf{muddy}_{s_{i}}(a)\text{ is defined}\end{subarray}}\\{v\in
W_{j}\mid\textbf{muddy}_{s_{j}}(a,v)\neq\textbf{muddy}_{s_{i}}(a)\\}$ (25)

where $\textbf{muddy}_{s_{j}}(a,v)$ is $\textbf{muddy}(a,v)$ on the $j$-th
session, and $\textbf{muddy}_{s_{i}}(a)$ is $\textbf{muddy}(a)$ on the $i$-th
session.

######  Definition 4.4 (Updated parallel model).

Let $\mathcal{M}$ be a parallel model, and $\alpha_{s_{i}}$ an action that
occurred on the $i$-th session, $0<i\leq|\text{\footnotesize SESSION}|$. Then

$\displaystyle\mathcal{M}|_{\alpha_{s_{i}}}=\bigtimes_{j<i}\textbf{propagate}\big{(}\alpha_{s_{i}},\mathcal{M}_{s_{j}}\big{)}\times\mathcal{M}|_{\alpha_{s_{i}}}\times\bigtimes_{i<j}\textbf{propagate}\big{(}\alpha_{s_{i}},\mathcal{M}_{s_{j}}\big{)}$
(26)

is the updated parallel model.

##  5 Application

In this section, we present a concrete parallel setting, and we study how the
session models interact. We have the following setup:

  1. 1.

$\text{\footnotesize SESSION}=\\{s_{1},s_{2},s_{3}\\}$;

  2. 2.

$\text{\footnotesize AGENT}_{1}=\\{a,b\\}$, $\text{\footnotesize
AGENT}_{2}=\\{b,c,d\\}$ and $\text{\footnotesize AGENT}_{3}=\\{a,d\\}$;

  3. 3.

$\mathcal{M}=\mathcal{M}_{1}\times\mathcal{M}_{2}\times\mathcal{M}_{3}$;

  4. 4.

suppose that the agents $a$, $c$ and $d$ are muddy, and $b$ is not, so in
$\mathcal{M}$ holds that
$\textbf{muddy}(a)\land\neg\textbf{muddy}(b)\land\textbf{muddy}(c)\land\textbf{muddy}(d)$.

In the following, we represent the models:

($\begin{subarray}{c}m_{a}=0\\\ m_{b}=0\end{subarray}$)($\begin{subarray}{c}m_{a}=0\\\ m_{b}=1\end{subarray}$)($\begin{subarray}{c}\mathbf{m_{a}=1}\\\ \mathbf{m_{b}=0}\end{subarray}$)($\begin{subarray}{c}m_{a}=1\\\ m_{b}=1\end{subarray}$)$R_{a}$$R_{a}$$R_{b}$$R_{b}$$\mathcal{M}_{1}$ | ($\begin{subarray}{c}m_{a}=0\\\ m_{d}=0\end{subarray}$)($\begin{subarray}{c}m_{a}=0\\\ m_{d}=1\end{subarray}$)($\begin{subarray}{c}m_{a}=1\\\ m_{d}=0\end{subarray}$)($\begin{subarray}{c}\mathbf{m_{a}=1}\\\ \mathbf{m_{d}=1}\end{subarray}$)$R_{a}$$R_{a}$$R_{d}$$R_{d}$$\mathcal{M}_{3}$
---|---

$\bigg{(}\begin{subarray}{c}m_{b}=0\\\ m_{c}=0\\\
m_{d}=0\end{subarray}\bigg{)}$$\bigg{(}\begin{subarray}{c}m_{b}=0\\\
m_{c}=1\\\
m_{d}=0\end{subarray}\bigg{)}$$\bigg{(}\begin{subarray}{c}m_{b}=1\\\
m_{c}=0\\\
m_{d}=0\end{subarray}\bigg{)}$$\bigg{(}\begin{subarray}{c}m_{b}=1\\\
m_{c}=1\\\
m_{d}=0\end{subarray}\bigg{)}$$\bigg{(}\begin{subarray}{c}m_{b}=0\\\
m_{c}=0\\\
m_{d}=1\end{subarray}\bigg{)}$$\bigg{(}\begin{subarray}{c}\mathbf{m_{b}=0}\\\
\mathbf{m_{c}=1}\\\
\mathbf{m_{d}=1}\end{subarray}\bigg{)}$$\bigg{(}\begin{subarray}{c}m_{b}=1\\\
m_{c}=0\\\
m_{d}=1\end{subarray}\bigg{)}$$\bigg{(}\begin{subarray}{c}m_{b}=1\\\
m_{c}=1\\\
m_{d}=1\end{subarray}\bigg{)}$$R_{b}$$R_{b}$$R_{b}$$R_{b}$$R_{c}$$R_{c}$$R_{c}$$R_{c}$$R_{d}$$R_{d}$$R_{d}$$R_{d}$$\mathcal{M}_{2}$

Consider the scenario in which we run this models independently, so each agent
has its own scope for every scenario. Using the results of Theorem 1, we know
that for the first model are 2 questions needed (so
$\mathcal{M}_{1}\models[QF_{2}^{1}](K_{a}m_{a}\land K_{b}\neg m_{b})$), for
the second one there are 3, and for the last one also 3 questions needed. We
conclude that if we analyze this scenario in a sequential manner, there are 8
question needed to solve the puzzle. Our target is to see if the number of
questions can be minimised if we run these models in parallel.

In the parallel setting, the order of actions is non-deterministic. We will
analyze a possible situation. Suppose that the first actions that occurs are
the father’s question for the first model. We already provided that are only
two question needed to solve the puzzle, so

$\displaystyle\mathcal{M}_{1}|_{QF_{2}}=\big{(}\\{(1,0)\\},\emptyset,V_{1}|_{\\{(1,0)\\}},Exp_{1}^{\prime}\big{)}$
(27)

Bearing in mind that we run the model in parallel, instead of just updating
the $\mathcal{M}_{1}$ model, we have to update the entire model,
$\mathcal{M}$. In that case, we have to propagate the new states, so
$\mathcal{M}_{2}$ and $\mathcal{M}_{3}$ will be modified by keeping just the
states in which $m_{a}$ holds and $m_{b}$ does not.

$\displaystyle\textbf{propagate}(\text{QF}_{1},\mathcal{M}_{2})$
$\displaystyle=(W^{\prime}_{2},R_{2}^{\prime}:=R_{2}|_{W^{\prime}_{2}},V_{2}^{\prime}:=V_{2}|_{W^{\prime}_{2}},Exp_{2})$
$\displaystyle=(W_{2}-\\{v\in W_{2}\mid\textbf{muddy}_{s_{2}}(b,v)\neq
0\\},R_{2}^{\prime},V_{2}^{\prime},Exp_{2})$
$\displaystyle=(W^{\prime}_{2}:=\\{(000),(010),(011),(001)\\},R_{2}^{\prime},V_{2}^{\prime},Exp_{2})$
$\displaystyle\textbf{propagate}(\text{QF}_{1},\mathcal{M}_{3})$
$\displaystyle=(W^{\prime}_{3},R_{3}^{\prime}:=R_{3}|_{W^{\prime}_{3}},V_{3}^{\prime}:=V_{3}|_{W^{\prime}_{3}},Exp_{3})$
$\displaystyle=(W_{3}-\\{v\in W_{3}\mid\textbf{muddy}_{s_{3}}(a,v)\neq
1\\},R_{3}^{\prime},V_{3}^{\prime},Exp_{3})$
$\displaystyle=(\\{W^{\prime}_{3}:=(10),(11)\\},R_{3}^{\prime},V_{3}^{\prime},Exp_{3})$

We represent the new $\mathcal{M}|_{QF_{1}}$ model as:

($\begin{subarray}{c}\mathbf{m_{a}=1}\\\
\mathbf{m_{b}=0}\end{subarray}$)$\mathcal{M}_{1}|_{QF_{1}}$$\bigg{(}\begin{subarray}{c}m_{b}=0\\\
m_{c}=0\\\
m_{d}=0\end{subarray}\bigg{)}$$\bigg{(}\begin{subarray}{c}m_{b}=0\\\
m_{c}=1\\\
m_{d}=0\end{subarray}\bigg{)}$$\bigg{(}\begin{subarray}{c}m_{b}=0\\\
m_{c}=0\\\
m_{d}=1\end{subarray}\bigg{)}$$\bigg{(}\begin{subarray}{c}\mathbf{m_{b}=0}\\\
\mathbf{m_{c}=1}\\\
\mathbf{m_{d}=1}\end{subarray}\bigg{)}$$R_{c}$$R_{c}$$R_{d}$$R_{d}$$\textbf{propagate}(\text{QF}_{1},\mathcal{M}_{2})$($\begin{subarray}{c}m_{a}=1\\\
m_{d}=0\end{subarray}$)($\begin{subarray}{c}\mathbf{m_{a}=1}\\\
\mathbf{m_{d}=1}\end{subarray}$)$R_{d}$$\textbf{propagate}(\text{QF}_{1},\mathcal{M}_{3})$

Suppose that the next action is father’s question in $\mathcal{M}_{3}$. The
agent $a$ already knows that $\textbf{muddy}(a)$ holds, so by seeing $d$ can
answer the question by $\textbf{muddy}(a)\land\textbf{muddy}(d)$. We also have
a propagation, that transforms $\mathcal{M}_{2}$ into a model with two worlds,
$W_{2}=\\{(0,1,1),(0,0,1)\\}$. After the father’s question, both $b$ and $d$
cand solve the puzzle, by seeing that $c$ is also muddy. In this setting, we
only needed four father’s questions instead of eight.

## Conclusion and Further Work

The formalism for representing parallel models presented in this article,
using the Muddy Children Puzzle as an example, is based on POL (public
observation logic [6]) and builds upon the modeling in PAL (public
announcement logic [5]). In POL, observations are seen as strings over an
alphabet $\Sigma$, which we replaced in our formalism with actions. For the
specific problem we presented, the only actions considered are represented by
the father’s questions QF. Although our aim was to demonstrate how information
can be propagated in parallel sessions for a simple case, this approach can be
generalized and applied to the analysis of security protocols.

In [4], we introduced a formalism for analyzing security protocols that use
symmetric key cryptography (called DELP, dynamic epistemic logic for
protocols), also starting from POL but providing a different semantics for
actions ($[\pi]\varphi$). An idea for future work is to combine DELP with the
method of transmitting information in parallel across multiple sessions to
study various types of attacks. This integration could enable a more
comprehensive analysis of security protocols, incorporating the dynamics of
information updates and potential attacks in a parallel setting. By combining
the concepts from DELP and the parallel model, security analysts can
investigate how various security protocols perform under different conditions
and explore possible vulnerabilities in a more intricate scenario.

## References

  * [1]
  * [2] Nina Gierasimczuk & Jakub Szymanik (2011): _A note on a generalization of the muddy children puzzle_.  In: Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge, pp. 257–264, 10.1145/2000378.2000409.
  * [3] David Harel, Dexter Kozen & Jerzy Tiuryn (2001): _Dynamic logic_.  ACM SIGACT News 32(1), pp. 66–69, 10.1145/568438.568456.
  * [4] Ioana Leuştean & Bogdan Macovei (2021): _DELP: Dynamic Epistemic Logic for Security Protocols_.  In: 2021 23rd International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), IEEE, pp. 275–282, 10.1109/SYNASC54541.2021.00053.
  * [5] Hans Van Ditmarsch, Wiebe van Der Hoek & Barteld Kooi (2007): _Dynamic epistemic logic_.  337, Springer Science & Business Media, 10.1007/978-1-4020-5839-4.
  * [6] Hans Van Ditmarsch, Sujata Ghosh, Rineke Verbrugge & Yanjing Wang (2014): _Hidden protocols: Modifying our expectations in an evolving world_.  Artificial Intelligence 208, pp. 18–40, 10.1016/j.artint.2013.12.001.


# Social Distancing via Social Scheduling

Deepesh Kumar Lall  Indian Institute of Technology Kanpur, {deepeshk, garimas,
<EMAIL_ADDRESS>Garima Shakya  Indian Institute of Technology Kanpur,
{deepeshk, garimas<EMAIL_ADDRESS>Swaprava Nath  Indian Institute of
Technology Kanpur, {deepeshk, garimas<EMAIL_ADDRESS>
###### Abstract

Motivated by the need of social distancing during a pandemic, we consider an
approach to schedule the visitors of a facility (e.g., a general store). Our
algorithms take input from the citizens and schedule the store’s discrete
time-slots based on their importance to visit the facility. Naturally, the
formulation applies to several similar problems. We consider indivisible job
requests that take single or multiple slots to complete. The salient
properties of our approach are: it (a) ensures social distancing by ensuring a
maximum population in a given time-slot at the facility, (b) aims to
prioritize individuals based on the importance of the jobs, (c) maintains
truthfulness of the reported importance by adding a cooling-off period after
their allocated time-slot, during which the individual cannot re-access the
same facility, (d) guarantees voluntary participation of the citizens, and yet
(e) is computationally tractable. The mechanisms we propose are prior-free. We
show that the problem becomes NP-complete for indivisible multi-slot demands,
and provide a polynomial-time mechanism that is truthful, individually
rational, and approximately optimal. Experiments with data collected from a
store show that visitors with more important (single-slot) jobs are allocated
more preferred slots, which comes at the cost of a longer cooling-off period
and significantly reduces social congestion. For the multi-slot jobs, our
mechanism yields reasonable approximation while reducing the computation time
significantly.

##  1 Introduction

Pandemics like the COVID-19 showed that one of the most effective solutions
against infectious diseases is social distancing [38]. Therefore, it is a
practice we ought to master and stay prepared as a preventive disease
containment measure in the future. While most citizens are willing to follow
social distancing, the lack of communication and coordination among them,
particularly prior to an immediate lockdown, overcrowds shopping centers even
though the footfalls could have been evenly distributed over the shop’s
working hours to maintain a medically recommended social distance.

In our setting, each customer has an infinite queue of jobs that have
different importances (privately known only to the customer) and lengths.
However, the customers are myopic, i.e., worries only about the last
unprocessed job. They experience a better value if the job is assigned their
preferred slots, but also a disutility to wait before submitting their next
job for allocation. All jobs are indivisible, i.e., has to be completed once
started. In this paper, we consider two settings: (i) all jobs are of single
time-slot length, (ii) different jobs are of different integral time-slot
lengths.

Though cast in the context of social scheduling for pandemics, a similar
problem arises in general scheduling settings, e.g., scheduling traffic in
freeways [2] or multi-ownership computational jobs in a single-core processor
[31]. Since all such settings have multiple agents competing for a common
resource and the importance of the jobs are private, the solutions involving
truthful revelation in a computationally tractable manner also apply to those
settings.

This paper introduces a novel approach to pandemic containment using mechanism
design that reduces the congestion in facilities, satisfies various desirable
theoretical properties, and exhibits fair performance in practice. The
following section details the contributions of this paper.

###  1.1 Brief Problem Description and Contributions

The opening hours of a facility are divided into periods (e.g., a day), each
of which has multiple slots (e.g., every hour when it is open). The customers
have an unlimited number of outstanding jobs to be processed in a sequence at
the facility, and they report the valuations of the immediate unprocessed
job.111A typical shopper knows that she needs to visit a store many times but
precisely knows the importance of the immediate visit. A valuation $v_{ij}$
denotes agent $i$’s importance for that job if it starts in slot $j$. Since
this information is private to agent $i$, a mechanism needs to elicit this
truthfully. In a setting where the agents’ preferences are private, if the
mechanism has no additional structures (e.g., transfers of payoff), only
dictatorial mechanisms (where a pre-selected agent’s favorite outcome is
always selected) are truthful [28, Thm 7.2]. Therefore, the use of transfers
in some form is inevitable to ensure truthfulness of the agents. However, for
pandemic containment, the use of money for scheduling citizens is unethical
and illegal in certain countries. Hence, we use time-delay as a replacement of
money. Waiting time is often seen as a resource that individuals agree to
trade with [24]. Our scheduling approach will work in all places where payment
can be replaced with a time-delay. Quite naturally, an agent prefers to have a
more valuable slot assigned to her with less time-delay. We model the agents’
payoffs using the well-known quasi-linear payoff model [34, Chap 10]. This
competitive scenario induces a game where agents’ actions are to report the
valuations. The agents may overstate (or understate) their actual valuations.
The contributions of this paper can be summarized into the following four
major points:

  * $\vartriangleright$

Even though maximizing the social welfare (sum of the agents’ valuations) of
the slot allocation is a combinatorial optimization problem; we show that this
problem is computationally easy to solve for jobs with single-slot length
(Theorems 1 and 2).

  * $\vartriangleright$

We show that the standard Vickrey-Clarke-Groves (VCG) payment [37, 12, 19] can
be used as the delay (cooling-off time) in this setting to ensure truthfulness
(Fact 1) and participation of the agents (Fact 2). We call the allocation and
delay together as the mechanism VCG-T (VCG with Time delays).

  * $\vartriangleright$

The welfare maximizing allocation of multi-slot jobs are computationally hard
(Theorem 3). We propose a polynomial time mechanism (Theorem 6) which ensures
participation (Theorem 4), truthfulness (Theorem 5), and is approximately
optimal (Theorem 7).

  * $\vartriangleright$

Our real and synthetic data experiments (Section 8) show that visitors with
more important jobs are allocated more preferred slots, which comes at the
cost of a longer delay to re-access the store. We show that social distancing
is significantly improved using users’ visit data from a store (Section 8.1).
For the multi-slot jobs, our approximately optimal mechanism provides a
reasonable approximation at a much reduced computational cost in practice
(Section 8.2).

The mechanisms presented in this paper are prior-free, i.e., they do not
depend on the probabilistic information of the valuations.

###  1.2 Related Work

Social distancing measures have been widely successful and recommended for
pandemic control [16, 35, 14]. However, it is also observed that the benefits
of social distancing depend on the extent to which the citizens follow it. An
extensive part of the recent research related to social distancing during
COVID19 aims to understand the relationship of social distancing with
different public policies and other factors [17, 1, 11, 26]. Individuals are
sometimes reluctant to pay the costs inherent in social distancing which can
limit its effectiveness as a control measure [27]. Toxvaerd [36] considers
social distancing in the susceptible-infected-recovered (SIR) epidemiological
model and shows that “during the equilibrium social distancing phase,
individuals gradually reduce their social distancing efforts despite the
infection probability not decreasing”. Cavallo [9] shows that under an
uncoordinated model, every equilibrium involves more social contact than it
occurs in a social optima. A related thread of social distancing measures
exists in workforce-intensive organizations in the forms of rostering,
workplace design, or allowing people to work from home [30]. However, these
measures are centrally controlled, and individuals do not have a scope to
behave strategically. On the other hand, the businesses maintain social
distancing by enforcing certain appointment booking apps (web or smartphone-
based) on customers. These apps run a first-come-first-served algorithm for
slot booking and do not provide any priority preservation guarantees.222An
example app is www.appointy.com.

Coordination among the citizens is essential for social distancing [33], but
the technology is still not much developed to address the social coordination
problem, particularly when the participants are self-interested independent
decision makers. Mechanism design is an approach which can equip an
artificially intelligent app to satisfy certain desirable properties on the
face of the participants’ strategic behavior. This is attempted in the current
paper.

Resource allocation with monetary transfers to ensure truthfulness, e.g., in
the context of jobshop scheduling [21], has a rich literature that is close to
our work. Lavi and Nisan [23] study online supply curves based auction of
identical divisible goods that ensures truthfulness. In this paper, we
consider an offline allocation problem but a comparatively more complex one
(multiple resources and indivisible tasks of different length). Chen et al.
[10] propose a truthful approximate mechanism for online allocation of job to
machines where the job can resume or restart once preempted. We provide a
comparatively better approximation ratio for efficiency, albeit in an offline
setting. The other related line of work involves designing incentives in
queueing problems with specific cost structures that aim to find an efficient
allocation truthfully and also ensures budget balance [25, 5, 15], while our
model can admit costs of any structure.

In the context of job scheduling without money, Koutsoupias [22] studies the
allocation of independent tasks to machines. Every machine reports the time it
takes to execute each task and the mechanism provides an approximation to the
minimum makespan in a truthful manner without money for one task—which can be
repeated for multiple tasks. In this paper, we maximize the sum of the
visitors’ valuations which are independent of the length of the job and
provide an approximate mechanism for multiple tasks maintaining the slot-
capacity. Braverman et al. [7] study a similar problem of the allocation of
medical treatments at hospitals that have differential costs to patients and
the patients value the hospitals differently. The waiting time before being
admitted to the hospital helps to get a stable matching. However, the value of
the agents do not change over slots and hence is different from our setting.

##  2 Single-slot Job Allocation Setup

Define $N\coloneqq\\{1,\ldots,n\\}$ to be the set of agents that are trying to
access a facility ${\cal F}$. Time is divided into periods, and each period is
further divided into slots. The set of slots is denoted by
$M\coloneqq\\{1,\ldots,m\\}$. Every slot has a maximum capacity of $k$, which
is decided by the region’s social distancing norm based on the size of the
facility.333The analysis and results will follow even if the capacity $k_{j}$
varies with the slots $j\in M$. A central planner (e.g., an AI app) allocates
these slots to the agents, maintaining the capacity constraint. Every agent
$i$ has a cardinal preference $v_{ij}\in\mathbb{R}_{\geqslant 0}$ (called the
agent’s valuation) if her immediate unprocessed job is allocated slot $j$. The
valuation implicitly reflects the importance of visiting the facility for that
agent. The valuation vector of $i$ is represented by $v_{i}=(v_{ij},j\in
M)\in\mathbb{R}_{\geqslant 0}^{m}$. In this paper, we consider different
facilities independently. The joint facility-slot allocation problem can be
modeled as a similar problem with the additional constraint that the same slot
cannot be allocated to the same agent at different facilities. We leave the
detailed analysis for it as future work.

The planner decides the allocation which can be represented as a matrix
$A=[a_{ij}]$, where $a_{ij}=1$, if agent $i$ is allotted slot $j$, and zero
otherwise. We assume that every agent can be assigned at most one slot in a
period, and the total number of agents assigned to each slot does not exceed
$k$. We denote the slot assigned to $i$ by $a_{i}^{*}$. The planner also
decides a delay $d=(d_{i},i\in N)$, where $d_{i}$ is the time-delay (in the
same unit as the valuation) of agent $i$ before which she cannot make another
request to the system. The net payoff of an agent is assumed to follow a
standard quasi-linear form [34], which implies that every agent wants a more
valued slot to be assigned to her and also wants to wait less.

$u_{i}((A,d),v_{i})=v_{i}(A)-d_{i},\text{ where }v_{i}(A)=v_{ia_{i}^{*}}.$ (1)

Denote the set of all allocations by ${\cal A}$. The delays
$d_{i}\in\mathbb{R}_{\geqslant 0},\forall i\in N$. The planner does not know
the valuations of the agents. Therefore he needs the agents to report their
valuations to decide the allocation and the delay. This leaves the opportunity
for an agent to misrepresent her true valuation. To distinguish, we use
$v_{ij}$ for the true valuation and $\hat{v}_{ij}$ for reported valuations. In
the first part of this paper, we will consider single-slot jobs and use the
shorthand $v=(v_{i})_{i\in N}$ to denote the true valuation profile
represented as an $m\times n$ real matrix, and $\hat{v}$ to denote the
reported valuation profile. The notation $v_{-i}$ denotes the valuation
profile of the agents except $i$. The decision problem of the planner is,
therefore, formally captured by the following function.

######  Definition 1 (Social Scheduling Function (SSF))

A social scheduling function (SSF) is a mapping $f:\mathbb{R}^{m\times
n}\to{\cal A}\times\mathbb{R}^{n}$ that maps the reported valuations to an
allocation and delay for every agent. Hence,
$f(\hat{v})=(A(\hat{v}),d(\hat{v}))$, where $A$ is the allocation and $d$ is
the delay function.444We overload the notation $A$ and $d$ to denote both
functions and values of those functions, since their use will be clear from
the context.

##  3 Preliminary Definitions

In this section, we formally define a few desirable properties that a social
scheduling function should satisfy. The properties address the issues of
prioritization, truthfulness, voluntary participation, and computational
complexity.

The first property ensures that the allocation is efficient in each period,
i.e., it maximizes the sum of the valuations of all the agents.

######  Definition 2 (Efficient Per Period (EPP))

An SSF $f$ is efficient per period (EPP) if at every period, it chooses an
allocation $A^{*}$ that maximizes the sum of the valuations of all the agents.
Formally, if $f(\cdot)=(A^{*}(\cdot),d(\cdot))$, then

$A^{*}(v)\in\operatorname*{\arg\\!\max}_{A\in{\cal A}}\sum_{i\in N}\sum_{j\in
M}v_{ij}a_{ij}.$ (2)

However, since the planner can only access the reported values
$\hat{v}_{i}$’s, which can be different from the true $v_{i}$’s, it is
necessary that the reported values are indeed the true values. The following
property ensures that the agents are incentivized to ‘truthfully’ reveal this
information irrespective of the reports of the other agents.

######  Definition 3 (Per Period Dominant Strategy Truthful)

An SSF $f(\cdot)=(A(\cdot),d(\cdot))$ is truthful in dominant strategies per
period if for every $v_{i},\hat{v}_{i},\hat{v}_{-i}$, and $i\in N$

$\displaystyle v_{i}(A(v_{i},\hat{v}_{-i}))-d_{i}(v_{i},\hat{v}_{-i})\geqslant
v_{i}(A(\hat{v}_{i},\hat{v}_{-i}))-d_{i}(\hat{v}_{i},\hat{v}_{-i}).$

The next property ensures that it is always weakly beneficial for every
rational agent to participate in such a mechanism.

######  Definition 4 (Individual Rationality)

An SSF $f(\cdot)=(A(\cdot),d(\cdot))$ is individually rational if for every
$v$, and $i\in N$

$\displaystyle v_{i}(A(v))-d_{i}(v)$ $\displaystyle\geqslant 0.$

Large facilities that have a large number of high-capacity slots lead to an
exponential increase in the size of the set ${\cal A}$. This largeness of
${\cal A}$ makes it challenging to find a solution quickly. There are problems
for which a quick method of solving them is not known yet. Still, a given
solution can be verified quickly in time polynomial of the input size, which
means that the given solution’s validity can be tested quickly. The complexity
class of such problems is known as NP (nondeterministic polynomial). We
consider the NP-complete class of problems, which is defined as follows.

######  Definition 5 (NP-complete)

A decision problem $Q$ is NP-complete if:

  1. 1.

$Q$ is in NP (class of all decision problems verifiable in polynomial time),
and

  2. 2.

Every problem in NP is reducible to $Q$ in polynomial time.

We will show that the slot allocation problem in a certain setting belongs to
this class.

In a practical setting, where the allocations and delays need to be decided
before every period, it is desirable to have an SSF that is computable in a
time polynomial in $n$ and $m$ so that it finishes the computation in a time
negligible to the time duration of the period. We consider algorithms that are
strongly polynomial [18]. The arithmetic model of computation defines strongly
polynomial algorithms. It is assumed that the basic arithmetic operations
(addition, subtraction, multiplication, division, and comparison) take a unit
time step to perform, regardless of the operands’ sizes.

######  Definition 6 (Strongly Polynomial)

An algorithm runs in strongly polynomial time if [18]

  * $\vartriangleright$

the number of operations in the arithmetic model of computation is bounded by
a polynomial in the number of operands in the input instance; and

  * $\vartriangleright$

the space used by the algorithm is bounded by a polynomial in the input size.

An SSF is strongly polynomial-time computable if there exists an algorithm
that computes it in a time strongly polynomial in $n$ and $m$, irrespective of
the size of the actual data, such as the value of the $v_{i}$s or $k$.

##  4 Periodic Mechanisms

We consider mechanisms that run at every period of this social scheduling
problem. The agents report their valuations at the beginning of every period.
The planner decides the schedules and delays.555For mechanisms that consider
the dynamic extension of such allocation problems with finite or infinite
horizon [4, e.g.], (a) the designer needs to know the transition
probabilities, (b) equilibrium guarantees are weaker, and (c) are
computationally expensive. These factors made us restrict our attention to
periodic mechanisms. Since the agents have the opportunity to overstate their
importance to get a better slot allotted to them, our approach that uses the
ideas of mechanism design [6] to this social scheduling problem is useful. We
use the delay as a surrogate for transferable utility among the agents to
satisfy several desirable properties. For the single-slot job setup, our
proposed mechanism is as follows.

#### Description of VCG-T.

The SSF needs to decide on the allocation $A$ and the delay $d$. VCG-T
computes the allocation as follows.

$\displaystyle\begin{split}&\operatorname*{\arg\\!\max}_{A}\sum_{j\in
M}\sum_{i\in N}v_{ij}a_{ij}\\\ &\text{s.t. }\sum_{j\in M}a_{ij}\leqslant 1,\
\forall i\in N;\ \sum_{i\in N}a_{ij}\leqslant k,\ \forall j\in M\\\
&a_{ij}\geqslant 0,\ \forall i\in N,j\in M.\end{split}$ (3)

This is an LP relaxation of the actual allocation problem, which allows
$a_{ij}$s to be only in $\\{0,1\\}$. We will show that this is without loss of
optimality since the solution to LP (3) will always be integral and will
coincide with the solution of the corresponding IP.

The delays of agents are computed via the standard VCG payment rule. Denote
the optimal allocation of LP (3) by $A^{*}(v)$. Also, denote the allocation
given by LP (3) when agent $i$ is removed from the system by
$A^{*}_{-i}(v_{-i})$. For agent $i$, the delay is given by,

$\displaystyle\begin{split}d_{i}&:=\sum_{\ell\in
N\setminus\\{i\\}}v_{\ell}(A^{*}_{-i})-\sum_{\ell\in
N\setminus\\{i\\}}v_{\ell}(A^{*}).\end{split}$ (4)

The mechanism in every period is described in Algorithm 1.

Algorithm 1 VCG-T in every period

1: Input: for every agent $i\in N$, the value $\hat{v}_{i}$

2: compute $A^{*}(\hat{v})$ (Equation 3) as the allocation

3: charge a delay $d_{i}(\hat{v})$ (Equation 4) to every $i\in N$ for which
they cannot access the scheduling mechanism again

4: Output: $A^{*}(\hat{v})$ and $d(\hat{v})$

In the following few sections, we present the theoretical results related to
single and multi-slot jobs.

##  5 Single-slot Jobs

We first show that the allocation given by VCG-T indeed maximizes per-period
social welfare.

###### Theorem 1

The allocation of VCG-T given by LP (3) always gives integral solutions.

Proof: Consider the vector
$x^{\top}=(a_{11},\ldots,a_{1m},\ldots,a_{n1},\ldots,a_{nm})$, i.e., the rows
of $A$ linearized as a vector. We can write the constraints of LP (3) in using
a $(n+m)\times nm$ constraint matrix, s.t.,

$\left(\begin{array}[]{ccccccccc}1&\ldots&1&0&\ldots&0&0&\ldots&0\\\
0&\ldots&0&1&\ldots&1&0&\ldots&0\\\ &&&&\ldots&&&&\\\
1&\ldots&0&1&\ldots&0&1&\ldots&0\\\ 0&1&\ldots&0&1&\ldots&0&1&0\\\
&&&&\ldots&&&&\end{array}\right)x\leqslant\left(\begin{array}[]{c}1\\\
\vdots\\\ k\\\ \vdots\end{array}\right)$

Denote the matrix on the LHS by $C$. The first $n$ and the next $m$ rows
correspond to the first and second set of constraints of LP (3) respectively.
We show that $C$ is totally unimodular (TU), which is sufficient to conclude
that LP (3) has integral solutions. We use the Ghouila-Houri characterization
[8] to prove that $C$ is TU. According to this characterization, a $p\times q$
matrix $C$ is TU if and only if each set $R\subseteq\\{1,2,\cdots,p\\}$ can be
partitioned into two sets $R_{1}$ and $R_{2}$, such that, $\sum\limits_{i\in
R_{1}}a_{ij}-\sum\limits_{i\in R_{2}}a_{ij}\in\\{1,0,-1\\}$, for
$j=1,2,\cdots,q$. Note that, in $C$ every column has two 1’s, one in the first
$n$ rows and one in the next $m$ rows. Pick any subset $R$ of the rows,
construct the $R_{1}$ to be the rows that come from the first $n$ rows, and
$R_{2}$ to be the rows that come from the last $m$ rows (one of these
partitions can be empty). Clearly, the difference in each column of the rows
$R$ will lie in $\\{1,0,-1\\}$. Hence proved. $\blacksquare{}$

The result above shows that the optimal solution of LP (3) is an optimal
solution of the corresponding integer program that maximizes the per-period
social welfare. Hence, we conclude the following.

###### Corollary 1

VCG-T is EPP.

Even though the LP formulation of VCG-T is without loss of optimality, in
general, LPs can be weakly polynomial, i.e., the space used by the algorithm
may not be bounded by a polynomial in the size of the input. However, we show
that an even stronger result holds for VCG-T. The forthcoming results show
that the allocation and delays of VCG-T are strongly polynomial. To show this,
we will first reduce the allocation problem (LP (3)) to a minimum weight
$b$-matching problem, which is known to be strongly polynomial [32].

Consider an edge-weighted bipartite graph $(N,M,E)$, where $N$ and $M$ are the
agent set and set of slots respectively. The set $E$ denotes the edges $(i,j)$
with weights $-v_{ij}$. The matching constraints are given by $b_{i}=1,\forall
i\in N$, and $b_{j}=k,\forall j\in M$.

###### Lemma 1

Let $E^{*}\subseteq E$ be a perfect $b$-matching in $(N,M,E)$ and
$A^{*}=[a_{ij}^{*}]_{i\in N,j\in M}$ be an allocation where
$a_{ij}^{*}=1\Leftrightarrow(i,j)\in E^{*}$. The matching $E^{*}$ is a minimum
weight perfect $b$-matching iff $A^{*}$ is an optimal solution to LP (3).

Proof: We prove this via contradiction. Suppose $A^{*}$ is not an optimal
solution to LP (3), i.e., there exists $A^{\prime}$ which satisfies the
constraints and yet gives a larger value to the objective function than that
of $A$. Hence, $\sum_{j\in M}\sum_{i\in N}v_{ij}a_{ij}^{\prime}>\sum_{j\in
M}\sum_{i\in N}v_{ij}a_{ij}^{*}$. Consider the edge set $E^{\prime}$
corresponding to $A^{\prime}$. Clearly this is a perfect $b$-matching, since
$A^{\prime}$ satisfies the constraints of LP (3), and $E^{\prime}$ gives a
lower weight than $E^{*}$, which proves that $E^{*}$ is not the minimum weight
perfect $b$-matching. The implications can be reversed to obtain the other
direction of the proof. $\blacksquare{}$

Note that the delays are calculated by solving an equivalent LP like LP (3)
with one less agent. Therefore, each of these LPs is strongly polynomial, and
the planner needs to solve $n$ of them. The computation of each delay needs
the addition of $2(n-1)$ terms and one subtraction. Hence, the number of
computations is polynomial in the number of numbers in the input instance, and
the space required is polynomial in the input size. Therefore we conclude the
following.

###### Corollary 2

The computation of the delays in VCG-T is strongly polynomial.

Combining Theorem 1, Lemma 1, and Corollary 2, we get the following result.

###### Theorem 2

VCG-T provides a combinatorial, strongly polynomial algorithm for computing a
social schedule and delays.

Since VCG-T uses the VCG payment expression to compute the time delay and
because the allocated slots are goods to the agents, the following two facts
follow from the known properties of the VCG mechanism.

###### Fact 1

VCG-T is per period dominant strategy truthful.

Proof: This proof is a standard exercise in the line of the proof for Vickery-
Clarke-Groves (VCG) mechanism [37, 12, 19].

Let us assume for the contradiction that, there exist an agent $i$ for having
true valuations for the slots as, $v_{i}$, but misreports it as
$v{{}^{\prime}}_{i}$(the corresponding value function is
$v{{}^{\prime}}_{i}$), and gets better utility. Suppose
${A}(v{{}^{\prime}}_{i},v_{-i})=A^{\prime}$ and ${A}({v}_{i},v_{-i})=A^{*}$.
The utility of $i$ for $A^{\prime}$ is:

$\displaystyle v_{i}(A^{\prime})-d_{i}(v^{\prime}_{i},v_{-i})$
$\displaystyle=v_{i}(A^{\prime})-\sum_{\ell\in
N\setminus\\{i\\}}v_{\ell}(A(v_{-i}))+\sum_{\ell\in
N\setminus\\{i\\}}v_{\ell}(A^{{}^{\prime}})$ $\displaystyle=\sum_{\ell\in
N}v_{\ell}(A^{{}^{\prime}})-\sum_{\ell\in
N\setminus\\{i\\}}v_{\ell}(A(v_{-i}))$

Similarly, the utility of $i$ for $A^{*}$ is:

$\displaystyle=\sum_{\ell\in N}v_{\ell}(A^{*})-\sum_{\ell\in
N\setminus\\{i\\}}v_{\ell}(A(v_{-i}))$

If $i$ gets better utility by misreporting her valuation as $v^{\prime}(.)$,
then

$\displaystyle\sum_{\ell\in N}v_{\ell}(A^{{}^{\prime}})>\sum_{\ell\in
N}v_{\ell}(A^{*})$

The above inequality leads to the contradiction that $A^{*}$ is optimal for
the reported valuation $({v}_{i},v_{-i})$. Therefore, VCG-T is dominant
strategy truthful in every period. $\blacksquare{}$

###### Fact 2

VCG-T is individually rational for every agent.

Proof: Consider agent $i$. The utility of $i$ under VCG-T is
$v_{i}(A^{*}(v))-d_{i}(v)$

$\displaystyle=v_{i}(A^{*})-\Big{(}\sum_{\ell\in
N\setminus\\{i\\}}v_{\ell}(A^{*}_{-i})-\sum_{\ell\in
N\setminus\\{i\\}}v_{\ell}(A^{*})\Big{)}$ $\displaystyle=\Big{(}\sum_{\ell\in
N}v_{\ell}(A^{*})-\sum_{\ell\in
N}v_{\ell}(A^{*}_{-i})\Big{)}+v_{i}(A^{*}_{-i})\geqslant 0$

The second equality holds by reorganizing the terms and adding and subtracting
$v_{i}(A^{*}_{-i})$. Note that the difference term in the parentheses in the
last expression is always non-negative since $A^{*}$ is the optimal allocation
for all allocations. In particular, $A^{*}_{-i}$ is also a feasible allocation
when agent $i$ is present. The term $v_{i}(A^{*}_{-i})$ is zero. Hence the
inequality follows. $\blacksquare{}$

The multi-slot jobs, unlike the single-slot jobs, are relatively difficult to
schedule, as we discuss in the following section.

##  6 Multi-slot Jobs

In this section, we consider jobs with different lengths, i.e., for agent $i$,
the job may be of length $l_{i}\geqslant 1$. Since the job is indivisible, the
entire length $l_{i}$ of the job requires contiguous slots for execution
within the period. For example, an individual may visit a facility (e.g., a
shopping mall) for a quick shopping, which may take a shorter duration, or for
dining, which may take longer. However, all these jobs are indivisible, and
the allocation needs to provide contiguous time-slots to that agent. The
agents report the valuations and lengths of their jobs. We show that the
optimal allocation problem in such a setting can be computationally
intractable. The notation is mildly updated as follows to accommodate the
multi-slot jobs.

Each agent $i$ gets a valuation $v_{ij}$ for her last unprocessed job if her
job begins at slot $j$, and has a length $l_{i}$. The value of the job is zero
if (a) it starts at any of the last $(l_{i}-1)$ time-slots of the period
(since it cannot finish within the period), and (b) if the job is unallocated.

A matrix $V$ consists of the agents’ reported valuations, and $L$ consists of
the lengths of agents’ jobs. Allocation is given by the matrix
$\mathcal{A}=[\mathfrak{a}_{ij}]$, where $\mathfrak{a}_{ij}=1$ if agent $i$’s
job starts at slot $j$, else $\mathfrak{a}_{ij}=0$, and $\mathfrak{a}_{i}$
represents the slot allocation vector for agent $i$. Keeping all other
notations as before, we define the MIA problem as follows.

######  Definition 7 (Multi-slot Indivisible jobs Allocation problem (MIA))

: Given $(N,M,V,L,k)$, find an allocation $\mathcal{A}$, such that $\sum_{i\in
N}\sum_{j\in M}v_{ij}(\mathfrak{a}_{ij})$ is maximum, subject to the
constraints that the total number of jobs allocated in a slot does not exceed
the capacity of the slot, and each job $i$ is assigned to at most $l_{i}$
contiguous slots. Mathematically, MIA is given by the following integer
program (IP).

$\displaystyle\begin{split}&\operatorname*{\arg\\!\max}_{A}\sum_{i\in
N}\sum_{j\in M}v_{ij}\ \mathfrak{a}_{ij}\\\ &\text{s.t. }\sum\limits_{i\in
N}\sum\limits_{\begin{subarray}{c}p\in M\\\
j\in[p,p+l_{i}-1]\end{subarray}}\mathfrak{a}_{ip}\leqslant k,\forall j\in
M,\\\ &\sum_{j\in M}\mathfrak{a}_{ij}\leqslant 1,\forall i\in N;\
\mathfrak{a}_{ij}\in\\{0,1\\},\forall i\in N,\forall j\in M\end{split}$ (5)

In the first set of inequalities, we sum over every job $i\in N$ and check if
it is under execution at $j$, for every $j\in M$. A job $i$ is under execution
at slot $j$, if it is allocated at a slot $p$ s.t. $j\leqslant p+l_{i}-1$. The
second set of inequalities ensure that no job is allocated more than once.

We show that MIA is computationally intractable by performing a polynomial
reduction from the Multi-Unit Combinatorial Auction (MUCA), which is NP-
complete.

Description of MUCA: Consider a multiset $\mathcal{M}=(\mathcal{G},y)$, where
$\mathcal{G}=\\{1,2,3,\ldots,g\\}$ is a set of goods and $y$ is a function,
$y:\mathcal{G}\to\mathbb{Z}_{\geqslant 0}$ representing the multiplicity or
the number of available units of the elements of $\mathcal{G}$ in
$\mathcal{M}$. Each agent $i\in\mathcal{N}=\\{1,2,\ldots,n\\}$ is a multi-
minded bidder, which means $i$ has a positive valuation $w_{i}(\cdot)$ for
multiple bundles of available goods. We call the set of bundles for which
agent $i$ has a positive valuation to be the demand set of $i$, represented by
$\mathcal{D}_{i}$. The valuation function is such that,
$w_{i}({q})\in\mathbb{R}_{\geqslant 0},\forall{q}\in\mathcal{D}_{i}$. We use
the following notation $\mathcal{D}=[\mathcal{D}_{i}]_{i\in\mathcal{N}}$ and,
$W_{i}=(w_{i}({q}))_{{q}\in\mathcal{D}_{i}}$, $W=[W_{i}]_{i\in\mathcal{N}}$.
In this paper we assume that, every agent demands at most one unit of every
good. With this assumption, an allocation of a bundle of goods to the agents
is represented as a matrix $\SS=[\mathfrak{s}_{iq}]$, where
$\mathfrak{s}_{iq}=1$, if the bundle $q\in\mathcal{D}_{i}$ is allocated to
$i$, else $\mathfrak{s}_{iq}=0$. For an allocation $\SS$, every agent $i$ gets
a valuation, $w_{i}(\SS)$=$\sum_{q\in\mathcal{D}_{i}}w_{i}({q})\
\mathfrak{s}_{iq}$, otherwise $w_{i}(\SS)=0$. The formal definition is as
follows.

######  Definition 8 (Multi-Unit Combinatorial Auction (MUCA))

Given $(\mathcal{N},\mathcal{M},W,D)$, find an allocation $\SS$ of goods to
the agents such that
$\sum_{i\in\mathcal{N}}\sum_{q\in\mathcal{D}_{i}}w_{i}({q})\
\mathfrak{s}_{iq}$ is maximum, and the total units of good $j\in\mathcal{G}$
allocated to the agents does not exceed $j$’s availability $y(j)$, and every
agent $i$ is assigned at most one of the demanded bundle from
$\mathcal{D}_{i}$. Mathematically, MUCA is given by the following integer
program (IP):

$\displaystyle\begin{split}&\operatorname*{\arg\\!\max}_{\SS}\sum\limits_{i\in\mathcal{N}}\sum\limits_{q\in\mathcal{D}_{i}}w_{i}({q})\
\mathfrak{s}_{iq}\\\ &\text{s.t.
}\sum_{i\in\mathcal{N}}\sum\limits_{\begin{subarray}{c}q\in\mathcal{D}_{i}\\\
j\in q\end{subarray}}\mathfrak{s}_{iq}\leqslant y(j),\forall
j\in\mathcal{G}\\\ &\sum_{q\in\mathcal{D}_{i}}s_{iq}\leqslant 1,\forall
i\in\mathcal{N};\ \mathfrak{s}_{iq}\in\\{0,1\\},\forall
i\in\mathcal{N},\forall q\in\mathcal{D}_{i}\end{split}$ (6)

The reduction of MIA to MUCA proceeds as follows. For a given instance
$(N,M,V,L,k)$ of MIA, construct an instance of
MUCA$(\mathcal{N},\mathcal{M},W,\mathcal{D})$ problem such that, the set of
agents $\mathcal{N}$ is $N$, the set of goods $\mathcal{G}$ is the set of the
slots $M$ within the period, where $y(j)=k$, $\forall j\in M$. For every
$i\in\mathcal{N}$, the demand set $\mathcal{D}_{i}$ consists of $(m-l_{i}+1)$
distinct bundles. Each of the bundles in $\mathcal{D}_{i}$ is of size $l_{i}$
and consists of $l_{i}$ contiguous slots. We denote a bundle as $q_{j}$ if it
contains $l_{i}$ contiguous slots starting from slot $j$, and $w_{i}(q_{j})$
is equal to $v_{ij}$ (the valuation $i\in N$ gets if her job starts at slot
$j\in M$). The above construction is done in polynomial steps of the input
size. We construct a solution of MIA from a solution of MUCA in the following
way: for every $q_{j}\in\mathcal{D}_{i}$ and $i\in\mathcal{N}$, if
$\mathfrak{s}_{iq_{j}}=1$ then, $\mathfrak{a}_{ij}=1$ for every $i\in N$ and
$j\in M$. Similarly, we construct a solution of MUCA from a solution MIA in
the following way: if $\mathfrak{a}_{ij}=1$ for $i\in N$ and $j\in M$ then,
$\mathfrak{s}_{iq_{j}}=1$ for every $q_{j}\in\mathcal{D}_{i}$ and
$i\in\mathcal{N}$. The following lemma shows that an optimal solution of MIA
is an optimal solution of MUCA and vice-versa.

###### Lemma 2

Let $\SS^{*}$ is a solution for MUCA for a multiset of goods $\mathcal{M}$,
and $\mathcal{A}^{*}$ is such that, $\mathfrak{a}_{ij}^{*}=1$ for $i\in N$ and
$j\in M$, if and only if $\mathfrak{s}_{iq_{j}}^{*}=1$ in $\SS^{*}$ for
$i\in\mathcal{N}$ and $q_{j}\in\mathcal{D}_{i}$, then $A^{*}$ is an optimal
solution for MIA if and only if $\SS^{*}$ is an optimal solution for MUCA.

Proof: Suppose the above statement is not true and hence
$\mathcal{A}^{{}^{\prime}}$ but not $\mathcal{A}^{*}$ is an optimal solution
for MIA.

$\sum_{i\in N}\sum_{j\in M}v_{ij}\
\mathfrak{a}^{\prime}_{ij}\geqslant\sum_{i\in N}\sum_{j\in M}v_{ij}\
\mathfrak{a}^{*}_{ij}$

As $w_{i}(q_{j})=v_{ij}$, and $\mathfrak{a}^{*}_{ij}=1$ only if
$\mathfrak{s}^{*}_{iq_{j}}=1$, with the constructed $\SS^{{}^{\prime}}$
corresponding to $\mathcal{A}^{{}^{\prime}}$ the following inequality holds,

$\sum_{i\in\mathcal{N}}\sum_{q_{j}\in\mathcal{D}_{i}}w_{i}(q_{j})\
\mathfrak{s}^{{}^{\prime}}_{iq_{j}}\geqslant\sum_{i\in\mathcal{N}}\sum_{q_{j}\in\mathcal{D}_{i}}w_{i}(q_{j})\
\mathfrak{s}^{*}_{iq_{j}}$

The above equation results in a contradiction that $\SS^{*}$ is an optimal
solution for MUCA.

Since each step of the above proof has implications in both directions, the
other direction of the proof is implied. $\blacksquare{}$

Since MUCA is NP-complete [13, 29], using Lemma 2, we get the following
theorem.

###### Theorem 3

MIA is NP-complete.

However, it is possible to find an approximately efficient allocation in
polynomial time that is truthful and individually rational. To find that, we
leverage the approximation algorithm of MUCA due to [3, Theorem 3]. Using
Lemma 2 and the next few results, we prove that there exists a polynomial time
truthful mechanism (MIA Approximation Algorithm or MAA) to achieve
$O\big{(}km^{\frac{1}{k-2}}\big{)}$ approximation to the optimal solution of
MIA.

Algorithm 2 MAA in every period

1: Procedure MAA($N,M,V,L,k$)

2: $b\leftarrow\underset{i}{\arg}\max\limits_{i\in N,j\in M}v_{ij}$; $\
v_{\max}\leftarrow\max\limits_{i\in N,j\in M}v_{ij}$; $\
r\leftarrow(6m(k-1))^{\frac{1}{k-2}}$

3: $\mathcal{Q}^{0}\leftarrow[0,0,\ldots,m\ \text{times}]$

4: $\mathfrak{a}_{bs^{\prime}}^{*}=1,\ \text{where}\
s^{\prime}\leftarrow\underset{j\in M}{\operatorname*{\arg\\!\max}}(v_{bj})$;
$\mathfrak{a}_{bj}^{*}=0$, $\forall j\in M\setminus\\{s^{\prime}\\}$; $\
\mathcal{P}_{b}=v_{\max}^{-b}$

5: for $i=\\{1,2,\ldots,n\\}$ and $i\neq b$ do

6: for $j=\\{1,2,\ldots,m\\}$ do

7: $P^{i}_{j}\leftarrow\pi_{0}\cdot r^{Q^{i-1}_{j}}$

8: end for

9: $\mathfrak{a}_{is}^{*}=1,\ \text{where}\
s\leftarrow\text{{{max}}}(P^{i},v_{i})$ (Equation 7)

10: $\mathfrak{a}_{ij}^{*}=0$, $\forall j\in M\setminus\\{s\\}$

11: $\mathcal{P}_{i}\leftarrow\sum_{j=s}^{s+l_{i}-1}P^{i}_{j}$

12: for $j=\\{1,2,\ldots,m\\}$ do

13: if $j\in[s,s+l_{i}-1]$ then

14: $\mathcal{Q}^{i}_{j}\leftarrow\mathcal{Q}^{i-1}_{j}+1$

15: else

16: $\mathcal{Q}^{i}_{j}\leftarrow\mathcal{Q}^{i-1}_{j}$

17: end if

18: end for

19: end for

20: return $\mathfrak{a}^{*},\mathcal{P}$

The operational principle of MAA is a sequential dictatorship, where the
sequence is an arbitrary order (WLOG $1,2,\ldots,n$) of the agents and is
independent of the information submitted by them. The mechanism comes with a
price666The terms price and delay are equivalent in the rest of the paper.
vector which is updated while iterating over the agents in the sequence. We
use a superscript $i$ to denote the the price faced by the agent $i$ for slot
$j$, $P_{j}^{i}$, when $i$’s turn comes. Hence, $P^{i}=[P_{j}^{i}]_{j\in M}$
denotes the price vector seen by $i$. The mechanism also uses a function max
that returns the slot $s$ that maximizes agent $i$’s utility given her
valuation vector $v_{i}$ and the price vector $P^{i}$ when her job of length
$l_{i}$ starts from slot $s$. Mathematically, max is defined as follows:

$\textbf{{max}}(v_{i},P^{i})=\operatorname*{\arg\\!\max}_{s\in M}\
(v_{is}-\sum\limits_{j\in[s,s+l_{i}-1]}P_{j}^{i})$ (7)

MAA maintains a vector $\mathcal{Q}^{i}=[\mathcal{Q}_{j}^{i}]_{j\in M}$, where
$\mathcal{Q}_{j}^{i}$ denotes the current allocated population of the slot $j$
after allocating slots to $i$. First, MAA picks the agent $b$ that has the
maximum valuation $v_{\max}$ for any slot, and initializes
$\mathcal{Q}^{0}_{j}=0,\forall j\in M$. The initial price of every slot is set
to $\pi_{0}:=\frac{v_{\max}}{6m(k-1)}$ and a constant factor
$r=(6m(k-1))^{\frac{1}{k-2}}$ is defined. Consider an arbitrary order (WLOG
$(1,2,\ldots,n)$) of the agents. For each agent $i\neq b$ in sequence, the
price $P^{i}_{j}$ is computed using $\mathcal{Q}^{i-1}_{j}$, $r$, and
$\pi_{0}$ such that the prices of the slots increase by a multiplicative
factor of a suitable exponent of $r$ such that the prices for more congested
slots are higher. Then the highest utility-deriving slot $s$ to start $i$’s
job is found using max, and the corresponding allocation vector for $i$ is
represented as $\mathfrak{a}_{i}^{*}$, where
$\mathfrak{a}_{is}^{*}=1,\mathfrak{a}_{ij}^{*}=0,\forall j\neq s$. The total
price (or delay) charged to $i$ is denoted by $\mathcal{P}_{i}$ and is equal
to $\sum_{j\in[s,s+l_{i}-1]}P^{i}_{j}$. The vector $\mathcal{Q}^{i}$ is
updated after the allocation of slots to agent $i$. The agent $b$ gets her
most valued starting slot and pays the maximum valuation among all other
agents and slots, which is represented by $v_{\max}^{-b}$.

An important feature of Algorithm 2 is that it does not explicitly check the
capacity constraint. However, we show that the choices of $\pi_{0}$ and $r$
implicitly maintains that in the following result. The units of slot $j$ after
Algorithm 2 executes that are occupied by agents except $b$ are
$\mathcal{Q}_{j}^{*}$.

###### Lemma 3

Let $\pi_{0},r,\delta>0$ be such that $\pi_{0}r^{\delta}\geqslant v_{\max}$,
then $\mathcal{Q}_{j}^{*}\leqslant\delta+1$. This implies that MAA maintains
the capacity constraints for each slot for $\delta=k-2$.

Proof: Assume for contradiction that $\mathcal{Q}_{j}^{*}>\delta+1$ and let
$i$ be the first customer due to which this contradiction takes place for some
slot $j$, i.e., $\mathcal{Q}_{j}^{i}>\delta+1$. Since each customer does not
get more than one unit of any slot, then it must be that
$\mathcal{Q}_{j}^{i-1}>\delta$. Hence, for slot $j$, the following holds:
$P_{j}^{i}>\pi_{0}r^{\delta}\geqslant v_{\max}\geqslant\max_{j\in M}\ v_{ij}$.
This makes $i$’s total price for $l_{i}$ contiguous slots including slot $j$
to be more than her corresponding total valuation for those slots. This
contradicts the definition of max since the utility becomes negative for agent
$i$. $\blacksquare{}$
The allocation to $b$ is at most one unit from each slot. With carefully
choosing $\pi_{0}$ and $r$, we bound the units of any slot allocated to all
the other agents, $\mathcal{Q}_{j}^{*}$ to $(k-1)$, maintaining the
possibility of the maximum use of every slot.

Since max allocates a slot only if that allocation increases the agent’s
utility, the following result holds.

###### Theorem 4

MAA is individually rational.

Next, we prove that misreporting the private information ($v_{i},l_{i}$) is
never beneficial for any agent $i$.

###### Theorem 5

In MAA, reporting $v_{i}$ and $l_{i}$ truthfully in every period is a dominant
strategy for all $i\in N$.

Proof: For the agent $b$, we see that the utility is that of a second price
auction and is independent of its length report. Since for second price
auction revealing valuation truthfully is a dominant strategy therefore
truthfully revealing valuation and length is a dominant strategy for $b$.

For the other agents, note that MAA considers the agents sequentially and
allocates the utility-maximizing available slots in their turn. The order of
the agents in MAA is independent of the valuations and lengths of the jobs.
Consider agent $i$. When her turn comes, the mechanism picks the slots that
give the maximum difference between the valuation of $i$ for those slots and
the current prices of those slots. Note that, the prices of those allocated
slots are not dependent on the valuation or length reported by agent $i$
(rather it is dependent on the reports of the previous agents in the sequence
and $b$), and the mechanism allocates her the optimal set of slots. Hence, by
misreporting the valuation $v_{i}$, agent $i$ can either continue to get the
same slots or get a worse set of slots w.r.t. her true valuation. Hence, there
is no incentive for $i$ to misreport her valuation.

Misreporting length: If $\hat{l}_{i}<l_{i}$, MAA allocates only $\hat{l}_{i}$
number of contiguous slots to $i$ (which can have zero value as $\hat{l}_{i}$
is not sufficient for completion of her job) and $i$ can get a negative payoff
as she has to pay $\mathcal{P}_{i}$ (which is non-negative). If
$\hat{l}_{i}>l_{i}$, then MAA allocates more slots than $i$ actually needs.
This allocation does not increase agent $i$’s valuation, but increases the
price since now she will be charged for $\hat{l}_{i}$ slots which is larger
than the true length.

Combining the above two arguments that hold for all $i\in N$ irrespective of
the reports of the other agents, we get the claim. $\blacksquare{}$

To find the best slot for an agent, max checks the feasibility constraints and
computes the allocation considering the valuation and the current price of the
slots. As there are $(m-l_{i}+1)$ possible allocations, max requires at most
$O(m)$ time for every agent $i$. Therefore, the following result on the
complexity of MAA holds.

###### Theorem 6

MAA has time complexity $O(mn)$.

To show the approximation factor of MAA, we need a few more results. We
restate a few results from [3], which help us prove the main theorem of
Section 6. The lemma and section numbers of these results in the original
paper are mentioned within parentheses in the restated lemmata.

######  Lemma 4 ([3, Section 4.2, Lemma 4])

For every agent $i$, $v_{i}(\mathfrak{a}^{*}_{i})\geqslant
v_{i}(\mathfrak{a}^{{}^{\prime}}_{i})-\sum_{j\in[s,s+l_{i}-1]\ s.t.\
\mathfrak{a}^{\prime}_{is}=1}P^{*}_{j}$ for every allocation
$\mathfrak{a}^{{}^{\prime}}_{i}$, where, ${P}^{*}$ is the vector of prices of
slots at the end of Algorithm 2.777With a slight abuse of notation, we denote
$[a,b]$ to be the integers between $a$ and $b$, where $a<b$.

Let $V(ALG)$ and $V(OPT)$ denotes the sum of valuations of customers for the
allocation $\mathcal{A}^{*}$ given by MAA, and that for the optimal allocation
(say $\hat{\mathcal{A}}$) respectively. Similarly, $V({ALG}^{-b})$ and
$V({OPT}^{-b})$ represents the sum of valuations of every agent except $b$
according to $\mathcal{A}^{*}$ and $\hat{\mathcal{A}}$ respectively. Summing
it for all the agent $i\in N$, we get the following corollary.

###### Corollary 3

$V({ALG}^{-b})\geqslant V(OPT^{-b})-(k-1)\sum\limits_{j\in M}P^{*}_{j}$

The following result provides a lower bound on $V({ALG}^{-b})$.

######  Lemma 5 ([3, Section 4.2, Lemma 5])

$V({ALG}^{-b})\geqslant\frac{\sum_{j\in M}P^{*}_{j}-m\pi_{0}}{r-1}$

Combining Lemma 5 and Corollary 3, we state the following result.

###### Lemma 6

If $m(k-1)\pi_{0}\geqslant\frac{V(OPT^{-b})}{2}$, then
$2((k-1)(r-1)+1)\geqslant V(OPT^{-b})/V({ALG}^{-b})$.

Following the conditions in Lemma 3 and Lemma 6, we fix
$\pi_{0}=\frac{v_{\max}}{6m(k-1)}$, $r=(6m(k-1))^{\frac{1}{k-2}}$. We restate
the following result about the approximation ratio from Bartal et al. [3].

######  Lemma 7 ([3, Section 5, Lemma 8])

The approximation ratio of Algorithm 2 is $3((k-1)(r-1)+1)$.

Finally, combining Lemmata 6 and 7, we get Theorem 7.

###### Theorem 7

There exists a polynomial time $(O(mn))$, incentive compatible, and
individually rational mechanism to achieve $O(km^{\frac{1}{k-2}})$
approximation to optimal solution for MIA.

The result above shows the existence of an approximately efficient mechanism
that satisfies the other three desirable properties. The question of finding a
lower bound on the approximation ratio remains open.

##  7 Multi-slot Divisible jobs

A divisible job implies that the job can be broken up into multiple pieces of
unit slot-size and can be executed independently within a period. Partial
execution of the jobs is also admissible. Examples of such jobs are parallel
computer programs, with each piece being an independent thread of the program.
In the context of social scheduling, divisible jobs can be interpreted as
independent needs of a customer that may be completed via multiple separate
visits to the store without any extra cost. The valuation of the job is the
sum of the valuations of the allocated slots. We assume that the length
$l_{i}$ of the job is verifiable and is common knowledge. Hence, the
valuations of each of the slots, i.e., $v_{ij}$’s, are the agents’ only
private information. In this setting, the valuation of agent $i$ from the
allocation $A$ can be written as $v_{i}(A)=\sum_{j:a_{ij}=1}v_{ij}a_{ij}$.
Note that the EPP condition under this setting is identical to the LP (3) with
the first set of constraints replaced by $\sum_{j\in M}a_{ij}\leqslant l_{i},\
\forall i\in N$. However, this does not alter the constraint matrix $C$, which
is TU (shown in the proof of Theorem 1). Therefore the new LP also has
integral optimal solution. The modified VCG-T is identical to Algorithm 1 with
Step 2 replaced with the solution to the modified LP as explained above.
Hence, the following results hold similarly.

###### Proposition 1

Modified VCG-T is per period dominant strategy truthful for multi-slot
divisible jobs.

###### Proposition 2

Modified VCG-T is individually rational for every agent.

###### Theorem 8

The allocation of the modified VCG-T always gives integral solutions.

Hence, the following proposition also holds.

###### Proposition 3

Modified VCG-T is EPP.

To reduce the allocation problem to a perfect $b$-matching problem, we need to
alter $b_{i}=l_{i}$, and Lemma 1 holds. Therefore, we conclude the following
result.

###### Theorem 9

Modified VCG-T provides a combinatorial, strongly polynomial algorithm for
computing a social schedule and delays.

##  8 Experiments

While the mechanisms presented in the previous sections satisfy several
desirable properties of a social scheduling mechanism for indivisible single
and multiple slot jobs, its prioritizing profile for different classes of
importance, costs of prioritization, and reduction in social congestion are
not theoretically captured. In this section, we investigate these properties
using real and synthetic datasets. The real dataset we collected from a store
gave us only the checkout times. In absence of the length information of the
visits, we resorted to the single-slot job model (with hourly slots) and
tested the performance of VCG-T on this data (§8.1). For multi-slot jobs, we
simulated MAA to find the suboptimality and the reduction in the running time
(§8.2). For these experiments, we consider three discrete levels of valuations
of the agents denoted by 3, 2, and 1, which can be interpreted as high,
medium, and low respectively. The numbers represent the agent’s valuation if
they are allocated their most preferred slot. The valuations for the other
slots are assumed to decrease with a multiplicative factor $\delta\in(0,1)$ in
the order of their slot preference, i.e., the valuation for the $t$-th most
preferred slot of a medium agent will be $2\delta^{t-1}$. We used Gurobi [20]
under an academic license for all experiments.

###  8.1 Reduction in the social congestion

This section considers a real data of customer footfall in a general store
that we have collected from the store. The dataset contains the customers’
hourly checkout (billing) time from 7 AM to 9 PM (opening hours of the store)
for the whole month of July 2020. Since the dataset was anonymized for
customer identification, we have assumed that the billing timestamps are
unique users for a day. Given the size of the store, around 32 people an hour
should be a fair capacity to maintain social distance. However, the data shows
that the monthly average during the periods 5-6 PM, 6-7 PM, and 7-8 PM were
38.00, 48.63, and 52.83 respectively. Interestingly, the monthly average of
the population in an hour is 26.5, which is well within the safety limits.
Therefore, this dataset works as a perfect example where users can benefit
significantly from social scheduling.

Figure 1: Social congestion reduction, slot capacities $28$ (top) and $32$
(bottom).

Figure 2: Priority and delay trade-off of VCG-T.

We divide the store opening hours into 14 hourly slots between 7 AM to 9 PM.
The valuations of every customer is drawn from a distribution {high:0.1,
medium:0.3, low:0.6}. In this experiment, an agent who is not allocated any
slot under VCG-T on a day is removed from the system and counted separately.
Fig. 2 shows the comparison of the average current population with that
allocated by VCG-T for slot capacities of 28 (above) and 32 (below). The
figures also show the daily non-allocated population in red. Each plot in this
section shows the average values with 95% confidence interval. The plots show
the trade-off between better social distancing (lower slot capacity) and its
cost (non-allocation). However, in both these cases, the social congestion is
reduced by approximately 50% during the rush hours.

VCG-T also prioritizes the jobs at a cost. The rows of Fig. 2 show the
allocated slot preference and the delays for the three difference classes of
valuations for the slot capacities 28 and 32 respectively. It shows that a
higher valuation comes with a higher delay.

###  8.2 Suboptimality and Complexity Reduction (MAA)

The sub-optimality of MAA (Algorithm 2) was obtained for a worst-case scenario
in §6. Here we investigate the sub-optimality of MAA and the amount of time it
reduces w.r.t. an algorithm that finds the optimal allocation of the slots.
The top plot of Fig. 4 shows the percentage reduction
($(t_{\text{{{OPT}}}}-t_{\text{\text{\bf{MAA}}}})/t_{\text{{{OPT}}}}$) in the
running time of MAA compared to the optimal mechanism, where
$t_{\text{{{OPT}}}}$ and $t_{\text{\text{\bf{MAA}}}}$ are the running times of
the optimal and MAA mechanisms respectively.

The bottom plot shows the ratio of the optimal social welfare to the welfare
yielded by MAA. The experiment is run with $n=6,k=5$, and $m$ varying from $3$
to $8$. For each value of $m,n,k$, the experiment is repeated $100$ times. The
parameters are chosen such that the optimal mechanism is computable in a
reasonable time, yet the experiment yields an insightful result. We see that
MAA reduces the running time by more than $99.5\%$ and yields an approximation
of roughly $1.75$ on an average.

Figure 3: Running time and approximation factor trade-off for MAA.

Figure 4: Priority-delay trade-off for VCG-T.

###  8.3 Prioritizing profile and its cost

In this section, we investigate what the typical priority slots allotted to an
agent of a specific class in VCG-T are. The top plot of Fig. 4 shows the
agents’ allocated slot preferences (mean with one standard deviation) versus
the population ($n$) plot where $m=5,k=4$, and $\delta=0.65$. The importance
of an agent is picked uniformly at random. Values of $n$ vary between $2$ to
$1.1mk$ in steps of 1 (for a population beyond $mk$, some agents have to be
dropped). The experiment is repeated $100$ times for every $n$. The plot shows
that the higher the importance, the lower is the allocated slot preference for
the agents, which is desirable.

However, VCG-T does the prioritized allocations of the agents at the cost of
their delays. The bottom plot of Fig. 4 shows the corresponding delays decided
by VCG-T for each of these three classes. The plot shows that an early slot
allocation of an agent because of her importance also comes with a longer
delay and shows the trade-off between these two decisions.

###  8.4 Scalability

This section examines VCG-T’s computation time for finding the allocation and
delays for a realistic population. We run VCG-T in Python for different number
of slots ($m$) with slot capacity ($k$) being 12. For every $m$, we fixed
$n=mk$ and repeated the experiment $10n$ times. Fig. 5 shows the growth of the
computation time of the mechanism. As a reference, to solve the allocation and
delays for the store of Section 8.1, it takes about 100 secs. The simulations
have been performed in a 64-bit Ubuntu 18.04 LTS machine with Intel(R)
Core(TM) i7-7700HQ CPU @2.80GHz quad-core processors and 16 GB RAM.

Figure 5: Computation times of VCG-T.

Epilogue: This paper provides a solution to social distancing using social
scheduling keeping the COVID-19 pandemic as a motivation, but the solution
apply to more general settings too. We have already developed an app that runs
VCG-T.

## References

  * Arazi and Feigel [2021] R. Arazi and A. Feigel.  Discontinuous transitions of social distancing in the sir model.  _Physica A: Statistical Mechanics and its Applications_ , 566:125632, 2021.
  * Aydos and O’Brien [2014] J. C. Aydos and A. O’Brien.  Scats ramp metering: strategies, arterial integration and results.  In _17th international IEEE conference on intelligent transportation systems (ITSC)_ , pages 2194–2201. IEEE, 2014.
  * Bartal et al. [2003] Y. Bartal, R. Gonen, and N. Nisan.  Incentive compatible multi unit combinatorial auctions.  In _Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge_ , pages 72–87, 2003.
  * Bergemann and Välimäki [2010] D. Bergemann and J. Välimäki.  The Dynamic Pivot Mechanism.  _Econometrica_ , 78:771–789, 2010.
  * Bloch [2017] F. Bloch.  Second-best mechanisms in queuing problems without transfers: The role of random priorities.  _Mathematical Social Sciences_ , 90:73–79, 2017.
  * Börgers [2015] T. Börgers.  _An introduction to the theory of mechanism design_.  Oxford University Press, USA, 2015.
  * Braverman et al. [2016] M. Braverman, J. Chen, and S. Kannan.  Optimal provision-after-wait in healthcare.  _Mathematics of Operations Research_ , 41(1):352–376, 2016.
  * Camion [1965] P. Camion.  Characterization of totally unimodular matrices.  _Proceedings of the American Mathematical Society_ , 16(5):1068–1073, 1965.
  * Cavallo [2021] R. Cavallo.  Social distancing equilibrium.  Unpublished, 2021.  URL http://www.eecs.harvard.edu/~cavallo/wp/cavallo-socdisteq.pdf.
  * Chen et al. [2016] X. Chen, X. Hu, T.-Y. Liu, W. Ma, T. Qin, P. Tang, C. Wang, and B. Zheng.  Efficient mechanism design for online scheduling.  _Journal of Artificial Intelligence Research_ , 56:429–461, 2016.
  * Cho [2020] S. Cho.  Mean-field game analysis of sir model with social distancing.  _arXiv preprint arXiv:2005.06758_ , 2020.
  * Clarke [1971] E. H. Clarke.  Multipart pricing of public goods.  _Public Choice_ , 11:17–33, 1971.
  * Cramton et al. [2004] P. Cramton, Y. Shoham, R. Steinberg, et al.  Combinatorial auctions.  Technical report, University of Maryland, Department of Economics-Peter Cramton, 2004.
  * Fong et al. [2020] M. W. Fong, H. Gao, J. Y. Wong, J. Xiao, E. Y. Shiu, S. Ryu, and B. J. Cowling.  Nonpharmaceutical measures for pandemic influenza in nonhealthcare settings—social distancing measures.  _Emerging infectious diseases_ , 26(5):976, 2020\.
  * Ghosh et al. [2020] S. Ghosh, Y. Long, and M. Mitra.  Prior-free online mechanisms for queueing with arrivals.  _Economic Theory_ , pages 1–30, 2020.
  * Glass et al. [2006] R. J. Glass, L. M. Glass, W. E. Beyeler, and H. J. Min.  Targeted social distancing designs for pandemic influenza.  _Emerging infectious diseases_ , 12(11):1671, 2006\.
  * Gosak et al. [2021] M. Gosak, M. U. Kraemer, H. H. Nax, M. Perc, and B. S. Pradelski.  Endogenous social distancing and its underappreciated impact on the epidemic curve.  _Scientific reports_ , 11(1):1–10, 2021.
  * Grötschel et al. [1993] M. Grötschel, L. Lovász, and A. Schrijver.  Complexity, oracles, and numerical computation.  In _Geometric Algorithms and Combinatorial Optimization_ , pages 21–45. Springer, 1993.
  * Groves [1973] T. Groves.  Incentives in teams.  _Econometrica_ , 41:617–631, 1973.
  * Gurobi Optimization [2020] L. Gurobi Optimization.  Gurobi optimizer reference manual, 2020.  URL http://www.gurobi.com.
  * Hajiaghayi [2005] M. T. Hajiaghayi.  Online auctions with re-usable goods.  In _Proceedings of the 6th ACM conference on Electronic commerce_ , pages 165–174, 2005.
  * Koutsoupias [2014] E. Koutsoupias.  Scheduling without payments.  _Theory of Computing Systems_ , 54(3):375–387, 2014.
  * Lavi and Nisan [2004] R. Lavi and N. Nisan.  Competitive analysis of incentive compatible online auctions.  _Theoretical Computer Science_ , pages 310:159–180, 2004.
  * Leclerc et al. [1995] F. Leclerc, B. H. Schmitt, and L. Dube.  Waiting time and decision making: Is time like money?  _Journal of Consumer Research_ , 22(1):110–119, 1995.
  * Mitra [2001] M. Mitra.  Mechanism design in queueing problems.  _Economic Theory_ , 17(2):277–305, 2001.
  * Pejó and Biczók [2020] B. Pejó and G. Biczók.  Corona games: Masks, social distancing and mechanism design.  In _Proceedings of the 1st ACM SIGSPATIAL International Workshop on Modeling and Understanding the Spread of COVID-19_ , pages 24–31, 2020.
  * Reluga [2010] T. C. Reluga.  Game theory of social distancing in response to an epidemic.  _PLoS Comput Biol_ , 6(5):e1000793, 2010.
  * Roberts [1979] K. Roberts.  The characterization of implementable choice rules.  _Aggregation and revelation of preferences_ , 12(2):321–348, 1979.
  * Rothkopf et al. [1998] M. H. Rothkopf, A. Pekeč, and R. M. Harstad.  Computationally manageable combinational auctions.  _Management science_ , 44(8):1131–1147, 1998\.
  * Roycroft et al. [2020] M. Roycroft, N. B. Bhala, S. Brockbank, D. O’Donoghue, A. Goddard, and A. M. Verma.  Rostering in a pandemic: Sustainability is key.  _Future Healthc J_ , 2020.
  * Sahni [1976] S. K. Sahni.  Algorithms for scheduling independent tasks.  _J. ACM_ , 23(1):116–127, Jan. 1976.  ISSN 0004-5411.  doi: 10.1145/321921.321934.  URL https://doi.org/10.1145/321921.321934.
  * Schrijver [2003] A. Schrijver.  _Combinatorial optimization: polyhedra and efficiency_ , volume 24.  Springer Science & Business Media, 2003.
  * Shadmehr and de Mesquita [2020] M. Shadmehr and E. B. de Mesquita.  Coordination and social distancing: Inertia in the aggregate response to covid-19.  _University of Chicago, Becker Friedman Institute for Economics Working Paper_ , (2020-53), 2020.
  * Shoham and Leyton-Brown [2008] Y. Shoham and K. Leyton-Brown.  _Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations_.  Cambridge University Press, 2008.
  * Thunström et al. [2020] L. Thunström, S. C. Newbold, D. Finnoff, M. Ashworth, and J. F. Shogren.  The benefits and costs of using social distancing to flatten the curve for covid-19.  _Journal of Benefit-Cost Analysis_ , pages 1–27, 2020.
  * Toxvaerd [2020] F. M. Toxvaerd.  Equilibrium social distancing.  2020\.
  * Vickrey [1961] W. Vickrey.  Counter speculation, auctions, and competitive sealed tenders.  _Journal of Finance_ , 16(1):8–37, 1961.
  * Wilder-Smith and Freedman [2020] A. Wilder-Smith and D. O. Freedman.  Isolation, quarantine, social distancing and community containment: pivotal role for old-style public health measures in the novel coronavirus (2019-ncov) outbreak.  _Journal of travel medicine_ , 2020.