Game Theory Based RSU Scheduling for Vehicular Networks in a Dense Traffic Scenario
\IEEEauthorblockN{Jiajun Sun} %\IEEEauthorblockA{Beijing Key Lab of Intelligent Telecomm.Software and Multimedia
%Atlanta, Georgia 30332--0250
%Email: http://www.michaelshell.org/contact.html} %
%\IEEEauthorblockN{Huadong Ma} %\IEEEauthorblockA{Beijing Key Lab of Intelligent Telecomm.Software and Multimedia
\IEEEauthorblockN{James Kirk
%and Montgomery Scott} %\IEEEauthorblockA{Starfleet Academy
%San Francisco, California 96678-2391
%Telephone: (800) 555--1212
%Fax: (888) 555--1212} %
Crowd sensing is a new paradigm which leverages the ubiquity of sensor-equipped mobile devices to collect data. To achieve good quality for crowd sensing, incentive mechanisms are indispensable to attract more participants. Most of existing mechanisms focus on the expected utility prior to sensing, ignoring the risk of low quality solution and privacy leakage. Traditional incentive mechanisms such as the Vickrey-Clarke-Groves (VCG) mechanism and its variants are not applicable here. In this paper, to address these challenges, we propose a behavior based incentive mechanism for crowd sensing applications with budget constraints by applying sequential all-pay auctions in mobile social networks (MSNs), not only to consider the effects of extensive user participation, but also to maximize high quality of sensing data submission for the platform (crowd sensing organizer) under the budget constraints, where users arrive in a sequential order. Through an extensive simulation, results indicate that incentive mechanisms in our proposed framework outperform existing solutions. %Crowd sensing is a new paradigm which leverages the ubiquity of %sensor-equipped smartphones and other mobile devices inspires crowd %sensing applications in mobile social networks(MSNs), which utilizes %the power of crowd to collect sensing data from our dynamic physical %world. To achieve good sensing quality for crowd sensing %applications, incentive mechanisms are indispensable to attract more %participants. Most of existing mechanisms focus on the expected %utility under various designs, ignoring her risk of low quality %solution and privacy leakage. To address these challenges, in this %paper, we propose a reputation based privacy-aware incentive %strategy for crowd sensing in MSNs, not only to consider a more real %crowd sensing application scenario, where the participants exert the %most sensing effort to get the most reputation points from an %all-pay auction, but also to protect a participant privacy for %crowd sensing applications in MSNs. Through extensive analysis, we %show that our proposed mechanism satisfying the computational %efficiency, individual rationality, budget feasibility, %truthfulness, consumer sovereignty and constant competitiveness. %Simulation results indicate that we evaluate the performance and %validate the theoretical properties of our reputation based %mechanisms.
Budget-Constraints-PracticalCrowdSensing.tex

%% bare_conf.tex
%% V1.3
%% 2007/01/11
%% by Michael Shell
%% See:
%% http://www.michaelshell.org/
%% for current contact information.
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.7 or later) with an IEEE conference paper.
%%
%% Support sites:
%% http://www.michaelshell.org/tex/ieeetran/
%% http://www.ctan.org/tex-archive/macros/latex/contrib/IEEEtran/
%% and
%% http://www.ieee.org/

%%*************************************************************************
%% Legal Notice:
%% This code is offered as-is without any warranty either expressed or
%% implied; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE!
%% User assumes all risk.
%% In no event shall IEEE or any contributor to this code be liable for
%% any damages or losses, including, but not limited to, incidental,
%% consequential, or any other damages, resulting from the use or misuse
%% of any information contained here.
%%
%% All comments are the opinions of their respective authors and are not
%% necessarily endorsed by the IEEE.
%%
%% This work is distributed under the LaTeX Project Public License (LPPL)
%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
%% distributed and modified. A copy of the LPPL, version 1.3, is included
%% in the base LaTeX documentation of all distributions of LaTeX released
%% 2003/12/01 or later.
%% Retain all contribution notices and credits.
%% ** Modified files should be clearly indicated as such, including  **
%% ** renaming them and changing author support contact information. **
%%
%% File list of work: IEEEtran.cls, IEEEtran_HOWTO.pdf, bare_adv.tex,
%%                    bare_conf.tex, bare_jrnl.tex, bare_jrnl_compsoc.tex
%%*************************************************************************

%
% Also note that the "draftcls" or "draftclsnofoot", not "draft", option
% should be used if it is desired that the figures are to be displayed in
% draft mode.
%
\documentclass[conference,10pt]{IEEEtran}

%% INFOCOM 2013 addition:
%\makeatletter
%\def\ps@headings{%
%\def\@oddhead{\mbox{}\scriptsize\rightmark \hfil \thepage}%
%\def\@evenhead{\scriptsize\thepage \hfil \leftmark\mbox{}}%
%\def\@oddfoot{}%
%\def\@evenfoot{}}
%\makeatother \pagestyle{headings}


\usepackage{comment}
%\usepackage{ulem}
\usepackage{epsfig}
\usepackage{amssymb}
\usepackage{cite}
% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
  % \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi
\usepackage[cmex10]{amsmath}
\usepackage{amsfonts}

% *** SPECIALIZED LIST PACKAGES ***
%
\usepackage{algorithm}
\usepackage{algorithmic}
%\usepackage[ruled,linesnumbered]{algorithm2e}

\usepackage{mdwmath}
\usepackage{mdwtab}
% *** SUBFIGURE PACKAGES ***
\usepackage[tight,footnotesize]{subfigure}
% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}




% new environment lemma  sjj add
\usepackage{float}
\usepackage{subfigure}
\usepackage{booktabs}


\newtheorem{lemma0}{\bf Lemma}
\def\thelem{\arabic{lemma0}}
% end of new environment lemma

% new environment assumption
\newtheorem{assumption0}{\bf Assumption}
\def\theass{\arabic{assumption0}}
% end of new environment assumption

% new environment definition
\newtheorem{definition0}{\bf Definition}
\def\theass{\arabic{definition0}}
% end of new environment definition

% new environment theorem
\newtheorem{theorem0}{\bf Theorem}
\def\thetheo{\arabic{theorem0}}


% new environment theorem
%\theoremstyle{remark}
\newtheorem{rmk}{\bf Remark}
\def\thetheo{\arabic{rmk}}
% end of new environment theorem

\newtheorem{example}{Example}




%\usepackage{stfloats}
%\newcounter{TempEqCnt}
%\usepackage{mathrsfs}
% end of new environment theorem  sjj add

\begin{document}
%
% paper title
% can use linebreaks \\ within to get better formatting as desired
%\title{Game Theory Based RSU Scheduling for Vehicular Networks in a Dense Traffic Scenario }
\title{Behavior-Based Online Incentive Mechanism for Crowd Sensing with Budget Constraints}
%\title{Uplink scheduling Strategy Based on A Population Game in Multichannel Vehicular Networks}
%\title{Multihoming Data Access of Vehicles with Saturated and Unsaturated Traffic by A Population Game in Vehicular Networks}
%\title{Multihoming Data Access with A Population Game for Vehicular Networks}

% author names and affiliations
% use a multiple column layout for up to three different
% affiliations

%\author{\IEEEauthorblockN{Jiajun Sun}
%\IEEEauthorblockA{Beijing Key Lab of Intelligent Telecomm.Software and Multimedia\\Beijing University of Posts and Telecomm.\\
%Georgia Institute of Technology\\
%Atlanta, Georgia 30332--0250\\
%Email: http://www.michaelshell.org/contact.html}
%\and
%\IEEEauthorblockN{Huadong Ma}
%\IEEEauthorblockA{Beijing Key Lab of Intelligent Telecomm.Software and Multimedia\\
%Beijing University of Posts and Telecomm.\\
%Email: homer@thesimpsons.com} \and \IEEEauthorblockN{James Kirk\\
%and Montgomery Scott}
%\IEEEauthorblockA{Starfleet Academy\\
%San Francisco, California 96678-2391\\
%Telephone: (800) 555--1212\\
%Fax: (888) 555--1212}
%}

% conference papers do not typically use \thanks and this command
% is locked out in conference mode. If really needed, such as for
% the acknowledgment of grants, issue a \IEEEoverridecommandlockouts
% after \documentclass

% for over three affiliations, or if they all won't fit within the width
% of the page, use this alternative format:
%
%\author{\IEEEauthorblockN{Jiajun Sun\IEEEauthorrefmark{1},
%Huadong Ma\IEEEauthorrefmark{2}, James Kirk\IEEEauthorrefmark{3},
%Montgomery Scott\IEEEauthorrefmark{3} and Eldon
%Tyrell\IEEEauthorrefmark{4}}
%\IEEEauthorblockA{\IEEEauthorrefmark{1}Beijing Key Lab of Intelligent Telecomm. Software and Multimedia,\\
%Beijing University of Posts and Telecomm.,\\
%Beijing 100876, China}
%\IEEEauthorblockA{\IEEEauthorrefmark{2}Twentieth Century Fox, Springfield, USA\\
%Email: homer@thesimpsons.com}
%\IEEEauthorblockA{\IEEEauthorrefmark{3}Starfleet Academy, San Francisco, California 96678-2391\\
%Telephone: (800) 555--1212, Fax: (888) 555--1212}
%\IEEEauthorblockA{\IEEEauthorrefmark{4}Tyrell Inc., 123 Replicant
%Street, Los Angeles, California 90210--4321}}
%
\author{\IEEEauthorblockN{Jiajun Sun and
Huadong Ma%, James Kirk\IEEEauthorrefmark{3},
%Montgomery Scott\IEEEauthorrefmark{3} and Eldon
%Tyrell\IEEEauthorrefmark{4}
}
\IEEEauthorblockA{%Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia,\\
Beijing University of Posts and Telecommunications, %\\
Beijing 100876, China\\
Email: jiajunsun.bupt@gmail.com}
%\IEEEauthorblockA{\IEEEauthorrefmark{2}Twentieth Century Fox, Springfield, USA\\
%Email: homer@thesimpsons.com}
%\IEEEauthorblockA{\IEEEauthorrefmark{3}Starfleet Academy, San Francisco, California 96678-2391\\
%Telephone: (800) 555--1212, Fax: (888) 555--1212}
%\IEEEauthorblockA{\IEEEauthorrefmark{4}Tyrell Inc., 123 Replicant Street, Los Angeles, California 90210--4321}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%sjj add addition author%%%%%%%%%%%
%\author{\IEEEauthorblockN{Jiajun Sun\IEEEauthorrefmark{1} and
%Huadong Ma\IEEEauthorrefmark{1}%, James Kirk\IEEEauthorrefmark{3},
%%Montgomery Scott\IEEEauthorrefmark{3} and Eldon
%%Tyrell\IEEEauthorrefmark{4}
%}
%\IEEEauthorblockA{\IEEEauthorrefmark{1}Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia,\\
%Beijing University of Posts and Telecommunications,\\
%Beijing 100876, China\\
%Email: jiajunsun.bupt@gmail.com, mhd@bupt.edu.cn}
%%\IEEEauthorblockA{\IEEEauthorrefmark{2}Twentieth Century Fox, Springfield, USA\\
%%Email: homer@thesimpsons.com}
%%\IEEEauthorblockA{\IEEEauthorrefmark{3}Starfleet Academy, San Francisco, California 96678-2391\\
%%Telephone: (800) 555--1212, Fax: (888) 555--1212}
%%\IEEEauthorblockA{\IEEEauthorrefmark{4}Tyrell Inc., 123 Replicant Street, Los Angeles, California 90210--4321}
%}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% sjj add addition author%%%%%%%%%%%%555



% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}




% make the title area
\maketitle

\begin{abstract}
Crowd sensing is a new paradigm which leverages the ubiquity of
sensor-equipped mobile devices to collect data. To achieve good
quality for crowd sensing, incentive mechanisms are indispensable to
attract more participants. Most of existing mechanisms focus on the
expected utility prior to sensing, ignoring the risk of low quality
solution and privacy leakage. Traditional incentive mechanisms such
as the Vickrey-Clarke-Groves (VCG) mechanism and its variants are
not applicable here. In this paper, to address these challenges, we
propose a behavior based incentive mechanism for crowd sensing
applications with budget constraints by applying sequential all-pay
auctions in mobile social networks (MSNs), not only to consider the
effects of extensive user participation, but also to maximize high
quality of sensing data submission for the platform (crowd sensing
organizer) under the budget constraints, where users arrive in a
sequential order. Through an extensive simulation, results indicate
that incentive mechanisms in our proposed framework outperform
existing solutions.
%Crowd sensing is a new paradigm which leverages the ubiquity of
%sensor-equipped smartphones and other mobile devices inspires crowd
%sensing applications in mobile social networks(MSNs), which utilizes
%the power of crowd to collect sensing data from our dynamic physical
%world. To achieve good sensing quality for crowd sensing
%applications, incentive mechanisms are indispensable to attract more
%participants. Most of existing mechanisms focus on the expected
%utility under various designs, ignoring her risk of low quality
%solution and privacy leakage. To address these challenges, in this
%paper, we propose a reputation based privacy-aware incentive
%strategy for crowd sensing in MSNs, not only to consider a more real
%crowd sensing application scenario, where the participants exert the
%most sensing effort to get the most reputation points from an
%all-pay auction,  but also to protect a participant privacy for
%crowd sensing applications in MSNs. Through extensive analysis, we
%show that our proposed mechanism satisfying the computational
%efficiency, individual rationality, budget feasibility,
%truthfulness, consumer sovereignty and constant competitiveness.
%Simulation results indicate that we evaluate the performance and
%validate the theoretical properties of our reputation based
%mechanisms.
\end{abstract}

% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle

\section{Introduction}\label{sec:intro}
%\IEEEPARstart{W}{ith}
With the increasing ubiquity of
sensor-embedded
mobile devices (e.g., smartphones), % with sensing and processing
%capabilities,
mobile social networks (MSNs), which integrate data collection
techniques and services into many kinds of social networks
\cite{aggarwal2011integrating,fan2013geocommunity}, have received
considerable research efforts in recent years due to two changes as
follows. First, the terminal devices for social network applications
change from PCs to mobile phones. Second, the interactive mode
extends from the virtual space to the real physical world. MSNs
provide a new opportunity for crowd sensing, which takes advantage
of the pervasive mobile devices to solve complex sensing tasks. A
typical example of crowd sensing applications is to provide the
support for green traffic by sensing and reporting timely the
measurements about
traffic flows in some region. %Although many public services (e.g., Google Maps) offer
%useful information for requesters, these information is very limited
%and are typically not timely updated. On the other hand,
Different from existing crowdsourcing systems, crowd sensing
exploits sensing and processing abilities of mobile devices to
provide sensing data from the real physical world towards a specific
goal or as part of a social or technical experiment
\cite{ra2012medusa,zhou2013consub}.

%\begin{figure}
%\center
%\hspace{-0.13in} \subfigure[]{ \label{crowd-VCG}
%\includegraphics[width=1.5in]{crowd-VCG.eps}}
%\hspace{-0.13in} \subfigure[]{ \label{crowd-allpay}
%\includegraphics[width=1.5in]{crowd-allpay.eps}}
%\caption{Comparison among different crowd sensing paradigms.(a)The
%VCG based crowd sensing process; (b)The all-pay based crowd sensing
%process proposed in this paper.}
%\label{fig:random} %\vspace{10pt}
%\end{figure}

Extensive user participation and submission quality are two crucial
factors determining whether crowd sensing applications in MSNs can
achieve good service quality. Most of the current crowd sensing
applications are based on a common hypothesis that all users
voluntarily participate in submitting the sensing data. However,
mobile devices are controlled by rational users, in order to
conserve energy, storage and computing resources, so selfish users
could be reluctant to participate in sensing data for crowd sensing
applications. Thus, it is indispensable to provide some incentive
schemes to stimulate selfish participants to cooperate in MSNs. Only
a handful of works
\cite{yang2012crowdsourcing,lee2010sell,duan2012incentive,jaimes2012location}
focus on incentive mechanism for crowd sensing applications. All of
these works apply a regular auction (e.g., a reverse auction) only
for off-line crowd sensing applications with the ex-ante payment
commonly known as ``Free rider problem".

The data submission quality issue from participants is also
challenging in crowd sensing applications
\cite{liu2011crowdsourcing}. If the submission quality of
participants is not well guaranteed, although the extensive user
participation offers useful information, the service quality from
participants is far from satisfactory to the requesters of crowd
sensing applications. For example, on the one hand, the limit of the
coverage constraint may make the participants with high quality data
drop out of crowd sensing application \cite{jaimes2012location}; On
the other hand, traditional incentive mechanisms such as the
Vickrey-Clarke-Groves (VCG) mechanism \footnote{Vickrey auction is a
type of sealed-bid auction, where bidders submit written bids
without knowing the bid of the other people in the auction, and in
which the highest bidder wins, ``but the price paid is the
second-highest bid.''} and its variants also will make the
participants with higher true valuation become starved frequently to
win, thereby drop out of crowd sensing applications
\cite{lee2010dynamic}. Therefore, special mechanisms must be
included to handle these challenges.

Although both extensive user participation and submission quality
issues have been identified as two crucial human factors for crowd
sensing applications, many recent research works
\cite{yang2012crowdsourcing,lee2010sell,duan2012incentive,jaimes2012location,liu2011crowdsourcing,lee2010dynamic,ghosh2011incentivizing,ren2012maximizing}
tend to separately study them in crowd sensing applications. The
reason is that, if the extensive user participation and submission
quality problems are addressed at the same time for crowd sensing
applications, the issue would become more challenging. For example,
some submission quality enhanced techniques
\cite{ghosh2011incentivizing,ren2012maximizing} stimulate
participants to generate high quality sensing contents to achieve
good service quality, but they could make some incentive strategies,
especially the reputation-based incentive strategies under budget
constraints, hard to implement extensive user participation coverage
constraints for crowd sensing applications, since it is not
practical to assume that the requester will always provide an
unlimited budget to achieve good service quality. Therefore, how to
simultaneously address both extensive user participation and
submission quality issues becomes particularly challenging for crowd
sensing applications with budget constraints.

%In practice, however, since the above theoretical mechanisms (i.e.,
%reverse auction mechanisms) require signing a contract with the
%winning bidder and thus could not be viable for practical crowd
%sensing applications when outcomes are not verifiable and contracts
%are incomplete in the trusted sever. On the other hand, a service
%provider recurrently and continuously requires participants' sensing
%data. In these reverse auctions, the participant with higher true
%valuation become starved frequently to win. Accordingly, he lose his
%interest in continuous crowd sensing actions and drop out of the
%reverse auction. Therefore, a contest instead of a campaign may be a
%more feasible option for practical crowd sensing applications. The
%contest allows for the behavior pattern of the participants to avoid
%risk-aversion, where the participants generate higher effort to gain
%more reputation points. The major difference of the contest from a
%reverse auction is that sensing data or services are finished before
%the winners are announced. Therefore, a behavior based incentive
%mechanism is necessary to generate higher effort under
%risk-aversion.

In this paper, to address the fore-mentioned challenges, we propose
a behavior based incentive mechanism for practical crowd sensing
applications with budget constraints. Specifically speaking, our
main contributions are summarized as follows:
\begin{itemize}
\item We explore a
behavior based incentive mechanism for crowd sensing applications
with budget constraints in MSNs. In order to simultaneously satisfy
the requirements of both extensive user participation and high
quality sensing data submission, we combine the all-pay auction
theory and a proportional share allocation rule to stimulate the
participants to generate high efforts and adequate coverage
constraints to achieve the better service for the requester of crowd
sensing applications with
budget constraints. %by differentiating with moderate
%performances and low performances instead of punishing all of them
%between players. We finish the game between the participants and the
%platform by two stages. In the first stage, each participant
%determines whether to join the sensing contest. In the second stage,
%each participant who exerted the most effort for sensing data
%service quality to win the more reputation points. Further, we apply
%the context based situation to assess these data quality from the
%participants.
\item We focus on a more real crowd sensing scenario where users arrive one by one online in a random order.
We model the issue as a sequential all-pay auction \footnote{All-pay
auction, is an auction in which every bidder must pay regardless of
whether he wins the prize, which is awarded to the highest bidder as
in a conventional auction.}, in which sensing data are submitted
sequentially and the users with the high quality sensing data are
selected as the winners. Further, after observing previous
submissions, we derive every user best response effort bidding
function for sequential crowd sensing applications with budget
constraints, which influences user participation and sensing data
submission quality.
\item Extensive simulations
show that our proposed incentive mechanism outperforms the existing
solutions.
\end{itemize}
%
%\begin{figure}
%\setlength{\abovecaptionskip}{0pt}
%\setlength{\belowcaptionskip}{10pt} \centering
%%\begin{minipage}[t]{0.4\linewidth}
%\centering
%\includegraphics[width=0.32\textwidth]{mrsu1.eps}%[width=0.42\textwidth]{mrsu2.eps}%totalheight=3in,width=3.5in
%%\renewcommand{\figurename}{fig2}
%\caption{A VANETs system with three coverage regions on a road with
%four lanes.} \label{fig:mrsu1}
%%\end{minipage}
%\end{figure}

The rest of the paper is organized as follows. In Section
\ref{related}, we briefly discuss the related work and motivation.
In Section \ref{SystemModel}, we present our system model, related
definitions and our design goals. In Section \ref{MecahnismDesgn},
we design a behavior based incentive strategy for sequential crowd
sensing in MSNs, and present the performance evaluation in Section
\ref{Experiment}. Finally, Section \ref{Conclude} concludes the
paper.

\section{Background and Related Work}~\label{related}
Extensive user participation and submission quality issues are two
crucial human factors for crowd sensing applications in MSNs. The
authors of \cite{reddy2010recruitment} proposed recruitment
frameworks to enable the platform to identify well-suited
participants for sensing data collections. However, they only
considered the users' selection, rather than the incentive mechanism
design. In recent years, most of reported studies have focused on
how to stimulate selfish participants to enhance user participation
levels. For instance, the authors of
\cite{duan2012incentive,lee2010dynamic,jaimes2012location,sun13globecom}
explored the extensive user participation to achieve a good sensing
service for crowd sensing applications. Obviously, it is not
practical to assume that the requester in their mechanisms will
always have an unlimited budget. The authors of
\cite{chen2011approximability,singer2010budget,tran2012efficient,yang2012crowdsourcing}
designed an incentive mechanism to enhance user participation levels
under a budget constraint. Although they designed truthful
mechanisms, which optimized the utility function of the platform
under a fixed budget constraint,
to incentive extensive user participation, the effects of the online sequential manner, in which users arrive, were neglected. %handle
%the ''price of being truthful`` issue of extensive user
%participating in a budget constraint framework,
In practice, recently, there are a few works focusing on both budget
constraints and the online sequential manner of users' arrival to
enhance user participating levels. For instance, the authors of
\cite{badanidiyuru2012learning,sun14ICCcollection} exploited posted
price mechanisms for stimulating the online arrival user
participation. The authors of \cite{singer2013pricing} leveraged
threshold price mechanism for maximizing the number of tasks under
budget constraints and task completion deadlines. However, they did
not consider the submission quality issue of sensing data.

Compared with the extensive user participation issue, there are only
a handful of research works
\cite{ghosh2011incentivizing,ren2012maximizing} focusing on the
submission quality issue for crowd sensing applications in MSNs.
These works stimulate participants to submit high quality sensing
data to achieve good service quality, but do not support the
extensive user participation issue. The authors of
\cite{pham2011novel} study a problem about the low  payment from  a
predefined number of participants. On the contrary, we focus on the
utility maximum problem with a given budget. In our mechanism, in
order to simultaneously satisfy the requirements of both extensive
user participation and high quality sensing data submission, we
combine the all-pay auction mechanism and a proportional share
allocation rule to achieve the better service for crowd sensing
applications with budget constraints. Furthermore, we account for
the online arrival of users and model the issue as an online
sequential all-pay auction. Simulations indicate that our proposed
incentive mechanisms outperform existing solutions.
%there is substantial literature on online mechanism design where
%users arrive according to a given distribution. In our model, we
%first consider mechanisms for submitting sensing data according to a
%zero arrival-departure interval manner. Then we extend this model to
%the general case.

\section{System Model and Problem Formulation}~\label{SystemModel}
\subsection{System Model}
We consider the following crowd sensing system model illustrated in
Fig.~\ref{crowd}. The system consists of a crowd sensing application
platform, to which a requester with a budget $B>0$ posts a crowd
sensing application that resides in the cloud and consists of
multiple sensing servers, and many mobile device users, which are
connected to the cloud by cellular networks (e.g., GSM/3G/4G) or
WiFi connections. The crowd sensing application first publicizes a
sequential sensing task in an Area of Interest (AoI), denoted by
$\Gamma=\{\tau_{1},\tau_{2},\cdots, \tau_{m}\}$. Assume that a set
of users $\mathcal {U}=\{1,2,\cdots,n\}$ interested in the crowd
sensing service campaign register to the platform, and then arrive
online in a sequential order.

\begin{figure}
\setlength{\abovecaptionskip}{0pt}
\setlength{\belowcaptionskip}{10pt} \centering
%\begin{minipage}[t]{0.4\linewidth}
\centering
\includegraphics[width=0.25\textwidth]{crowd.eps}%[width=0.42\textwidth]{mrsu2.eps}%totalheight=3in,width=3.5in
%\renewcommand{\figurename}{fig2}
\caption{Our crowd sensing system framework with all-pay auctions.}
\label{crowd}
%\end{minipage}
\vspace{-15pt}
\end{figure}

%More formally, we model the interactive process between the platform
%and users as an online all-pay auction and are interested in online
%settings, where the plethora of users with different preference and
%skill ability $\theta \in[\underline{\theta}, \overline{\theta}]$
%($\underline{\theta}$ and $\overline{\theta}$ denote the least
%skilled behavior ability and the most skilled behavior ability
%respectively) arrive and compete in a contest by their efforts in
%one period. User behavior abilities are described by the
%distribution function $\Phi$. Each competing user can submit one
%solution at most. The user determines the efforts $e$ of the
%submitted solution according to its preference and skill ability.
%The platform determines the payment $M_{1}, M_{2}, \cdots, M_{n}$ to
%the top $n$ (highest-ranked) submissions  in one period $(M_{1}\geq
%M_{2} \geq\cdots \geq M_{L}=m>M_{L+1}=\cdots=M_{n}=0,
%\sum_{l=1}^{n}M_{l}=B)$: the user with the best submission receives
%$M_{1}$, the first runner-up
%receives $M_{2}$, and so forth. % Considering possible risk aversion
%of users by introducing a von Neumann-Morgenstern utility function
%$V$, the utility of participant $i$ who has behavior ability
%$\theta_{i}$ and submits effort $e_{i}$ is
%$V(M_{j})-e_{i}/\theta_{i}$ if $i$ wins the $j-th$ prize. %If we
%separate the uncertainties of user $i$ into its coverage region
%unique $\epsilon _{i}$ and common $\eta_{i}$, then its sensing
%outcome $x_{i}(e_{i})=e_{i}+\epsilon _{i} + \eta_{i}$ is determined
%stochastically from its effort $e_{i}$.
%Each user submits his efforts to the platform. The platform
%determines the number of prizes and the size of prizes to maximize
%the total efforts from the participatory users.

\subsection{User Model}
We explore online auctions where each user arriving randomly has a
chance to win the auction, and each offering sensing data such as
location information for constructing network coverage maps, for
which each user associate a private cost $c_{i}$. The platform has a
public (known to the mechanism designer and maybe known to all
agents) budget $B\in\mathbb{R}_{+}$, and a public nondecreasing
utility function $U$ over the subsets of users. We assume that in
each time step, a single user appears and the platform makes a
decision that is based on the information it has about the user and
the history of the previous $i-1$ stages. Generally, there are three
classes of user models: \textit{the i.i.d. model}, \textit{the
secretary model}, and \textit{the adversarial model}. The first
model means that at each time step the costs and values of users are
drawn from some unknown distributions. The second model means that
the users' costs are chosen by an adversary, however their arrival
order is a permutation that is drawn uniformly at random from the
set of all possible permutations. In the third model, the users'
costs and their arrival order are chosen by an adversary. Note that
in the third model, although the adversary cannot observe the
actions the mechanism takes, since it has full knowledge, the
adversary chooses the worst arrival order and costs. Thereby, the
mechanism cannot obtain the optimal solutions. Thus, in this paper,
we only account for the two models with respect to the distribution
of users, described in increasing order of generality: the
i.i.d.model and the secretary model.

\subsection{Problem Formulation}
We model the above interactive process between the platform and
users as an online sequential all-pay auction with the budget
constraint, where the plethora of users with different preference
and skill ability $\theta \in[\underline{\theta},
\overline{\theta}]$ ($\underline{\theta}$ and $\overline{\theta}$
denote the least skilled behavior ability and the most skilled
behavior ability respectively) arrive and compete in a contest by
their efforts in one period. User behavior abilities are described
by the distribution function $F$. Assume that users are
game-theoretic and seek to make strategy to maximize their
individual utility in equilibrium. Receiving the crowd sensing
campaign from the platform, each user $i$ provides its sensing
profile $\Gamma_{i}$ to the platform according to its preference and
skill ability so as to expect a prize allocation (i.e.,payment) in
return for its sensing data submission. The platform determines the
payment $M_{1}, M_{2}, \cdots, M_{n}$ to the top $n$
(highest-ranked) submissions in one period $(M_{1}\geq M_{2}
\geq\cdots \geq M_{L}=m>M_{L+1}=\cdots=M_{n}=0,
\sum_{l=1}^{n}M_{l}=B)$: the user with the best submission receives
$M_{1}$, the first runner-up receives $M_{2}$, and so forth. Note
that different from traditional mechanisms, here $\Gamma_{i}$ is not
fixed. Thereby, the contribution of user $i$, denoted by $e_{i}$, is
uncertain and depends on user's efforts. But when these sensing data
are submitted to the platform, the platform can identify their
contributions, i.e., their marginal utility (to be elaborated
later).

More formally, an online mechanism $\mathcal{M}=(f,p)$, which
consists of an allocation function $f:
\mathcal{R}_{+}^{n}\rightarrow 2^{[n]}$ and a payment function $p:
\mathcal{R}_{+}^{n}\rightarrow\mathcal{R}_{+}^{n}$, is needed. That
is, for any random arriving users'
$\hat{\mathcal{P}}=(\Gamma_{1},\Gamma_{2},\cdots,\Gamma_{n})$
strategy sequence, the allocation function computes an allocation of
the budget for participatory users $S^{'}\subseteq \mathcal{U}$ and
the payment function returns a payment vector to participatory
users. Thus, the utility of user $i$ is
$p_{i}-\frac{e_{i}}{\theta_{i}}$ if it is allocated,
$-\frac{e_{i}}{\theta_{i}}$ otherwise. The platform expect to obtain
the maximum value from the particpatory users' service quality under
the budget constraint, i.e.,

\begin{equation*}
\max U(S^{'}) ~~~~Subject ~to ~\sum_{i\in S^{'}} p_{i}\leq B
\end{equation*}
where $U(S^{'})$ is the monotone submodular value function of
services from the participatory users $S^{'}$. More variables are
given in Table \ref{tab:notations}.

\begin{table}[t]
\begin{center}\caption{Summary of Notations} \label{tab:notations}
\begin{tabular}{cc}\toprule
Variable & Description\\ \midrule
$\mathcal {U}$, $n$, $i$ & set of users, number of users, and some user\\
$B, B^{'}, e^{*}$ & budget constraint and stage-budget, the effort threshold\\
$T, T^{'}, t$ & deadline, end time step of each stage, and each time step\\
$\Gamma_{i}$ & user $i$' sensing profile\\
$\Gamma, m, \tau_{j}$ & set of services, number of services, and some service\\
$\theta_{i}, e_{i}, U_{i}$ & behavior ability, effort bid and marginal utility of user $i$  \\
$S^{'}, \mathcal{J}$ & set of sampled users and winners in sampled users\\
$L$ & number of users with allocated prizes larger than zero\\
$p_{i}, F_i$ & number of allocated prizes and ability distribution of user $i$\\
$\underline{\theta},\overline{\theta}$ & the least skilled and the most skilled behavior ability\\
$\Phi_{j}$ & order cumulative distribution function of the $j$-th best type \\
 \bottomrule
\end{tabular}
\end{center}
\vspace{-20pt}
\end{table}

Putting the above online policy together, we design incentive
mechanisms based on users' behavior abilities to simultaneously
satisfy the requirements of both extensive user participation and
high quality sensing data submission. To stimulate users to produce
endogenous maximal efforts, we introduce a sequential all-pay
auction to the above online allocation strategies for our incentive
mechanism design. Considering a risk-neutral budget constrained
all-pay auctions, the above utility function $U(S^{'})$ indicates
that $U(e_{1},\cdots,e_{L})=\sum _{i\in S^{'}}f(e_{i})$, where the
effort $f(e_{i})$ is equal to the marginal utility of user $i$,
i.e., $f(e_{i})=U_{i}(S^{'})=U(S^{'}\cup\{i\})-U(S^{'})$ when the
set of sampled users is $S^{'}$.

Generally speaking, the goal of the platform is to select a subset
$S$ with the size $L$
that maximizes the total efforts of the users under the given budget. % Since users' valuations are
%considered private information, the platform awards prizes to help
%achieve good equilibria. For a profile of users' effort bids $e$,
%when the  subset by the mechanism is the area $A$ and the
%prizes profile is $p=\{M_{1},M_{2},\cdots,M_{L}\}$, the utility of a
%user $i$ denoted $u_{i}(e)=\upsilon_{i}(A)-M_{i}$
A utility-maximizing platform should select the number of prizes
$L$, the total prize budget B and the allocation of prizes
$M_{1}+M_{2}+\cdots+M_{L}=B$ which maximizes the platform's utility
$U(e_{1},\cdots,e_{L},B)$. More generally, given a budget $B$ and a
reserved effort $m$, finding a subset $S$, is equivalent to
maximizing the above coverage issue of sensing data submitted by
users.

\textbf{A case study:} We consider the following scenario where the
platform expects to obtain the sensing data covering all roads in an
AoI. For convenience of presentations and calculations, we divide
each road in the AoI into multiple discrete points, and the
objective of the platform is equivalent to receiving the submitted
sensing data covering all points before $T$. The set of all points
in the AOI is denoted by $\Gamma=\{\tau_{1},\tau_{2},\cdots,
\tau_{m}\}$. The set of points submitted by user $i$ is denoted by
$\Gamma_{i}$ (called user $i$'s sensing profile), which are the
result of users' efforts based on their behavior ability. For ease
of presentation, assume that each point $\tau_{j}$ needs to be
sensed at most one time. The value of the sampled users to the
platform is: $U(S^{'})=\sum\limits_{j = 1}^m {\min \left\{
{1,\sum\nolimits_{i \in S^{'}} {s_{i,j} } } \right\}}$, where
$s_{i,j}$ equals to $1$ if $\tau_{i}\in\Gamma_{i}$, $0$ otherwise.



%illustrated in the following definition. %This case can be applied in
%many real scenarios.

%\begin{definition0}[\textbf{Submodular Function}]\label{df:nashequilibrium}
%Let $\mathbb{N}$ be a finite set, a function $U$ :
%$2^{\Omega}\rightarrow \mathbb{R}$ is submodular if
%$U(S\cup\{i\})-U(S)\geq U(T\cup\{i\})-U(T), \forall S\subseteq
%T\subseteq \Omega$, where $\mathbb{R}$ is the set of reals.
%\end{definition0}


% $\delta\sum_{i = 1}^n {e_i}$, where $\delta$
%is profit margin.
%\subsection{Contextual Situation}
%The contextual situation is a description of the sensing
%environment. The authors in [15] show in virtually all crowd sensing
%applications time and location are two important factors related to
%sensing data quality. Other than time and location, we believe the
%skill of events and the sensing environment also largely affect the
%quality of the sensing data. For instance, usually we consider a
%picture or a video clip better than a text-only description. Also,
%inaccurate sensing reports tend to be generated when a participant
%is traveling at a very fast speed. Therefore, we make time,
%location, sensor mode and traveling mode as the four contextual
%factors that we are going to use for assessing the trust of the
%sensing reports. These contextual attributes usually have a big
%influence on the trust of the sensing reports.
%\subsection{Sensing Report Quality Assessment}
%First of all, time and location are two critical factors for
%assessing sensing report quality.  We call the target time or
%location (denoted as $T_{t}$ or $L_{t}$) and the sensing time or
%location (denoted as $T_{s}$ or $L_{s}$) respectively. We denote
%$|T_{s}-T_{t}|$ and $|L_{s}-L_{t}|$ as the time and distance between
%them respectively. Spatial cloaking techniques may obfuscate the
%sensing location. We call this sensing area as the cloaking area,
%which is denoted by its diameter $D_{s}$. We then formally express
%the location factor $\lambda$ as
%$\lambda=e^{-D_{s}\cdot\alpha}\cdot(1-e^{-|L_{s}-L_{t}|\cdot\alpha})$.
%If we denote the cloak time interval as $\Delta(t_{c})$, the time
%factor $\tau$ is also obtained as
%$\tau=e^{-\Delta(t_{c})\cdot\alpha}\cdot(1-e^{-|T_{s}-T_{t}|\cdot\alpha})$.
%$\alpha$ and $\beta$ are the location and time factors respectively.
%%\subsection{Sensing Report Diversity}
%%
%%Sensing report diversity is another crucial factor to enhance the
%%total quality for crowd sensing applications. The aspect of
%%diversity is included by calculating the similarity of the views of
%%the sensing reports sampled in the recent past. Now consider two
%%questions: first, how do we know that two sensing reports are
%%dissimilar? and second, how to choose sensing report based on the
%%diversity? The first question is beyond our discussion scope, and we
%%propose to apply a clustering algorithm to group the sensing
%%reports, which describe the same event. Thus, each user can have
%%different collections of sensing reports and each collection
%%represents a single sensing task. Let $H$ be the history of the
%%sensing task that have been sampled so far. We calculate the
%%diversity of the sensing reports by comparing current report with
%%the reports stored in the history, i.e.,
%%$\upsilon=Diff(I_{c},I_{h})$, where $I_{c}$ is current sensing
%%report and $I_{h}$ is the set of sensing reports in the history, and
%%$Diff$ can be any function to calculate sensing report similarity.
%%For this purpose, we use SSIM \cite{saini2012movimash}. It is
%%intuitive for the given sensing report to see that the user interest
%%decreases with sensing time over which the relay node watches same
%%or similar data. Hence, the diversity factor of the $i^{th}$
%%sensing report $\varsigma ^{d}=\delta\cdot e^{-1/|C_i |}{\sum_{j \in
%%C_i } {\upsilon _{ij}  * T_s } }/(|C_i | - 1)$. Where $|C_{i}|$ and
%%$\delta$ are the number of sensing reports in the collection $C_{i}$
%%and the diversity weighting parameter respectively.
%Thus, we can obtain the assessment of the sensing reports from the
%participants as follows:
%\begin{equation}\label{qualityAssessment}
% Q = (1 - \lambda) + (1 - \tau). %+  \varsigma ^d.
%\end{equation}
%
%Obviously, the above quality assessment expression can easily be
%tailored based on the specific crowd sensing application's needs.
%\subsection{Attack Models}
%In this paper, we consider several powerful malicious attacks.
%\begin{definition0}[\textbf{Dictionary profiling}]\label{df:nashequilibrium}
%A powerful attacker who has obtained the dictionary of all possible
%attributes tries to determine a specific user's attribute set by
%enumerating or guessing all likely attribute sets.
%\end{definition0}
%
%\begin{definition0}[\textbf{Cheating}]\label{df:nashequilibrium}
%Cheating is another threat for most existing private profile
%matching approaches. In the process of profile matching, a
%participant may cheat by deviating from the agreed protocol.
%\end{definition0}
%
%\begin{definition0}[\textbf{Colluding}]\label{df:colludingattacks}
%The adversary may collude with other users to try to infer the
%user's private information.
%\end{definition0}
%
%%\subsection{Design Goals}
%%Specifically, the following three desirable objectives will be
%%achieved.
%%\begin{itemize}
%%\item \emph{Improving MSNs's performance with stimulation}:
%%\item \emph{Fair}: In the practical incentive protocol, the fairness is also considered.
%%\end{itemize}
%\subsection{Problem Formulation}
% from user $i$ can be computed according to the method in \cite{oscar2013artsense}. %, where $\upsilon_j$ is the valuation of
%coverage area $j$ and $A=\bigcup_i^{L} {e_{i}}$.

%We model possible risk aversion of participants with respect to
%prizes by introducing winning probabilities $P_{i}(e)$, where a
%participant of behavior ability type $\theta$ will choose to
%maximize the expected utility. Assume that $e$ denotes the effort
%strategy for the participant with behavior ability type $\theta$,
%which is related to the equilibrium effort. Accordingly, the
%participant's optimization problem is equivalent to solving the
%following expression: $\mathop {\max }_e \sum _{i} {P_i
%(e)V(M_i)-e/\theta}$, which is often referred to as the condition of
%incentive compatibility (IC). We can obtain the following Lemma
%\ref{optimallevelofeffort} about the optimal level of effort.
%\begin{lemma0}[\textbf{Incentive Compatibility
%Condition}]\label{optimallevelofeffort} According to the above
%mentioned incentive compatibility condition, the first order
%condition can transform to the following expression: $e^ * (\theta
%)=\int_\theta ^{\underline{\theta}} {s[{\sum_{l = 1}^L {P'_l
%(s)\Delta V(M_l ,M_{l + 1} )} }]ds},$ where ${\Delta V(M_l,M_{l
%+1})}=V(M_l)-V(M_{l + 1})$ denotes the gain in user's utility from
%pacing one spot higher.
%\end{lemma0}
%\emph{Proof:} The detail proof is given in our online technical
%report \cite{sun2014infocom}.
%\begin{lemma0}[\textbf{Participant Equilibrium Strategy}]\label{relayincentivecondition}
%The best strategy for each participant with the behavior ability
%$\theta$ to maximize its expected utility is to exert $e^ *(\theta)$
%efforts.
%\end{lemma0}
%\emph{Proof:} The detail proof is given in our online technical
%report \cite{sun2014infocom}.
%%\penalty10000\hfill\penalty10000\vrule height 4pt depth 2pt width
%%6pt \penalty-10000
%
%Thus, the expected total effort is given by $U_{total}  = \delta
%n\int_{\underline{\theta}}^{\overline{\theta}} {e^
%*(\theta )p(\theta )d\theta}$.
%%Obviously, from expression (\ref{ExpectedTotalefforts}), we can
%%observe that the expected total effort from the participants
%%($U_{total}$) is linear in prizes $M_{i}$ and the optimal prize
%%structure will depend on the different marginal effects of each
%%prize.
%Furthermore, we consider the condition of individual rationality
%(IR), $\sum_i {P_i (s)V(M_i) - e/\theta}\geq0$, i.e.,
%$1/nV(M_i) - e/\theta\geq0$ (expecting an equal
%probability $(1/n)$ to reach any of the n ranks). Thus, to
%satisfy the conditions of incentive compatibility (IC) and
%individual rationality (IR), the platform's total sensing data
%quality (i.e., total expected effort) problem can be written as:
%%\begin{equation}\label{prizeoptimal}
%%\begin{array}{l}
%% \mathop {\max }\limits_{\{ M_1 ,M_2 , \cdots M_n \} } U_{total} (M_1 ,M_2 , \cdots M_n ) \\
%% s.t.:\gamma \sum\limits_{j = 1}^m {( - M_j ) + } \sum\limits_{j = m + 1}^n {(M_j ) \le B}  \\
%% \end{array}
%%\end{equation}
%
%\begin{equation}\label{prizeoptimal}
%\begin{array}{l}
% \mathop {\max }\limits_{\{ M_1 ,M_2 , \cdots M_n \} } U_{total} (M_1 ,M_2 , \cdots M_n ) \\
% s.t.: \int_\theta ^{\underline{\theta}}
%{s[{\sum\limits_{l = 1}^L {P'_l (s)\Delta V(M_l ,M_{l + 1} )} }]ds}-e^ *  (\theta )=0;\\
% ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\frac{1}{n}V(M_i) - \frac{e^ *(\theta)}{\theta}\geq0; \\
% ~~~~~~~~~~~~~~~~~~~~~~~\sum\limits_{j =1}^{L} {M_j} +\gamma\sum\limits_{j =L+1}^n{(-M_j)}= B;  \\
% %~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~M_j\geq0.   \\
% \end{array}
%\end{equation}
%
%The platform chooses the prize structure to maximize the total
%expected effort, subject to the constraint that the reputation point
%cost of rewards and subsidies can not exceed the budget $B$. Our
%objective is to design an online mechanism satisfying the optimal
%conditions of the expression (\ref{prizeoptimal}).
%
%A reputation mechanism allows platform to report the reputation
%points of each participant obtained from the outcome of the data
%sensing contest with all-pay auctions to the center at the end of
%each period. We normalize the prizes awarded by applying Gaussian
%similarity function in \cite{li2010cpmc}% and \cite{von2007tutorial}
%to make $0\leq \bar{M}_{j}^{*}\leq 1$
%hold:$\bar{M}_{j}^{*}=exp(-(M_{j}^{*})^{2}/2\sigma^{2})$. The center
%aggregates all past sensing reports and publishes a reputation
%profile for the participants at the beginning of each period. The
%reputation profiles of the participants can be any statistic derived
%from that sensing history.
%
%Thus, our goals are to develop a practical prize structure
%strategies to stimulate users to participate in crowd sensing
%applications and exert highest efforts so that the platform can
%achieve the total
%expected effort maximum, which satisfying the above constraint conditions. %incentive protocol to not only
%stimulate the selfish relay nodes to participate in forwarding in
%MSNs and the crowd sensing application providers to produce high
%quality sensing data but also preserve mobile node's privacy.

\section{Optimal Mechanism Design for The Sensing Contest} \label{MecahnismDesgn}
In this section, we present an online contest mechanism for
achieving extensive user participation and stimulating users to
submit high quality sensing data. To this end, we adopt a
multiple-stage sampling-accepting process for guaranteeing extensive
user participation. Then we introduce an online sequential all-pay
auction for stimulating users to submit high quality sensing data.
\subsection{Incentive Mechanism Design}
An online contest mechanism needs to overcome several nontrivial
challenges. First, the users' effort bids are unknown and need to be
elicited in a truthful reporting manner. Second, the total prizes
cannot exceed the platform's budget; Thirdly, the mechanism needs to
tackle the online arrival of the users and  makes irrevocable
decisions on whether to allocate the number of prizes; Finally, and
most important, the mechanism needs to cope with strategic users'
endogenous efforts. To achieve good service quality, previous online
solutions and generalized secretary problems
\cite{hajiaghayi2004adaptive,bateni2010submodular,singer2013pricing,kleinberg2005multiple}
is via sampling: the first batch of the input is rejected and used
as a sample which enables making an informed decision on the rest of
the users. However, since users are likely to be discouraged to
sense data knowing the pricing mechanism will automatically reject
their effort bid. In other words, those users arriving early have no
incentive to report their bids to the platform, which may delay the
users' completion or even lead to task starvation. %Although the
%author of \cite{kleinberg2005multiple} adopts a multi-stage
%sampling-accepting process, it applies Dynkin's algorithm
%\cite{dynkin1963optimum} for the classic secretary problem at the
%first stage. Obviously, this solution also cannot ensure the
%consumer sovereignty, since Dynkin's algorithm adopts a two-stage
%sampling-accepting process.
On the other hand, the above mechanisms only apply for fixed
services submitted by each user, thereby neglect users' endogenous
efforts.

To address the above challenges, we adopt a multiple-stage
sampling-allocating process to design our online contest incentive
mechanism. At each stage, based on the above submodularity, the
mechanism maintains a effort threshold which is used to decide to
allocate the number of the users' prizes. The mechanism dynamically
increases the sample size and learns a budget that are enough to
allocate users for maximizing the total utility, then apply this
density threshold for making further allocation decisions.

Specifically, given a distribution on the arrival of users, we can
easily calculate every time step $t$ s.t. the probability that a
user arrives before t is $1/2^{i}$. All of $T$ time steps are
divided into $2^{i}$ quantiles: $\{0,1,\cdots,\lceil\log T\rceil\}$.
We apply $S^{'}$ to denote the set of all sampled users until the
time step $t$. Our mechanism (see Algorithm \ref{prizestructure})
iterates over $q_{i}\in\{0,1,\cdots,\lceil\log T\rceil\}$ and at
every time step $q_{i}$, a budget of $B/2^{i}$ is applied to
allocate the number of prizes (illustrated in
Fig.~\ref{multistage}). Firstly, when a new user $i$ arrives, with
probability $1/3$, our mechanism computes the best response effort
bid of user $i$ according to his current behavior ability, and
thereby can submit its sensing data as a result of his efforts.
Receiving user $i$'s sensing data $\Gamma_{i}$, regardless of
whether it is given prizes, it is added to the sample set $S^{'}$
due to the nature of the all-pay auction. Given a set of sampled
users $S^{'}$, the platform computes the marginal utility of user
$i$, i.e., $U_{i}(S^{'})=U(S^{'}\cup\{i\})-U(S^{'})$, $i\notin
S^{'}$. The mechanism allocates prizes to user $i$ as long as the
minimal prizes of the last offline sample stage is not larger than
the result of effort threshold $e$ (to be elaborated in the
following subsection) multiplied by the marginal utility $U_{i}(S)$,
and the allocated stage-budget $B'$ has not been exhausted. At the
first stage, we set a small effort threshold and minimal prizes to
start our mechanism. The randomization addresses extreme cases in
which only a single user with the strongest behavior abilities can
complete a large fraction of the crowd sensing application at the
threshold efforts. This is the result that an incentive compatible
variant of Dynkin's celebrated algorithm \cite{dynkin1963optimum} to
the issue of hiring the best secretary, is tailored to our setting.

To make the above mechanism to achieve our goal, in the following,
we elaborate the computation methods of the effort threshold  and
the arrival user's optimal sequential efforts.

\begin{algorithm}[t] %�㷨�Ŀ�ʼ
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand\algorithmicensure {\textbf{Output:} }
\caption{The Budgeted Behavior-based incentive mechanism under
Sequential all-pay auctions(BBS)} %�㷨�ı���
\label{prizestructure} %���㷨һ����ǩ���������������ж��㷨������
\begin{algorithmic}[1] %���1 ��ʾÿһ�ж���ʾ����
\REQUIRE Budget constraint $R$, deadlines $T$ \\
\STATE
$(T^{'},B^{'},S^{'},e^{*},M^{*},t)\leftarrow(\frac{T}{2^{\lfloor\log_{2} T\rfloor}},\frac{B}{2^{\lfloor\log_{2} T\rfloor}},\emptyset,\varepsilon,\nu,1)$;\\

\FOR{$t\leq T$}
            \IF{there is a user $i$ arriving at time step $t$}\label{threeline1}
            \STATE With probability 1/3 do:\\
                \STATE Exert the effort $e_{i}$ for user $i$ obtained according to his behavior abilities by using the expression (\ref{bideffort})
                and submit its sensing data $\Gamma_{i}$ as its effort result to the platform;\\
                \STATE Receiving these data $\Gamma_{i}$, the platform computes the marginal utility of user $i$, i.e., $U_{i}(S^{'})$;\\
                \IF {$M^{*}\leq e^{*}\cdot U_{i}(S^{'})\leq B^{'}-\sum_{j\in S}{p_{j}}$}\label{fourline1}
                    \STATE $p_{i}\leftarrow e\cdot U_{i}(S^{'})$;\label{fiveline1}\\
                %\ELSE \STATE$p_{i}\leftarrow 0$;\label{sixline1}\\
                \ENDIF
                %\IF {$e_{i}\leq e\cdot U_{i}(\mathcal {A})\leq \mathcal{B^{'}}-\sum_{j\in\mathcal {A}}{e_{j}}$}
%                    \STATE $e_{i}= e$, $\mathcal {A}=\mathcal {A}\cup\{i\}$;\\
%                \ENDIF
                \STATE $S^{'}\leftarrow S^{'}\cup\{i\}$;\\
            \STATE Otherwise do:
                   \FOR {the first user $i$ arriving by $\lfloor T^{'}\rfloor$}
                       \STATE  Run Dynkin's algorithm and offer $B$ the winner; \\%allocate $e_{i}=min\{e,\mathcal{B^{'}}\}$;\\
                       %the sequential all-pay auction to pay the winner $\mathcal{B^{'}}$ according to \cite{liu2011crowdsourcing,sela2012multi}
                   \ENDFOR

            \ENDIF\label{eightline1}
            \IF{$t=\lfloor T^{'}\rfloor$}
                \STATE Calculate $(e^{*}, M^{*})$=GetEffortThreshold($S^{'}$, 2$B^{'}$);\\
                \STATE set $B^{'}\leftarrow 2B^{'}$, $T^{'}\leftarrow 2T^{'}$;\\
            \ENDIF
            \STATE $t\leftarrow t+1$;\label{thirteenline1}\\
\ENDFOR
\end{algorithmic}
\end{algorithm}


%\begin{algorithm}[htb] %�㷨�Ŀ�ʼ
%\renewcommand{\algorithmicrequire}{\textbf{Input:}}
%\renewcommand\algorithmicensure {\textbf{Output:} }
%\caption{The Budgeted Behavior-based incentive mechanism under
%Sequential all-pay auctions(BBS)} %�㷨�ı���
%\label{prizestructure} %���㷨һ����ǩ���������������ж��㷨������
%\begin{algorithmic}[1] %���1 ��ʾÿһ�ж���ʾ����
%\REQUIRE Budget constraint $B$, sensing task deadlines $T$ \\
%\STATE Initialize: quantiles $\{0,1,\cdots,\lceil\log T\rceil\}$, Budget $B^{'}=2^{{-(l+1)}}B$, $t=1$, $l=2^{\lfloor\log T\rfloor}$;\\
%            \FOR{every quantile $t=q_{j}, j=l,l-1,\cdots,1$ }
%                   \STATE Calculate $e$=GetEffortThreshold($\mathcal {X^{'}}$, 2$\mathcal{B^{'}}$);\\
%                   \STATE Set $\mathcal{B^{'}}=2\mathcal{B^{'}}$, the winner set $\mathcal {A}\leftarrow \emptyset$;\\
%                   \STATE With probability 1/3 do:\\
%                   \WHILE{$q_{j}<t\leq q_{j+1}$}
%                        \FOR{every user $i$ who arrives at time $t$}
%                            \STATE Compute the effort bids $e_{i}$ for user $i$ according to his behavior abilities by using the expression (\ref{bideffort});\\
%                            \IF {$e_{i}\leq e\cdot U_{i}(\mathcal {A})\leq \mathcal{B^{'}}-\sum_{j\in\mathcal {A}}{e_{j}}$}
%                                \STATE $e_{i}= e$, $\mathcal {A}=\mathcal {A}\cup\{i\}$;\\
%                            \ENDIF
%                            \STATE $\mathcal {X^{'}}=\mathcal{X^{'}}\cup\{i\}$;\\
%                         \ENDFOR
%                    \ENDWHILE
%                   \STATE Otherwise do:
%                   \FOR {the first user $i$ arriving by $q_{j+1}$}
%                       \STATE  Run Dynkin's algorithm and offer $B$ the winner; \\%allocate $e_{i}=min\{e,\mathcal{B^{'}}\}$;\\
%                       %the sequential all-pay auction to pay the winner $\mathcal{B^{'}}$ according to \cite{liu2011crowdsourcing,sela2012multi}
%
%                   \ENDFOR
%            \ENDFOR
%\end{algorithmic}
%\end{algorithm}

\begin{figure}
\setlength{\abovecaptionskip}{0pt}
\setlength{\belowcaptionskip}{10pt} \centering
%\begin{minipage}[t]{0.4\linewidth}
\centering
\includegraphics[width=0.42\textwidth,height=0.12\textwidth]{multistage.eps}%[width=0.42\textwidth]{mrsu2.eps}%totalheight=3in,width=3.5in
%\renewcommand{\figurename}{fig2}
\caption{Illustration of a multi-stage sample process with deadlines
$T$. (a)Budget $B^{'}$ versus quantile $q_{i}$; (b)Quantile $q_{i}$
versus time $t$.} \label{multistage}
%\end{minipage}
\vspace{-15pt}
\end{figure}

\subsection{Threshold Effort Decision}
In this subsection, we first introduce a threshold effort to ensure
the extensive participation. Then we apply all-pay auction to
enhance users' submission quality. We now turn to the following
definition of nondecreasing submodular functions used in our pricing
mechanisms.

\begin{definition0}[\textbf{Submodular Function}]\label{df:nashequilibrium}
Let $\mathbb{N}$ be a finite set, a function $U$ : $2^{\mathcal
{U}}\rightarrow \mathbb{R}$ (the set of reals) is submodular if
$U(S\cup\{i\})-U(S)\geq U(S^{'}\cup\{i\})-U(S^{'}), \forall
S\subseteq S^{'}\subseteq \mathcal {U}$, where $S, S^{'}$, and
$\mathcal {U}$ are illustrated in Table \ref{tab:notations}, and $i$
denotes some user.
\end{definition0}

\indent\textbf{Background:} Submodularity, a discrete analog of
convexity, has played an essential role in combinatorial
optimization \cite{lovasz1983submodular}. It appears in many
important settings and almost everywhere
\cite{goemans2009approximating} including cuts in graphs
\cite{goemans1995improved,queyranne1995combinatorial,iwata2001combinatorial},
rank function of matroids \cite{edmonds2003submodular}, set covering
problems and plant location problems \cite{feige1998threshold}. In
many settings such as set covering or matroid optimization, the
relevant submodular functions are monotone, meaning that $U(S)\leq
U(S^{'})$ whenever $S\subseteq S^{'}$. More recently submodular
functions have become key concepts both in the machine learning and
algorithmic game theory communities. For example, submodular
functions have been used to model bidders' valuation functions in
combinatorial auctions \cite{lehmann2001combinatorial,
dobzinski2006truthful, balcan2011learning}, and for solving feature
selection problems in graphical models \cite{krause2012near} or for
solving various clustering problems \cite{narasimhan2007local}.

\begin{lemma0}\label{expectedsubmodular}
The value function $U(S)$ is monotone submodular.
\end{lemma0}

The proof of Lemma \ref{expectedsubmodular} is given in the
Appendix.

%\begin{table}[t]
%\centering \caption{Summary of Notations} \label{tab:notations}
%\begin{tabular}{|c|c|}
%\hline Variable & Description\\
%\hline $\tau$ & The number of slots. \\
%\hline $k$ & A class that a user belongs to.\\
%\hline $T$ & The number of slots included in a period.\\
%\hline $j$ & The number of truncated periods.\\
%\hline $\mathbb{S}$ & The social state space. \\
%\hline $s_{i}$ & The social state of user $i$. \\
%\hline $\phi$ & An element in the policy set $\Phi$.\\
%\hline $\nu$ & An subsidy of the RMBP.\\
%\hline $\omega_{i}$ & The belief value of user $i$.\\
%\hline $c$ & Fixed cost of data sensing for a time slot.\\
%\hline $d_{i}$ & The owed delivery of user $i$.\\
%\hline $r$ & At least timely-submission requirement.\\
%\hline $\mu_{i}$ & The number of user $i$ packets delivered.\\
%\hline $\beta$ & A time-discounted factor.\\

%\hline $W_{k}(\omega_{i})$ & The Whittle's index value of user $i$ in class $k$.\\
%\hline $\Lambda$ & The network stable optimality region. \\
%\hline
%\end{tabular}
%\end{table}

In a general submodular maximization problem, a proportional share
allocation rule is a natural fit to compute the effort threshold
(see Algorithm \ref{efforttheshold}) due to its monotonicity when
users are sorted according to their efforts relative to increasing
marginal contributions. %The standard greedy approach to achieve
%desirable performance of the online arrival is via sampling: the
%first batch of the contest is rejected and used as a sample to make
%an informed decision on the rest of the contest. However, since
%users knowing the fact that the mechanism will automatically reject
%their bid are reluctant to work on tasks, thereby drop out of the
%contest.
%
%To handle this challenge, we apply the following method. At each
%stage the proposed mechanism maintains an effort threshold which is
%used to decide whether to accept the users' efforts. The proposed
%mechanism dynamically increases the sample size and updates the
%effort threshold, while increasing the budget it uses for
%allocation. Thereby, users are not automatically rejected during the
%sampling. %In a sample stage, we assume that the arriving users
%%always perform and submit their crowd sensing efforts.
%At the end of every time step, our mechanism calculates an effort
%threshold for users arriving during the next time step. Since each
%stage maintains a common effort threshold, it is a natural to
%introduce a proportional share allocation rule to estimate the
%effort threshold from every sample set $\mathcal {X^{'}}$ and the
%allocated stage-budget $\mathcal {B^{'}}$. The effort threshold'
%calculation is illustrated in Algorithm \ref{efforttheshold}.
However, to enhance the sensing data quality (users' efforts), we
apply the optimal winning participant number $L$ and the optimal
prize amounts $M_{i} (i\in\{1,\cdots, L\})$ to calculate the effort
threshold of the next time step. The optimal winning participant
number $L$ and the optimal prize amounts $M_{i} (i\in\{1,\cdots,
L\})$ can be calculated according to the method in
\cite{archak2009optimal}.
 %The only difference from the proportional
%share allocation rule, at the beginning of Algorithm
%\ref{efforttheshold}, the optimal winning participant number $L$ and
%the optimal prize amounts $M_{i} (i\in\{1,\cdots, L\})$ are
%calculated according to the method in \cite{archak2009optimal}.
%Then, the algorithm runs a proportional share allocation rule to
%calculate the effort threshold.
%\begin{lemma0}[\textbf{Optimal Winning Participants}\cite{archak2009optimal}]\label{sampleofeffort}
%From the above objectives, we can identify the optimal winning
%participant number $L = \inf \left\{ {L|\sum_{k = 1}^K {\zeta _k
%W_{kL} \ge m/{V(m)\bar \theta }}} \right\}$ and the optimal bid
%prices $M_j  = \max \left( {\begin{array}{*{20}c}{m,} & {J\left( {\frac{1}{{\bar \theta }}[\sum_{k = 1}^K {\zeta _k W_{kj} } ]^{ - 1} } \right)}  \\
%\end{array}} \right)$, where $J$ is the inverse of the marginal
%utility of money, $\zeta _k$ is the constant marginal utility of the
%quality of the $k$-th best solution ($\zeta _1\geq\zeta
%_2\geq\cdots\geq\zeta _k$), and $W_{kj}=\frac{1}{2^{k+j-1}}\left(
%{\begin{array}{*{20}c}
%   {k+j-2}  \\
%   {k - 1}  \\
%\end{array}} \right)$.
%\end{lemma0}
%From the optimal winning participant number $L$ and the optimal bid
%prices $M_j$, after our mechanisms can get some price allocation
%outcomes and the requirements of their efforts for winning, users
%dynamically learns an appropriate behavior efforts for their
%abilities when performing sensing tasks. Furthermore, we use the
%sample to estimate a threshold effort. Since each stage maintains a
%common effort threshold, it is a natural to introduce a proportional
%share allocation rule to estimate the effort threshold from every
%sample set $\mathcal {X^{'}}$ and the allocated stage-budget
%$\mathcal {B^{'}}$.
Then, these sampled users are sorted according to increasing
marginal contributions relative to their prize amounts. This sorting
implies:
\begin{equation*}
U_{1}/ M_{1}\geq U_{2}/ M_{2}\geq \cdots \geq U_{L}/ M_{L},
\end{equation*}
where $U_{i}$ denotes $U_{i\mid S^{'}_{i-1}}=(U(
S^{'}_{i-1}\cup\{i\})-U(S^{'}_{i-1})$), $ S^{'}_{i-1}=\{1,2,
\cdots,i-1\}$, and $S^{'}_{0}=\emptyset$. The specifical iteration
process is illustrated in Algorithm \ref{efforttheshold} to
guarantee the extensive user participation.

\begin{algorithm}[t] %�㷨�Ŀ�ʼ
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand\algorithmicensure {\textbf{Output:} }
\caption{GetEffortThreshold} %�㷨�ı���
\label{efforttheshold} %���㷨һ����ǩ���������������ж��㷨������
\begin{algorithmic}[1] %���1 ��ʾÿһ�ж���ʾ����
\REQUIRE Sample set $S^{'}$, stage budget constraint
$B^{'}$ \\% and the positive reserve $m$ \\%, the period deadline $T$ \\
\ENSURE Effort threshold and minimal prizes, i.e., $(e, M_{L})$. \\ %�㷨�������Output
\STATE Compute the optimal winners' number and the optimal prize
amounts $M_{i} (i\in\{1,\cdots, L\})$;\\
\STATE Sort their marginal utility relative to their prize amounts,
s.t. $U_{1}/ M_{1}\geq U_{2}/ M_{2}\geq \cdots \geq U_{L}/ M_{L}$; set $k=1$;\\

\STATE The winner set $\mathcal {J}\leftarrow \emptyset$;
$i\leftarrow\arg\max_{j\in\mathcal {X^{'}}}(U_{j}(\mathcal
{J})/M_{j})$;\\
            \WHILE{$k\leq L$ and $M_{i}\leq U_{i}B^{'}/U(\mathcal {J}\cup i)$}
                    \STATE $\mathcal {J}\leftarrow \mathcal {J}\cup i$;\\
                    \STATE $i\leftarrow\arg\max_{j\in S^{'}\setminus\mathcal {J}}(U_{j}(\mathcal{J})/M_{j})$;\\
                    \STATE $k\leftarrow k+1$;\\
            \ENDWHILE
            \STATE $e \leftarrow \mathcal{B^{'}}/U(\mathcal {J})$;\\
            \RETURN $(e, M_{L})$;\\
\end{algorithmic}
\end{algorithm}
\subsection{Computing Sequential Efforts}
In the following subsection, due to space limitations, assuming that
the reserved value $m$ is zero, i.e., $e_{0}=0$, we derive the
equilibrium effort bidding function for sequential all-pay auction
arrival users. For the positive reserve case, $e_{0}>0$, the similar
results can also be derived, which will be discussed in our future
work.

For technical reasons, we assume that ties are broken in favor of
the late entrant \footnote{This is a technical assumption to derive
strict subgame perfect equilibria instead of $\epsilon$-equilibria.}
so as to illicit the truthful effort bid of the current user. For
user $i$, a submission of quality $e_{i}$ costs $e_{i}/\theta_{i}$,
indicating that it is less costly for a high ability user to submit
a sensing data of a given quality than a low ability user. Assume
that $\Phi_j$ is the cumulative distribution function of the $j$-th
best type out of $n-1$ users. According to equation (2.1.3) of
\cite{david2003order}, we have
\begin{equation*}
\Phi_j(e)=\sum\limits_{i = 1}^{n - 1} {\left( {\begin{array}{*{20}c}
   {n - 1}  \\
   i  \\
\end{array}} \right)} \Phi (e)^i (1 - \Phi (e))^{n - 1 - i}.
\end{equation*}

Moreover, the expected utility $\overline V$ of the user of ability
type $\theta$ bidding with quality $e$ is $\overline
V=\sum\limits_{l =
1}^L {\Phi _j (e)(M_l-M_{l + 1})}$. %\Delta V(M_l ,M_{l + 1} )}$, where $\Delta V(M_l
%,M_{l + 1} )=V(M_l)-V(M_{l + 1})$.
Thus, applying backward induction iteratively for user $n,
n-1,\cdots,i+1$, we can obtain the following maximization problem of
the just arrival user $i$:

\begin{equation}\label{effortbid}
\begin{array}{l}
 \mathop {\max }\limits_{e_i } \{ \overline V \prod\limits_{j = i + 1}^n {F _j (e_j  = 0)}  - \frac{{e_i }}{{\theta _i }}\} \\
 s.t.~~~e_i  \ge  e_{L-th} (\theta _{L-th}), \\
 \end{array}
\end{equation}
where $e_{L-th} (\theta _{L-th})$ denotes the L-th largest effort
bids observed by user $i$.

Therefore, in the following, we derive user $i$'s best response
effort bidding function based on the assumption that the behavior
ability distribution function is $F(x)=x^{c}$, where ${0<c<1}$ like
\cite{sela2012multi,liu2011crowdsourcing}. To derive a closed-form
solution, we therefore restrict attention to the specific family of
concave distribution functions, for which we are able to explicitly
calculate the subgame perfect equilibrium e��ort of each contestant.
This will allow us to derive some general optimal results on
multi-stage sequential all pay auctions. If we let ${\overleftarrow
{\theta _i } =[(1 - d_{L - th} )\theta _{L - th} ]^{d_i /d_{L - th}
} }$, and ${\overrightarrow {\theta _i }= [(1 - d_{1 - th} )\theta
_{1 - th} ]^{d_i /d_{1 - th} } /c}$, given
$e_{1},e_{2},\cdots,e_{i-1}$, user $i$'s best response effort
bidding function is obtained as follows (the complete calculation
process given in the Appendix):%our full version \cite{DBLPjiajunsun}

\begin{equation}\label{bideffort}
e_i  = \left\{ {\begin{array}{*{20}c}
   {\begin{array}{*{10}c}
   {0~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}  & {0 \le \theta _i  < \overleftarrow {\theta _i } }  \\
\end{array}}  \\
   {\begin{array}{*{20}c}
   {\{ e_{j - th} (\theta _{j - th} )\} _{j \in \{ 1,2, \cdots ,L\} } }  & {\overleftarrow {\theta _i }  \le \theta _i  < \overrightarrow {\theta _i } }  \\
\end{array}}  \\
   {\begin{array}{*{20}c}
   {\overline V [\theta _i (1 - d_i )]^{1/d_i } ~~~~~~~~~~~~}  & {\overrightarrow {\theta _i }  \le \theta _i  \le 1}  \\
\end{array}}  \\
\end{array}} \right.
\end{equation}

%\subsection{Designing Incentive Mechanism}
%Given a distribution on the arrival of users, we can easily
%calculate every time step $t$ s.t. the probability that a user
%arrives before t is $1/2^{i}$. All of $T$ time steps are divided
%into $2^{i}$ quantiles: $\{0,1,\cdots,\lceil\log T\rceil\}$. We
%apply $\mathcal {X^{'}}$ to denote the set of all winning bids until
%the time step $t$.
%
%\begin{figure}
%\setlength{\abovecaptionskip}{0pt}
%\setlength{\belowcaptionskip}{10pt} \centering
%%\begin{minipage}[t]{0.4\linewidth}
%\centering
%\includegraphics[width=0.42\textwidth,height=0.12\textwidth]{multistage.eps}%[width=0.42\textwidth]{mrsu2.eps}%totalheight=3in,width=3.5in
%%\renewcommand{\figurename}{fig2}
%\caption{Illustration of a multi-stage sample process with deadlines
%$T$. (a)Budget $B^{'}$ versus quantile $q_{i}$; (b)Quantile $q_{i}$
%versus time $t$.} \label{multistage}
%%\end{minipage}
%\vspace{-15pt}
%\end{figure}
%
%Our mechanism (see Algorithm \ref{prizestructure}) iterates over
%$q_{i}\in\{0,1,\cdots,\lceil\log T\rceil\}$ and at every time step
%$q_{i}$ a budget of $B/2^{i}$ is applied to allocate sensing tasks
%(illustrated in Fig.~\ref{multistage}). Firstly, our mechanism
%computes a winning sample user set by applying the all-pay auctions
%and then obtains a threshold price according to Algorithm
%\ref{efforttheshold}. In the sequel, as long as the arrival user
%efforts from his behavior abilities are above the threshold effort
%and the budget has not been exhausted, the arriving user chooses to
%perform data sensing. Finally, our mechanism allocates its entire
%budget to the user that their efforts are below the threshold
%efforts. The randomization addresses extreme cases in which only a
%single user with the strongest behavior abilities can complete a
%large fraction of the crowd sensing application at the threshold
%efforts. This is the result that an incentive compatible variant of
%Dynkin's celebrated algorithm \cite{dynkin1963optimum} to the issue
%of hiring the best secretary, is tailored to our setting.

\section{Performance Evaluation}~\label{Experiment}
To evaluate the performance of our BBS mechanism, and explore the
effects of extensive user participation and high quality sensing
data submission for real crowd sensing applications, we implement
the mechanism by applying the well-known Manhattan model obtained
from the Google Map, which is the same as \cite{sheng2012energy}.

\subsection{Experimental Setup}

In the simulation, the sensing range of each mobile phone is set to
7 meters. The AoI obtained from the Google Map is located at
Manhattan, NY, which spans $4$ blocks from west to east with a total
length of $1.135km$ and $4$ blocks from south to north with a total
width of $0.319 km$, and includes 3 Avenues and 3 Streets. We divide
each road in the AoI into multiple discrete AoIs with a uniform
spacing of 1 meter, so the AoI consists of $1135*3+319*3-9=4353$
PoIs in total, where each Avenue has $1135$ points and each Street
has $319$ points, and the crossing of Avenues and Streets includes
$9$ points. Data sensing area sizes are set at random. In summary,
we used $1887$ sensing data packets from different locations via
$200$ different users \cite{sheng2012energy}. The sensing range
(behavior ability) of different users' sensor changes from $3$
meters to $10$ meters. To start the mechanism, we initially set the
effort threshold $e^{*}$ and the number of minimal prizes $M^{*}$ of
Algorithm \ref{prizestructure} are set to $0.1$. Users arrive
according to a Poisson process in time with arrival rate $\lambda$,
which varies from 0.3 to 8 with the increment of 0.1. Arriving at
our scenario, some user is placed randomly at some location on the
AoI's roads. All measurements are averaged over $30$ sensing tasks.
Our primary goals are to evaluate the performance of the online
mechanism on real effort bids as well as to test users'
participating response to different mechanisms.

%\begin{figure}
%\setlength{\abovecaptionskip}{0pt}
%\setlength{\belowcaptionskip}{10pt} \centering
%%\begin{minipage}[t]{0.4\linewidth}
%\centering
%\includegraphics[width=0.32\textwidth]{map.eps}%[width=0.42\textwidth]{mrsu2.eps}%totalheight=3in,width=3.5in
%%\renewcommand{\figurename}{fig2}
%\caption{An area of interest for a crowd sensing application. }
%\label{map}
%%\end{minipage}
%\end{figure}

\begin{figure*}
\vspace{10pt} \centering \subfigure[]{ \label{threshold}
\includegraphics[width=1.7in, height=1.3in]{threshold.eps}}
%\vspace{10pt} \centering \subfigure[]{ \label{reputation}
%\includegraphics[width=1.5in]{reputation100.eps}}
\hspace{-0.08in} \subfigure[]{ \label{participants}
\includegraphics[width=1.7in, height=1.3in]{participants.eps}}
\hspace{-0.08in} \subfigure[]{ \label{efforts}
\includegraphics[width=1.7in, height=1.3in]{efforts.eps}}
\hspace{-0.08in} \subfigure[]{ \label{errors}
\includegraphics[width=1.7in, height=1.3in]{errors.eps}}
\caption{(a)The threshold efforts $e$ versus sample stage $t$;
%(b)The cumulative effort values of sensing reports from 50
%participants with varying $\alpha$, $\beta$ and $\delta$;
(b)Effects of user participation; (c)Effects of submission quality;
(d)The difference of submission quality.} \label{fig:random}
\vspace{-15pt}
\end{figure*}

\subsection{Threshold Evolution of Different Mechanisms}
To test the performance of our BBS mechanism, we use the users'
effort bids from all-pay auctions and compare our mechanism against
several benchmarks. Note that in order to show how many users can be
accepted to participate in the crowd sensing given a specified
budget, we only need to computing the values of users' best response
effort bidding function, which is practically obtained according to
the users' arrival sequence. We compare our BBS mechanism against
two benchmarks. One has full knowledge about users' costs, and the
other is the GetEffortThreshold procedure applied offline. We
simulate these algorithms on different budgets to examine the change
in the threshold efforts as the number of users increases in the
sample. In all simulations, we observe that the threshold efforts
converged quickly. Fig. \ref{threshold} shows that the value of the
threshold efforts changes with the stage of the mechanism (the
number of users that submitted their effort bids) on the logarithmic
scale. As we can see, the threshold efforts quickly stabilize and
remain almost constant throughout the running.
%\subsection{Impact of Different Factors}
%
%The location factor $\alpha$, time factor $\beta$, and diversity weighting parameter $\delta$ are
%vital to our sensing data quality assessment. Thus, we first
%investigate how these parameters affect users' reputation. We
%assume all users has an initial reputation of $0$. Fig. \ref{reputation} shows how $\alpha$, $\beta$ and $\delta$
%affect the reputation from one user with random sensing locations and times of these sensing
%reports.
%When $\delta$ is large,
%considering the more diversity, the sensing report diversity overwhelms
%the randomness in the contextual factors and therefore the platform gets more profits and
%all participants always get similar size prizes. When $\alpha$ and $\beta$ are large, the randomness of the
%contextual factors begins to appear, where the reputation of a good
%participant goes up and down on some curves. It does not
%mean these cases are not good. If our crowd application is sensitive to
%the context, reports with unideal contextual
%factors may increase the participants' reputation. It is obvious that the reputation curves fluctuate since the contextual factors and the
%similarity factor affect the reputation of an individual report.
%Therefore, based on the time and location
%sensitivity of the system, proper $\alpha$ and $\beta$ values should be
%chosen. Based on the proper choice of $\alpha$ and $\beta$ and other system
%parameters, a applicable $\delta$
%value needs to be chosen in order to support the
%diversity factor from having too much or too little influence.

\subsection{Effects of User Participation}
%\subsection{Impact of Different Pricing Mechanisms}
To examine whether users perform strategic considerations in their
prizing mechanisms, we can observe the distinct difference between
the plots of the different total efforts (bids) in Fig.
\ref{participants} based on different mechanisms. Most of users in
the Winner-Take-All scheme, where a single winner gets all prizes,
drop out of the contest, since the probability of winning the crowd
sensing contest decreased with number of participants. Users in the
Multiple-Winners scheme, where multiple winners get the same prizes,
exert lower effort when there are larger number of participants. In
the reverse auction, bidders accepted in the best possible scheme
increase their bids. (The following drops off since we enforce the
budget constraint). In the best incentive compatible schemes, bids
are lowered, since users bids are rejected. We believe that this is
a strong support for persisting in incentive compatible mechanisms,
since they think that this will increase their profit.
Interestingly, our BBS scheme solves both incentive compatibility
and individual rationality problems.

\subsection{Effects of Submission Quality}
%\subsection{Impact of Different Pricing Mechanisms}
To examine the quality of submission sensing data quality, we plot
the total utility value as a function of different budgets in Fig.
\ref{efforts}. In the Winner-Take-All scheme, most of users drop out
of the contest, since the probability of winning the crowd sensing
contest decreases with the number of participants increasing. Thus,
the total utility value would decreased from its maximum. Users in
the Multiple-Winners scheme, where multiple winners get the same
prizes, exert lower effort and obtain more total utility values when
there are larger numbers of participants as more budgets are
provided. In the reverse auction, bidders accepted in the best
possible scheme increased their bids. In the following, they drop
off since we enforced the budget constraint. In the best incentive
compatible schemes, bids are lowered, since users bids are rejected.
We believe that this is a strong support for persisting in incentive
compatible mechanisms, since they think that this will increase
their total utilities. Interestingly, our BBS scheme solves both IR
and IC problems, therefore, it ensures extensive user participation
and high quality sensing data submission, just as illustrated in
Fig. \ref{participants} and Fig. \ref{efforts}.

Furthermore, we also quantify submission quality by considering
users' mean differences from true on-site data over their effort
bids. Fig. \ref{errors} indicates that our BBS mechanism has a lower
mean errors than the proportional share allocation rule.

\section{Conclusions and Future Work}~\label{Conclude}
In this paper, we present a behavior based incentive strategy to
motivate users to exert the most sensing effort according to their
behavior abilities and willingness for practical crowd sensing
applications. We assess the participants' efforts according to their
context situation (e.g., sensing location and sensing
time). %The strategy is easy to implement, apply well for practical
%crowd sensing applications, and have strong theoretical guarantees.
%Compared with existing incentive mechanisms based on the reverse
%auction, where deals are performed prior to data sensing, our
%strategy motivates users' activity to exert the most sensing effort
%for practical crowd sensing applications. We focus on a more real
%crowd sensing scenario where participants arrive one by one online
%in a random order. We model the issue as an online sequential
%all-pay auction in which each participants who exert the most effort
%for sensing data service quality to win more payments over time, and
%sensing data are submitted sequentially. Further, after observing
%previous submissions, we derive reward effects on participant level
%and expected submission quality for sequential crowd sensing
%applications with budget constraints.
We believe that sequential all-pay auctions in our proposed
framework provide a good basis for real crowd sensing applications.
Future research could expand on our BBS mechanism by studying the
effects of privacy protection on participation level and submission
quality. A natural extension of this scheme may be desirable to have
submissions privacy protected and to hide user experience level or
identity.

\section*{Acknowledgment}
This work is supported by the National Natural Science Foundation of
China under Grant No.61332005, No.61272517, No.61133015, the Funds
for Creative Research Groups of China under Grant No.61121001, the
Specialized Research Fund for the Doctoral Program of Higher
Education under Grant No.20120005130002, and the Key Technologies
R\&D Program of China under Grant No.2011BAC12B03.

%\section*{Acknowledgment}
%The research reported in this paper is supported by the National
%Basic Research Program of China (973 Program) under grant No.
%2011CB302701; %China National Funds for Distinguished Young
%Scientists under Grant No. 60925010;
%The Cosponsored Project of
%Beijing Committee of Education; The Program for Changjiang Scholars
%and Innovative Research Team in University under Grant No.IRT1049;
%Asia Foresight Program under
%NSFC Grant No. 61161140320.
\bibliographystyle{IEEEtran}

\bibliography{IEEEtran}
\section* {APPDENX}
\noindent\textbf{{Proof of Lemma \ref{expectedsubmodular}:}}\\
From the previous case, we know $U(S)=\sum\limits_{j = 1}^m {\min
\left\{ {1,\sum\nolimits_{i \in S} {s_{i,j} } } \right\}}$. For
$\forall S\subseteq S^{'}\subseteq \mathcal {U}$ and $k\in \mathcal
{U}\setminus S^{'}$, we have
\begin{equation*} %\label{eq:11}
\begin{split}
U(S\cup\{k\})-U(S)&= \sum\limits_{j = 1}^m {\min \left\{ {\max\{0,
1-\sum_{i \in S} {s_{i,j} }\}, s_{k,j}  }
\right\}} \\
 &\geq\sum\limits_{j = 1}^m {\min \left\{ {\max\{0,
1-\sum_{i \in S^{'}} {s_{i,j} }\}, s_{k,j}  } \right\}}\\
&=U(S^{'}\cup\{k\})-U(S^{'})
 \end{split}
 \end{equation*}
Besides, for $\forall S\subseteq \mathcal {U}$ and $k\in \mathcal
{U}\setminus S$, we have $U(S\cup\{k\})-U(S)\geq 0$. Thus, $U(S)$ is
monotone submodular. Thereby the Lemma \ref{expectedsubmodular}
holds.

\noindent\textbf{{Proof of User $i$ Bidding Function:}}\\
%Applying backward induction iteratively for user $n,
%n-1,\cdots,i+1$, %we expect that user $n$ will win the auction if the
%%quality of her solution is higher than or equal to the best quality
%%submission among all previous submissions, $\max \left\{ {e_j
%%(\theta _j )} \right\}_{j < n}$, and if her ability is sufficiently
%%high
%%
%%user $i$ wins a reward equal to $\overline V$ if and only if the
%%quality of her submission is not less than the L-th highest among
%%the submissions, i.e., $e_i  \ge  e_{L-th} (\theta _{L-th})$.
%%
%%
%we can obtain the following maximization problem of the just arrival
%user $i$:
%
%\begin{equation}\label{effortbid}
%\begin{array}{l}
% \mathop {\max }\limits_{e_i } \{ \overline V \prod\limits_{j = i + 1}^n {P _j (e_j  = 0)}  - \frac{{e_i }}{{\theta _i }}\}  \\
% s.t.~~~e_i  \ge  e_{L-th} (\theta _{L-th}), \\
% \end{array}
%\end{equation}
%where $e_{L-th} (\theta _{L-th})$ denotes the L-th largest effort
%bids observed by user $i$. Besides, $\overline V$ is derived as
%follows:
%\begin{equation*}
%P_j(e)=\sum\limits_{i = 1}^{n - 1} {\left( {\begin{array}{*{20}c}
%   {n - 1}  \\
%   i  \\
%\end{array}} \right)} \Phi (e)^i (1 - \Phi (e))^{n - 1 - i}.
%\end{equation*}
%Thus, the expected utility $\overline V$ of the user of ability type
%$\theta$ bidding with quality $e$ is $\overline V=\sum\limits_{l =
%1}^L {\Phi _j (e)\Delta V(M_l ,M_{l + 1} )}$, where $\Delta V(M_l
%,M_{l + 1} )=V(M_l)-V(M_{l + 1})$.
In the following, we derive user $i$'s best response effort bidding
function based on the assumption that the behavior ability
distribution function is $F(x)=x^{c}$, where ${0<c<1}$ like
\cite{sela2012multi,liu2011crowdsourcing}. Applying backward
induction, % iteratively for user $n, n-1,\cdots,i+1$,
we expect that user $n$ will win the auction if the quality of her
solution is higher than or equal to the best quality submission
among all previous submissions, $\max \left\{ {e_j (\theta _j )}
\right\}_{j < n}$, and if her ability is sufficiently high, $\theta
_n  \ge \frac{1}{\overline V}\max \left\{ {e_j (\theta _j )}
\right\}_{j < n}$. If her ability is not high enough, i.e., $\theta
_n < \frac{1}{\overline V}\max \left\{ {e_j (\theta _j )}
\right\}_{j < n}$, then her benefit from winning ($\overline V$) is
less than her bidding cost. In this case, she should bid zero.
Likewise, if he bids zero, indicating that his ability is not high
enough, i.e., $\theta _n < \frac{1}{\overline V}\max \left\{ {e_j
(\theta _j )} \right\}_{j < n}$. On the other hand, user $n-1$ wins
the all-pay auction conditional on her submitting sensing data with
quality at least as high as the best previous submission. Thus,
$\max \left\{ {e_j (\theta _j )} \right\}_{j < n}=e_{n-1}$ holds.
Putting these together, we have: if user $n$ bids zero, his ability
must be not high enough, i.e., $\theta _n < \frac{e_{n-1}}{\overline
V}$. In other words, $F_n (e_n  = 0)=F_n (\theta _n
<\frac{e_{n-1}}{\overline V})=(\frac{e_{n-1}}{\overline V})^{c}$
holds. Likewise, for user $i+1$, we have $F_{i+1} (e_{i+1}  =
0)=(\frac{e_{i}}{\overline V})^{c}$ holds. Applying backward
induction, iteratively for user $n, n-1,\cdots,i+1$, we can obtain
the following equation.
%user $n-1$ the best response bidding function of the last user, $n$,
%is given by: The probability that user $i$ wins the all-pay auction
%conditional on her submitting sensing data with quality at least as
%high as the best previous submission becomes:
\begin{equation*}
\begin{array}{l}
 \prod\limits_{j = i + 1}^n {F_j (e_j  = 0)}  \\
  = [\frac{{e_i }}{{\overline V}}]^{c(1 - c)^{n - (n - (i + 1))} } [\frac{{e_i }}{{\overline V}}]^{c(1 - c)^{n - (n - (i + 2))} }  \cdots [\frac{{e_i }}{{\overline V}}]^c  \\
  = [\frac{{e_i }}{{\overline V}}]^{1-(1 - c)^{n - i} }  \\
 \end{array}
\end{equation*}
Since the constraint is not binding, the above equation is fed into
equation (\ref{effortbid}) to compute the first-order condition,
thereby, $e_{i}$ is obtained by:
\begin{equation*}
[1 - (1 - c)^{n - i} ][\frac{{e_i }}{{\overline V}}]^{ - (1 - c)^{n
- i} }  - \frac{1}{{\theta _i }} = 0.
\end{equation*}

The second-order condition is obtained by:
 \begin{equation*}
 - \frac{1}{{\overline V}}\{ (1 - c)^{n - i} (1 - (1 - c)^{n - i} )[\frac{{e_i }}{{\overline V}}]^{ - (1 - c)^{n - i} } \}  < 0
 \end{equation*}

Thus, the interior solution is $e_{i}(\theta _i)=\overline V[\theta
_i (1 - (1 - c)^{n - i} )]^{\frac{1}{{(1 - c)^{n - i} }}}$. Let
$d_{i}=(1-c)^{n-i}$. The interior solution is rewritten as
$e_{i}(\theta _i)=\overline V[\theta _i (1 -
d_{i})]^{\frac{1}{d_{i}}}$. Therefore, if we let ${\overleftarrow
{\theta _i } =[(1 - d_{L - th} )\theta _{L - th} ]^{d_i /d_{L - th}
} }$, and ${\overrightarrow {\theta _i }= [(1 - d_{1 - th} )\theta
_{1 - th} ]^{d_i /d_{1 - th} } /c}$, given
$e_{1},e_{2},\cdots,e_{i-1}$, user $i$'s best response effort
bidding function, i.e. the previous expression (\ref{bideffort})
holds evidently.


\end{document}

Budget-Constraints-PracticalCrowdSensing.bbl
\begin{thebibliography}{10}
\providecommand{\url}[1]{#1}
\csname url@rmstyle\endcsname
\providecommand{\newblock}{\relax}
\providecommand{\bibinfo}[2]{#2}
\providecommand\BIBentrySTDinterwordspacing{\spaceskip=0pt\relax}
\providecommand\BIBentryALTinterwordstretchfactor{4}
\providecommand\BIBentryALTinterwordspacing{\spaceskip=\fontdimen2\font plus
\BIBentryALTinterwordstretchfactor\fontdimen3\font minus
  \fontdimen4\font\relax}
\providecommand\BIBforeignlanguage[2]{{%
\expandafter\ifx\csname l@#1\endcsname\relax
\typeout{** WARNING: IEEEtran.bst: No hyphenation pattern has been}%
\typeout{** loaded for the language `#1'. Using the pattern for}%
\typeout{** the default language instead.}%
\else
\language=\csname l@#1\endcsname
\fi
#2}}

\bibitem{aggarwal2011integrating}
C.~C. Aggarwal and T.~Abdelzaher, ``Integrating sensors and social networks,''
  in \emph{Social Network Data Analytics}.\hskip 1em plus 0.5em minus
  0.4em\relax Springer, 2011, pp. 379--412.

\bibitem{fan2013geocommunity}
J.~Fan, J.~Chen, Y.~Du, W.~Gao, J.~Wu, and Y.~Sun, ``Geocommunity-based
  broadcasting for data dissemination in mobile social networks,'' \emph{IEEE
  Transactions on Parallel and Distributed Systems}, vol.~24, no.~4, pp.
  734--743, 2013.

\bibitem{ra2012medusa}
M.-R. Ra, B.~Liu, T.~F. La~Porta, and R.~Govindan, ``Medusa: A programming
  framework for crowd-sensing applications,'' in \emph{Proceedings of the 10th
  international conference on Mobile systems, applications, and services},
  2012, pp. 337--350.

\bibitem{zhou2013consub}
H.~Zhou, J.~Chen, J.~Fan, Y.~Du, and S.~K. Das, ``Consub: Incentive-based
  content subscribing in selfish opportunistic mobile networks,'' \emph{IEEE
  Journal on Selected Areas in Communications}, no.~99, pp. 1--11, 2013.

\bibitem{yang2012crowdsourcing}
D.~Yang, G.~Xue, X.~Fang, and J.~Tang, ``Crowdsourcing to smartphones:
  incentive mechanism design for mobile phone sensing,'' in \emph{Proceedings
  of ACM MobiCom}, 2012, pp. 173--184.

\bibitem{lee2010sell}
J.-S. Lee and B.~Hoh, ``Sell your experiences: a market mechanism based
  incentive for participatory sensing,'' in \emph{Proceedings of IEEE PerCom},
  2010, pp. 60--68.

\bibitem{duan2012incentive}
L.~Duan, T.~Kubo, K.~Sugiyama, J.~Huang, T.~Hasegawa, and J.~Walrand,
  ``Incentive mechanisms for smartphone collaboration in data acquisition and
  distributed computing,'' in \emph{Proceedings of IEEE INFOCOM}, 2012, pp.
  1701--1709.

\bibitem{jaimes2012location}
L.~G. Jaimes, I.~Vergara-Laurens, and M.~A. Labrador, ``A location-based
  incentive mechanism for participatory sensing systems with budget
  constraints,'' in \emph{Proceedings of IEEE PerCom}, 2012, pp. 103--108.

\bibitem{liu2011crowdsourcing}
T.~X. Liu, J.~Yang, L.~A. Adamic, and Y.~Chen, ``Crowdsourcing with all-pay
  auctions: A field experiment on taskcn,'' \emph{Proceedings of the American
  Society for Information Science and Technology}, vol.~48, no.~1, pp. 1--4,
  2011.

\bibitem{lee2010dynamic}
J.-S. Lee and B.~Hoh, ``Dynamic pricing incentive for participatory sensing,''
  \emph{Pervasive and Mobile Computing}, vol.~6, no.~6, pp. 693--708, 2010.

\bibitem{ghosh2011incentivizing}
A.~Ghosh and P.~McAfee, ``Incentivizing high-quality user-generated content,''
  in \emph{Proceedings of ACM WWW}, 2011, pp. 137--146.

\bibitem{ren2012maximizing}
S.~Ren, J.~Park, and M.~van~der Schaar, ``Maximizing profit on user-generated
  content platforms with heterogeneous participants,'' in \emph{Proceedings of
  IEEE INFOCOM}, 2012, pp. 612--620.

\bibitem{reddy2010recruitment}
S.~Reddy, D.~Estrin, and M.~Srivastava, ``Recruitment framework for
  participatory sensing data collections,'' in \emph{Pervasive
  Computing}.\hskip 1em plus 0.5em minus 0.4em\relax Springer, 2010, pp.
  138--155.

\bibitem{sun13globecom}
J.~Sun, ``An incentive scheme based on heterogeneous belief values for crowd
  sensing in mobile social networks,'' in \emph{Proceedings of IEEE Globecom},
  2013, pp. 1717--1722.

\bibitem{chen2011approximability}
N.~Chen, N.~Gravin, and P.~Lu, ``On the approximability of budget feasible
  mechanisms,'' in \emph{Proceedings of ACM-SIAM}, 2011, pp. 685--699.

\bibitem{singer2010budget}
Y.~Singer, ``Budget feasible mechanisms,'' in \emph{Proceedings of IEEE FOCS},
  2010, pp. 765--774.

\bibitem{tran2012efficient}
L.~Tran-Thanh, S.~Stein, A.~Rogers, and N.~R. Jennings, ``Efficient
  crowdsourcing of unknown experts using multi-armed bandits,'' in
  \emph{European Conference on Artificial Intelligence}, 2012, pp. 768--773.

\bibitem{badanidiyuru2012learning}
A.~Badanidiyuru, R.~Kleinberg, and Y.~Singer, ``Learning on a budget: Posted
  price mechanisms for online procurement,'' in \emph{Proceedings of the 13th
  ACM Conference on Electronic Commerce}, 2012, pp. 128--145.

\bibitem{sun14ICCcollection}
J.~Sun and H.~Ma, ``Collection-behavior based multi-parameter posted pricing
  mechanism for crowd sensing,'' in \emph{Proceedings of IEEE ICC}, 2014.

\bibitem{singer2013pricing}
Y.~Singer and M.~Mittal, ``Pricing mechanisms for crowdsourcing markets,'' in
  \emph{Proceedings of ACM WWW}, 2013, pp. 1157--1166.

\bibitem{pham2011novel}
H.~N. Pham, B.~S. Sim, and H.~Y. Youn, ``A novel approach for selecting the
  participants to collect data in participatory sensing,'' in \emph{Proceedings
  of IEEE SAINT}, 2011, pp. 50--55.

\bibitem{hajiaghayi2004adaptive}
M.~T. Hajiaghayi, R.~Kleinberg, and D.~C. Parkes, ``Adaptive limited-supply
  online auctions,'' in \emph{Proceedings of the 5th ACM conference on
  Electronic commerce}, 2004, pp. 71--80.

\bibitem{bateni2010submodular}
M.~Bateni, M.~Hajiaghayi, and M.~Zadimoghaddam, ``Submodular secretary problem
  and extensions,'' in \emph{Approximation, Randomization, and Combinatorial
  Optimization. Algorithms and Techniques}, 2010, pp. 39--52.

\bibitem{kleinberg2005multiple}
R.~Kleinberg, ``A multiple-choice secretary algorithm with applications to
  online auctions,'' in \emph{Proceedings of the sixteenth annual ACM-SIAM
  SODA}, 2005, pp. 630--631.

\bibitem{dynkin1963optimum}
E.~B. Dynkin, ``The optimum choice of the instant for stopping a markov
  process,'' in \emph{Soviet Math. Dokl}, vol.~4, no. 627-629, 1963.

\bibitem{lovasz1983submodular}
L.~Lov{\'a}sz, ``Submodular functions and convexity,'' in \emph{Mathematical
  Programming The State of the Art}.\hskip 1em plus 0.5em minus 0.4em\relax
  Springer, 1983, pp. 235--257.

\bibitem{goemans2009approximating}
M.~X. Goemans, N.~J. Harvey, S.~Iwata, and V.~Mirrokni, ``Approximating
  submodular functions everywhere,'' in \emph{Proceedings of the twentieth
  Annual ACM-SIAM SODA}.\hskip 1em plus 0.5em minus 0.4em\relax Society for
  Industrial and Applied Mathematics, 2009, pp. 535--544.

\bibitem{goemans1995improved}
M.~X. Goemans and D.~P. Williamson, ``Improved approximation algorithms for
  maximum cut and satisfiability problems using semidefinite programming,''
  \emph{Journal of the ACM}, vol.~42, no.~6, pp. 1115--1145, 1995.

\bibitem{queyranne1995combinatorial}
M.~Queyranne, ``A combinatorial algorithm for minimizing symmetric submodular
  functions,'' in \emph{Proceedings of the sixth ACM-SIAM SODA}, 1995, pp.
  98--101.

\bibitem{iwata2001combinatorial}
S.~Iwata, L.~Fleischer, and S.~Fujishige, ``A combinatorial strongly polynomial
  algorithm for minimizing submodular functions,'' \emph{Journal of the ACM},
  vol.~48, no.~4, pp. 761--777, 2001.

\bibitem{edmonds2003submodular}
J.~Edmonds, ``Submodular functions, matroids, and certain polyhedra,'' in
  \emph{Combinatorial Optimization��Eureka, You Shrink!}\hskip 1em plus 0.5em
  minus 0.4em\relax Springer, 2003, pp. 11--26.

\bibitem{feige1998threshold}
U.~Feige, ``A threshold of ln n for approximating set cover,'' \emph{Journal of
  the ACM}, vol.~45, no.~4, pp. 634--652, 1998.

\bibitem{lehmann2001combinatorial}
B.~Lehmann, D.~Lehmann, and N.~Nisan, ``Combinatorial auctions with decreasing
  marginal utilities,'' in \emph{Proceedings of the 3rd ACM conference on
  Electronic Commerce}, 2001, pp. 18--28.

\bibitem{dobzinski2006truthful}
S.~Dobzinski, N.~Nisan, and M.~Schapira, ``Truthful randomized mechanisms for
  combinatorial auctions,'' in \emph{Proceedings of the thirty-eighth annual
  ACM symposium on Theory of computing}, 2006, pp. 644--652.

\bibitem{balcan2011learning}
M.-F. Balcan and N.~J. Harvey, ``Learning submodular functions,'' in
  \emph{Proceedings of the 43rd annual ACM-SIAM SODA}, 2011, pp. 793--802.

\bibitem{krause2012near}
A.~Krause and C.~E. Guestrin, ``Near-optimal nonmyopic value of information in
  graphical models,'' \emph{arXiv preprint arXiv:1207.1394}, 2012.

\bibitem{narasimhan2007local}
M.~Narasimhan and J.~Bilmes, ``Local search for balanced submodular
  clusterings.'' in \emph{Proceedings of Twentieth International Joint
  Conference on Arti?cial Intelligence}, 2007, pp. 981--986.

\bibitem{archak2009optimal}
N.~Archak and A.~Sundararajan, ``Optimal design of crowdsourcing contests.'' in
  \emph{Proceedings of ICIS}, 2009, p. 200.

\bibitem{david2003order}
H.~A. David and H.~N. Nagaraja, \emph{Order statistics}.\hskip 1em plus 0.5em
  minus 0.4em\relax John Wiley \& Sons, 2003.

\bibitem{sela2012multi}
A.~Sela and E.~Segev, ``Multi-stage sequential all-pay auctions,'' Ben-Gurion
  University of the Negev, Department of Economics, Tech. Rep., 2012.

\bibitem{sheng2012energy}
X.~Sheng, J.~Tang, and W.~Zhang, ``Energy-efficient collaborative sensing with
  mobile phones,'' in \emph{Proceedings of IEEE INFOCOM}, 2012, pp. 1916--1924.

\end{thebibliography}
