7 Result(s)
within
Chapter
Anna R. Karlin
Algorithm Analysis and Problem Complexity
Computer Communication Networks
-
Chapter and Conference Paper
Competition Alleviates Present Bias in Task Completion
We build upon recent work by Kleinberg, Oren, and Raghavan [10–12] that considers present biased agents, who place more weight on costs they must incur now than costs they will incur in the future. They consider ...
-
Chapter and Conference Paper
A Prior-Independent Revenue-Maximizing Auction for Multiple Additive Bidders
Recent work by Babaioff et al. [1], Yao [30], and Cai et al. [7] shows how to construct an approximately optimal auction for additive bidders, given access to the priors from which the bidders’ values are drawn. ...
-
Chapter and Conference Paper
On Revenue Maximization for Agents with Costly Information Acquisition
A prevalent assumption in traditional mechanism design is that buyers know their precise value for an item; however, this assumption is rarely true in practice. In most settings, buyers can “deliberate”, i.e.,...
-
Chapter and Conference Paper
Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
In this paper, we study the integrality gap of the Knapsack linear program in the Sherali-Adams and Lasserre hierarchies. First, we show that an integrality gap of 2 – ε persists up to a linear number of rounds o...
-
Chapter and Conference Paper
On Revenue Maximization in Second-Price Ad Auctions
Most recent papers addressing the algorithmic problem of allocating advertisement space for keywords in sponsored search auctions assume that pricing is done via a first-price auction, which does not realistic...
-
Chapter and Conference Paper
Dynamically Fault-Tolerant Content Addressable Networks
We describe a content addressable network which is robust in the face of massive adversarial attacks and in a highly dynamic environment. Our network is robust in the sense that at any time, an arbitrarily lar...
-
Chapter
On the performance of competitive algorithms in practice
