diff options
Diffstat (limited to 'problem.tex')
| -rw-r--r-- | problem.tex | 16 |
1 files changed, 9 insertions, 7 deletions
diff --git a/problem.tex b/problem.tex index 98ca4ac..4ddaab4 100644 --- a/problem.tex +++ b/problem.tex @@ -54,7 +54,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 @@ -67,10 +67,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,8 +108,10 @@ c_{-i})$ implies $i\in f(c_i', c_{-i})$, and (b) \end{lemma} \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 -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$. +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$. \subsection{Budget Feasible Experimental Design} In this paper, we approach the problem of optimal experimental design from the @@ -130,9 +132,9 @@ incentivize her participation in the study. Note that, in this setup, the featur %\subsection{D-Optimality Criterion} 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 costraints of truthfulness, budget feasibility, and individual rationallity. +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 value fuction $V(S) = \det{\T{X_S}X_S}$. +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}$. \end{lemma} \begin{proof} \input{proof_of_lower_bound1} |