\section{#2}\label{s:#1}}
\newcommand\Endnote[2]{\endnote{#2}#1\xspace}

\begin{document}
\title{The equilibrium classical scatter spectrum of waves}
\author{V. Guruprasad}
\affiliation{Inspired Research, New York.}
\begin{abstract}
\noindent
Regardless of
	the unspecific notions of photons as
		light complexes, radiation bundles or wave packets,
the radiation from
	a single state transition
is at most
	a single continuous wave train
that starts and ends
	with the transition.
The radiation equilibrium spectrum must be
	the superposition sum of
		the spectra of such wave trains.
A classical equipartition of
	wave trains
cannot diverge
	since they would be finite in number,
whereas standing wave modes are
	by definition infinite,
		which had doomed Rayleigh's theory,
and
	concern only
		the total radiation.
Wave trains are
	the microscopic entities of radiation
		interacting with matter,
that correspond to
	molecules in kinetic theory.
Their quantization
	came from matter transitions
in Einstein's 1917 derivation
	of Planck's law.
The spectral scatter of wave trains
	by Doppler shifts,
which cause
	the wavelength displacements in Wien's law
used for the frequency dependence
	in Einstein's derivation,
is shown to yield
	the shape of the Planck spectrum.
A Lorentz transform property of Doppler shifts
	discovered by Einstein
is further shown equivalently
	necessary and sufficient
		to have corrected Rayleigh's theory.

\end{abstract}
\maketitle

\newcommand\Expv[1]{\ensuremath{\bar{#1}}}
\newcommand{\mathbf{e}_x}{\mathbf{e}_x}
\newcommand{\mathbf{e}_y}{\mathbf{e}_y}

\Section{intro}{Introduction}

Presented below is
	the first-ever treatment of
the classical spectral scatter of
	electromagnetic wave trains
		in a cavity,
due to classical Doppler shifts by simple reflection
	from atoms or cavity walls
and
	their thermal motions or vibrations.
As the number and energy of
	wave trains
from
	a finite set of atoms
		would be finite,
the divergence of
	Rayleigh's theory
		cannot occur.
The spectral scatter is shown to bear
	the form of the Planck spectrum
classically due to
	proportional energy increases
as a Lorentz transform effect in
	Doppler frequency shifts,
incidentally discovered by Einstein
	\cite{Einstein1905c},
who ascribed it to
	``light complexes''
	\cite{Einstein1905c}
	or ``bundles''
	\cite{Einstein1917qt}
in deference to
	the quantum hypothesis
	\cite{Redzic2004,Norton2006,Norton2008}.
Other traditional notions of photons as wave packets having
	distinct phase and group velocities
	(\cf \cite[\S{31}]{Dirac})
		refer to Fourier spreads
	also possessed by
		the wave trains.
There was also a recent attempt to identify photons with
	the individual undulations in sinusoidal waves
	\cite{Popescu2007},
which makes partial sense in
	harmonic families of standing wave modes
	\cite{Prasad2006b}.
The present focus is more simply on
	\emph{arbitrary} classical travelling waves
constrained only by finiteness of
	length and energy.

The Lorentz property holds analytically for
	classical electromagnetic waves of
		arbitrary amplitudes
	between
		phase boundaries
	\cite{Popescu2007},
and thus specifically
	the wave trains.
Einstein's notions of
	radiation energy and momentum in
		detailed balance with state transitions in matter
	\cite{Einstein1917qt}
extended
	known classical principles of these quantities
		to radiation,
and its only other input
	concerning radiation was Wien's law,
		also classical in origin.
His treatment was thus
	a rigorous classical derivation of
		Planck's law
that traced
	quantization to matter transitions,
despite
	his own apparent attribution of the Lorentz property
		to inherent quantumness.

The present result proves
	this contrarian insight correct
by showing that
	the same physical mechanisms
do reproduce
	the Planck form
		without quantization
in the absence of
	matter transitions.
It also implies that
	Einstein's treatment was incomplete,
despite reproducing
	Planck's law,
in overlooking
	the Doppler shifts from non-transitional reflections,
and that
	radiation quantization is
		an over-reaching premise
though empirically correct at
	optical frequencies.

The result complements
	emerging reports of entanglement
obtainable classically
	via fluid mechanics
	\cite{Brady2013}
with relation to
	electromagnetic theory
	\cite{Brady2015},
and from Maxwell's equations
	under various conditions
	\cite{Carroll2015,Qian2013},
even as
	loophole-free confirmations of non-locality
		are achieved for the quantum result
	\cite{LoopholeFree2015}.
The quantumness implication of entanglement itself
	is now questioned
	\cite{Ghose2013,Qian2015},
echoing
	general anticipation of entanglement in classical waves
in
	\cite{Prasad2000b}.

The result is
	straightforward,
and could be overturned only by
	an error in assuming
that
	any single state transition of matter
emits at most
	a single continuous wave train of radiation.
If we assumed,
	like Planck and Einstein,
that matter comprises
	a dynamical structure of particles,
		some with charge,
and its internal states comprise
	specific arrangements and motions,
then classically,
	a state transition must involve
		a continuous change
	from one arrangement and motions to the next,
implying
	a continuous variation of
		electric and magnetic forces
	at any point of observation,
which qualifies as
	a continuous wave train.
Emission from
	a single state transition
cannot be
	a multitude of whole wave trains,
nor
	a more general combination of
		sinusoidal wave components
	amounting to more than
		a single wave train,
as also inferred by Einstein
	\cite{Einstein1917qt}
	for concurrently acting ``bundles''.

A finite wave train is
	the simplest and most general description of
an electromagnetic waveform
	associable with
		any single, discrete state transition in matter,
and is sufficient,
as each such wave train would not only
	bear a full energy quantum
but also satisfy
	directionality and momentum balance
		in interactions with matter,
	as shown by Einstein
	\cite{Einstein1917qt},
and its spatial extent suffices to explain
	quantum non-locality,
		as also proved here.
The traditional broader allowance for complexes or bundles
	thus did not serve for generality
except in analogy to
	``complexions'' or microstates
in view of
	their arbitrary
		amplitude and polarization distributions
	and
		wavefronts,
and has instead inadvertently denied
	the only possible functional form for representing
		discrete interactions with matter.
Related historical difficulties,
leading to a belief in
	the inadequacy of classical physics itself,
can be attributed to
	standing wave modes
		without the Lorentz property
being
	the only classical model
		in Rayleigh and Planck theories
	\cite{Planck1900,Planck1901,Planck1914},
as well as
in recent ideas of
	a classical origin of Planck's law arguing
		zero-point energy and Casimir forces are classical
	(\cf \cite{Boyer1969,Boyer2002,Boyer2003,Boyer2012,Cercignani1972,Cercignani1998}).

The modes are favoured as
	a stationary representation of
		the equilibrium steady state,
and also
	for their similarity to
		the vibrational modes of molecules
and to
	cyclic coordinates associated with stationary states
		in classical equipartition
	\cite{Rayleigh1900ke,Rayleigh1900rad}.
However,
	standing wave modes
by definition concern
	the \emph{total} radiation in the cavity,
and the role of molecular vibrations
	more precisely concerns
		spin and orbital angular momenta,
	as contained in
		the polarization and wavefront distributions,
	respectively
which are now well understood
	\cite{NaturePhotonics2015}.
Further,
	modes are defined by geometry
		and inherently infinite in number,
as
	wavelengths are infinitely divisible
		real valued quantities,
so Rayleigh's theory was
	doomed to divergence by
		this choice of entities,
in treating
	classical equilibration
		without the Lorentz property.
As shown later by Bose
	\cite{Bose1924},
Planck's oscillator hypothesis
	also obviates Wien's law,
and thereby
	\emph{all} dynamical considerations.
This leaves Einstein's work
	the only historical consideration of
		the microscopic dynamics of radiation.

Correspondingly,
the present theory is the radiative analogue of
	the treatment of molecular motions
		in the kinetic theory
but got skipped in
	radiation theory
due to
	the success of
		macroscopic thermodynamic principles,
	using standing waves,
in yielding
	the analogous result of
		radiation pressure
in
	Stefan-Boltzmann and Wien's laws.
The wavelength displacements
	in Wien's law
are Doppler shifts upon reflection at walls
	subject to macroscopic motions
	\cite{Planck1914},
so wall Doppler shifts provided
	a critical physical mechanism for dispersing
		the radiant energy across frequencies
	in treatments
		including Einstein's,
as modes,
	by definition,
cannot mutually interact
	and atomic spectra are narrow.
However,
as all considerations in Wien's law
	are macroscopic,
it constrained rather than explain
	the spectral equilibration.
Brownian motions
	due to radiation reactions,
also considered by Einstein
	\cite{Einstein1917qt},
would be
	a weak mechanism at very low pressures.

It could be argued,
	especially on the basis of Fermi-Pasta-Ulam theory
	(\cf \cite{FPU1955,TodaKuboSaito1992,Berman2005,Porter2009})
	and related ideas of fluctuations,
that reflections by stationary walls suffice
	to explain the spectral equilibration,
as they would spatially disperse
	wave fronts much like molecules.
However,
the premise of
	stationary confining walls
in both kinetic and radiation theories is itself
	another traditionally overlooked defect,
since wall impacts,
	whether by molecules or photons,
should also set
	real walls of finite mass
		into vibration,
much as
	the photon interactions would set
		the molecules into Brownian motions
	in Einstein's treatment
	\cite{Einstein1917qt},
until
	the wall vibration modes reach equilibrium with
		the confined gas or radiation.
The wall vibrations do not alter
	equilibrium energy, temperature or pressure,
so their neglect
	did not affect the overall result,
but their absence must denote
	walls at absolute zero temperature
		by the third law,
	which was only realized later
		\cite{Nernst1926},
and would thereby violate
	the premise of equilibrium of
		a confined gas or radiation
			at a steady non-zero temperature.
Their inclusion is thus required for
	completeness of the dynamical considerations,
and would also resolve
	Loschmidt's paradox
	(\cf \cite{Loschmidt1876,PhysWebPlanck2000})%
	\footnote {
	Essentially by implying that
		a statistical system in equilibrium cannot be also truly closed.
	},
besides providing
	a general mechanism
for Doppler shifts
	at the microscopic level.

The overall result is thus not only that
	the classical electromagnetic wave
is also
	the most general notion of a photon
		given by quantum theory,
in all aspects of
	matter interactions and thermodynamics
as well as
	non-locality,
but more so that
	the current ideas fundamentally derive from
		ignorance and flaws
	in the classical attempts,
and misperception of
	a key classical electromagnetic wave property
		by Einstein.
Complementary ideas of
	the thermodynamics of
		information representation
	and
		erasure
	in physical observers
	\cite{Landauer1961b,Landauer1991,Bennett1973,Bennett1987},
and application of
	the third law to
		observer state transitions
	in process of physical observations,
classically impose
	an inherent probabilistic character
		to all observations,
so that
	even the quantum probabilities
cannot remain
	a matter of postulate.

\vspace{3pt}

The next section revisits
	Einstein's 1905 and 1917 papers
		in the present view.
Sufficiency of the Lorentz property
	to correct Rayleigh's theory
is shown
	in Section \ref{s:rayleigh}.
The core result for wave trains follows
	in Section \ref{s:theory}.

\Section{background}{Background of the core result}

In the 1917 paper
	\cite{Einstein1917qt},
Einstein considered that
	the equilibrium with radiation
could not change
	the molecular energy distribution,
	$
	W_n
	=
		p_n
		e^{
			- E_n  k_B T
		}
	$
	from the kinetic theory,
where
	$W_n$ denoted the relative frequency of
		a state of energy $E_n$.
This led,
	via considerations of energy and momentum exchanges
		with radiation,
to the condition
\begin{equation} \label{e:einstein}
		p_n
		e^{
			- E_n  k_B T
		}
		B^{m}_{n}
		\rho
	=
		p_m
		e^{
			- E_m  k_B T
		}
		\left(
			B^{n}_{m}
			\rho
		+
			A^{n}_{m}
		\right)
\quad
\text{whence}
\quad
	\rho
	=
		\frac{
			A^{n}_{m}  B^{n}_{m}
		}{
			e^{
				(
				E_m
				-
				E_n
				)
				 k_B T
			}
			- 1
		}
\end{equation}
where
	$A^{n}_{m}$ was
		a probability coefficient to represent
			spontaneous emission,
and
	$B^{m}_{n}$ and $B^{n}_{m}$ were
		coefficients to denote
			absorption and stimulated emission,
	respectively.
The emission and absorption mechanisms
	were the only assumptions
		new in the 1917 paper,
and no inherent dependence on frequency
	was assumed.

The connection to frequencies was obtained by
equating to
	Wien's law in the form
	$
	\rho =
		\alpha \nu
		e^{
			- h \nu  k_B T
		}
	$,
which led to
	the relations
	$
	A^{n}_{m}  B^{n}_{m} = \alpha \nu^3
	$
and
	$
	E_m - E_n = h \nu
	$,
where the latter relates to
	Bohr's model.
In this form of Wien's law,
	$h$ is a scale factor
		relating time and energy
and signifies no quantization,
	as pointed out by Einstein.
The wavelength displacements
	providing the frequency $\nu$
result from
	the Doppler shifts of standing wave modes
caused by
	macroscopic motions of cavity walls
during
	adiabatic compression or expansion
	\cite{Einstein1905a,Planck1914}.
The only assumptions of discreteness were therefore that
	molecules had discrete energy levels $E_n$,
so only
	the energy levels enter eq.~(\ref{e:einstein}),
and that
	their radiative interactions occurred as
		discrete events,
limiting
	the duration or length of the wave trains
		emitted in each transition.

The additional arguments of momentum
were necessary for
	completeness of the dynamical picture of interaction,
including
	the implication of induced Brownian motion
		from the radiative reactions.
Those ideas refined over
	his 1905 photoelectricity paper
	\cite{Einstein1905a},
which had concerned energy quanta
	but not momentum.
The arguments used the relation
	$p = E  c$
	from classical electromagnetics
	\footnote {
	The momentum implication led Maxwell to accept
		Crooke's explanation of the radiometer
			that turned out wrong
		and was corrected by Reynold's theory
			in Maxwell's last paper
			(1879).
	The radiation pressure in
		both the Stefan-Boltmann and Wien's laws
	comes from
		classical radiation momentum,
	and both Planck and Einstein
		depended on Wien's law.
	},
and the Lorentz property,
\begin{equation} \label{e:lorentz}
	E' = E
		\sqrt{
			\frac{
				1 - v  c
			}{
				1 + v  c
			}
		}
\quad
\text{along with}
\quad
	\nu' = \nu
		\sqrt{
			\frac{
				1 - v  c
			}{
				1 + v  c
			}
		}
	.
\end{equation}
which had been derived from
	a standpoint of energy conservation
		in his 1905 relativity paper
	\cite{Einstein1905c},
without involving
	any specific wave representation,
as opposed to
	its derivation in
	\cite{Popescu2007}.
The approach avoided
	convergence issues
historically encountered
	in Fourier theory
	\cite{Wheeler1987,Kleiner1989},
as well as
	problems of
		complexity and completeness of representation.

Einstein had been expressly concerned
	with ``the theory of light
		which operates with continuous spatial functions''
	in his photoelectricity paper
	\cite{Einstein1905a},
but his perception was
	classical and deterministic,
just as
	the action-angle formalism of quantum mechanics
to which he made key contributions
	\cite{Curtis2009}.
Eq.~(\ref{e:lorentz}) did not require or prove
	the irreducibility of quantization to classical laws,
despite its similarity to
	Planck quantization.
The dissociation from wave representations
	would have impeded
application of eq.~(\ref{e:lorentz}) to
	standing wave modes
		following Rayleigh and Planck,
however, just as
the strong notion of localization of radiant energy
	in deriving eq.~(\ref{e:lorentz})
went against
	the probabilistic quantum notions in
	\cite{EPR1935}.
In any case,
\emph{every} input in
	Einstein's derivation
was thus classical
\emph{except}
	the discreteness of molecular states and their transitions
	(eq.~\ref{e:einstein}),
so the derivation already implicated
	the discreteness of matter
		for quantization.

The classical derivation of eq.~(\ref{e:lorentz})
	needed for the present result
is adequately treated in
	\cite{Popescu2007},
but the further notion of quanta
	in \cite{Popescu2007}
as half-wavelength segments of travelling waves
	is not endorsed,
as it contradicts the uncertainty principle
	in single photon observations.
The only physical basis for that notion is
	the conservation of energy of
		any sequence of such segments,
\ie,
	of whole wave trains,
	under propagation
		and Lorentz transformations,
already assured classically
	without quantum significance.
Such half-wavelength segments of
	\emph{standing wave modes}
do correspond to quanta
	under second quantization
because
	harmonically related modes differ in geometry
		only by multiples of half-wavelengths,
	and in energy
		by whole quanta.
Along an internal dimension $L$
	in a cavity,
a standing wave mode of wavelength $\lambda$
	would have
	$
	N =
		2 L  \lambda
	=
		2 L \nu  c
	$
	such segments,
whence
	$N$ is proportional to frequency $\nu$.
Planck's quantization rule
	$E = h \nu$
then promises
	$
	EN =
		h \nu c  2 L \nu
	=
		h c  2 L
	$,
independent of wavelength or mode,
	for segment energy,
and the quantum $h \nu$ is the energy of
	a whole mode of frequency $\nu$,
and not of
	an individual half-wavelength segment.

\Section{rayleigh}{Doppler-Lorentz correction to Rayleigh's theory}

The further attempt in
	\cite{Prasad2006b}
to identify
	families of harmonically related
		standing wave modes
	with Planck oscillators,
		consistent with second quantization,
	was incomplete,
as it needed
	mode energies to correspond to
		integrals over phase increments in multiples of $\pi  2$,
	instead of
		the cavity dimension $L$.
The ordinary classical proportionality of
	standing wave energies to $L$
would leave the modes equiprobable under
	a Boltzmann probability distribution,
and thus reduce to
	Rayleigh's theory
		and its problem of divergence.
In hindsight,
eq.~(\ref{e:lorentz})
	also addresses that problem
since the premise of
	Doppler shifts due to wall vibrations
		as the mechanism of mode interactions
implies that
	a transition from a mode of frequency $N c  2 L$
		to frequency $(N + 1) \, c  2 L$
would also raise the energy by
	a ratio $(N + 1)N$,
taking up energy and momentum
	from the wall vibrations,
		and the \emph{vice versa}\xspace.
The energy of a mode of $N$ segments
	is then proportional to $N$,
		as required for Planck quantization
	per the reasoning above,
instead of being
	invariant of frequency,
as Rayleigh had assumed
	in ignorance of eq.~(\ref{e:lorentz}).
The corrected theory then yields
	the same cutoff at higher frequencies
		as Planck's,
as the higher frequencies would be less probable
	by the same probability factors
		because of the higher energies.

Since Planck's theory
	did not concern matter states,
and the standing wave modes,
	though discrete like the molecular states,
led to divergence
	in Rayleigh's theory,
Planck's inference of quantization derived from,
and thereby depended on,
	his hypothesis of oscillators
		with discrete energy levels.
This dependence is especially clear from
	the Bose derivation
	\cite{Bose1924},
which uses
	a dynamical phase space for
		the radiation energy and momentum
	discretized under
		Planck quantization
to eliminate
	Wien's law.
In his 1901 paper
	\cite{Planck1901},
Planck introduced
	a model of $N$ discrete resonators
that could bear only exact multiples of
	a small amount of energy $\epsilon$,
to compute
	the probability $W$ in Boltzmann's equation
		$S = k_B \log W$,
from
the number of ways
	the total energy $U_N = P \epsilon$
could be shared among
	the $N$ resonators.
This gave
\begin{equation} \label{e:oscentropy}
	S
	=
		k
			( 1 + U  \epsilon )
			\log
			( 1 + U  \epsilon )
		-
			( U  \epsilon )
			\log
			( U  \epsilon )
\end{equation}
for the per-resonator entropy
	in terms of the resonator energy $U$.
Separately,
Wien's law in the form
	$
	E \, d \lambda
	=
		\theta^5
		\gamma (\lambda \theta)
	\,
		d \lambda
	$
was shown to imply,
	via Kirchhoff-Clausius law
		for blackbody emissivity,
the energy density
\begin{equation} \label{e:wienthiesenplanck}
	u
	=
		\frac{\nu^3}{c^3}
		f
		\left(
			\frac{\theta}{\nu}
		\right)
	,
\end{equation}
where
	$\gamma$ and $f$ are functions
whose precise form
	is not significant in the result,
and
	$\theta$ is
		the thermodynamic temperature.
The energy $U$ of a resonator
	had been independently
related to
	the intensity of
		an applied linearly polarized oscillating field
	as
	$
	I = U \nu^2  c^2
	$,
which then led,
	via the relation
	$
	u = 8 \pi I  c
	$,
to
	$
	u
	=

		8 \pi \nu^2 I  c^3
	$,
so $U$ could be obtained independently of $c$,
	and related to temperature and frequency,
by combining with
	eq.~(\ref{e:wienthiesenplanck})
as
\begin{equation} \label{e:oscthermo}
	U
	=
		\nu f \left(
			\frac{\theta}{\nu}
		\right)
\quad
\text{or, equivalently,}
\quad
	\theta
	=
		\nu f \left(
			\frac{U}{\nu}
		\right)
	.
\end{equation}
The statistical definition of temperature
	$
	dS  dU = 1 / \theta
	$
then led to
	$
	S = f ( U  \nu )
	$
	with eqs.~(\ref{e:oscthermo}),
and to
	the proportionality
	$
	\epsilon \propto \nu
	$
on comparing with
	eq.~(\ref{e:oscentropy}).
Replacing
	$\epsilon$
with
	$h \nu$
in
	eq.~(\ref{e:oscentropy})
and evaluating
	the derivative $d S  d U$
then led to
\begin{equation} \label{e:planck}
	U
	=
		\frac{h \nu}{
			e^{h \nu  k_B T} - 1
		}
\quad
\text{and, via the $u$-$I$-$U$ relations above,}
\quad
	u
	=
		\frac{8 \pi h \nu^3}{c^3}
		\frac{h \nu}{
			e^{h \nu  k_B T} - 1
		}
	.
\end{equation}
Eqs.~(\ref{e:oscentropy}-\ref{e:planck})
	are directly reproduced from
	\cite{Planck1901}
but using symbol $I$ for the field intensity,
	instead of Planck's $K$,
and $k_B$ for Boltzmann's constant,
	to avoid confusion with wave numbers
		in the present treatment.

The resonator thermodynamic relations
	in eqs.~(\ref{e:oscthermo})
could not have implied
	discreteness of energy,
since
	eq.~(\ref{e:wienthiesenplanck}) comes from Wien's law
		whose considerations are strictly macroscopic,
and the only other consideration is
	the analogue field intensity $I$.
The discreteness and quantization
	in the result, eqs.~(\ref{e:planck}),
thus seem to originate from
	the oscillator model in eq.~(\ref{e:oscentropy}).
The proportionality implication is that
	the same factor $h$ must hold for all resonators
		in any cavity,
and also
	in all sets of cavities
		allowed to interact via radiation,
so $h$ must be
	a universal constant,
uniquely determined by
	the empirical energy density spectra,
		eqs.~(\ref{e:planck}),
	at different temperatures.

Yet, dimensionally,
	$h$ is a scale factor linking energy and frequency scales,
much as
	Boltzmann's constant $k_B$ relates
		energy and temperature
	and is also a universal constant,
and
Planck's model clearly followed
	Boltzmann's treatment of molecular energies
		in equal increments of $\epsilon$
	\cite{Boltzmann1877,Sharp2015},
which does not lead to
	a quantization of the molecular energies.
The result
	$\epsilon = h \nu$
does \emph{not} hold
	without eqs.~(\ref{e:oscthermo}) from Wien's law,
however,
so the cause of quantization in Planck's theory is again
	the atomic transitions producing the radiation
		in the observed spectra.
Bose's derivation showed that
	the nature of the frequency domain
makes
	$h$ irreducible to zero,
echoed in
	the quantum condition
	\cite{Born1926,Aitchison2008,Fedak2009},
but that aspect is implicit in
	the inherent anti-commutation of Poisson brackets
	\cite{Dirac1925}
	\cite[\S{21}]{Dirac}
and confers no more
	``experimental authority''
than say Hamilton already had for anticipating quantization
	(\cf \cite[\S{10-8}]{Goldstein}).

To verify this,
consider that in standing wave modes,
	discreteness is assured by definition,
and further,
any energy $\epsilon$ transferred from
	a mode of frequency $\nu$
to
	another of frequency $\nu' \ne \nu'$,
by simple reflection and Doppler shift
	from a moving wall or molecule,
or indirectly by
	its absorption by a molecule
		and subsequent re-emission
	with Doppler shift,
would be amplified to
	$
	\epsilon \nu'  \nu
	$
	by eq.~(\ref{e:lorentz}),
the difference
	$
	\epsilon (
		\nu' - \nu
		)
	$
coming from
	the reflecting wall or molecule.
Equality of energy in
	the half-wavelength segments of a mode
is assured by
	wave propagation.
Assuming
	all frequency transitions
are governed by
	eq.~(\ref{e:lorentz}),
if the excitation energy $\epsilon$
	at frequency $\nu$
transits to
	a harmonically related mode of frequency $N \nu$,
by eq.~(\ref{e:lorentz}),
	the excitation at the harmonic would be
	$
	N \epsilon
	$,
	and the \emph{vice versa}\xspace.
If the transitions are due to
	classical interactions with molecules or the walls,
the harmonic excitation
	should occur with probability
	$
	e^{-N \epsilon  k_B T }
	$.
We should find
	the initial excitation
appears as
	energy $\epsilon$ at $\nu$
		with probability (or relative frequency) $e^{- \epsilon  k_B T}$,
	as $2 \epsilon$ at $2 \nu$
		with probability $e^{- 2 \epsilon  k_B T}$,
	and so on,
so the mean energy across
	harmonically related modes
becomes
\begin{equation} \label{e:swm}
	\Exp{\epsilon}
	=
		\frac{
			\epsilon e^{- \epsilon  k_B T}
		+
			2 \epsilon e^{- 2 \epsilon  k_B T}
		+
			\dots
		}{
			e^{- \epsilon  k_B T}
		+
			e^{- 2 \epsilon  k_B T}
		+
			\dots
		}
	=
		\frac{
			\epsilon
		}{
			e^{\epsilon  k_B T} - 1
		}
	,
\end{equation}
same as the expression for $U$ in
	Planck's result, eqs.~(\ref{e:planck}),
but with no reason to assume
	$\epsilon$ is quantized.
Eq.~(\ref{e:swm}) implies that
	harmonic families of standing wave modes
behave as
	Planck's harmonic oscillators
under equilibration by
	Doppler shifts.
The $-1$ in the denominator implies
	the same cutoff as Planck's law,
so Rayleigh's theory
	stands corrected.

Evaluation of the expectation
	over arbitrary sets of modes
would yield
	the same result,
since both
	molecular motions and wall vibrations
would equilibrate
	across all modes.
This too is easy to prove
	with the hindsight of past work.
The detailed balance between
	an arbitrary pair of modes
of frequencies
	$\nu$
and
	$\gamma \nu$
then requires
	$
	\epsilon e^{- \epsilon  k_B T}
	=
		\gamma \epsilon e^{- \gamma \epsilon  k_B T }
	$
for a non-zero real ratio $\gamma$
	due to eq.~(\ref{e:lorentz}),
whence
	$
	\gamma
	=
		e^{ ( \gamma - 1 ) \epsilon  k_B T }
	$,
or equivalently
	$
	\gamma + 1
	=
		e^{ \gamma \epsilon  k_B T }
	$,
so that
	$
	(\gamma + 1)  \gamma
	=
		e^{ \epsilon  k_B T }
	$,
whereby the energy expectation is again
	$
	\Exp{ \epsilon }
	=
		\epsilon  [ e^{ \epsilon / k_B T } - 1 ]
	$,
along the lines of
	the Bose-Einstein derivation of Planck's law
	(\cf \cite[III-4-5]{Feynman}),
without depending even on
	the discreteness of the modes.
The constancy of $h$ in Planck's result,
	eqs.~(\ref{e:planck}),
thus indeed came from
	the atomic interactions leading to Wien's law.

\Section{theory}{Equilibrium and spectra of wave trains}

Whereas Wien's law was
	a classical constraint
in obtaining
	the blackbody spectrum,
physicists have long followed the inverse position
	epitomized in the correspondence principle,
that classical physics is
	the long wavelength approximation of
		quantum mechanics.
The view reflects
	the traditional belief
that
	classical physics cannot possibly explain
		quantum behaviour,
whereas extrapolating
	the internal structure and properties of matter
		revealed by quantum mechanics
to explain
	macroscopic classical phenomena
look like
	a mere computational exercise.
While fundamental limits on such computations
	are also being discovered
	\cite{Cubitt2015},
our preceding result implies more than
	a mere equivalence of
		the power of classical physics,
since its reasoning involves
	inherently fewer assumptions.

The only new premise, that
	frequency transitions are governed by
		the Lorentz condition,
	eq.~(\ref{e:lorentz}),
had been already argued by Einstein in 1917
	as a condition for
		dynamical consistency
	with the equilibrium of matter.
Only the further notion of
	equilibrating Doppler shifts
provided by wall vibrations
	is new,
but is more an intuition than a requirement,
	because eq.~(\ref{e:lorentz}) also holds with
		molecular absorptions and emissions
	in Einstein's reasoning.
The idea instead allows us to correct
	the defect of
		in Boltzmann's and Planck's theories
	of neglecting wall vibrations,
which would be available for equilibrating radiation
	even in a cavity with a perfect vacuum.

Also by Einstein's argument,
both molecular motions and wall vibrations
	should retain their classical equipartitions
requiring
	a distribution of $k_B T  2$ energy
		per degree of freedom,
but the standing wave modes are
	spectral components of the total radiation,
as well as
	macroscopic in geometry,
and for that reason,
	cannot exhibit mean energies of $k_B T  2$.
As wave trains emitted or absorbed by
	matter transitions
were pointed out as
	the real microscopic entities of radiation
		in thermal equilibrium with matter,
it might be thought that
	the wave trains must then possess $k_B T  2$ energies,
which too is impossible
	since the wave train energies
		must correspond initially to atomic transitions
	and do not change
		other than via atomic transitions,
	in Einstein's treatment.
Radiation is merely
	a means of exchange of energy and momentum
between
	the material constituents of
		the classical equipartition.
Like the stiffness of massless springs
	in a mechanical lattice,
a constraint on wave train energies
would affect
	the equilibration rate
but not
	the final equilibrium distribution.
All initial quantized energies and frequency spreads
	of the wave trains
are lost in
	the overall equilibrium,
so even wave trains,
	though particle-like
		in dynamical interactions,
are thermodynamically not at all
	particulate.

The derivation of
	the equilibrium spectrum for wave trains
below
illustrates
	another property of the Doppler effect
rarely discussed
	because of the traditional focus on individual frequencies,
		which correspond to Fourier components,
	instead of
		the composite wave trains
			they represent.
As derived in
	\cite{Einstein1905c}
and also explained in
	\cite{Popescu2007},
the Lorentz transform implies
	\emph{quadratic} variation in
		electromagnetic field strengths
	with Doppler shifts,
but as the shifts themselves signify
	an inverse \emph{linear} variation in wavelengths
and thereby in the total \emph{duration} of
	any sequence of half-wavelength segments,
		meaning time dilations,
the energies delivered by the wave trains
	vary linearly with the shifts,
yielding
	eq.~(\ref{e:lorentz}).

The Doppler time dilations have been inconsequential
	for sinusoidal wave functions and Fourier components
because such functions are considered
	to extend to infinity.
They do affect
	timings in signal modulation,
as discovered recently the hard way
	\cite{Oberg2004,Oberg2005},
and admit propagating chirp modes
	that have been correspondingly overlooked
		in all of physics
	for three centuries
	\cite{Prasad2015b}.
The time dilations were not relevant
	in the reasoning of eq.~(\ref{e:swm})
as standing wave modes are Fourier components
	extending in time to $\pm \infty$.
The mode energies and probabilities
	were determined from
the varying number $N$ of half-wavelength segments
	under Doppler transitions
under
	a static cavity dimension $L$.
The lengths and
	amplitude distributions of wave trains
would be unchanged by reflections
	at strictly static walls
even as
	the wavefronts are spatially scattered,
but both would be affected by
	the Doppler shifts
		from vibrating walls.

Three further complications arise in considering
	wave trains.
Firstly,
only one standing wave mode is defined to exist
	at each location within a cavity
with given
	frequency,
	direction,
	polarization
	and angular momentum characteristics,
but any number of wave trains
	can share these properties,
analogous to
	photons in lasing.
As the spectral contributions of the wave trains
	merely superpose on one another
and wave trains
	do not exchange energy or momentum,
the spectral contributions of each wave train
	in equilibrium
must bear the same shape,
	and therefore follow eq.~(\ref{e:swm}).

Secondly,
eq.~(\ref{e:swm}) was derived for
	the thermalization of modes
describing
	the total radiation,
and a similar treatment seems needed for
	wave train spectra,
but eq.~(\ref{e:lorentz}) is only applicable to
	finite sequences of half-wavelength segments,
whereas
	a Fourier component of a wave train
		would have infinite segments.
A solution exists in
	the Dirichlet treatment for
		Fourier representations
	over a finite interval,
according to which
	the behaviour of components outside the interval
		should be immaterial.
The component energy
	beyond the wave train
		must be irrelevant because
the components must cancel out in phase
	beyond the wave train.
This notion is not diminished by
	the spatial dispersion of the wave fronts by
		the wall reflections,
since the energy delivered by a component
	at any given location
		is an integral over time.
With wall vibrations,
continuity of the wave trains
	is also not assured
because
the velocity of a reflecting wall will fluctuate
	over the duration and expanse of a wave train.
The \emph{temporal} volume of
	the original wave train
is unaffected except as
	the overall Doppler time dilation,
however,
so both
	time dilations
and
	the Lorentz property
are meaningful.

The third complication is that
	the probability factors of the ``oscillator expansion''
		represented in eq.~(\ref{e:swm}),
as well as
	in the corresponding detailed balance
		of frequencies $\nu$ and $\gamma \nu$,
	concern different standing wave modes,
as in
	Boltzmann's original reasoning for molecular energies
		in the kinetic theory,
but must now relate
	spectral components of the same wave train.
If a wave train occurred with probability $p$
	at overall energy $\epsilon$,
which got boosted to $\gamma \epsilon$
	by a Doppler shift of its spectrum,
the probability of observing it
	at the total energy $\gamma \epsilon$
		should be still $p$,
as Doppler shifts
	do not create or annihilate waves
		or wave spectral components.

However,
wave trains suffer fragmentation
	due to the wall vibrations,
and the fragments suffer
	differing, unrelated shifts at random,
so the multiplicative law
	$
	p(u)
	\equiv
		e^{- u  k_B T }
	=
		\exp(
			- \sum_i u_i  k_B T
		)
	\equiv
		\prod_i
			p(u_i)
	$,
holds, where $u_i$ denote
	fragment probabilities.
If a fragment bears
	energy $u$ at frequency $\nu$
		for a time interval $\tau$,
it can later appear
	with its original probability
	$
	e^{- u  k_B T }
	$
at frequency
	$\nu' = \gamma \nu$,
under
	a Doppler shift factor
		$\gamma \ne 1$
only with energy
	$
	u'
	=
		u \omega'  \omega
	\equiv
		\gamma u
	$
	due to the Lorentz increase
and only for
	the shorter period
	$
	\tau'
	=
		\tau
		\;
		\omega  \omega'
	\equiv
		\tau  \gamma
	$.
To be observed at $\nu'$ for
	the full original interval $\tau$,
the fragment must
	\emph{repeatedly appear} at $\nu'$
		$\gamma$ times in succession,
which has
	the product probability
	$
	e^{- \gamma u  k_B T }
	$.
This is indeed how standing wave modes at
	frequencies $\nu$ and $\gamma \nu$
		are related,
as the $\gamma \nu$ mode corresponds to
	$\gamma$ repetitions of
		the $\nu$ mode \emph{in phase}
	over their common length $L$
		given by the cavity geometry.
Setting
	$\gamma = 2, 3 \dots$
reproduces
	the terms of the ``oscillator expansion''
		in eq.~(\ref{e:swm}),
	and hence the same result.

\section{Conclusion

Despite reproducing
	Planck's result
and
reinforcing
	his own heuristic of radiation quanta
		in photoelectricity theory
	with momentum arguments,
Einstein's 1917 derivation was
	rigorous reasoning of classical dynamics,
and its prediction of
	stimulated emission,
for instance,
	would have been unconvincing otherwise.
It traced quantization to
	the discreteness of atomic states
and
	constancy of
		their transition energies,
which means conversely that
the equilibrium should exhibit
	the Planck form without quantization
if matter state transitions
	were excluded.
This converse implication has been proved above for
	the equilibration
both of
	standing wave modes
and of
	arbitrary sets of wave trains.

That
Einstein did not emphasize
	this fundamental implication of
		matter interactions
	in his derivation
		of Planck's law,
and
	of the Lorentz property
		that he himself had discovered,
and instead endorsed
	Bose's derivation
and formulated
	Bose-Einstein statistics,
is consistent wtih
	his focus on
		the internal structure of matter.
It is at most
	a error of omission
in not examining
	the converse implication,
and an informal concern
	against the present result.

More particularly,
the physicists' ignorance of
	the classical Lorentz property,
and not an inability of
	classical physics,
has been shown the real reason for
	Rayleigh's failure in obtaining
		the correct law.
Likewise,
the inattention to matter interactions,
	which enter only via Wien's law
		and were addressed only later by Einstein,
has been shown to have left
	Planck unable to distinguish
the origin of quantization from
	a computational artefact in estimating entropy
		also used by Boltzmann.
An even older defect,
neglect of
	thermal vibrations of the bounding walls
in direct contact
	with a gas or radiation
		stipulated to be in equilibrium,
has been also identified
	and corrected with the converse insight.

\begin{comment}


\section{Introduction}
Crowdsourcing is widely used in procuring labels and services for traditional AI applications. Often many of the tasks crowdsourced are more readily accomplished by humans than computers. An additional advantage is the scalable and cost-effective nature of crowdsourcing.
However, typical crowdsourcing platforms may not consider several important aspects of traditional planning such as ensuring work completion within a strict deadline and with assured guarantees on the quality.

As a motivating example for this paper, consider a sequence of jobs arriving online where each job corresponds to translating  a large document which has to be completed within a deadline and with an assured level of accuracy. It may not be possible for a single individual worker to accomplish this job, so the requester could split such a job into tasks (either at chapter or section or any other level) and allocate each task to a crowd worker. Due to the very nature of the task, a worker, if employed for a long duration, might start committing errors. We refer to the duration until which an agent works without committing any error as the time to failure (TTF). Also, each worker differs in the time taken to complete the entire job (if the entire job is executed by the worker). The time taken by a worker to complete the job all by himself is called the job completion time (JCT) of that worker. Each worker incurs a certain cost to complete the entire job. Note that the workers are heterogeneous in terms of their costs, JCT, and TTF. Moreover, JCT and TTF of the workers are stochastic. An additional non-trivial challenge occurs when crowd workers are strategic and may misrepresent their costs in the hope of gaining higher utility.  This setting occurs in other problems such as tagging of a large repository of images, audio transcriptions, etc.

In this work, we consider jobs which (a) arrive online, (b) are divisible (into tasks),  (c) have strict completion deadlines, and (d) are to be completed with an assured accuracy.  We propose a multi-armed bandit (MAB) mechanism which learns the two parameters (mean job completion time (MJCT) and mean time to failure (MTTF)) of the workers while eliciting their privately held costs truthfully. We show that the proposed MAB mechanism minimizes the regret while meeting the deadline and accuracy requirements on every job. The following are the specific contributions of this work.

\begin{enumerate}[leftmargin=*]
\item \emph{\textbf{Non-strategic, with learning:}}
We look at the problem of allocating divisible online jobs to crowd workers so as to meet the constraints on deadline and accuracy (\Cref{sec:non-strategic}). The underlying optimization problem turns out to be non-trivial since the parameters MJCT and MTTF of the workers are unknown. We overcome this challenge by devising a biparameter learning scheme based on the Robust UCB~ algorithm \cite{DBLP:BUBECK12HEAVYTAIL}. Further, we embed this learning scheme into our social welfare maximizing algorithm, which we refer to as SW-GREEDY.

\item \emph{\textbf{Strategic, with learning:}} We next non-trivially extend the results above to the setting where worker costs are privately held (\Cref{sec:strategic}) by designing a mechanism (TD-UCB). This mechanism is is dominant strategy incentive compatible  and ex-post individually rational (\Cref{thm:ic-ir}).
\item \emph{\textbf{Regret Analysis:}} In \Cref{sec:regret-analysis}, we show, for non-strategic as well as strategic settings, that the number of jobs for which a non-optimal worker set is chosen, is upper bounded by $O(\log T)$ (\Cref{thm:optpull}), where $T$ is the total number of jobs to be completed.  Moreover, once an optimal worker set is selected, the allocation algorithm converges asymptotically to an efficient allocation, ensuring that the average regret goes to zero in the limit (\Cref{thm:asym}).
\item \emph{\textbf{Simulations:}} Finally, we show the practical efficacy of our learning mechanism via simulations in \Cref{sec:simulations}.
\end{enumerate}

\section{Previous Work}
We now look at previous work related to our setting. We group the relevant literature based on whether or not crowd workers are strategic.

In the non-strategic case, most of the work in crowdsourcing has focused on  models for aggregating labels and building classifiers \cite{RAYKAR10,KARGER11}. Many efforts also address problems similar to the one considered in our paper. \citet{FARADANIHI11} look at the design of pricing schemes dependent on the completion times of the workers.
The strategic nature of the workers is not considered here. The problem of completing tasks within a deadline is also investigated by \citet{YU15}. The authors consider the setting where the workers delegate tasks to other workers when they are unable to complete the work within a deadline.
Here the costs to workers are assumed to be known and workers are non-strategic.
Under a different setup, \citet{ding2013multi} look at the budgeted multi-armed bandit problem where the two parameters stochastic costs and stochastic rewards are learnt. However, they do not consider strategic workers.

In the strategic case, \citet{PRAPHUL15} look at allocating indivisible tasks to strategic crowd workers under deadline constraints with the assumption that the reliability (in terms of completion of the task) of the agents is common knowledge and not estimated. \citet{SINGER13} and \citet{Biswas2015} look at pricing mechanisms in the presence of budget constraints and task completion deadlines. However, the heterogeneity with respect to time to failure is not modelled.  \citet{Tran-Thanh2013} look at crowdsourcing classification tasks with the goal of trading off cost and accuracy of the estimation. However the TTF and JCT of the workers is not modeled here. Choosing an optimal worker set in order to obtain an assured accuracy level has been studied in \citet{JainGBZN14}. The allocation algorithm makes use of the multi-armed bandits abstraction \citet{AUER02}. A version of their allocation algorithm was designed for the case where workers are strategic with respect to bidding their costs. However, their setting does not look at the completion of tasks within a deadline.
The problem of allocating tasks concurrently to several workers in order to meet deadlines is looked at by  \citet{GERDING2010}. The work uses a variant of VCG mechanism  to elicit the costs truthfully from the workers. They consider stochastic completion times of tasks but do not consider the time to failure during the allocation.

Our work differs from all the work listed above in that, we design an allocation scheme to complete jobs within a deadline while simultaneously learning the mean completion time as well as the mean time to failure of the  workers. We also design a mechanism to elicit the costs of the workers truthfully.

\section{The Model}
Let $N=\{1,\ldots,n\}$ denote the set of crowd workers (also referred to as agents) available to the requester. A sequence of $T$ homogeneous jobs arrives at the platform, one at a time. Following are some of the design issues pertaining to the requester.
\begin{enumerate}[leftmargin=3mm]
\item \textbf{Job Parameters}
\begin{enumerate}[leftmargin=1mm]
\item \emph{Deadline:} The clock starts ticking for a job as soon as it arrives. We use $D$ to denote the deadline. The deadline $D$ on each job is an upper bound on the duration, starting from the arrival of that job,  before which the job is required to be completed in expectation.
\item \emph{Task creation:} The requester can divide a current job $t$ $(t=1, \ldots, T)$ into a certain number of tasks so as to facilitate completion of the job by the deadline $D$. We use $x_i^{(t)}$ to denote the fraction of the job $t$ assigned as a task to the worker $i$. Therefore,  $0 \leq x_i^{(t)} \leq 1$ and $\sum_{i=1}^n x_i^{(t)} = 1$. We assume arbitrary division of a given job into tasks for ease of exposition. However, this assumption can be relaxed to capture meaningful constraints such as the size of the task.
\item \emph{Threshold on probability of failure for tasks:} A worker is more likely to commit an error if he works for a longer duration on a task. We say a worker has failed when he commits an error. We use $\varepsilon$ to denote (the common) threshold on probability of failure for any task. This threshold allows the requester to control the overall ``quality" of the job.
\end{enumerate}
\item \textbf{Worker Parameters}
\begin{enumerate}[leftmargin=1mm]
\item \emph{Job Completion Time (JCT):}  A worker has a stochastic job completion time, which is the time he requires to complete the entire job by himself. JCT for a worker is random variable with a fixed but unknown mean. We refer to the mean job completion time as MJCT. The requester wishes to learn the MJCT for each worker. If $\rho_i$ is the MJCT of worker $i$, then the task allocation $x_i^{(t)}$ will meet the deadline constraint in expectation if $x_i^{(t)} \times \rho_i \leq D$.
\item \emph{Time to Failure (TTF):} A worker is also characterized by a stochastic time to failure, which denotes the duration for which a worker would work without a failure.  Like JCT, TTF also has a fixed yet unknown mean, which the requester wishes to learn.  If $F_i$ is the CDF of TTF for agent $i$, who workers for a expected duration $x_i^{(t)} \times \rho_i$ on the task allocation given by the fraction $x_i^{(t)}$ of job $t$, the requirement on threshold probability error dictates $F_i(x_i^{(t)} \times \rho_i) \leq \varepsilon$.
\item \emph{Cost Incurred:} Worker $i$ has a privately held cost $c_i \in [\barbelow{c},\bar{c}]$ which represents the cost incurred by worker $i$  to complete the job entirely on his own. Therefore, the cost involved to complete $x_i^{(t)}$ fraction of the job by the worker $i$ is $c_i x_i^{(t)}$.
\end{enumerate}
\item \textbf{Goal of Optimization Problem:} The constraints on deadline and threshold on probability of failure for every task has to be met in a cost optimal way for every online job $t$. Thus, the underlying optimization problem for the entire collection of  jobs $\{1,2,\ldots, T\}$ is given by \cref{opt_problem}.
\end{enumerate}

\begin{equation}
\label{opt_problem}
\begin{array}{|c|}
\hline\\
\displaystyle \min_{x_i^{(t)} \in [0,1]} \quad \sum_{t=1}^T \displaystyle \sum_{i=1}^n c_ix_i^{(t)},\\
\text{subject to}, \\
\sum_{i=1}^n x_i^{(t)} = 1, \forall t\\
\text{Completion time}(x_i^{(t)}) \leq D \;\forall i \in N, \forall t,\\
\text{Probability of failure}(x_i^{(t)}) \leq \varepsilon \; \forall i \in N, \forall t.
\;\\
\hline
\end{array}
\end{equation}
As mentioned earlier, the JCT and the TTF of the workers are stochastic in nature. We assume the JCT of each worker follows a log-normal distribution with unknown yet fixed mean $\rho_i \in [\barbelow{\rho}, \bar{\rho}]$ while the TTF for each worker follows an exponential distribution with mean $\beta_i \in [\barbelow{\beta},\bar{\beta}]$.
\begin{remark}[Choice of Distributions]
The choice of log-normal distribution is due to its wide applicability in social sciences and economics to model similar quantities. However any suitable non-negative random variable whose distribution is sub-Gaussian (or sub-exponential) may be used.
As discussed, the errors in this setting are introduced due to higher working duration on the task. This is analogous to the modelling of failure as function of time, in biological or computer or reliability literature, as exponential distributions. Hence, we model the TTF of the workers as exponential.
\end{remark}
The optimization problem stated in \cref{opt_problem} involves a learning scheme along with cost minimization across all the $T$ online jobs. However, due to independence across the jobs, the problem can be decomposed into a sequential cost minimization problem corresponding to each job ($t$). Therefore, in \cref{opt_problem} the summation over the jobs can be omitted. This enables us to use $x_i$ in place of $x_i^{(t)}$ for the sequential optimization problem for each job.

\section{The Case of Non-Strategic Workers}
\label{sec:non-strategic}
We first study the scenario where the costs $c_i$ incurred by the workers are common knowledge. If the means ($\rho_i$ and $\beta_i$) are known to the requester, no feasible allocation $x_i$ to the worker $i$ should exceed $D/\rho_i$. The additional requirement on accuracy requires that the probability of a worker failing in the duration $\rho_ix_i$ does not exceed $\varepsilon$. This is equivalent to the constraint $F_i(\rho_ix_i) \leq \varepsilon$ where $F_i$ is the CDF of the random variable TTF of worker $i$ which we model as the exponential distribution with mean $\beta_i$. On simplification, the requester's optimization problem reduces to \cref{opt_problem_known}.

\begin{equation}
\label{opt_problem_known}
\begin{array}{|c|}
\hline\\
\displaystyle \min_{x_i \in [0,1]}  \displaystyle \sum_{i=1}^n c_ix_i,\\
\text{subject to}, \\
\sum_{i=1}^n x_i = 1,\\
x_i \leq \frac{1}{\rho_i}\min\left(D,\beta_i \ln\left(\frac{1}{1-\varepsilon}\right)\right) \;\forall i \in N, \\
\;\\
\hline
\end{array}
\end{equation}
In practice, $\rho_i$ and $\beta_i$ are not known and need to be learnt.  We make use of the multi-armed bandit (MAB) abstraction for learning these parameters. More specifically, since $\rho_i$ and $\beta_i$ are sub-exponential distributions, we appeal to the Robust UCB technique~\cite{DBLP:BUBECK12HEAVYTAIL}. While $\psi$-UCB algorithm~\cite{DBLP:BUBECK2012REGRET} is a regret minimizing scheme for  learning the mean of sub-Gaussian distributions, for heavy tailed distributions (e.g. log normal and exponential), Robust UCB has been shown to be regret minimizing~\cite{DBLP:BUBECK12HEAVYTAIL}. We adopt the Robust UCB scheme with truncated empirical mean as the estimator.

\subsection{Difficulty in Learning $\beta_i$}
If a worker $i$, allocated a fraction $x_i$ of the job, takes time $\tau$ for completion, then $\tau/x_i$ is a sample from the distribution log-normal($\rho_i$). Therefore, every allocation contributes one such sample for the Robust UCB algorithm estimating $\rho_i$.  However, for estimating $\beta_i$, each sample allocation fed to the Robust UCB algorithm must correspond to a failure, but this is not practical as we do not observe failure at every instance of allocation. To handle this difficulty, we propose to use a surrogate random variable. Consider the experiment where a worker $i$ is allocated a task (fraction of a job) on which the worker spends a duration of at least $\delta$. The experiment is deemed to have failed if the worker $i$ fails in the first $\delta$ duration of allocation, otherwise it is deemed a success. Let $N_\delta^{(i)}$ be the number of such independent experiments till a failure is encountered. We propose to use the random variable  $\beta_{\delta,i}^{'} = \delta \times N_\delta^{(i)}$ to construct a sample from exponential($\beta_i$). To obtain such a sample, for every job $t$, we observe for a duration $\delta$ to see if any of the allocated workers have failed. Let $\eta_\delta^{(i)}$ be the number of contiguous instances (of jobs) of allocation during which a worker $i$ does not fail in the interval $\delta$. Note that $\eta_\delta^{(i)}$ is a sample from $N_{\delta}^{(i)}$. Therefore, the value $\delta \times \eta_{\delta}^{(i)}$ forms a sample of interest. Once a sample is obtained, $\eta_{\delta}^{(i)}$ is reset and the  process is again repeated to collect more samples. The expectation of the surrogate random variable in the limit coincides with $\beta_i$ due to \Cref{lemma_main}.
\begin{lemma}
\label{lemma_main}
$\lim_{\delta \rightarrow 0 }\mathbb{E}[\beta_{\delta,i}^{'}] = \beta_i$
\end{lemma}
\begin{proof}
By definition, $
\beta_{\delta,i}^{'} = N^{(i)}_\delta \times  \delta $.
Note, $N_{\delta} \sim \text{Geometric}(1- \exp(-\delta/\beta_i))$ and therefore, $\mathbb{E}[N_\delta] = \frac{1}{1- \exp(-\delta/\beta_i)}$.
\begin{align}
\label{L-hospital-simplify}
\lim_{\delta \rightarrow 0} \mathbb{E}[\beta_{\delta,i}^{'}] &= \lim_{\delta \rightarrow 0}\frac{ \delta}{
1- \exp(-\delta/\beta_i)} = \beta_i
\end{align}
where \cref{L-hospital-simplify} follows by applying the L'Hospital's rule.
\end{proof}

\subsection{SW-GREEDY: A Greedy Allocation}
The workers are indexed in an increasing order of their costs and each worker $i$ is allocated the largest possible fraction $x^{\textsc{\tiny PST}}_i$ which does not violate the constraints in \cref{opt_problem_known} till all tasks of the job are allocated.

The constraint $\frac{1}{\rho_i}\min\left(D,\beta_i \ln\left(\frac{1}{1-\varepsilon}\right)\right)$, involves means which are unknown. As mentioned earlier, we use Robust UCB to learn estimates for $\rho_i$ and $\beta_i$. $\hat{\rho}_i^+$ and $ \hat{\beta}_i^+$ are the upper confidence indices while $\hat{\rho}_i^-$ and $\hat{\beta}_i^- $ are the lower confidence indices of MJCT and MTTF respectively, obtained from Robust UCB. $\hat{\rho}_i$ and $\hat{\beta}_i$ are the empirical estimates of MJCT and MTTF respectively for worker $i$.  We could substitute $\hat{\rho}_i^{-}, \hat{\rho}_i $ or $ \hat{\rho}_i^{+}$ as the estimate for $\rho_i$ in our constraint. A higher value of $\rho_i$ enforces a lower allocation to worker $i$ compared to when a lower value of $\rho_i$ is used. Hence we refer to $\hat{\rho}_i^{+}$ as a pessimistic estimate for
$\rho_i$. By a similar reasoning, we refer to $\hat{\beta}_i^- $ as the pessimistic estimate for $\beta_i$. The use of the pessimistic estimates ensures that even with the true underlying means the constraint in \cref{opt_problem_known} is satisfied.

The allocation algorithm discussed above ensures that the social welfare regret of the learning scheme is optimized, hence we refer to the above allocation as SW-GREEDY\ (Algorithm~\ref{al:sw-greedy}). The social welfare is defined as follows.

\begin{definition}{Social Welfare:} Social welfare of a feasible (i.e. satisfying \cref{opt_problem_known}) allocation $x$ is the sum of valuations of the agents under that allocation. In this setting, the valuation of a crowd agent is $-c_ix_i$. Therefore, social welfare is given by $\sum_{i=1}^n -c_i x_i$.
\end{definition}

Every worker $i$ is paid an amount equal to the cost incurred, i.e. $ x_i^{\textsc{\tiny PST}}(t) \times c_i$, where $x_i^{\textsc{\tiny PST}}$ is the allocation to agent $i$ given by Algorithm \ref{al:sw-greedy}.

\begin{remark}[Pessimistic Selection] The fundamental underlying philosophy of the UCB family of algorithms is  ``optimism under uncertainty." Intuitively, this optimism helps in adequate exploration realtive to a naive scheme which just uses the empirical estimate. In our work, we do not use this philosophy implicitly, however, due to the greedy nature of the allocation scheme, the pessimistic allocation set is a superset of the optimistic allocation.
\end{remark}
\newpage
\MyBoxX{starta}{enda}{gray}
\MyBoxY{startb}{endb}{gray}
\MyBoxZ{startc}{endc}{gray}
\begin{algorithm}[h!]
\label{al:sw-greedy}
\DontPrintSemicolon
\caption{SW-GREEDY\ Allocation Algorithm}
\KwIn {Set of workers $N$, number of jobs $T$, deadline $D$, accuracy level $\varepsilon$, input cost vector: $c_1 \leq c_2 \leq \ldots \leq c_n$ (By re-indexing $N$)\vspace{0.04in}}
\tikzmark{starta} $\forall i \in N$, $\hat{\rho}_i = \bar{\rho}$, $\hat{\rho}_i^+ = \bar{\rho}$, $\hat{\rho}_i^- = \barbelow{\rho}$, $N_{i,t = 0}$ \;
\hspace{0.5in}$\hat{\beta}_i = \barbelow{\beta}$, $\hat{\beta}_i^+ = \bar{\beta}$, $\hat{\beta}_i^- = \barbelow{\beta}$, $N_{i,t}^\beta = 0$, \;
$\eta_\delta^{(i)}=0$ \hspace{2in} \label{initialize} \vspace{2ex} \tikzmark{enda}\;

\For{ Online job arrival $t=1,\ldots,T $}
{
\vspace{1ex}
\tikzmark{startb}$x^{\textsc{\tiny PST}}(t)=\{x_1^{\textsc{\tiny PST}}(t),\ldots, x_n^{\textsc{\tiny PST}}(t)\} = \{0,\ldots,0\}$\;
$i=1$\;
\While{$\sum_{j=1}^n x_j^{\textsc{\tiny PST}}(t) < 1$}
{
$x_i^{\textsc{\tiny PST}}(t)$ = $\frac{1}{\hat{\rho}_i^+} \min \left( D, \beta_i^- \ln \left[\frac{1}{1-\varepsilon} \right]\right)$\;

\If{$1-\sum_{j=1}^{i-1} x_j^{\textsc{\tiny PST}}(t)< x_i^{\textsc{\tiny PST}}(t)$}
{
$ x_i^{\textsc{\tiny PST}}(t) = 1-\sum_{j=1}^{i-1} x_j^{\textsc{\tiny PST}}(t)$ \;
}
$i=i+1$ \tikzmark{endb} \;
}
Define $\bar{k}_t = \max\{i:x_i^{\textsc{\tiny PST}} > 0\}$ \;
Allocate the job $t$ as per $x_i^{\textsc{\tiny PST}}$ \;
Observe $\tilde{\tau}_i$, the time of completion of $x_i^{\textsc{\tiny PST}}$ by $i$\;
$\forall i \in \{1,\ldots,\bar{k}_t \}, N_{i,t} = N_{i,t-1} +1 $\;
$\hat{\rho}_i = \left( N_{i,t-1} \times \hat{\rho}_i + \frac{\tilde{\tau}_i}{x_i^{\textsc{\tiny PST}}(t)} \right) \times \frac{1}{N_{i,t}} $\;
\tikzmark{startc}\For{$i \in \{1,\ldots,\bar{k}_t\}$}
{
\If{Worker $i$ made an error during $\delta$}
{
$\hat{\beta}_i = \frac{\hat{\beta}_i \times N_{i,t-1}^\beta +  (\delta \times \eta_\delta^{(i)})}{N_{i,t-1}^{\beta} + 1}$\;
$N_{i,t}^{\beta}= N_{i,t-1}^{\beta} + 1$\;
$\eta_\delta^{(i)} = 0$\;
}
\Else
{
$\eta_\delta^{(i)} = \eta_\delta^{(i)} + 1$\;
$N_{i,t}^{\beta} = N_{i,t-1}^{\beta} $\tikzmark{endc}\;
}
}
}
\end{algorithm}

\definecolor{ashgrey}{rgb}{0.7, 0.75, 0.71}
\begin{tikzpicture}[remember picture,overlay]
\coordinate (aa) at ($(pic cs:starta)+(5.7,-.8)$);
\node[rectangle,draw,white, fill=ashgrey, text width=1.5cm,align=left,right] at (aa) {Initialize};
\end{tikzpicture}

\begin{tikzpicture}[remember picture,overlay]
\coordinate (aa) at ($(pic cs:startb)+(5.7,-.55)$);
\node[rectangle,draw,white, fill=ashgrey, text width=1.5cm,align=left,right] at (aa) {Pessimistic \\ Selection};
\end{tikzpicture}

\begin{tikzpicture}[remember picture,overlay]
\coordinate (aa) at ($(pic cs:startc)+(5.1,-1.68)$);
\node[rectangle,draw,white, fill=ashgrey, text width=1.3cm,align=left,right] at (aa) {Updates for \\ Surrogate of $\beta_i$ };
\end{tikzpicture}

\section{The Case of Strategic Workers: TD-UCB}
\label{sec:strategic}
Here, before an allocation is performed, the agents announce their bids. These bids may or may not be equal to their true private costs. We denote the bid profile by $(b_i, b_{-i})$, where $b_i$ is the bid of agent $i$ and $b_{-i}$ denotes the collection of bids of all agents except agent $i$.
In order to ensure that the agents bid their costs truthfully, we introduce a mechanism TD-UCB.
The allocation rule remains the same as the one for the case where the workers are non-strategic. We use the allocation given in Algorithm~\ref{al:sw-greedy} replacing the input costs with the bids.

\subsection{Payment Scheme}
 Let $\xi_t$ denote a tuple of allocation and performance of the allocated workers for the job $t$. The learning until job $t$ is captured in the history $h_t = \{\xi_k\}_{k=0}^{t}$. In order to specify the payment scheme, we require the notion of `externality' imposed by an agent on another. We denote the externality imposed by agent $i$ on $j$ as $x_{i,j}^{\textsc{\tiny EXT}}(b_i,b_{-i};h_t,t)$, which signifies the additional fraction of the job allocated to the agent $j$ in the absence of agent $i$.  The externality for the job $t$ depends on the bid profile $(b_i, b_{-i})$ as well as the history of allocations till job $t$. Let $\overline{k_t}$ be the agent with the largest reported bid in the worker set chosen by the allocation scheme. \Cref{fig:schematic-pos} provides a schematic diagram indicating the position of the bids and the agents chosen by our algorithm.

\begin{figure}[h!]
\centering
\includegraphics[scale=0.64]{AAMAS_alloc-crop.pdf}
\caption{Schematic of the allocation}
\label{fig:schematic-pos}
\end{figure}
Formally, the externality is defined as \begin{align}
x_{i,j}^{\textsc{\tiny EXT}}(b_i, b_{-i};t) =
  \begin{cases}
   0     & \text{if } j< \overline{k_t} \text{ or } i> \overline{k_t},\\
    Z_1 &\text{if } j=\overline{k_t},\\
    Z_2 &\text{if } j>\overline{k_t}, \quad\text{where},\\
  \end{cases}
\label{eq:ext}
\end{align}
 \[  Z_1 = \min\left(\frac{1}{\hat{\rho}_j^+} \min\left(D, \hat{\beta}_j^{-}\log\left(\frac{1}{1-\epsilon}\right)\right)- x_j^{\textsc{\tiny PST}}(t), x_i^{\textsc{\tiny PST}}(t)\right) , \]
\[  Z_2 = \min\left(\frac{1}{\hat{\rho}_j^+} \min\left(D, \hat{\beta}_j^{-}\log\left(\frac{1}{1-\epsilon}\right)\right), x_i^{\textsc{\tiny PST}}(t) - \displaystyle\sum_{s =\overline{k}_t}^{j-1} x_{i,s}^{\textsc{\tiny EXT}}(t)\right) \]

We now propose a payment structure in \cref{eq:pymt} that ensures truthful bidding and positive utility to the participating agents (\Cref{thm:ic-ir}).

\begin{align}
p_i(b_i, b_{-i};t) =
  \begin{cases}
   0     & \text{if } i> \overline{k_t},\\
    Z_3 &\text{otherwise, \quad \text{where},}
  \end{cases}
\label{eq:pymt}
\end{align}
\[  Z_3 = \displaystyle\sum_{s=\overline{k}_t}^n
\left[x_{i,s}^{\textsc{\tiny EXT}}(t)\times b_s\right] +  \left(x_i^{\textsc{\tiny PST}}(t) - \displaystyle\sum_{s=\overline{k}_t}^n x_{i,s}^{\textsc{\tiny EXT}}(t) \right) \times \bar{c}   \]

\begin{remark}[Notation]
All the mechanism side parameters such as $x_i^{\textsc{\tiny PST}}$ or $p_i$ are a function of $(b_i,b_{-i};h_t,t)$. Similarly, the agent side parameters such as utility $u_i$ depend on the tuple $(b_i, b_{-i};c_i,h_t,t)$. Note that the agent side parameters have an additional dependency on the true cost $c_i$. Whenever clear from the context, we drop one or more of these dependencies for ease of  notation.
\end{remark}

\begin{remark}[Externality] Our mechanism is an externality based scheme like the VCG mechanism. We now set about the task of proving that the mechanism is truthul, regret minimizing, and individually rational,  while learning the associated stochastic parameters. Earlier works have shown the non-triviality involved in the design of such learning mechanisms~\cite{BABAIOFF09,DEVANUR09}.
\end{remark}

\subsection{Properties of TD-UCB\ Mechanism}
\begin{definition}{Utility of an Agent:} The utility of an agent in this setting is the difference between the valuation of an allocation and the payment made. The utility is given by the following.
\[ u_i(b_i,b_{-i};c_i,h_t,t) = -c_i \times x_i^{\textsc{\tiny PST}}(b_i,b_{-i};c_i,h_t,t) + p_i(b_i,b_{-i};c_i,h_t,t)\]
\end{definition}
\begin{definition}{Dominant Strategy Incentive Compatible (DSIC): }A mechanism is DSIC if the utility $u_i(c_i, b_{-i}; c_i) \geq u_i(b_i, b_{-i}; c_i)\; \forall b_i \in [\underline{c}, \overline{c}],
\; \forall b_{-i} \in [\underline{c}, \overline{c}]^{n-1}, \; \forall i \in N$, where $b_i$  and $c_i$ are the bid and true cost incurred by the worker $i$ respectively, $b_{-i}$ is the bid profile of all agents other than $i$.
\end{definition}
A DSIC mechanism ensures that an agent obtains the highest utility by bidding his true cost, irrespective of the bids of other agents.

\begin{definition}{Ex-post Individually Rational (IR): }
A mechanism is ex-post individually rational if $u_i(c_i, b_{-i}; c_i) \geq 0)$, $ \forall b_{-i} \in [\underline{c}, \overline{c}]^{n-1}\; \forall i \in N$.
\end{definition}
An IR mechanism ensures that for every agent, the utility obtained from truthful bidding of the costs is non-negative.

\begin{theorem}
The TD-UCB\ mechanism is DSIC and IR.
\label{thm:ic-ir}
\end{theorem}
\begin{proof}
IR is immediate and follows from the definition of the payment scheme of the mechanism ({\cref{eq:pymt}}). \\
We prove the DSIC property by examining different possible scenarios of allocation for an agent.  In each of these scenarios, we compute the utilities with truthful bids as against strategic misreports of bids.

For performing any job $t$, utility of a worker $i$ is defined as follows.
\begin{equation}
u_i(b_i, b_{-i}; c_i) = p_i(b_i, b_{-i}) - c_i \times x_i^{\textsc{\tiny PST}}(b_i, b_{-i})
\end{equation}
where $x^{\textsc{\tiny PST}}_i(b_i, b_{-i})$ and $p_i(b_i,b_{-i})$ are the allocation and the payment to the worker $i$ respectively.
We consider the following three possible scenarios for the positioning of each worker $i$ in the increasing order of ranking of the bids of the workers. We refer to the set of workers with non-zero task allocation as the active set in this proof.
Throughout the proof, we denote by $A$ the active set of allocated workers when agent $i$ bids his true cost $c_i$. We denote by $A'$ the active set when the agent bids untruthfully.
\begin{itemize}[leftmargin=0mm, labelwidth=-2mm]
\item Case 1: $i > \overline{k_t}$\\
In this scenario, when the agent bids truthfully,
\begin{align*}
\underbrace{b_1 <b_2 < \cdots <   b_{ \overline{k_t}}}_{\text{Bids from} A} < \cdots < b_{i-1} < c_i <b_{i+1} < \cdots < c_N
\end{align*}
When the worker reports his cost truthfully (i.e, $b_i = c_i $), he does not receive any allocation and therefore $u_i(c_i, b_{-i}; c_i) = 0$. Now we consider the following two cases when he misreports his cost.
\begin{enumerate}[leftmargin=1mm,label=\alph*),labelwidth=-3mm]
\item \label{overbid-main}
Overbid of cost ($b_i > c_i$) : \\
Since $x_i^{\textsc{\tiny PST}}( c_i, b_{-i}; c_i) = 0$, a higher bid $b_i$ would only place the agent at a position $o_i(b_i, b_{-i}) \geq o_i(c_i, b_{-i}) = i$ in the revised ranking order. At the position $o_i(b_i, b_{-i})$, again the allocation to him would be zero, that is,  $x_i^{\textsc{\tiny PST}}( b_i, b_{-i}; c_i) = 0$ and thereby the utility from overbidding would be same as the utility from truthful bidding. Hence, he does not benefit from overbidding his cost.
\item Underbid of cost ($b_i < c_i$):\\
Here there could be two possibilities:
\begin{enumerate}[label=(\roman*),leftmargin=2mm,  labelwidth=-3mm]
\item $b_i \geq b_{\overline{k_t}}$: This scenario is identical to case 1(a) shown above and hence there is no incentive for the agent to bid in this manner.
\item $b_i < b_{\overline{k_t}}$:
With such a bid, the agent $i$ is able to enter the active set of allocated workers. \\
Let the position of the agent $i$ in the new active set $A'$ be $j$, that is,
$o_i(b_i, b_{-i}) = j$,  and the agent with the highest bid in $A'$ is $\overline{k_t}' \leq \overline{k_t}$. Therefore, by underbidding his cost, agent $i$ is able to move the workers $p \in \{\overline{k_t}'+1, \cdots,  \overline{k_t}\}$ out of the active set. We now show that such a bid does not fetch agent $i$ an  increased utility.
As per the payment structure,
\begin{align}
\label{payment-outofA-overbid}
p_i&(b_i, b_{-i}) = \sum_{s=  \overline{k_t}'}^{\overline{k_t}} x_{i,s}^{\textsc{\tiny EXT}}(b_i, b_{-i}) b_s \nonumber\\
& +  \sum_{s = \overline{k_t}+1}^{N} x_{i,s}^{\textsc{\tiny EXT}}(b_i, b_{-i}) b_s \nonumber\\& + \left(x_i^{\textsc{\tiny PST}}(b_i, b_{-i})  - \sum_{s=\overline{k_t}' , s \neq i}^N x_{i,s}^{\textsc{\tiny EXT}}(b_i, b_{-i})\right) \overline{c}
\end{align}
The second term in \cref{payment-outofA-overbid} is zero, this is due to the fact that in absence of agent $i$ $\{1,2,\ldots, \overline{k_t}\}$ can complete the current job $t$. Therefore, with even an underbid $i$ has no externality on agents $\{\overline{k_t}+1,\ldots,n\}$.
The third term in \cref{payment-outofA-overbid} is also zero as the allocation with truthful bidding was enough to complete the job $t$ by agents $\{1,2,\ldots, \overline{k_t}\}$. Hence in absence of $i$ the allocation with underbid $x_i^{\textsc{\tiny PST}}(b_i,b_{-i})$ is met by the externality sum. By underbidding, the agent $i$ is therefore able to obtain the portions of the job which would have been allocated to $s \in \{\overline{k_t}'+1 ,\cdots, \overline{k_t}\}$. For all such agents $s$, $x_{i,s}^{\textsc{\tiny EXT}}(b_i, b_{-i}) >0$, since in the absence of $i$, these agents would have received an allocation. But note that  $b_s < c_i$ and so these agents contribute towards a negative utility.
Therefore the net utility $u_i(b_i, b_{-i}; c_i) < u_i(c_i, b_{-i}; c_i)$.

\end{enumerate}
\end{enumerate}
\item Case 2: $i = \overline{k_t}$.\\
When agent $i$ bids truthfully, the active set is as follows:
\begin{align*}
\underbrace{b_1 \leq \cdots \leq b_{j} \leq \cdots \leq c_i }_{\text{Bids from} A} \leq b_{i+1} \cdots
\end{align*}
and the payment to agent $i$
\begin{align}
\label{payment-last-agent-truthful}
p_i(c_i,&b_{-i}) = \sum_{s= i+1}^N x_{i,s}^{\textsc{\tiny EXT}} (c_i, b_{-i}) b_s\nonumber\\ &+ \left( x_i^{\textsc{\tiny PST}}(c_i, b_{-i}) - \sum_{s=i+1}^n x_{i,s}^{\textsc{\tiny EXT}}(c_i, b_{-i})\right)\overline{c}
\end{align}
\begin{enumerate}[leftmargin=1mm, label=\alph*), labelwidth=-2mm]
\item Overbid of cost ($b_i > c_i$): \\
Here we look at two possible values of the range of the bids.
\begin{enumerate}[label=(\roman*), leftmargin=3mm, labelwidth=-4mm]
\item \textit{An overbid such that agent $i$ no longer belongs to the active set $A'$}:  At the position $o_i(b_i, b_{-i})$, the allocation to him is zero, that is,  $x_i^{\textsc{\tiny PST}}( b_i, b_{-i}; c_i) = 0$ and thereby the utility from overbidding would be less than the utility from truthful bidding. Hence, he does not benefit from overbidding his cost in this manner.
\item \textit{An overbid such that agent $i$ remains in the active set but brings in other higher cost agents into the active set}:
Suppose the active set $A'$ contains the agents $\{i+1, \cdots, p \}$ in addition to the set $A$, such that, without loss of generality,
\begin{align*}
\underbrace{b_1 < \cdots < b_{i-1} < b_{i+1} < \cdots < b_p < b_i}_{\text{Bids from} A'} < b_{p+1} < \cdots
\end{align*}
The payment to agent $i$ with overbid is,
\begin{align}
\label{payment-overbid-newagents-lastagent}
p_i(b_i,&b_{-i}) = \sum_{s= p+1}^N x_{i,s}^{\textsc{\tiny EXT}} (b_i, b_{-i}) b_s\nonumber\\ &+ ( x_i^{\textsc{\tiny PST}}(b_i, b_{-i}) - \sum_{s=p+1}^n x_{i,s}^{\textsc{\tiny EXT}}(b_i, b_{-i}))\overline{c}
\end{align}
Since the agents $\{i+1, \cdots, p \}$ have moved before $i$ in the ordering of the bids, those agents do not contribute to $p_i(b_i,b_{-i})$ further. However, for the agents $s \in \{p+1, \cdots, N\}$, $x_{i,s}^{\textsc{\tiny EXT}} (b_i, b_{-i}) =x_{i,s}^{\textsc{\tiny EXT}} (c_i, b_{-i})$ because the same proportion of job must be reassigned to the agent $s$ when $i$ bids $b_i$ as well as when $i$ is truthful. The first term in \cref{payment-last-agent-truthful} therefore strictly exceeds first term in \cref{payment-overbid-newagents-lastagent}.
We now show that the second terms in \cref{payment-last-agent-truthful} and \cref{payment-overbid-newagents-lastagent} are equal.
Observe that,
\begin{align*}
x_i^{\textsc{\tiny PST}}(c_i, b_{-i}) &= x_i^{\textsc{\tiny PST}}(b_i, b_{-i}) + \sum_{s=i+1}^p x_{j}^{\textsc{\tiny PST}}(b_i, b_{-i})\nonumber \\
 &= x_i^{\textsc{\tiny PST}}(b_i, b_{-i}) + \sum_{s=i+1}^p x_{i,s}^{\textsc{\tiny EXT}}(b_i, b_{-i})
\end{align*}
A simple substitution for $x_i^{\textsc{\tiny PST}}(b_i, b_{-i})$ in \cref{payment-overbid-newagents-lastagent} shows that the second terms in
\cref{payment-last-agent-truthful} and \cref{payment-overbid-newagents-lastagent} are equal.
Therefore the overall payment $p_i(b_i, b_{-i}) < p_i(c_i, b_{-i})$ and further $u_i(b_i,b_{-i}; c_i) < u_i(c_i, b_{-i}; c_i)$.
\end{enumerate}
\item Underbid of cost ( $b_i < c_i$):
Note that in this scenario, there are the following two possibilities.
\begin{enumerate}[label=(\roman*),leftmargin=1mm, labelwidth=-3mm]
\item The active set $A'$ = $A$. The agent $i$ moves to a new position $j$, that is, $o_i(b_i, b_{-i}) = j$. Without loss of generality, we can consider that the agent with the highest bid in $A'$ is now agent $i - 1$.
The ordering of the agents is now,
\begin{align*}
\underbrace{b_1 \leq \cdots \leq b_{j-1} \leq \bold{b_i} \leq b_j \leq b_{i-1}}_{\text{Bids from} A'} \leq b_{i+1} \cdots .
\end{align*}

 By our payment structure,
\begin{align}
\label{payment-underbid-last-item}
p_i(b_i,&b_{-i}) = \sum_{\substack{ s= i-1 \\ s \neq i}}^N x_{i,s}^{\textsc{\tiny EXT}} (b_i, b_{-i}) b_s\nonumber\\ &+ ( x_i^{\textsc{\tiny PST}}(b_i, b_{-i}) - \sum_{\substack{ s= i-1 \\ s \neq i}}^N x_{i,s}^{\textsc{\tiny EXT}}(b_i, b_{-i}))\overline{c}
\end{align}
Since the active set remains the same in spite of underbidding, $\forall s, \; i+1 \leq s \leq N$, $x_{i,s}^{\textsc{\tiny EXT}}(b_i, b_{-i}) = x_{i,s}^{\textsc{\tiny EXT}} (c_i, b_{-i})$ and in addition, $x_{i, i-1}^{\textsc{\tiny EXT}}(b_i, b_{-i}) > 0$, but, $b_{i-1} < c_i$.  Therefore, the first term in \cref{payment-last-agent-truthful} exceeds the first term in \cref{payment-underbid-last-item}.
We also know that,
\begin{equation}
x_i^{\textsc{\tiny PST}}(b_i, b_{-i}) = x_i^{\textsc{\tiny PST}}(c_i, b_{-i}) + x_{i, i-1}^{\textsc{\tiny EXT}}(b_i, b_{-i})
\end{equation}
 since the additional allocation that $i$ gets due to an overbid would be allocated to the last agent $i-1$ in $A'$, in the absence of $i$. A simple substitution in \cref{payment-underbid-last-item} shows that the second terms in \cref{payment-last-agent-truthful} and  \cref{payment-underbid-last-item} are equal. Therefore $u_i(b_i, b_{-i}; c_i) < u_i(c_i, c_{-i}; c_i)$.
\item The active set $A'$ due to underbidding by agent $i$ is smaller than the active set $A$ due to truthful bidding by agent $i$: This means that some agents get removed from $A$.
Suppose the agents  $ s \in \{j+1, \cdots, i-1\}$ get pushed out in the active set $A'$. Then by a similar argument as in the case 2 (b) (i) above, $x_{i,s}^ {\textsc{\tiny EXT}}(b_i, b_{-i}) > 0 $, but $b_s < c_i$. Therefore these agents contribute towards a negative utility and hence, $u_i(b_i, b_{-i}; c_i) < u_i(c_i, c_{-i}; c_i)$.
\end{enumerate}
\end{enumerate}
\item Case 3: $i < \overline{k_t}$
\begin{enumerate}[label=\alph*), leftmargin=1mm, labelwidth=-3mm]
\item Overbid of cost ($b_i > c_i$):\\
If the agent $i$ bids a higher cost, the position of $i$ in the ranking order changes to one of the following.
\begin{enumerate}[label=(\roman*), leftmargin=1mm, labelwidth=-3mm]
\item $i \leq o_i(b_i, b_{-i}) < \overline{k_t}$:
 The allocation to the worker remains the same as when he is truthful, that is, $x_i^{\textsc{\tiny PST}} (b_i, b_{-i}) $ $= x_i^{\textsc{\tiny PST}} (c_i, b_{-i})$. Our payment structure ensures that the payment $p_i(b_i, b_{-i
}) = p_i(c_i, b_{-i})$ and hence $u_i(b_i, b_{-i}; c_i) = u_i(c_i, b_{-i}; c_i)$.
\item $o_i(b_i, b_{-i}) = \overline{k_t}$:
In this case, agent $i$ ends up losing a part of $x_i^{\textsc{\tiny PST}}(c_i, b_{-i})$ to the worker $k_t$. This scenario is analogous to Case 2 (a) (ii) where a worker who bids truthfully would have been at the last position $k_t$, but by overbidding ends up sharing his allocation with other agents. Therefore $u_i(b_i, b_{-i}; c_i) < u_i(c_i, b_{-i}; c_i)$.

\item $ o_i(b_i, b_{-i}) > \overline{k_t}$: Here, agent $i$ does not receive any allocation and thereby his payment as well as utility are both zero.
\end{enumerate}
\item Underbid of cost ($b_i < c_i$):\\
 Upon bidding a lower cost, the agent moves further up in the ranking order, that is $o_i(b_i, b_{-i}) \leq i$. The allocation also does not change, that is, $x_i^{\textsc{\tiny PST}} (b_i, b_{-i}) = x_i^{\textsc{\tiny PST}} (c_i, b_{-i})$. Our payment structure ensures that the payment $p_i(b_i, b_{-i
}) = p_i(c_i, b_{-i})$ and hence $u_i(b_i, b_{-i}; c_i) = u_i(c_i, b_{-i}; c_i)$.
\end{enumerate}
\end{itemize}
\emph{Future rounds}: If the agent $i$ ignores the loss incurred in the current job $t$ and chooses to manipulate the current bid for future utility, the resulting argument rolls back to one the above three cases.\hfill \qed
\end{proof}

\section{Regret Analysis}
\label{sec:regret-analysis}
\noindent In the strategic as well as the non-strategic settings, the underlying optimization problem involves parameters that are learnt in tandem. Hence regret is an important notion which we analyse in this section. Following are some relevant definitions. A problem instance in this space is characterized by a set of crowd agents $N$, the vector $c$ of their costs, the mean vectors ($\rho, \beta$), and the design parameters -- Deadline($D$), accuracy ($\varepsilon$).

\begin{definition}{Optimal worker set:} For a problem instance with all the parameters known, in the solution to the optimization problem of \cref{opt_problem_known}, we refer to the set of agents allocated non-zero fraction of the job as the the optimal worker set.
\end{definition}

\begin{definition}{Optimal allocation:} We refer to the solution of \cref{opt_problem_known} as the optimal allocation.
\end{definition}

\begin{definition}{$\Delta$-Separation:} Let $k^*$ be the agent in the optimal worker set with the highest bid. In the optimal allocation (social welfare maximizing), all workers' allocation except $k^*$ would meet the constraints in \cref{opt_problem_known} with equality. We refer to the $\Delta$-separation as the additional fraction of the job which agent $k^*$ can take without violating any of the constraints. As all the stochastic parameters in this space are continuous, almost surely $\Delta >0$.
\end{definition}

\begin{definition}{Regret:} A learning mechanism in this space suffers a loss in social welfare due to either a) non-optimal set selection or b) due to suboptimal allocation within the optimal set. Formally, regret of a mechanism $\mathcal{A}$, is given by
\[R(\mathcal{A}) = T \sum_{i=1}^n c_ix_i^* - \sum_{t=1}^T \sum_{i=1}^n c_ix_i^{(\mathcal{A})}(t), \]
where $x_i^{(\mathcal{A})}(t)$ is the allocation to the agent $i$ for the job $t$ by the mechanism $\mathcal{A}$.
\end{definition}

\noindent We use the truncated empirical estimator within our Robust UCB scheme. Through an invocation of the Bernstein inequality, we have, with high confidence (probability $> 1-t^{-4}$ for the $t^{th}$ job), the true mean lies within the Robust UCB and LCB indices(see Lemma 1 in \cite{DBLP:BUBECK12HEAVYTAIL}). With enough samples, the symmetric indices of the Robust UCB scheme shrinks small enough so that no additional agents than the optimal set are required to meet the spill-over even due to the pessimistic strategy used.

\begin{theorem}
The TD-UCB\ mechanism selects an optimal set after the job $t' \in O(\log T)$.
\label{thm:optpull}
\end{theorem}

\begin{proof}
We denote $k^*$ as the costliest agent in the optimal set. Let $x^* = \{x_1^*,\ldots,x_{k^*}^*\}$ denote the allocations when the means are known.  Consider $\Delta$,
$$\Delta = \frac{\min(D,\beta_{k^*} \log(\frac{1}{1-\varepsilon}))}{\rho_{k^*}} - x_{k^*}(t,\beta)$$
$\Delta$ denotes the additional fraction of work the agent $k^*$ can take up without violating the constraints.  Following is a sufficient condition on $t$ when the set selected by the pessimistic estimate matches the optimal set.
\begin{equation}
\begin{array}{|c|}
\hline\vspace{-1ex}\\
\vspace{-2ex}
\text{Need to get :}x^*_i(\rho,\beta) - x_i^{\textsc{\tiny PST}}(t) \leq \frac{\Delta}{n},\; \forall i \leq k^*\\ \\
\hline
\end{array}
\label{eq:suffcond}
\end{equation}
We denote $\rho_{\textsc{\tiny RI}}(t)$ and $\beta_{\textsc{\tiny RI}}(t)$ as the Robust UCB indices of the JCT and the TTF of a worker in the active set. Recall, the active set for job $t$ denotes an agent allocated a non-zero fraction of the job. The expression for the pessimistic allocation $  \forall i \in \{1,\ldots,k^*\}$ at job $t$ is given by
\begin{align}
x_i^{\textsc{\tiny PST}}(t) \times (\hat{\rho}_i + \rho_{\textsc{\tiny RI}}) = \min\left(D , (\hat{\beta}_i- \beta_{\textsc{\tiny RI}}) \log\left(\frac{1}{1-\varepsilon}\right)\right)
\label{eq:pess}
\end{align}
The allocation $x_i^{\textsc{\tiny PST}}$ is determined by equality in \cref{eq:pess} whenever the set chosen is not optimal. We analyse this allocation via  two cases to determine the job $t$ when condition in \cref{eq:suffcond} is met.\\
\noindent Case (i): $x_i^{\textsc{\tiny PST}}(t)\times(\hat{\rho}_i + \rho_{\textsc{\tiny RI}}) = D$ or $ x_i^{\textsc{\tiny PST}}(t)  = \frac{D}{\hat{\rho}_i + \rho_{\textsc{\tiny RI}}} $ Consider,
\begin{align*}
&x^*_i(\rho,\beta) - x_i^{\textsc{\tiny PST}}(t) \\
 &= \frac{\min\left(D, \beta_i \log \left(\frac{1}{1-\varepsilon}\right) \right)}{\rho_i} - \frac{D}{\hat{\rho}_i + \rho_{\textsc{\tiny RI}}} \\
&\leq \frac{D}{\rho_i} - \frac{D}{\hat{\rho}_i + \rho_{\textsc{\tiny RI}}}\\
&\leq \frac{D}{\hat{\rho}_i - \rho_{\textsc{\tiny RI}}} - \frac{D}{\hat{\rho}_i + \rho_{\textsc{\tiny RI}}}  [\because  \text{w.h.p. $\rho_i \geq \hat{\rho}_i - \rho_{\textsc{\tiny RI}}$}] \\
& \leq \frac{2D \rho_{\textsc{\tiny RI}}}{\barbelow{\rho}^2}
\end{align*}
In the current case, we have that the sufficiency condition is met whenever $\rho_{\textsc{\tiny RI}} \leq \frac{\Delta \barbelow{\rho}^2}{2nD}$. In terms of the job $t$, through the expression of robust UCB index $\rho_{\textsc{\tiny RI}}$, the case is met whenever,
\begin{equation}
t \geq \frac{336 u_\rho n^2 D^2 \log(T)}{\Delta^2 \barbelow{\rho}^4}
\end{equation}
where $u_\rho$ is an upper bound on the second moment of completion time (can be shown via easy computation).\\
\noindent Case (ii): $x_i^{\textsc{\tiny PST}}(t)\times(\hat{\rho}_i + \rho_{\textsc{\tiny RI}}) = (\hat{\beta}_i - \beta_{\textsc{\tiny RI}}) \log \left(\frac{1}{1-\varepsilon}\right)$ or $ x_i^{\textsc{\tiny PST}}(t)  = \frac{\hat{\beta}_i - \beta_{\textsc{\tiny RI}}}{\hat{\rho}_i + \rho_{\textsc{\tiny RI}}}\log \left(\frac{1}{1-\varepsilon}\right) $. Unlike $\rho_{i}$ where samples are obtained for every $t$, the samples from surrogate are obtained after multiple (yet finite due to bounded $\beta$) jobs.  To simplify our analysis, we consider as if a sample of $\beta_i$ is obtained for every job, the difference due to this simplification is only within constant factors. Consider,
\allowdisplaybreaks
\begin{align*}
& x^*_i(\rho,\beta) - x_i^{\textsc{\tiny PST}}(t) \\
 &= \frac{\min\left(D, \beta_i \log \left(\frac{1}{1-\varepsilon}\right) \right)}{\rho_i}
- \frac{\hat{\beta}_i - \beta_{\textsc{\tiny RI}}}{\hat{\rho}_i + \rho_{\textsc{\tiny RI}}}\log \left(\frac{1}{1-\varepsilon}\right) \\
&\leq \left(\frac{\beta_i}{\rho_i} - \frac{\hat{\beta}_i - \beta_{\textsc{\tiny RI}}}{\hat{\rho}_i + \rho_{\textsc{\tiny RI}}}\right)\log \left(\frac{1}{1-\varepsilon}\right)\\
&\leq \left(\frac{\hat{\beta}_i + \beta_{\textsc{\tiny RI}}}{\hat{\rho}_i - \rho_{\textsc{\tiny RI}}} - \frac{\hat{\beta}_i - \beta_{\textsc{\tiny RI}}}{\hat{\rho}_i + \rho_{\textsc{\tiny RI}}}\right)\log \left(\frac{1}{1-\varepsilon}\right) \\
&\intertext{W.h.p $\rho_i \geq \hat{\rho}_i - \rho_{\textsc{\tiny RI}}$ and $\beta_i \leq \hat{\beta}_i + \beta_{\textsc{\tiny RI}} $. As the surrogate observes at most one sample for every sample of $\rho_i$, we have $\beta_{\textsc{\tiny RI}} \geq \rho_{\textsc{\tiny RI}}$}\\
&\leq \beta_{\textsc{\tiny RI}} \times \frac{2\bar{\rho}+2\bar{\beta}}{\barbelow{\rho}^2} \log \left( \frac{1}{1-\varepsilon} \right)
\end{align*}
This gives us that the sufficiency condition is met whenever $\beta_{\textsc{\tiny RI}} \leq \frac{\Delta \barbelow{\rho}^2}{n(2\bar{\rho}+2\bar{\beta}) \log \left( \frac{1}{1-\varepsilon} \right) }$. In terms of the round $t$,
the sufficiency condition is met whenever
\begin{equation}
t \geq \frac{64 n^2 u_\beta \log(T) (2\bar{\rho}+2\bar{\beta})^2 \log^2\left( \frac{1}{1-\varepsilon}\right)}{\Delta^2 \barbelow{\rho}^4}
\label{eq:beta}
\end{equation}
where $u_\beta $ is an upper bound on the second moment on the TTF. From \cref{eq:pess} and \cref{eq:beta}, the optimal set is chosen after $O(\log(T))$ online jobs.
\end{proof}

\noindent As mentioned earlier, the regret in this setting arises first out of sub-optimal set selection and thereon out of sub-optimal allocation. Through \cref{thm:optpull}, we bound the number of jobs where sub-optimal set is chosen. The following theorem establishes the asymptotic efficiency of our learning scheme.

\begin{theorem}
Average regret of TD-UCB\ mechanism approaches zero asymptotically.
\label{thm:asym}
\end{theorem}
\begin{prf}
WLOG due to \Cref{thm:optpull},  we will consider the case where the active set is the optimal set. Let $k^*$ be the last member in the active set. The average regret, for the job $t$, is then given by
\[ R_{avg,t} = \sum_{i=1}^n \frac{c^{k^*}\left(x^*_i - x^{\textsc{\tiny PST}}_i(t)\right)}{t}\]
Through steps similar to the proof of \cref{thm:optpull}, we have for a job $t$ for an agent $i$ either
\[ \frac{c^{k^*}\left(x^*_i - x^{\textsc{\tiny PST}}_i(t)\right)}{t} \leq \frac{2D \rho_{\textsc{\tiny RI}}}{t \times \barbelow{\rho}^2} \]
\[ \text{or } \frac{c^{k^*}\left(x^*_i - x^{\textsc{\tiny PST}}_i(t)\right)}{t} \leq \frac{\beta_{\textsc{\tiny RI}}}{t} \times \frac{2\bar{\rho}+2\bar{\beta}}{\barbelow{\rho}^2} \log \left( \frac{1}{1-\varepsilon} \right). \]
As both $\beta_{\textsc{\tiny RI}} /t$ and $\rho_{\textsc{\tiny RI}}/t$  approach zero, we have
\begin{align*}
\lim_{t\rightarrow \infty}R_{avg,t} = 0.  \qed
\end{align*}
\end{prf}

\section{Simulations}
\label{sec:simulations}
We have shown theoretical guarantees on the regret in the asymptotic sense. In practice, the constants pertaining to the same are unknown. Also, our algorithm focusses on the  optimization of social welfare. However, the payments to the workers involve externality to the workers which depend on the Robust UCB learning scheme. The learning scheme does not provide guarantees on the stochastic parameters for the sub-optimal workers. But the payments to the optimal worker set may also involve these parameters of the sub-optimal workers. Hence the simulations help us to form a fair idea about the same.
Therefore, in order to investigate the efficacy of our algorithm in practical terms, we tested our method on  synthetically generated datasets.

We simulated a set of 400 diverse workers with different costs, completion times and error rates.
We fixed the following values, $\underline{\rho} = 50$, $\overline{\rho} = 100$, $\underline{\beta} = 25$, $\overline{\beta} =  35$, $\underline{c} = 10$ and $\overline{c} = 100$. Out of the 400 workers, 250 high performing workers were simulated with $\rho$ values uniformly sampled from $[50, 75]$, $\beta$ values uniformly from $[30,35]$ and costs from $[10,50]$. A set of 150 mediocre workers were also simulated. These workers were simulated with $\rho$ values set to $100$, $\beta$ to  $25$, and costs to $100$. The deadline $D$ was fixed as $50$ and the error probability threshold ($\varepsilon$) for an agent allocated a task was set to $0.01$.

We checked the performance of our algorithm for a total of $10^6$ jobs. The baseline used for comparison is the omniscient greedy allocation scheme with the parameters $\beta$ and $\rho$ known. We refer to this baseline as `Optimal'. In the context of payments, the `Optimal' baseline refers to the minimum payment for inducing truthful reports for the greedy allocation aware of the means.

With increasing number of jobs, we observed that the total payment reduced and the negative social welfare decreased. The plots for the same are shown in \cref{fig1}(a) and \cref{fig1}(b).   The performance of TD-UCB\  improves towards `Optimal' when executed over more jobs. This shows that the learning improves over time and converges to the optimal set / optimal allocation.
\begin{figure}[!htb]
 \centering
    \begin{minipage}{.25\textwidth}
        \centering
       \includegraphics[scale=0.2]{figure_1-crop.pdf}\\(a)
    \end{minipage}%
    \begin{minipage}{0.25\textwidth}
        \centering
        \includegraphics[scale=0.2]{figure_2-crop.pdf}\\(b)
 \end{minipage}
     \caption{(a) Negative Social Welfare of the workers, (b) Total Payment to the workers. No. of workers = 400, $\varepsilon$ = 0.01}
     \label{fig1}
\end{figure}
\section{Future Work}
\noindent Following are some directions for future work.
\begin{enumerate}[label=\alph*),leftmargin=1mm]
\item The derivation of theoretical bounds on the payments to the workers is still an open question. It would be interesting to see how these learned values affect the payment.
\item Investigate the use of other models for the JCT and TTF. For instance, the error committed by a worker could be modelled as a Bernoulli random variable the bias of which could depend on the time to completion. Such models would pose more challenges for the learning due to the interdependency between the stochastic parameters.
\item In our formulation of the problem in \cref{opt_problem_known}, we have posed the constraint on meeting the deadline as a requirement to be met in expectation. We would also be interested in satisfying the constraints in a probabilistic sense.
\end{enumerate}
\newpage
\bibliographystyle{abbrvnat}