Search

We revisit the basic variant of the classical secretary problem. We propose a new approach in which we separate between an agent (the sender) that evaluates the secretary performance and one (the receiver) that makes the hiring decision. The sender signals the quality of the candidate to the hiring agent. Whenever the two agents' interests are not fully aligned, this induces an information transmission (signaling) challenge for the sender. We study the sender's optimization problem subject to persuasiveness constraints for the receiver in several variants of the problem. Our results quantify the loss in performance for the sender due to online arrival. We provide optimal and near-optimal persuasive mechanisms. In most cases the sender can recover at least a constant fraction of the utility that he would have obtained had he been able to access all information at the outset. [ABSTRACT FROM AUTHOR]

Abstract We consider the design of strategyproof cost-sharing mechanisms. We give two simple, but extremely versatile, black-box reductions , that in combination reduce the cost-sharing mechanism-design problem to the algorithmic problem of finding a min-cost solution for a set of players. Our first reduction shows that any truthful, α -approximation mechanism for the social-cost minimization (SCM) problem satisfying a technical no-bossiness condition can be morphed into a truthful mechanism that achieves an O (α log ⁡ n) -approximation where the prices recover the cost incurred. Thus, we decouple the approximation and cost-recovery objectives. Our second reduction nicely complements the first one by showing that any LP-relative ρ -approximation for the problem of finding a min-cost solution for a set of players yields a truthful, no-bossy, (ρ + 1) -approximation for the SCM problem (and hence, a truthful (ρ + 1) log ⁡ n -approximation cost-sharing mechanism). These reductions yield the first, or improved, polytime cost-sharing mechanisms for a variety of problems. [ABSTRACT FROM AUTHOR]

We consider the design of dominant strategy incentive compatible, revenue-maximizing auctions for an indivisible good, when bidders' values are drawn from a correlated distribution. For independent distributions, Myerson showed that the optimal auction for risk-neutral bidders remains incentive compatible regardless of bidders' risk attitudes. We show that, for correlated distributions, the same is true when only two bidders are involved, whereas for more bidders, randomization can generate strictly more revenue. However, for risk-neutral bidders, we show this gain is never more than a 5 3 -factor. This is a consequence of two results of independent interest: (1) a polynomial-time derandomization of auctions for two bidders; (2) a polynomial-time computable deterministic auction that 5 3 -approximates the optimal revenue extractable from risk-neutral bidders. Moreover, we give a polynomial-time algorithm to compute optimal auctions for a constant number of bidders, and for any number of bidders we give polynomial-time algorithms with approximation factors arbitrarily close to 3 2 . [ABSTRACT FROM AUTHOR]

We revisit the problem of designing the profit-maximizing single-item auction, solved by Myerson in his seminal paper for the case in which bidder valuations are independently distributed. We focus on general joint distributions, either discrete or Lipschitz-continuous, seeking the optimal deterministic incentive compatible auction. We give a geometric characterization of the optimal auction, resulting in a duality theorem and an efficient algorithm for finding the optimal deterministic auction in the two-bidder case and an NP-completeness result for three or more bidders. [ABSTRACT FROM AUTHOR]

Abstract: When attempting to design a truthful mechanism for a computationally hard problem such as combinatorial auctions, one is faced with the problem that most efficiently computable heuristics can not be embedded in any truthful mechanism (e.g. VCG-like payment rules will not ensure truthfulness). We develop a set of techniques that allow constructing efficiently computable truthful mechanisms for combinatorial auctions in the special case where each bidder desires a specific known subset of items and only the valuation is unknown by the mechanism (the single parameter case). For this case we extend the work of Lehmann, O''Callaghan, and Shoham, who presented greedy heuristics. We show how to use If-Then-Else constructs, perform a partial search, and use the LP relaxation. We apply these techniques for several canonical types of combinatorial auctions, obtaining truthful mechanisms with provable approximation ratios. [Copyright &y& Elsevier]

Abstract: In many economic settings, like spectrum and real-estate auctions, geometric figures on the plane are for sale. Each bidder bids for his desired figure, and the auctioneer has to choose a set of disjoint figures that maximizes the social welfare. In this work, we design mechanisms that are both incentive compatible and computationally feasible for these environments. Since the underlying algorithmic problem is computationally hard, these mechanisms cannot always achieve the optimal welfare; Nevertheless, they do guarantee a fraction of the optimal solution. We differentiate between two information models—when both the desired figures and their values are unknown to the auctioneer or when only the agents'' values are private data. We guarantee different fractions of the optimal welfare for each information model and for different families of figures (e.g., arbitrary convex figures or axis-aligned rectangles). We suggest using a measure on the geometric diversity of the figures for expressing the quality of the approximations that our mechanisms provide. [Copyright &y& Elsevier]