Gal Oshri

Contracting experts with unknown cost structures

Mark Braverman, Gal Oshri

We investigate the problem of a principal looking to contract an expert to provide a probability forecast for a categorical event. We assume all experts have a common public prior on the event's probability, but can form more accurate opinions by engaging in research. Various experts' research costs are unknown to the principal. We present a truthful and efficient mechanism for the principal's problem of contracting an expert. This results in the principal contracting the best expert to do the work, and the principal's expected utility is equivalent to having the second best expert in-house. Our mechanism connects scoring rules with auctions, a connection that is useful when obtaining new information requires costly research.


Search using queries on indistinguishable items

Mark Braverman, Gal Oshri

We investigate the problem of determining a set $S$ of $k$ indistinguishable integers in the range $[1, n]$. The algorithm is allowed to query an integer $q\in [1,n]$, and receive a response comparing this integer to an integer randomly chosen from $S$. The algorithm has no control over which element of $S$ the query $q$ is compared to. We show tight bounds for this problem. In particular, we show that in the natural regime where $k\le n$, the optimal number of queries to attain $n^{-\Omega(1)}$ error probability is $\Theta(k^3 \log n)$. In the regime where $k>n$, the optimal number of queries is $\Theta(n^2 k \log n)$. Our main technical tools include the use of information theory to derive the lower bounds, and the application of noisy binary search in the spirit of Feige, Raghavan, Peleg, and Upfal (1994). In particular, our lower bound technique is likely to be applicable in other situations that involve search under uncertainty.

presented at STACS'13, arXiv