2 Search Results for "Raghavan, S."

Document
DOI: 10.4230/LIPIcs.STACS.2013.610
Search using queries on indistinguishable items

Authors: Mark Braverman and Gal Oshri

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
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 <= 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.
Cite as

Mark Braverman and Gal Oshri. Search using queries on indistinguishable items. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 610-621, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.STACS.2013.610,
  author =	{Braverman, Mark and Oshri, Gal},
  title =	{{Search using queries on indistinguishable items}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{610--621},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.610},
  URN =		{urn:nbn:de:0030-drops-39696},
  doi =		{10.4230/LIPIcs.STACS.2013.610},
  annote =	{Keywords: Search, Noisy Search, Information Theory, Query Complexity}
}
Document
DOI: 10.4230/DagSemProc.05011.9
Fair Payments for Efficient Allocations in Public Sector Combinatorial Auctions

Authors: Robert Day and S. Raghavan

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

Abstract
Motivated by the increasing use of auctions by government agencies, we consider the problem of fairly pricing public goods in a combinatorial auction. A well-known problem with the incentive-compatible Vickrey-Clarke-Groves (VCG) auction mechanism is that the resulting prices may not be in the core. Loosely speaking, this means the payments of the winners could be so low, that there are losing bidders who would have been willing to pay more than the payments of the winning bidders. Clearly, this ``unfair'' outcome is unacceptable for a public-sector auction. Proxy-based combinatorial auctions, in which each bidder submits several package bids to a proxy, result in efficient outcomes and bidder-Pareto-optimal core-payments by winners, thus offering a viable practical alternative to address this problem. This paper confronts two critical issues facing the proxy-auction. First, motivated to minimize a bidder's ability to benefit through strategic manipulation (through collusive agreement or unilateral action), we demonstrate the strength of a mechanism that minimizes total payments among all possible proxy auction outcomes, narrowing the previously broad solution concept. Secondly, we address the computational difficulties of achieving these outcomes with a constraint-generation approach, promising to broaden the range of applications for which the proxy-auction achieves a comfortably rapid solution.
Cite as

Robert Day and S. Raghavan. Fair Payments for Efficient Allocations in Public Sector Combinatorial Auctions. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{day_et_al:DagSemProc.05011.9,
  author =	{Day, Robert and Raghavan, S.},
  title =	{{Fair Payments for Efficient Allocations in Public Sector Combinatorial Auctions}},
  booktitle =	{Computing and Markets},
  pages =	{1--29},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.9},
  URN =		{urn:nbn:de:0030-drops-1832},
  doi =		{10.4230/DagSemProc.05011.9},
  annote =	{Keywords: auctions , core , bidder-Pareto-optimal , constraint generation , VCG payments , proxy auctions , combinatorial auctions}
}
  • Refine by Author
  • 1 Braverman, Mark
  • 1 Day, Robert
  • 1 Oshri, Gal
  • 1 Raghavan, S.

  • Refine by Classification

  • Refine by Keyword
  • 1 Information Theory
  • 1 Noisy Search
  • 1 Query Complexity
  • 1 Search
  • 1 VCG payments
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2005
  • 1 2013

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact