Bayesian Algorithmic Mechanism Design (2009)
Hartline, Jason D., Lucier, Brendan
The principal problem in algorithmic mechanism design is in merging the incentive constraints imposed by selfish behavior with the algorithmic constraints imposed by computational intractability....
Competitiveness Consensus, Andrew V. Goldberg, Jason D. Hartline
We introduce Consensus Revenue Estimate (CORE) auctions. This is a class of competitive auctions that is interesting for several reasons. One auction from this class achieves a better competitive...
Bayesian Optimal No-Deficit Mechanism Design ⋆ (2009)
Shuchi Chawla, Jason D. Hartline, R. Ravi
Abstract. One of the most fundamental problems in mechanism design is that of designing the auction that gives the optimal profit to the auctioneer. For the case that the probability distributions on...
Andrew V. Goldberg, Andrew Wright, Jason D. Hartline, Michael Saks, Anna R. Karlin
We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...
Maria-florina Balcan, Avrim Blum, Jason D. Hartline, Yishay Mansour
We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a broad class of revenue-maximizing...
Andrew V. Goldberg, Jason D. Hartline, Michael Saks, Andrew Wright, Anna R. Karlin
We study a class of single-round, sealed-bid auctions for an item in unlimited supply, such as a digital good. We introduce the notion of competitive auctions. A competitive auction is truthful...
Bayesian Optimal No-deficit Mechanism Design? (2008)
Shuchi Chawla, Jason D. Hartline, Uday Rajan, R. Ravi
1 Introduction Suppose a seller is able to provide a service at total cost C to any number ofusers. Suppose further that the seller has done market research to determine the
Gagan Aggarwal, Jason D. Hartline, Nicole Immorlica, Andrew V. Goldberg
We study the problem of designing seller-optimal auctions, i.e. auctions where the objective is to maximize revenue. Prior to this work, the only auctions known to be approximately optimal in the...
ABSTRACT Optimal Mechanism Design and Money Burning (2008)
Mechanism design is now a standard tool in computer science for aligning the incentives of self-interested agents with the objectives of a system designer. There is, however, a fundamental disconnect...
Abstract On Profit-Maximizing Envy-free Pricing (2008)
Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe
We study the problem of pricing items for sale to consumers so as to maximize the seller’s revenue. We assume that for each consumer, we know the maximum amount he would be willing to pay for each...
Optimal Mechansim Design and Money Burning (2008)
Hartline, Jason D., Roughgarden, Tim
Mechanism design is now a standard tool in computer science for aligning the incentives of self-interested agents with the objectives of a system designer. There is, however, a fundamental disconnect...
Abstract On Profit-Maximizing Envy-free Pricing (2008)
Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe
We study the problem of pricing items for sale to consumers so as to maximize the seller’s revenue. We assume that for each consumer, we know the maximum amount he would be willing to pay for each...
Gagan Aggarwal, Jason D. Hartline, Nicole Immorlica, Andrew V. Goldberg
We study the problem of designing seller-optimal auctions, i.e. auctions where the objective is to maximize revenue. Prior to this work, the only auctions known to be approximately optimal in the...
Bayesian Optimal No-deficit Mechanism Design ⋆ (2008)
Shuchi Chawla, Jason D. Hartline, Uday Rajan, R. Ravi
Abstract. One of the most fundamental problems in mechanism design is that of designing the auction that gives the optimal profit to the auctioneer. For the case that the probability distributions on...
Competitive Generalized Auctions Amos Fiat (2008)
Jason D. Hartline, A. Alfred Taubman, Andrew V. Goldberg, Anna R. Karlin
God help us if we ever take the theater out of the auction business or anything else. It would be an awfully boring world.
Competitive Generalized Auctions Amos Fiat (2008)
Jason D. Hartline, A. Alfred Taubman, Andrew V. Goldberg, Anna R. Karlin
God help us if we ever take the theater out of the auction business or anything else. It would be an awfully boring world.
Andrew V. Goldberg, Jason D. Hartline, Michael Saks, Andrew Wright, Anna R. Karlin
We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...
Gagan Aggarwal, Jason D. Hartline, Nicole Immorlica, Andrew V. Goldberg
We study the problem of designing seller-optimal auctions, i.e. auctions where the objective is to maximize revenue. Prior to this work, the only auctions known to be approximately optimal in the...
Maria-florina Balcan, Avrim Blum, Jason D. Hartline, Yishay Mansour
We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a broad class of revenue-maximizing...
Abstract On Profit-Maximizing Envy-free Pricing (2008)
Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe
We study the problem of pricing items for sale to consumers so as to maximize the seller’s revenue. We assume that for each consumer, we know the maximum amount he would be willing to pay for each...
Andrew V. Goldberg, Andrew Wright, Jason D. Hartline, Michael Saks, Anna R. Karlin
We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...
Andrew V. Goldberg, Jason D. Hartline
1 Introduction Consider an airplane flight where passengers have individual movie screens and can choose to view one out of a dozen movies that are broadcast simultaneously. The flight is only long...
Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin
Abstract In this paper we consider the problem of designing a mechanism for double auctions where bidders each bid to buy or sell one unit of a single commodity. We assume that each bidder's...
Competitive Generalized Auctions Amos Fiat (2007)
Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin
God help us if we ever take the theater out of the auction business or anything else. It would be an awfully boring world. | A. Alfred Taubman, Chairman, Sotheby Galleries.
Submitted to Games and Economic Behavior Competitive Auctions (2007)
Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Andrew Wright
We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...
Money burning and implementation (2007)
Jason D. Hartline, Tim Roughgarden
In response to public disapproval for any electronic mail system that includes a charge for sending email, computational spam fighting, which was originally proposed in [4], has reemerged as an...
Algorithmic pricing via virtual valuations (2007)
Shuchi Chawla, Jason D. Hartline, Robert D. Kleinberg
Algorithmic pricing is the computational problem that sellers (e.g., in supermarkets) face when trying to set prices for their items to maximize their profit in the presence of a known demand....
Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan
We study the problem of designing seller optimal auctions. Prior to this work, the only previously known auctions that are approximately optimal in worst case employ randomization. Our main result is...
Collusion-Resistant Mechanisms for Single-Parameter Agents (2005)
Andrew V. Goldberg, Jason D. Hartline
We consider the problem of designing mechanisms with the incentive property that no coalition of agents can engage in a collusive strategy that results in an increase in the combined utility of the...
On the Competitive Ratio of the Random Sampling Auction (2005)
Uriel Feige, Abraham Flaxman, Jason D. Hartline, Robert Kleinberg
Abstract. We give a simple analysis of the competitive ratio of the random sampling auction from [10]. The random sampling auction was first shown to be worst-case competitive in [9] (with a bound of...
Near-Optimal Online Auctions (2005)
Abstract We consider the online auction problem proposed byBar-Yossef, Hildrum, and Wu [4] in which an auctioneer is selling identical items to bidders arriving one at atime. We give an auction that...
Collusion-Resistant Mechanisms for Single-Parameter Agents (2005)
Andrew V. Goldberg, Jason D. Hartline
We consider the problem of designing mechanisms with the incentive property that no coalition of agents can engage in a collusive strategy that results in an increase in the combined utility of the...
On the Competitive Ratio of the Random Sampling Auction (2005)
Uriel Feige, Abraham Flaxman, Jason D. Hartline, Robert Kleinberg
Abstract. We give a simple analysis of the competitive ratio of the random sampling auction from [10]. The random sampling auction was first shown to be worst-case competitive in [9] (with a bound of...
From Optimal Limited to Unlimited Supply Auctions (2005)
We investigate the class of single-round, sealed-bid auctions for a set of identical items to bidders who each desire one unit. We adopt the worst-case competitive framework defined by [9, 5] that...
Near-Optimal Pricing in Near-Linear Time (2005)
Jason D. Hartline, Vladlen Koltun
Abstract. We present efficient approximation algorithms for a number of problems that call for computing the prices that maximize the revenue of the seller on a set of items. Algorithms for such...
On the Competitive Ratio of the Random Sampling Auction (2005)
Uriel Feige, Abraham Flaxman, Jason D. Hartline, Robert Kleinberg
Abstract. We give a simple analysis of the competitive ratio of the random sampling auction from [10]. The random sampling auction was first shown to be worst-case competitive in [9] (with a bound of...
Mechanism Design via Machine Learning (2005)
Avrim Blum, Jason D. Hartline, Yishay Mansour
We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a broad class of revenue-maximizing...
Mechanism Design via Machine Learning (2005)
Maria-florina Balcan, Jason D. Hartline
We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a wide variety of revenue-maximizing...
Mechanism design via machine learning (2005)
Maria-florina Balcan, Avrim Blum, Jason D. Hartline, Yishay Mansour
Science Foundation, by a grant from BSF and an IBM faculty award. This publication reflects only the authors ’ views.
On the Competitive Ratio of the Random Sampling Auction (2005)
Uriel Feige, Abraham Flaxman, Jason D. Hartline, Robert Kleinberg
Abstract. We give a simple analysis of the competitive ratio of the random sampling auction from [10]. The random sampling auction was first shown to be worst-case competitive in [9] (with a bound of...
Near-Optimal Pricing in Near-Linear Time (2005)
Jason D. Hartline, Vladlen Koltun
Abstract. We present efficient approximation algorithms for a number of problems that call for computing the prices that maximize the revenue of the seller on a set of items. Algorithms for such...
Mechanism design via machine learning (2005)
Maria-florina Balcan, Jason D. Hartline
We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a wide variety of revenue-maximizing...
On the Competitive Ratio of the Random Sampling Auction (2005)
Uriel Feige, Abraham Flaxman, Jason D. Hartline, Robert Kleinberg
We give a simple analysis of the competitive ratio of the random sampling auction from [10]. The random sampling auction was first shown to be worst-case competitive in [9] (with a bound of 7600 on...
A Lower Bound on the Competitive Ratio of Truthful Auctions (2004)
Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael Saks
Abstract We study a class of single-round, sealed-bid auctions for a set of identical items. We adopt the worst case competitive framework defined by [1,2] that compares the profit of an auction to...
A Lower Bound on the Competitive Ratio of Truthful Auctions (2004)
Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael Saks
Abstract We study a class of single-round, sealed-bid auctions for a set of identical items. We adopt the worst case competitive framework defined by [1,2] that compares the profit of an auction to...
Envy-free auctions for digital goods (2003)
Andrew V. Goldberg, Jason D. Hartline
We study auctions for a commodity in unlimited supply, e.g., a digital good. In particular we consider three desirable properties for auctions: Competitive: the auction achieves a constant fraction...
Envy-free auctions for digital goods (2003)
Andrew V. Goldberg, Jason D. Hartline
We study auctions for a commodity in unlimited supply, e.g., a digital good. In particular we consider three desirable properties for auctions: Competitive: the auction achieves a constant fraction...
Optimization in the private value model: Competitive analysis applied to auction design (2003)
Jason D. Hartline, Jason D. Hartline
We consider the study of a class of optimization problems with applications towards profit maximization. One feature of the classical treatment of optimization problems is that the space over which...
Competitiveness via consensus (2003)
Andrew V. Goldberg, Jason D. Hartline
We introduce the following consensus estimate problem. Several processors hold private and possibly different lower bounds on a value. The processors do not communicate with each other, but can...
Optimization in the private value model: Competitive analysis applied to auction design (2003)
Jason D. Hartline, Jason D. Hartline
We consider the study of a class of optimization problems with applications towards profit maximization. One feature of the classical treatment of optimization problems is that the space over which...
Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Andrew Wright, Michael Saks
We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...
Dynamic posted price mechanisms (2002)
Abstract We consider the problem of selling a single commodity in unlimited supply, e.g., a digital good, by a dynamic "posted price " mechanism. In such a mechanism, each consumer...
Truthful and Competitive Double Auctions (2002)
Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin
1 Introduction Dynamic pricing mechanisms, and specifically auctions with multiple buyers and sellers, are becoming increasing popular in electronic commerce. We consider double auctions in which...
Truthful and Competitive Double Auctions (2002)
Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin
1 Introduction Dynamic pricing mechanisms, and specifically auctions with multiple buyers and sellers, are becoming increasing popular in electronic commerce. We consider double auctions in which...
Characterizing History independent Data Structures (2002)
Jason D. Hartline, Edwin S. Hong, Er E. Mohr, William R. Pentney, Emily C. Rocke
Abstract. We consider history independent data structures as proposed for study by Teague and Naor [2]. In a history independent data structure, nothing can be learned from the representation of the...
Truthful and Competitive Double Auctions (2002)
Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin
Abstract In this paper we consider the problem of designing a mechanism for double auctions where bidders each bid to buy or sell one unit of a single commodity. We assume that each bidder’s...
Competitive Generalized Auctions (2002)
Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, A. Alfred Taubman
We describe mechanisms for auctions that are simultaneously truthful (alternately known as strategy-proof or incentive -compatible) and guarantee high "net" profit. We make use of...
Competitiveness via Consensus (2002)
Andrew V. Goldberg, Jason D. Hartline
We introduce the following consensus estimate problem. Several processors hold private and possibly different lower bounds on a value. The processors do not communicate with each other, but can...
Competitiveness via Consensus (2002)
Andrew V. Goldberg, Jason D. Hartline
this paper we study auctions, which are an important class of mechanisms. We consider auctions for a set of identical items. We assume that each consumer has a private utility value, i.e., the...
Truthful and Competitive Double Auctions (2002)
Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin
In this paper we consider the problem of designing a mechanism for double auctions where bidders each bid to buy or sell one unit of a single commodity. We assume that each bidder's utility...
Competitive auctions and digital goods (2001)
Andrew Goldberg, Jason Hartline, Andrew Wright, Jason D. Hartline
Abstract We study a class of single round, sealed bid auctions for items in unlimited supply such as digital goods. We focus on auctions that are truthful and competitive. Truthful auctions encourage...
Competitive Auctions for Multiple Digital Goods (2001)
Andrew Goldberg, Hartline May, Andrew V. Goldberg, Jason D. Hartline
Abstract Competitive auctions encourage consumers to bid their utility values while achieving revenueclose to that of fixed pricing with perfect market analysis. These auctions were introduced in [4]...
Competitive auctions and digital goods (2001)
Andrew V. Goldberg, Jason D. Hartline, Andrew Wright
We study a class of single round, sealed bid auctions for items in unlimited supply such as digital goods. We focus on auctions that are truthful and competitive. Truthful auctions encourage bidders...
Competitive auctions and digital goods (2001)
Andrew Goldberg, Jason Hartline, Andrew V. Goldberg, Jason D. Hartline, Andrew Wright
We study a class of single round, sealed bid auctions for items in unlimited supply such as digital goods. We focus on auctions that are truthful and competitive. Truthful auctions encourage bidders...
Andrew Goldberg, Jason Hartline, Andrew V. Goldberg, Jason D. Hartline, Andrew Wright
We study a class of single round, sealed bid auctions for items in unlimited supply such as digital goods. We focus on auctions that are truthful and competitive. Truthful auctions encourage bidders...
Competitive Auctions for Multiple Digital Goods (2000)
Andrew V. Goldberg, Jason D. Hartline
Competitive auctions encourage consumers to bid their utility values while achieving revenue close to that of xed pricing with perfect market analysis. These auctions were introduced in [6] in the...
Competitive Auctions and Digital Goods (1999)
Andrew V. Goldberg, Jason D. Hartline, Andrew Wright
We study a class of single round, sealed bid auctions for items in unlimited supply such as digital goods. We focus on auctions that are stable and competitive. Stable auctions encourage bidders to...
Mobile Agents: A Survey of Fault Tolerance and Security (1998)
This survey presents issues and current solutions in the area of mobile agent security and fault-tolerance. We discuss the use of accepted authentication and cryptographic signature techniques...
Mobile Agents: A Survey of Fault Tolerance and Security (1998)
Abstract This survey presents issues and current solutions in the area of mobile agent security and fault-tolerance. We discuss the use of accepted authentication and cryptographic signature...