diff options
Diffstat (limited to 'problem.tex')
| -rw-r--r-- | problem.tex | 5 |
1 files changed, 3 insertions, 2 deletions
diff --git a/problem.tex b/problem.tex index 6f07d29..033c7e1 100644 --- a/problem.tex +++ b/problem.tex @@ -100,7 +100,7 @@ In the full-information case, the experiment costs are common knowledge; as such \text{subject to}\quad \sum_{i\in S} c_i&\leq B \end{align}\label{edp} \end{subequations} -We denote by +\emph{W.l.o.g.}, we assume that $c_i\in [0,B]$ for all $i\in \mathcal{N}$, as no $i$ with $c_i>B$ can be in $S$. We denote by \begin{equation}\label{eq:non-strategic} OPT = \max_{S\subseteq\mathcal{N}} \Big\{V(S) \;\Big| \; \sum_{i\in S}c_i\leq B\Big\} @@ -141,7 +141,7 @@ yields an approximation ratio of $\frac{5 e }{e-1}~$\cite{singer-mechanisms}; t \subsection{Budget-Feasible Experimental Design: Strategic Case} -Rather than the above full information case, we study the strategic case, in which the costs $c_i$ are {\em not} common knowledge and their reporting can be manipulated by the experiment subjects. The latter are strategic and wish to maximize their utility, which is the difference of the payment they receive and their true cost. We note that, though subjects may misreport $c_i$, they cannot lie about $x_i$ (\emph{i.e.}, all public features are verifiable prior to the experiment) nor $y_i$ (\emph{i.e.}, the subject cannot falsify her measurement). +We study the following \emph{strategic} setting, in which the costs $c_i$ are {\em not} common knowledge and their reporting can be manipulated by the experiment subjects. The latter are strategic and wish to maximize their utility, which is the difference of the payment they receive and their true cost. We note that, though subjects may misreport $c_i$, they cannot lie about $x_i$ (\emph{i.e.}, all public features are verifiable prior to the experiment) nor $y_i$ (\emph{i.e.}, the subject cannot falsify her measurement). %The subjects report $c_i$ in order to maximize their expected {\em utility} which is $p_i-c_i$. @@ -205,6 +205,7 @@ Ideally, we would like the allocation $S$ to be of maximal value; however, truth should be computable in time polynomial in various parameters. %time in the number of agents $n$. %\thibaut{Should we say something about the black-box model for $V$? Needed to say something in general, but not in our case where the value function can be computed in polynomial time}. \end{itemize} +%\emph{W.l.o.g.}, we assume in the sequel that costs are at most $B$, \emph{i.e.}, $c_i\in[0,B]$, for all $i\in \mathcal{N}$. This is because, by individual rationality, any $i$ for which $c_i>B$ clearly cannot be allocated; as such, any mechanism that satisfies the above properties ignores such subjects. \begin{comment} As noted in \cite{singer-mechanisms, chen}, budget feasible reverse auctions are \emph{single parameter} auctions: each agent has only one |