diff options
| -rw-r--r-- | problem.tex | 33 |
1 files changed, 14 insertions, 19 deletions
diff --git a/problem.tex b/problem.tex index a3b54b4..b3df3ee 100644 --- a/problem.tex +++ b/problem.tex @@ -119,16 +119,11 @@ for all $S\subseteq\mathcal{N}$, since the matrix $\T{X_S}X_S$ is positive semi- the optimal value achievable in the full-information case. \subsection{Budget-Feasible Experimental Design: Strategic Case} -We study the strategic case when $c_i$'s are specified by the subjects and they are strategic. -In this case, the costs $c_i$ are {\em not} common knowledge and they are reported by the -% their reporting can be manipulated by the -experiment subjects. - Moreover, though a subject may lie about her true cost $c_i$, she 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$. +We study the strategic case, in wich 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$. -When the experiment subjects are strategic, the experimental design problem becomes a special case of a \emph{budget feasible reverse auction}, as introduced by \citeN{singer-mechanisms}. %comprises a set of items $\mathcal{N}=\{1,\ldots,n\}$ as well as a single buyer. Each item has a cost $c_i\in\reals_+$. Moreover, the buyer has a positive value function $V:2^{\mathcal{N}}\to \reals_+$, as well as a budget $B\in \reals_+$. In the \emph{full information case}, the costs $c_i$ are common + %comprises a set of items $\mathcal{N}=\{1,\ldots,n\}$ as well as a single buyer. Each item has a cost $c_i\in\reals_+$. Moreover, the buyer has a positive value function $V:2^{\mathcal{N}}\to \reals_+$, as well as a budget $B\in \reals_+$. In the \emph{full information case}, the costs $c_i$ are common %knowledge; the objective of the buyer in this context is to select a set $S$ %maximizing the value $V(S)$ subject to the constraint $\sum_{i\in S} c_i\leq %B$. We write: @@ -137,26 +132,26 @@ When the experiment subjects are strategic, the experimental design problem beco % \sum_{i\in S}c_i\leq B\Big\} %\end{equation} %for the optimal value achievable in the full-information case. %\stratis{Should be $OPT(V,c,B)$\ldots better drop the arguments here and introduce them wherever necessary.} -In this case, the costs $c_i$ are not common knowledge and their reporting can be manipulated by the experiment subjects. - Moreover, though a subject may lie about her true cost $c_i$, she 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). +%In this case, the costs $c_i$ are not common knowledge and their reporting can be manipulated by the experiment subjects. +% Moreover, though a subject may lie about her true cost $c_i$, she 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). -A \emph{mechanism} $\mathcal{M} = (S,p)$ comprises (a) an \emph{allocation function} +When the experiment subjects are strategic, the experimental design problem becomes a special case of a \emph{budget feasible reverse auction}, as introduced by \citeN{singer-mechanisms}. Formally, a \emph{mechanism} $\mathcal{M} = (S,p)$ comprises (a) an \emph{allocation function} $S:\reals_+^n \to 2^\mathcal{N}$ and (b) a \emph{payment function} $p:\reals_+^n\to \reals_+^n$. Given the -vector or costs $c=[c_i]_{i\in\mathcal{N}}$, the allocation function $f$ determines the set in +vector or costs $c=[c_i]_{i\in\mathcal{N}}$, the allocation function $S$ determines the set in $ \mathcal{N}$ of items to be purchased, while the payment function returns a vector of payments $[p_i(c)]_{i\in \mathcal{N}}$. - Let $s_i(c) = \id_{i\in S(c)}$ be the binary indicator of $i\in f(c)$. Mechanism design in budget feasible reverse auctions seeks mechanisms that have the following properties \cite{singer-mechanisms,chen}: + Let $s_i(c) = \id_{i\in S(c)}$ be the binary indicator of $i\in S(c)$. Mechanism design in budget feasible reverse auctions seeks mechanisms that have the following properties \cite{singer-mechanisms,chen}: \begin{itemize} \item \emph{Normalization.} Unallocated experiments receive zero payments, \emph{i.e.}, \begin{align}s_i(c)=0\text{ implies }p_i(c)=0.\label{normal}\end{align} \item\emph{Individual Rationality.} Payments for allocated experiments exceed costs, \emph{i.e.}, \begin{align} p_i(c)\geq c_i\cdot s_i(c).\label{ir}\end{align} \item \emph{No Positive Transfers.} Payments are non-negative,\emph{i.e.}, -\begin{align}p_i(c)\geq 0\label{pt}\end{align}. +\begin{align}p_i(c)\geq 0\label{pt}.\end{align} \item \emph{Truthfulness.} An agent has no incentive to missreport her true cost. Formally, let $c_{-i}$ be a vector of costs of all agents except $i$. Then, % $c_{-i}$ being the same). Let $[p_i']_{i\in \mathcal{N}} = p(c_i', % c_{-i})$, then the @@ -164,7 +159,7 @@ returns a vector of payments $[p_i(c)]_{i\in \mathcal{N}}$. \item \emph{Budget Feasibility.} The sum of the payments should not exceed the budget constraint, \emph{i.e.} %\begin{displaymath} - \begin{align} \sum_{i\in\mathcal{N}} p_i \leq B.\label{budget}\end{align} + \begin{align} \sum_{i\in\mathcal{N}} p_i(c) \leq B.\label{budget}\end{align} %\end{displaymath} \end{itemize} We define the \emph{Strategic} version of \EDP as @@ -173,7 +168,7 @@ We define the \emph{Strategic} version of \EDP as %\begin{subequations} \begin{align*} \text{Maximize:}&\quad V(S) = \log\det(I_d+\T{X_{S}}X_{S}) \\ %\label{modified} \\ -\text{subject to:}&\quad (S,p)\text{ satisfying }\eqref{normal}-\eqref{budget} +\text{subject to:}&\quad \mathcal{M}=(S,p)\text{ satisfies }\eqref{normal}-\eqref{budget} \end{align*} %\end{subequations} \end{center} @@ -194,10 +189,10 @@ Given that the full information problem \EDP{} is NP-hard, we further seek mecha \end{itemize} As noted in \cite{singer-mechanisms, chen}, budget feasible reverse auctions are \emph{single parameter} auctions: each agent has only one -private value. In this case, Myerson's Theorem \cite{myerson} gives +private value (namely, $c_i$). As such, Myerson's Theorem \cite{myerson} gives a characterization of truthful mechanisms. -\begin{lemma}[Myerson \cite{myerson}]\label{thm:myerson} +\begin{lemma}[\citeN{myerson}]\label{thm:myerson} \sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is truthful iff: %\begin{enumerate} @@ -212,7 +207,7 @@ c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b) \fussy Myerson's Theorem % is particularly useful when designing a budget feasible truthful mechanism, as it -allows us to focus on designing a monotone allocation function. Then, the +allows us to focus on designing a monotone allocation function $S$. Then, the mechanism will be truthful as long as we give each agent her threshold payment---the caveat being that the latter need to sum to a value below $B$. \begin{comment} |