diff options
Diffstat (limited to 'problem.tex')
| -rw-r--r-- | problem.tex | 21 |
1 files changed, 18 insertions, 3 deletions
diff --git a/problem.tex b/problem.tex index 47991e3..a0a4419 100644 --- a/problem.tex +++ b/problem.tex @@ -55,7 +55,7 @@ B$. We write: \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 the \emph{strategic case}, each items in $\mathcal{N}$ is held by a different strategic agent, whose cost is a-priori private. +In the \emph{strategic case}, each items in $\mathcal{N}$ is held by a different strategic agent, whose cost is \emph{a priori} private. A \emph{mechanism} $\mathcal{M} = (f,p)$ comprises (a) an \emph{allocation function} $f:\reals_+^n \to 2^\mathcal{N}$ and (b) a \emph{payment function} $p:\reals_+^n\to \reals_+^n$. Given the @@ -68,10 +68,10 @@ no positive transfers ($p_i(c)\geq 0$). In addition to the above, mechanism design in budget feasible reverse auctions seeks mechanisms that have the following properties \cite{singer-mechanisms,chen}: \begin{itemize} - \item \emph{Truthfulness.} An agent has no incentive to missreport her true cost. Formally, let $c_{-i}$ + \item \emph{Truthfulness.} An agent has no incentive to misreport her true cost. Formally, let $c_{-i}$ be a vector of costs of all agents except $i$. % $c_{-i}$ being the same). Let $[p_i']_{i\in \mathcal{N}} = p(c_i', % c_{-i})$, then the -A mechanism is truthful iff every $i \in \mathcal{N}$ and every two cost vectors $(c_i,c_{-i})$ and $(c_i',c_{-i})$ +A mechanism is truthful iff for every $i \in \mathcal{N}$ and every two cost vectors $(c_i,c_{-i})$ and $(c_i',c_{-i})$ $p_i(c_i,c_{-i}) - s_i(c_i,c_{-i})\cdot c_i \geq p_i(c_i',c_{-i}) - s(c_i',c_{-i})\cdot c_i$. \item \emph{Budget Feasibility.} The sum of the payments should not exceed the budget constraint: @@ -108,10 +108,18 @@ c_{-i})$ implies $i\in f(c_i', c_{-i})$, and (b) %\end{enumerate} \end{lemma} \fussy +<<<<<<< HEAD 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 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$. +======= +Myerson's Theorem is particularly useful when designing a budget feasible truthful +mechanism. One can focus on designing a monotone allocation function, and the +resulting mechanism will be truthful as long as each agent is given her +threshold payment---the caveat being that the latter need to sum to a value +below $B$. +>>>>>>> c29302b25adf190f98019eb8ce5f79b10b66d54d \subsection{Budget Feasible Experimental Design} @@ -132,10 +140,17 @@ etc.). The cost $c_i$ is the amount the subject deems sufficient to incentivize her participation in the study. Note that, in this setup, the feature vectors $x_i$ are public information that the experimenter can consult prior the experiment design. Moreover, though a subject may lie about her true cost $c_i$, she cannot lie about $x_i$ (\emph{i.e.}, all features are verifiable upon collection) or $y_i$ (\emph{i.e.}, she cannot falsify her measurement). %\subsection{D-Optimality Criterion} +<<<<<<< HEAD Ideally, motivated by the $D$-optimality criterion, we would like to design a mechanism that maximizes or approximates \eqref{dcrit} . Since \eqref{dcrit} may take arbitrarily small negative values, to define a meaningful approximation one would consider the (equivalent) maximization of $V(S) = \det\T{X_S}X_S$. %, for some strictly increasing, on-to function $f:\reals_+\to\reals_+$. However, the following lower bound implies that such an optimization goal cannot be attained under the constraints of truthfulness, budget feasibility, and individual rationality. \begin{lemma} For any $M>1$, there is no $M$-approximate, truthful, budget feasible, individionally rational mechanism for a budget feasible reverse auction with $V(S) = \det{\T{X_S}X_S}$. +======= +Ideally, motivated by the $D$-optimality criterion, we would like to design a mechanism that maximizes \eqref{dcrit} within a good approximation ratio. As \eqref{dcrit} may take arbitrarily small negative values, to define a meaningful approximation one would consider the (equivalent) maximization of $V(S) = \det\T{X_S}X_S$. %, for some strictly increasing, on-to function $f:\reals_+\to\reals_+$. +However, the following lower bound implies that such an optimization goal cannot be attained under the constraints of truthfulness, budget feasibility, and individual rationality. +\begin{lemma} +For any $M>1$, there is no $M$-approximate, truthful, budget feasible, individually rational mechanism for a budget feasible reverse auction with value function $V(S) = \det{\T{X_S}X_S}$. +>>>>>>> c29302b25adf190f98019eb8ce5f79b10b66d54d \end{lemma} \begin{proof} \input{proof_of_lower_bound1} |