\subsection{Related Work}
\label{sec:literature}
Social distancing measures have been widely successful and recommended for pandemic control~\cite{glass2006targeted,thunstrom2020benefits,fong2020nonpharmaceutical}.
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~\cite{gosak2021endogenous,arazi2021discontinuous,cho2020mean,pejo2020corona}. 
Individuals are sometimes reluctant to pay the costs inherent in social distancing which can limit its effectiveness as a control measure~\cite{reluga2010game}. \citet{toxvaerd2020equilibrium} 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". \citet{cavallo2021social} 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~\cite{roycroft2020rostering}. 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 {\em first-come-first-served} algorithm for slot booking and do not provide any priority preservation guarantees.\footnote{An example app is \url{www.appointy.com}.}

 

 Coordination among the citizens is essential for social distancing \cite{shadmehr2020coordination}, 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 \cite{hajiaghayi2005online}, has a rich literature that is close to our work. 
\citet{lavi-nisan04dynamic-online-auctions} study online supply curves based auction of {\em 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). 
\citet{chen2016efficient} 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~\cite{mitra2001mechanism,bloch2017second,ghosh2020prior}, while our model can admit costs of any structure.

In the context of job scheduling without money, \citet{koutsoupias2014scheduling} 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 {\em makespan} in a truthful manner without money for one task---which can be repeated for multiple tasks. 
In this paper, we maximize the {\em 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.
\citet{braverman2016optimal} 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.








\section*{Appendix}

\section{Proof of \Cref{thm:relax}}



\section{Proof of \Cref{lem:equivalence}}



\section{Proof of \Cref{lem:MUCA_reduction}}



\section{Proof of \Cref{lem:alg2_validity}}



\section{Proof of \Cref{lem:alg2IC}}



\section{Proof of \Cref{thm:dsic}}\label{APP_DSIC}


\section{Proof of \Cref{thm:ir}}\label{APP_IR}
















\section{Restated results from \cite{bartal2003incentive}} \label{sec:Lemmata_bartal}

\section{Additional Experimental Results}


\section{Summary and Plans of Extension}

\smallskip \noindent
{\bf 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 \text{\bf \texttt{VCG-T}}.

\section{Experiments}
\label{sec:experiment}

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 \text{\bf \texttt{VCG-T}}\ on this data (\S\ref{sec:reduction}). For multi-slot jobs, we simulated \text{\bf \texttt{MAA}}\ to find the suboptimality and the reduction in the running time (\S\ref{sec:approx-plot}).
For these experiments, we consider three discrete levels of valuations of the agents denoted by 3, 2, and 1, which can be interpreted as \text{\bf \texttt{high}}, \text{\bf \texttt{medium}}, and \text{\bf \texttt{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 \text{\bf \texttt{medium}}\ agent will be $2 \delta^{t-1}$. We used Gurobi~\cite{gurobi} under an academic license for all experiments.

\subsection{Reduction in the social congestion}
\label{sec:reduction}
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.


\begin{figure}[h]
\begin{multicols}{2}
\centering
    \includegraphics[width=\linewidth]{images/congestion_28_32.pdf}
    \caption{Social congestion reduction, slot capacities $28$ (top) and $32$ (bottom).}
    \label{fig:congestion}
    \centering
    \includegraphics[width=\linewidth]{images/congestion_pref_delay_28_32.pdf}
    \caption{Priority and delay trade-off of \text{\bf \texttt{VCG-T}}.}
    \label{fig:trade-off}
\end{multicols}
\end{figure}

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 \{\text{\bf \texttt{high}}:0.1, \text{\bf \texttt{medium}}:0.3, \text{\bf \texttt{low}}:0.6\}.
In this experiment, an agent who is not allocated any slot under \text{\bf \texttt{VCG-T}}\ on a day is removed from the system and counted separately. 
\Cref{fig:congestion} shows the comparison of the average current population with that allocated by \text{\bf \texttt{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.

\text{\bf \texttt{VCG-T}}\ also prioritizes the jobs at a cost. The rows of \Cref{fig:trade-off} 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.

\subsection{Suboptimality and Complexity Reduction (\text{\bf \texttt{MAA}})}
\label{sec:approx-plot}

The sub-optimality of \text{\bf \texttt{MAA}}\ (\Cref{alg:alg2}) was obtained for a worst-case scenario in \S\ref{sec:multi}. Here we investigate the sub-optimality of \text{\bf \texttt{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 \Cref{fig:tradeoff} shows the percentage reduction ($(t_\text{\textbf{\texttt{OPT}}} - t_\text{\text{\bf \texttt{MAA}}})/t_\text{\textbf{\texttt{OPT}}}$) in the running time of \text{\bf \texttt{MAA}}\ compared to the optimal mechanism,
where $t_\text{\textbf{\texttt{OPT}}}$ and $t_\text{\text{\bf \texttt{MAA}}}$ are the running times of the optimal and \text{\bf \texttt{MAA}}\ mechanisms respectively. 

The bottom plot shows the ratio of the optimal social welfare to the welfare yielded by \text{\bf \texttt{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 \text{\bf \texttt{MAA}}\ reduces the running time by more than $99.5\%$ and yields an approximation of roughly $1.75$ on an average. 
   
\begin{figure}[h]
\begin{multicols}{2}
\centering
    \includegraphics[width=\linewidth]{images/N6_K5}
    \caption{Running time and approximation factor trade-off for \text{\bf \texttt{MAA}}.}
    \label{fig:tradeoff}
    \centering
    \includegraphics[width=\linewidth]{images/priority-delay.pdf}
    \caption{Priority-delay trade-off for \text{\bf \texttt{VCG-T}}.}
    \label{fig:priority-delay}
\end{multicols}
\end{figure}
\subsection{Prioritizing profile and its cost}
\label{sec:priority}

In this section, we investigate what the typical priority slots allotted to an agent of a specific class in \text{\bf \texttt{VCG-T}}\ are. The top plot of \Cref{fig:priority-delay} 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.1 mk$ 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, \text{\bf \texttt{VCG-T}}\ does the prioritized allocations of the agents at the cost of their delays. The bottom plot of \Cref{fig:priority-delay} shows the corresponding delays decided by \text{\bf \texttt{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.


\subsection{Scalability}
\label{sec:scalability}

 This section examines \text{\bf \texttt{VCG-T}}'s computation time for finding the allocation and delays for a realistic population. We run \text{\bf \texttt{VCG-T}}\ in \textsf{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. \Cref{fig:scalability} shows the growth of the computation time of the mechanism. As a reference, to solve the allocation and delays for the store of \Cref{sec:reduction}, 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.
\begin{figure}
\centering
    \includegraphics[width=0.55\linewidth]{images/scalability_cropped}
    \caption{Computation times of \text{\bf \texttt{VCG-T}}.}
    \label{fig:scalability} 
\end{figure}



\section{Introduction}
\label{sec:intro}

Pandemics like the COVID-19 showed that one of the most effective solutions against infectious diseases is {\em social distancing}~\cite{wilder2020isolation}. 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 {\em 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 {\em disutility} to wait before submitting their next job for allocation. All jobs are {\em indivisible}, i.e., has to be completed once started.
In this paper, we consider {\em 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~\cite{aydos2014scats}
or multi-ownership computational jobs in a single-core processor~\cite{Sahni76}.
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.


\subsection{Brief Problem Description and Contributions}
\label{sec:contributions}

The opening hours of a facility are divided into {\em periods} (e.g., a day), each of which has multiple {\em 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.\footnote{A 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 {\em dictatorial} mechanisms (where a pre-selected agent's favorite outcome is always selected) are truthful~\cite[Thm 7.2]{Roberts79}. 
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 {\em time-delay} as a replacement of money. Waiting time is often seen as a resource that individuals agree to trade with~\cite{leclerc1995waiting}. 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 \cite[Chap 10]{SL08}.
This competitive scenario induces a {\em game}
where agents' actions are to report the valuations. The agents may {\em overstate} (or {\em understate}) their actual valuations.
The contributions of this paper can be summarized into the following {\em four} major points:
\begin{itemize}
    \item Even though maximizing the {\em 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 (\Cref{thm:relax,thm:strong}). 
    \item We show that the standard Vickrey-Clarke-Groves (VCG) payment~\citep{Vick61,Clar71,Grov73} can be used as the delay (cooling-off time) in this setting to ensure truthfulness (\Cref{thm:dsic}) and participation of the agents (\Cref{thm:ir}). We call the allocation and delay together as the mechanism \text{\bf \texttt{VCG-T}}\ ({\bf \texttt{VCG}} with {\bf \texttt{T}}ime delays).
    \item The welfare maximizing allocation of multi-slot jobs are computationally hard (\Cref{thm:NPc}). We propose a polynomial time mechanism (\Cref{lem:alg2complexity}) which ensures participation (\Cref{lem:alg2IR}), truthfulness (\Cref{lem:alg2IC}), and is approximately optimal (\Cref{thm:apprx_multi}).
    \item Our real and synthetic data experiments (\Cref{sec:experiment}) 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 (\Cref{sec:reduction}). For the multi-slot jobs, our approximately optimal mechanism provides a reasonable approximation at a much reduced computational cost in practice (\Cref{sec:approx-plot}).
\end{itemize}
The mechanisms presented in this paper are {\em prior-free}, i.e., they do not depend on the probabilistic information of the valuations.

\input{ShortLiteratureReview}

\if 0
\subsection{Related Work}
\label{sec:literature}

\sn{needs to be reduced by one column}

Social distancing measures have been widely successful and recommended for pandemic control~\cite{glass2006targeted,thunstrom2020benefits,fong2020nonpharmaceutical}.
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 is to understand the relationship of social distancing with different public policies and other factors~\cite{toxvaerd2020equilibrium,gosak2021endogenous,arazi2021discontinuous,cho2020mean}. \cite{pejo2020corona} model the coronavirus situation as a game between rational agents where the strategies are whether to wear a mask or not, to go out for a meeting or not, and others. They show how the decision of an agent to go out to attend a meeting at the risk of her own life depends on the maximum duration, the maximum number of people allowed in a gathering, and the probability of getting infected. \citet{toxvaerd2020equilibrium} considers social distancing in the susceptible-infected-recovered (SIR) epidemiological model and characterizes the equilibrium dynamics in terms of peak prevalence, time-domain properties of the disease, and other factors. \citet{toxvaerd2020equilibrium} shows that "during the equilibrium social distancing phase, individuals gradually reduce their social distancing efforts despite the infection probability not decreasing."


Individuals are sometimes reluctant to pay the costs inherent in social distancing, which can limit its effectiveness as a control measure~\cite{reluga2010game}. This is particularly important when the movement of the people is mainly uncoordinated. Under an uncoordinated model, \cite{cavallo2021social} shows that every equilibrium involves more social contact than it occurs in a social optima. Coordination is essential for social distancing \cite{shadmehr2020coordination}, 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 that 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.

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~\cite{roycroft2020rostering}. However, these measures are centrally controlled, and an individual does not have a scope to behave strategically.

On the other hand, the businesses maintain social distancing by enforcing certain appointment booking apps (either web or smartphone-based) to their customers. These apps run a {\em first-come-first-served} (FCFS) algorithm for slot booking and do not provide any priority preservation guarantees.\footnote{An example app is \url{www.appointy.com}.}


Resource allocation with monetary transfers to ensure truthfulness, e.g., in the context of job shop scheduling, has a rich literature that is close to our work (even though our mechanisms do not use money). \cite{friedman2003pricing} consider interruptible and non-interruptible versions of the online {\em single} resource allocation problem, where the resources can be allocated to a limited number of users, e.g., the WiFi at Starbucks or shared computation on a server. They assume that the agents can not lie about their arrival time and get better valuations and prove that the online version of VCG is strategyproof only if the allocation rule is time-monotonic. They also show that a simple fixed price payment can result in a close-to-optimal solution for a non-interruptible version of their problem. \cite{lavi-nisan04dynamic-online-auctions} study online supply curves based auction of {\em identical divisible goods} that ensures truthfulness. This paper considers an offline allocation problem but a comparatively more complex one (multiple resources and indivisible tasks of different lengths). 

\cite{hajiaghayi2005online} provide an online auction for reusable goods, e.g., assigning time slots of a machine to unit length jobs. They study {\em single-capacity machines} and give a truthful randomized mechanism. 

Our work is different in the sense that the jobs we consider and the machine capacities can be of varied length. \cite{chen2016efficient} consider a job allocation to machines that is closely related to our setting. However, the job arrivals and allocation are online in that setting. They propose a truthful approximate mechanism for models 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~\cite{mitra2001mechanism,bloch2017second,ghosh2020prior}, while our model can admit costs of any structure.

In the context of job scheduling without money, \cite{koutsoupias2014scheduling} studies the allocation of independent tasks to machines, where the machines are lazy agents and prefer not to execute any task. Every machine reports the time it takes to execute each task (private information), and the allocation is done to minimize the {\em makespan}. The author provides a truthful in expectation, approximate mechanism without money for one task---which can be repeated for multiple tasks. 

In our setup, we consider maximizing the {\em sum of the visitors' valuations} which are independent of the length of the job and provide an approximate mechanism for multiple tasks respecting the capacity at all times.

\cite{braverman2016optimal} study the Provision-After-Wait allocation of medical treatments at hospitals of different costs to patients who each value the hospitals differently. A central authority pays the hospital bills for every patient but has a finite budget. In every allocation period, a waiting time is computed for every hospital, which helps to get a stable matching. If a patient wants treatment at a hospital, she must wait until the calculated waiting time corresponding to that hospital. In our setup, a capacity constraint is over each of the available resources, the time slots. In \cite{braverman2016optimal}, the valuation of a patient for a hospital does not change over time, so the patients can wait before being treated without altering the valuations. In our setting, the valuation vector of an agent can be very different in the next period. Therefore, assigning a waiting time before the service will make it impossible to efficiently allocate and analyze the allocation's characteristics in the current and future periods.


\fi

\section{Basic Problem Setup}
\label{sec: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 {\em periods}, and each period is further divided into {\em 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 social distancing norm of the region and the size of the facility. A {\em central planner} (e.g., an AI app) allocates these slots to the agents maintaining the capacity constraint. Every agent has a preference over the slots which is represented by a real number against each slot. For instance, the preference (we will call this the agent's {\em valuation}) of agent $i$ for slot $j$ is denoted by $v_{ij} \in \mathbb{R}_{\geqslant 0}$, which is interpreted as if slot $j$ is allotted to $i$, then $i$ is willing to wait for $v_{ij}$ time periods before requesting another access to the facility.\footnote{The valuation $v_{ij}$ need not be integral. In practice, the facility will be frozen for that duration of time in the booking app.} Thus the valuation implicitly reflects the importance to visit the facility for that agent. 
The valuation vector of $i$ is represented by $v_i \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 a 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. We denote the slot assigned to $i$ by $a_i^*$. The planner also decides a delay $d = (d_i, i \in N)$ for each agent before which they cannot make another request to the system. We assume that every agent wants a more valued slot to be assigned to her and also wants to wait less. Therefore, the net payoff of an agent is assumed to follow a standard {\em quasi-linear form}~\cite{SL08}
\begin{equation}
    \label{eq:utility}
    u_i((A,d), v_i) = v_i(A) - d_i, \text{ where } v_i(A) = v_{i a_i^*}.
\end{equation}
Denote the set of all allocations by ${\cal A}$ and $d_i \in \mathbb{R}, \forall i \in N$. The planner does not know the valuations (or urgencies) of the agents. Therefore he needs the agents to report their valuations and decide the allocation and the delay. This leaves the opportunity for an agent to misrepresent her true valuation, e.g., an agent can report a \texttt{not-urgent} valuation as \texttt{urgent} for a prioritized scheduling. To distinguish, we use $v_{ij}$ for the true valuation and $\hat{v}_{ij}$ for reported valuations. We will 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.
\begin{definition}[Social Scheduling Function (SSF)]
 A {\em 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.\footnote{We overload the notation $A$ and $d$ to denote both functions and values of those functions, since their use will be clear from the context.}
\end{definition}




\section{Preliminary Definitions}
\label{sec:desiderata}

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

The first property ensures that the allocation is {\em efficient} in each period, i.e., it maximizes the sum of the valuations of all the agents. As an effect, every slot will be allocated to an agent who values it the most, breaking ties arbitrarily.
\begin{definition}[Efficient Per Period (EPP)]
 \label{def:efficiency}
 An SSF $f$ is {\em 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
 \begin{equation}
     \label{eq:efficient}
     A^*(v) \in \argmax_{A \in {\cal A}} \sum_{i \in N} \sum_{j \in M} v_{ij} a_{ij}.
 \end{equation}
\end{definition}

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 robots are incentivized to `truthfully' reveal these information.
\begin{definition}[Per Period Dominant Strategy Truthful]
 \label{def:non-manipulability}
 An SSF $f(\cdot) = (A(\cdot), d(\cdot))$ is {\em truthful in dominant strategies per period} if for every $v_i, \hat{v}_i, \hat{v}_{-i}$, and $i \in N$
  \begin{align*}
   \lefteqn{ v_i(A(v_i, \hat{v}_{-i})) - d_i(v_i, \hat{v}_{-i})} \\
   \quad &\geqslant v_i(A(\hat{v}_i, \hat{v}_{-i})) - d_i(\hat{v}_i, \hat{v}_{-i}).
  \end{align*}
\end{definition}
The inequality above shows that if the true value of agent $i$ is $v_i$, the allocation and delay resulting from reporting it `truthfully' maximizes her payoff {\em irrespective of the reports of the other robots}.

\begin{definition}[Individual Rationality]
 \label{def:ir}
 An SSF $f(\cdot) = (A(\cdot), d(\cdot))$ is {\em individually rational} if for every $v$, and $i \in N$
  \begin{align*}
   v_i(A(v)) - d_i(v) &\geqslant 0.
  \end{align*}
\end{definition}
Individual rationality ensures that it is always weakly beneficial for every rational agent to participate in such a mechanism.

In large facilities, the number and capacities of the slots are large, leading 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 \textit{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 \textit{NP (nondeterministic polynomial)}. We consider the NP-complete class of problems which is defined as follows.
\begin{definition}[NP-complete]
A decision problem $Q$ is NP-complete if:
\begin{enumerate}
    \item $Q $ is in NP (class of all decision problems verifiable in	polynomial time), and
    \item Every problem in NP is reducible to $Q$ in polynomial time.
\end{enumerate}
\end{definition}
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 {\em strongly polynomial}. Strongly polynomial algorithms are defined by their arithmetic model of computation. The basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a unit time step to perform, regardless of the sizes of the operands. 


\begin{definition}[Strongly Polynomial]
 \label{def:strong-poly}
    An algorithm runs in {\em strongly polynomial time} if \citep{grotschel1993complexity}
    \begin{itemize}
        \item 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
        \item the space used by the algorithm is bounded by a polynomial in the size of the input.
    \end{itemize}
\end{definition}





\section{Periodic Mechanisms}
\label{sec:online}

We consider mechanisms that run at every period of this social scheduling problem. The agents report their valuations in the beginning of every period. The planner decides the schedules and delays.\footnote{For mechanisms that consider the finite or infinite horizon of such allocation problems \citep[e.g.]{bergemann-valimaki10dynamic-pivot}, (a)~the designer needs to know the transition probabilities, (b)~solution concepts are weaker, and (c)~are computationally expensive. These factors made us restrict our attention to periodic mechanisms.}


In our setting, the agents have the opportunity to overstate their urgencies to get a better slot allotted to them. This is precisely where our approach using the ideas of mechanism design \citep{borgers2015introduction} is useful. 

 In a setting where the agents' valuations are private, if the mechanism has no additional tool (e.g., delays in time in our context) to penalize overstating, only {\em dictatorial} mechanisms (where a pre-selected agent's favorite outcome is selected always) are truthful \citep{Gib73,Sat75}. This negative result holds irrespective of whether agents' preferences are {\em ordinal} (representable as an order relation over the outcomes) or {\em cardinal} (agents have a real number to represent the intensity of the preference). Note that in our setup, the agents' preferences are cardinal.
 A complementary analysis by \citet[Thm 7.2]{Roberts79} shows that a dictatorship result reappears under certain mild conditions in a {\em quasi-linear} setting (which is our current setting), unless transfers (of utility) are allowed. 
 In this paper, we use delay as a surrogate for transferable utility among the agents to ensure truthful value revelation at every period. 
 
We are now in a position to present the proposed mechanism \text{\bf \texttt{VCG-T}}\ ({\bf \texttt{VCG}} with {\bf \texttt{T}}ime delays).

\begin{algorithm}[h!]
 \caption{\text{\bf \texttt{VCG-T}}\ in every period}
 \begin{algorithmic}[1]
   \STATE {\bf Input:} for every agent $i \in N$, the value $\hat{v}_i$
      \STATE compute $A^*(\hat{v})$ (\Cref{eqn:LP}) as the allocation \label{alg:allocation-step}
      \STATE charge a delay $d_i(\hat{v})$ (\Cref{eqn:payment}) to every $i \in N$ for which they cannot access the scheduling mechanism again
    \STATE {\bf Output:} $A^*(\hat{v})$ and $d(\hat{v})$
  \end{algorithmic}
 \label{algo:mechanism}
 \end{algorithm}
 
\paragraph{Description of \text{\bf \texttt{VCG-T}}}

The SSF needs to decide on the allocation $A$ and the delay $d$. The actual allocation that satisfies EPP is given by the following integer program (IP).
\begin{align}
 \label{eqn:IP}
 \begin{split}
     \argmax_{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} \in \{0, 1\}, \ \forall i \in N, j \in M.
 \end{split}
\end{align}
However, IPs are NP-complete in general. Therefore, \text{\bf \texttt{VCG-T}}\ computes the LP relaxation of the above problem, given as follows.
\begin{align}
 \label{eqn:LP}
 \begin{split}
     \argmax_{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}
\end{align}
We will show that this is without loss of optimality, since the solution to LP~\ref{eqn:LP} will always be integral and will coincide with the solution of IP~\ref{eqn:IP}. 

The delay of agents are computed via the standard Vickery-Clarke-Groves (VCG) rule \cite{Vick61,Clar71,Grov73}. Denote the optimal allocation of LP~\ref{eqn:LP} by $A^*(v)$. Also, denote the allocation given by LP~\ref{eqn:LP} when agent $i$ is removed from the system by $A^*_{-i}(v_{-i})$.
For agent $i$, the delay is given by,
\begin{align}
\label{eqn:payment}
\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}
\end{align}
The mechanism in every period is described in \Cref{algo:mechanism}.

Note that the allocation is different from that of a sorted importance sequential dictator, i.e., where the agents are sorted based on their importance and asked to pick their favorite slots in that order. For example, consider two agents A and B, and two slots of capacity one. Valuations are (51, 50) and (50, 0) respectively for A and B respectively for the two slots -- sequential dictator would allocate slot 1 to A and 2 to B, while the socially optimal is to allocate slots 2 and 1 to A and B respectively, which is allocated by \text{\bf \texttt{VCG-T}}.

\section{Theoretical guarantees}
\label{sec:theory}


Our first result shows that \text{\bf \texttt{VCG-T}}\ ensures proper prioritization of the agents and reveals their importance truthfully.
\begin{theorem}
\label{thm:dsic}
 \text{\bf \texttt{VCG-T}}\ is per period dominant strategy truthful.
\end{theorem}


\shortversion{\noindent This proof of per period dominant strategy truthful is a standard extension of the proof for Vickery-Clarke-Groves (VCG) mechanism \cite{Vick61,Clar71,Grov73} and is available in the supplemental material.
}

\longversion{
\begin{proof}
 This proof is a standard exercise in the line of the proof for Vickery-Clarke-Groves (VCG) mechanism \cite{Vick61,Clar71,Grov73}. \text{\bf \texttt{VCG-T}}\ follows the VCG allocation and payment locally at every intersection calculated by the LIM. Hence, the payoff of robot $i$ at intersection $k$ is given by (for brevity of notation, we hide the time argument in every function and write $a_k^*$ as $a_k^*(v_i, v_{-i})$)
 \begin{align*}
   \lefteqn{ \text{\bf val}_i(a_k^*(v_i, \hat{v}_{-i}), v_i) - p_i(v_i, \hat{v}_{-i})} \\
   &= \sum_{j \in N_k}  \text{\bf val}_j(a_k^*(v_i, \hat{v}_{-i}), \hat{v}_j) - \sum_{j \in N_k \setminus \{i\}} \text{\bf val}_j(a_k^{*,N_k \setminus \{i\}}, \hat{v}_j) \\
   &\geqslant \sum_{j \in N_k}  \text{\bf val}_j(a_k^*(\hat{v}_i, \hat{v}_{-i}), \hat{v}_j) - \sum_{j \in N_k \setminus \{i\}} \text{\bf val}_j(a_k^{*,N_k \setminus \{i\}}, \hat{v}_j) \\
   &= \text{\bf val}_i(a_k^*(\hat{v}_i, \hat{v}_{-i}), v_i) - p_i(\hat{v}_i, \hat{v}_{-i}).
  \end{align*}
The first equality is obtained by writing and reorganizing the expression for $p_i$. The inequality holds since by definition $\sum_{j \in N_k}  \text{\bf val}_j(a_k^*(v_i, \hat{v}_{-i}), \hat{v}_j) \geqslant \sum_{j \in N_k}  \text{\bf val}_j(a_k, \hat{v}_j)$ for every $a_k$; in particular, we chose $a_k^*(\hat{v}_i, \hat{v}_{-i})$. The last equality is obtained by reorganizing the expressions again.
\end{proof}
}

The next result ensures that the agents are incentivized to voluntarily participate in \text{\bf \texttt{VCG-T}}.
\begin{theorem}
 \label{thm:ir}
 \text{\bf \texttt{VCG-T}}\ is individually rational for every agent.
\end{theorem}

\begin{proof}
 Consider agent $i$. The utility of $i$ under \text{\bf \texttt{VCG-T}}\ is given by
 \begin{align*}
     \lefteqn{ v_i(A^*(v)) - d_i(v) } \\
     &= v_i(A^*) - \left( \sum_{\ell \in N \setminus \{i\}} v_\ell(A^*_{-i}) - \sum_{\ell \in N \setminus \{i\}}  v_\ell(A^*) \right) \\
     &= \left( \sum_{\ell \in N}  v_\ell(A^*) - \sum_{\ell \in N} v_\ell(A^*_{-i}) \right) + v_i(A^*_{-i}) \geqslant 0
 \end{align*}
 The second equality holds by reorganizing the terms and by 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.
\end{proof}

The next few results show that even if the allocation problem of IP~\ref{eqn:IP} falls in a computationally intractable class, its special structure can be used to find a tractable solution.
\begin{theorem}
 \label{thm:relax}
 The allocation of \text{\bf \texttt{VCG-T}}\ given by LP~\ref{eqn:LP} always gives integral solutions.
\end{theorem}

\begin{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~\ref{eqn:LP} 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~\ref{eqn:LP} respectively. We show that $C$ is totally unimodular (TU), which is sufficient to conclude that LP~\ref{eqn:LP} has integral solutions.
 We use the Ghouila-Houri characterization \cite{camion1965characterization} 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.
\end{proof}

The result above shows that the optimal solution of LP~\ref{eqn:LP} is an optimal solution of IP~\ref{eqn:IP}. Hence, the mechanism is indeed doing an efficient allocation which can be summarized in the following corollary.
\begin{corollary}
\label{cor:efficient}
 \text{\bf \texttt{VCG-T}}\ is EPP.
\end{corollary}

\Cref{thm:relax} shows that the solution to the LP relaxation of the allocation problem is without loss of optimality. LPs are known to be polynomially computable. However, in general it 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. The forthcoming results show that the solutions of allocation and delays of \text{\bf \texttt{VCG-T}}\ are strongly polynomial (\Cref{def:strong-poly}). 
To show this, we will first reduce the allocation problem (LP~\ref{eqn:LP}) to a minimum weight $b$-matching problem, which is known to be strongly polynomial \citep{schrijver2003combinatorial}.

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 given by $b_i = 1, \forall i \in N$, and $b_j = k, \forall j \in M$.

\begin{lemma}
\label{lem:equivalence}
 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~\ref{eqn:LP}.
\end{lemma}

\begin{proof}
 We prove this via contradiction. Suppose $A^*$ is not an optimal solution to LP~\ref{eqn:LP}, i.e., there exists $A'$ 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}' > \sum_{j \in M} \sum_{i \in N} v_{ij} a_{ij}^*$. Consider the edge set $E'$ corresponding to $A'$. Clearly this is a perfect $b$-matching, since $A'$ satisfies the constraints of LP~\ref{eqn:LP}, and $E'$ 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.
\end{proof}
Note that the delays are calculated by solving an equivalent LP like LP~\ref{eqn:LP} with one less agent. Each of these LPs is therefore strongly polynomial and the planner needs to solve $n$ of them. The computation of the each delay needs 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 size of the input. Therefore we conclude the following.

\begin{corollary}
\label{cor:delay}
 The computation of the delays in \text{\bf \texttt{VCG-T}}\ is strongly polynomial.
\end{corollary}
Combining \Cref{thm:relax}, \Cref{lem:equivalence}, and \Cref{cor:delay},  we get the following result.

\begin{theorem}
 \label{thm:strong}
  \text{\bf \texttt{VCG-T}}\ provides a combinatorial, strongly polynomial algorithm for computing a social schedule and delays.
\end{theorem}

The following section addresses the problem with every agent having jobs with duration spanning multiple time-slots.

\section{Multi-slot Jobs}
\label{sec:multi}

In this section, we consider jobs that has different lengths, i.e., for agent $i$, the job may be of length $l_i \geqslant 1$. In this section, we consider two cases of such jobs, which can be either {\em divisible} or {\em indivisible}. 

\paragraph{Divisible jobs}
In this section, we consider jobs that are {\em divisible}. This means 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 portion of the code. For social scheduling, these jobs may be completed by an agent 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 a common knowledge. Hence, the valuations of each of the slots, i.e., $v_{ij}$'s, are the only private information of the agents. 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 IP~\ref{eqn:IP} with the first set of constraints replaced by 
\[ \sum_{j \in M} a_{ij} \leqslant l_i, \ \forall i \in N.\]
Clearly, the LP relaxation of the new IP is identical to LP~\ref{eqn:LP} with the first set of constraints replaced with the above set of constraints. However, this does not alter the constraint matrix $C$, which is TU (shown in the proof of \Cref{thm:relax}). Therefore the new LP also gives integral solutions which is an optimal solution to the new IP. 
The {\em modified} \text{\bf \texttt{VCG-T}}\ is identical to \Cref{algo:mechanism} with Step~\ref{alg:allocation-step} replaced with the solution to the modified LP as explained above.
Hence, the following results hold in a similar manner.

\begin{theorem}
 \label{thm:multi-divisible-dsic}
 Modified \text{\bf \texttt{VCG-T}}\ is per period dominant strategy truthful for multi-slot divisible jobs.
\end{theorem}

\begin{theorem}
 \label{thm:multi-divisible-ir}
 Modified \text{\bf \texttt{VCG-T}}\ is individually rational for every agent.
\end{theorem}

\begin{theorem}
 \label{thm:multi-divisible-relax}
 The allocation of the modified \text{\bf \texttt{VCG-T}}\ always gives integral solutions.
\end{theorem}
Hence, the following corollary also holds.
\begin{corollary}
\label{cor:multi-divisible-efficient}
 Modified \text{\bf \texttt{VCG-T}}\ is EPP.
\end{corollary}
To reduce the allocation problem to a perfect $b$-matching problem, we need to alter $b_i = l_i$, and \Cref{lem:equivalence} holds. Therefore, we conclude that 
\begin{theorem}
 \label{thm:multi-divisible-strong}
  Modified \text{\bf \texttt{VCG-T}}\ provides a combinatorial, strongly polynomial algorithm for computing a social schedule and delays.
\end{theorem}

\paragraph{Indivisible jobs}

A job is {\em indivisible} if the entire length $l_i$ of the job requires contiguous slots for execution within the period. Examples of such jobs are computer programs that are not parallelizable and needs a continuous execution. In the social scheduling setting, an individual may not be willing to visit the store multiple times, and therefore an allocation needs to allocate contiguous time-slots to that agent. We show that the optimal allocation problem in such a setting can be computationally intractable.

To show this, we consider the following simplification of the problem. Agent $i$ comes with a job having a valuation $v_i$ (private) and its length $l_i$ (public). The valuation is independent of the starting point of the job during that period. 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 tuple $V$ consists of agents' valuations and $L$ consists of the lengths of agents' jobs. The number of slots within a period are $m$. Each unit of the slot capacity ($k$) can be thought of a counter. Each counter processes one job until it is complete. The set of counters is denoted by $K=\{ 1,2,\dots,k \}$. In this section, we denote the set of all \textit{job-to-counter} allocations by $\mathcal{X}$. An allocation $X\in\mathcal{X}$, is a matrix $[x_{ic}]$ such that:
\begin{equation*}
x_{ic}=
    \begin{cases}
    1, & \text{if agent $i$'s job is allocated to counter $c$}\\
    0, & \text{otherwise}
    \end{cases}
\end{equation*}
\begin{definition}{\textbf{Multi-slot Indivisible Jobs Allocation Problem} (\text{\bf \texttt{MIA}})}: Given $(N,V,L,K,m)$, find $x\in\mathcal{X}$, such that the total valuation of the allocated jobs is maximum subject to the constraints that the total length of jobs allocated to any counter does not exceed the number of slots in that period and each job is assigned to at most one of the counters. Mathematically, \text{\bf \texttt{MIA}}\ is given by the following integer program (IP).
\begin{align}
 \label{eqn:MULTIALLOC_IP}
 \begin{split}
     \argmax_{X} & \sum_{c \in K} \sum_{i \in N}   v_{i}\ x_{ic} \\
     \text{s.t. } & \sum_{i \in N} l_i \ x_{ic} \leq m \quad \quad \forall c \in K\\
     & \sum_{c \in K} x_{ic} \leq 1 \quad \quad \forall i \in N\\
     & x_{ic}\in \{ 0,1\} \quad \quad \forall i \in N, \forall c \in K
 \end{split}
\end{align}
\end{definition}
We denote the decision version of \text{\bf \texttt{MIA}}\ with the same name which is defined as follows:
\begin{quote}
Given $(N,V,L,K,m,\beta)$, is there an allocation $X$ such that $\sum_{i \in N} l_i x_{ic} \leqslant m, \ \forall c \in K$, $\sum_{c \in K} x_{ic} \leqslant 1,\  \forall i \in N$, and $\sum_{c \in K} \sum_{i \in N}   v_{i}\ x_{ic}\geqslant \beta$ where $\beta\in\mathbb{R}$.
\end{quote}
\begin{theorem}
\label{thm:NPc}
 \text{\bf \texttt{MIA}}\ is NP-complete.
\end{theorem}
\begin{proof} 
To prove that \text{\bf \texttt{MIA}}\  is in $NP$, we have to show that, ``given an allocation $X$, one can verify in polynomial time that $X$ is a valid solution for \text{\bf \texttt{MIA}}.'' The verification will need to solve and check the $k+n$ constraints, which are linear inequalities. Therefore, the computation of the value of objective function and comparison with $\beta$ is doable in polynomial time. Hence, \text{\bf \texttt{MIA}}\  is in NP.

Next we have to show that, ``every problem in NP is reducible to \text{\bf \texttt{MIA}}\  in polynomial time." To prove this, we select the classical \textit{knapsack problem}, which is NP-complete and  show that it is reducible to \text{\bf \texttt{MIA}}. The \textit{knapsack problem} is as follows: given a set of items $I=\{1,2,\dots,n\}$, their weights $W=(w_1,w_2,\dots,w_n)$, profits $P=(p_1,p_2,\dots,p_n)$ and a knapsack of capacity $\kappa$, find a subset $Y$ of items from $I$ such that the total profit of the selected items is maximum, and the total weights of the selected items does not exceed $\kappa$. Let $y$ be a vector such that, $y_i=1$ if $i \in Y$, and $y_i=0$ otherwise. The decision version of the knapsack problem is: ``Given $(I,P,W,\kappa,\beta')$, is there a vector $y$ such that $\sum_{i\in I} y_i\ w_i \leq \kappa$, and for which $\sum_{i\in I} p_i y_i \geq$ $\beta'$ where $\beta' \in \mathbb{R}$."

Considering the set of items $I$ as the set of agents $N$, item's profit in $P$ as the value of agent's job in $V$, item's weight in $W$ as the length of the jobs in $L$, and the knapsack with a capacity $\kappa$ as the single counter available till $\kappa$ number of slots; the knapsack problem $(I,P,W,\kappa,\beta')$ is reducible in polynomial time to \text{\bf \texttt{MIA}}\ $(I,P,W,\{1\},\kappa, \beta')$.
\end{proof}

Our primary objective in this paper is to find a computationally tractable mechanism that satisfies the desired properties outlined in \Cref{sec:desiderata}. We see that in the context of indivisible job allocation, the problem of finding the efficient allocation is intractable. However, it may be possible to find an approximately efficient tractable allocation which is truthful and individually rational. We leave this problem for a future investigation.

In the following section, we investigate the performance of \text{\bf \texttt{VCG-T}}\ in real-world scenarios.

\section{Single-slot Job Allocation Setup}
\label{sec: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 {\em periods}, and each period is further divided into {\em 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.\footnote{The analysis and results will follow even if the capacity $k_j$ varies with the slots $j \in M$.} A {\em central planner} (e.g., an AI app) allocates these slots to the agents, maintaining the capacity constraint. Every agent $i$ has a {\em cardinal} preference $v_{ij} \in \mathbb{R}_{\geqslant 0}$ (called the agent's {\em 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 {\em quasi-linear form}~\cite{SL08}, which implies that every agent wants a more valued slot to be assigned to her and also wants to wait less.
\begin{equation}
    \label{eq:utility}
    u_i((A,d), v_i) = v_i(A) - d_i, \text{ where } v_i(A) = v_{i a_i^*}.
\end{equation}
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.
\begin{definition}[Social Scheduling Function (SSF)]
 A {\em 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.\footnote{We overload the notation $A$ and $d$ to denote both functions and values of those functions, since their use will be clear from the context.}
\end{definition}

\section{Preliminary Definitions}
\label{sec:desiderata}

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 {\em efficient} in each period, i.e., it maximizes the sum of the valuations of all the agents. 
\begin{definition}[Efficient Per Period (EPP)]
 \label{def:efficiency}
 An SSF $f$ is {\em 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
 \begin{equation}
     \label{eq:efficient}
     A^*(v) \in \argmax_{A \in {\cal A}} \sum_{i \in N} \sum_{j \in M} v_{ij} a_{ij}.
 \end{equation}
\end{definition}

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 {\em irrespective of the reports of the other agents}.
\begin{definition}[Per Period Dominant Strategy Truthful]
 \label{def:non-manipulability}
 An SSF $f(\cdot) = (A(\cdot), d(\cdot))$ is {\em truthful in dominant strategies per period} if for every $v_i, \hat{v}_i, \hat{v}_{-i}$, and $i \in N$
  \begin{align*}
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}).
  \end{align*}
\end{definition}


The next property ensures that it is always weakly beneficial for every rational agent to participate in such a mechanism.
\begin{definition}[Individual Rationality]
 \label{def:ir}
 An SSF $f(\cdot) = (A(\cdot), d(\cdot))$ is {\em individually rational} if for every $v$, and $i \in N$
  \begin{align*}
   v_i(A(v)) - d_i(v) &\geqslant 0.
  \end{align*}
\end{definition}


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 \textit{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 \textit{NP (nondeterministic polynomial)}. We consider the NP-complete class of problems, which is defined as follows.
\begin{definition}[NP-complete]
A decision problem $Q$ is NP-complete if:
\begin{enumerate}
    \item $Q $ is in NP (class of all decision problems verifiable in	polynomial time), and
    \item Every problem in NP is reducible to $Q$ in polynomial time.
\end{enumerate}
\end{definition}
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 {\em strongly polynomial} \cite{grotschel1993complexity}. 
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. 


\begin{definition}[Strongly Polynomial]
 \label{def:strong-poly}
    An algorithm runs in {\em strongly polynomial time} if \cite{grotschel1993complexity}
    \begin{itemize}
        \item 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
        \item the space used by the algorithm is bounded by a polynomial in the input size.
    \end{itemize}
\end{definition}
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$.

\section{Periodic Mechanisms}\label{sec:online}


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.\footnote{For mechanisms that consider the dynamic extension of such allocation problems with finite or infinite horizon~\cite[e.g.]{bergemann-valimaki10dynamic-pivot}, (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 \cite{borgers2015introduction} 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.

\paragraph{Description of \text{\bf \texttt{VCG-T}}.}
The SSF needs to decide on the allocation $A$ and the delay $d$. 
\text{\bf \texttt{VCG-T}}\ computes the allocation as follows.
\begin{align}
 \label{eqn:LP}
 \begin{split}
     & \argmax_{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}
\end{align}
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~(\ref{eqn:LP}) 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~(\ref{eqn:LP}) by $A^*(v)$. Also, denote the allocation given by LP~(\ref{eqn:LP}) when agent $i$ is removed from the system by $A^*_{-i}(v_{-i})$.
For agent $i$, the delay is given by,
\begin{align}
\label{eqn:payment}
\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}
\end{align}
The mechanism in every period is described in \Cref{algo:mechanism}.

\begin{algorithm}[H]
\caption{\text{\bf \texttt{VCG-T}}\ in every period}
 \begin{algorithmic}[1]
  \STATE {\bf Input:} for every agent $i \in N$, the value $\hat{v}_i$
      \STATE compute $A^*(\hat{v})$ (\Cref{eqn:LP}) as the allocation \label{alg:allocation-step}
      \STATE charge a delay $d_i(\hat{v})$ (\Cref{eqn:payment}) to every $i \in N$ for which they cannot access the scheduling mechanism again
    \STATE {\bf Output:} $A^*(\hat{v})$ and $d(\hat{v})$
  \end{algorithmic}
 \label{algo:mechanism}
     \end{algorithm}


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

\section{Single-slot Jobs}
\label{sec:theory}
We first show that the allocation given by \text{\bf \texttt{VCG-T}}\ indeed maximizes per-period social welfare.
\begin{theorem}
 \label{thm:relax}
 The allocation of \text{\bf \texttt{VCG-T}}\ given by LP~(\ref{eqn:LP}) always gives integral solutions.
\end{theorem}
\begin{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~(\ref{eqn:LP}) 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~(\ref{eqn:LP}) respectively. We show that $C$ is totally unimodular (TU), which is sufficient to conclude that LP~(\ref{eqn:LP}) has integral solutions.
 We use the Ghouila-Houri characterization \cite{camion1965characterization} 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.
\end{proof}

The result above shows that the optimal solution of LP~(\ref{eqn:LP}) is an optimal solution of the corresponding integer program that maximizes the per-period social welfare. Hence, we conclude the following.
\begin{corollary}
\label{cor:efficient}
 \text{\bf \texttt{VCG-T}}\ is EPP.
\end{corollary}

Even though the LP formulation of \text{\bf \texttt{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 \text{\bf \texttt{VCG-T}}. The forthcoming results show that the allocation and delays of \text{\bf \texttt{VCG-T}}\ are strongly polynomial.
To show this, we will first reduce the allocation problem (LP~(\ref{eqn:LP})) to a minimum weight $b$-matching problem, which is known to be strongly polynomial \cite{schrijver2003combinatorial}.

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$.

\begin{lemma}
\label{lem:equivalence}
 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~(\ref{eqn:LP}).
\end{lemma}
\begin{proof}
 We prove this via contradiction. Suppose $A^*$ is not an optimal solution to LP~(\ref{eqn:LP}), i.e., there exists $A'$ 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}' > \sum_{j \in M} \sum_{i \in N} v_{ij} a_{ij}^*$. Consider the edge set $E'$ corresponding to $A'$. Clearly this is a perfect $b$-matching, since $A'$ satisfies the constraints of LP~(\ref{eqn:LP}), and $E'$ 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.
\end{proof}

Note that the delays are calculated by solving an equivalent LP like LP~(\ref{eqn:LP}) 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.

\begin{corollary}
\label{cor:delay}
 The computation of the delays in \text{\bf \texttt{VCG-T}}\ is strongly polynomial.
\end{corollary}
Combining \Cref{thm:relax}, \Cref{lem:equivalence}, and \Cref{cor:delay},  we get the following result.

\begin{theorem}
 \label{thm:strong}
  \text{\bf \texttt{VCG-T}}\ provides a combinatorial, strongly polynomial algorithm for computing a social schedule and delays.
\end{theorem}


Since \text{\bf \texttt{VCG-T}}\ uses the VCG payment expression to compute the time delay and because the allocated slots are {\em goods} to the agents, the following two facts follow from the known properties of the VCG mechanism.
\begin{fact}
\label{thm:dsic}
 \text{\bf \texttt{VCG-T}}\ is per period dominant strategy truthful.
\end{fact}
\begin{proof}
 This proof is a standard exercise in the line of the proof for Vickery-Clarke-Groves (VCG) mechanism \cite{Vick61,Clar71,Grov73}. 
 
 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{'}_{i}$(the corresponding value function is $v{'}_{i}$), and gets better utility.
 Suppose ${A}(v{'}_{i},v_{-i}) = A'$ and ${A}({v}_{i},v_{-i}) = A^{*}$. The utility of $i$ for $A'$ is:
 \begin{align*}
     \lefteqn{v_i(A')- d_i(v'_{i},v_{-i})} \\
     & = v_i(A') - \sum_{\ell \in N \setminus \{i\}} v_\ell(A(v_{-i})) + \sum_{\ell \in N \setminus \{i\}}  v_\ell(A^{'})\\
     & = \sum_{\ell \in N }  v_\ell(A^{'}) - \sum_{\ell \in N \setminus \{i\}} v_\ell(A(v_{-i}))  
 \end{align*}
 Similarly, the utility of $i$ for $A^{*}$ is:
 \begin{align*}
      = \sum_{\ell \in N }  v_\ell(A^{*}) - \sum_{\ell \in N \setminus \{i\}} v_\ell(A(v_{-i}))  
 \end{align*}
 If $i$ gets better utility by misreporting her valuation as $v'(.)$, then
 \begin{align*}
     \sum_{\ell \in N }  v_\ell(A^{'})  > \sum_{\ell \in N }  v_\ell(A^{*}) 
 \end{align*}
 The above inequality leads to the contradiction that $A^{*}$ is optimal for the reported valuation $({v}_{i},v_{-i})$. Therefore, \text{\bf \texttt{VCG-T}}\ is dominant strategy truthful in every period.
\end{proof}

\begin{fact}
 \label{thm:ir}
 \text{\bf \texttt{VCG-T}}\ is individually rational for every agent.
\end{fact}
\begin{proof}
 Consider agent $i$. The utility of $i$ under \text{\bf \texttt{VCG-T}}\ is $v_i(A^*(v)) - d_i(v)$
 \begin{align*}
     &= v_i(A^*) - \Big( \sum_{\ell \in N \setminus \{i\}} v_\ell(A^*_{-i}) - \sum_{\ell \in N \setminus \{i\}}  v_\ell(A^*) \Big) \\
     &= \Big( \sum_{\ell \in N}  v_\ell(A^*) - \sum_{\ell \in N} v_\ell(A^*_{-i}) \Big) + v_i(A^*_{-i}) \geqslant 0
 \end{align*}
 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.
\end{proof}

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

\section{Multi-slot Jobs}
\label{sec:multi}

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 {\em 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 $\AA=[\ensuremath{\mathfrak a}\xspace_{ij}]$, where $\ensuremath{\mathfrak a}\xspace_{ij}=1$ if agent $i$'s job starts at slot $j$, else $\ensuremath{\mathfrak a}\xspace_{ij}=0$, and $\ensuremath{\mathfrak a}\xspace_{i}$ represents the slot allocation vector for agent $i$.  
Keeping all other notations as before, we define the \text{\bf \texttt{MIA}}\ problem as follows.
\begin{definition}[Multi-slot Indivisible jobs Allocation problem (\text{\bf \texttt{MIA}})]: Given $(N, M, V, L,k)$, find an allocation $\AA$, such that $\sum_{i \in N} \sum_{j \in M} v_{ij}(\ensuremath{\mathfrak a}\xspace_{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, \text{\bf \texttt{MIA}}\ is given by the following integer program (IP).
\begin{align}
 \label{eqn:MULTIALLOC_IP}
 \begin{split}
      & \argmax_{A} \sum_{i \in N} \sum_{j \in M}  v_{ij}\ \ensuremath{\mathfrak a}\xspace_{ij} \\
      & \text{s.t. } \sum\limits_{i \in N} \sum\limits_{\substack{p \in M \\ j \in [p, p+l_i-1]}} \ensuremath{\mathfrak a}\xspace_{ip} \leqslant k, \forall j \in M,\\  &  \sum_{j \in M} \ensuremath{\mathfrak a}\xspace_{ij} \leqslant 1, \forall i \in N; \ \ensuremath{\mathfrak a}\xspace_{ij}\in \{ 0,1\}, \forall i \in N, \forall j \in M
 \end{split}
\end{align}
\end{definition}
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 \text{\bf \texttt{MIA}}\ is computationally intractable by performing a polynomial reduction from the Multi-Unit Combinatorial Auction (\text{\bf \texttt{MUCA}}), which is NP-complete.

\input{multi_indiv_approx}


\section{Multi-slot Divisible jobs}
\label{sec:div-jobs}
A {\em 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~(\ref{eqn:LP}) 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 \Cref{thm:relax}). Therefore the new LP also has integral optimal solution. 
The {\em modified} \text{\bf \texttt{VCG-T}}\ is identical to \Cref{algo:mechanism} with Step~\ref{alg:allocation-step} replaced with the solution to the modified LP as explained above.
Hence, the following results hold similarly.

\begin{proposition}
 \label{thm:multi-divisible-dsic}
 Modified \text{\bf \texttt{VCG-T}}\ is per period dominant strategy truthful for multi-slot divisible jobs.
\end{proposition}

\begin{proposition}
 \label{thm:multi-divisible-ir}
 Modified \text{\bf \texttt{VCG-T}}\ is individually rational for every agent.
\end{proposition}

\begin{theorem}
 \label{thm:multi-divisible-relax}
 The allocation of the modified \text{\bf \texttt{VCG-T}}\ always gives integral solutions.
\end{theorem}
Hence, the following proposition also holds.
\begin{proposition}
\label{cor:multi-divisible-efficient}
 Modified \text{\bf \texttt{VCG-T}}\ is EPP.
\end{proposition}
To reduce the allocation problem to a perfect $b$-matching problem, we need to alter $b_i = l_i$, and \Cref{lem:equivalence} holds. Therefore, we conclude the following result.
\begin{theorem}
 \label{thm:multi-divisible-strong}
  Modified \text{\bf \texttt{VCG-T}}\ provides a combinatorial, strongly polynomial algorithm for computing a social schedule and delays.
\end{theorem}











