How Costly is The Truth?
Nathaniel Hawthorn expressed, rather eloquently in his short story "The Birthmark"
A negative nihilist (do positive nihilists exist?) might say 'It's never worth it'. To an Apollonian moralist, truth may be everything. A scholar pilloried to reason, rationality and reality (and the relations therein) might conceive the 'pursuit of the discovery of truth' and the 'quest for knowledge' as perhaps the very reasons for her existence. To a gloomy artist, it might be, as is remarkably expressed by the gifted twelve year old Avijit (from Born Into Brothels) [when asked for his opinion on a rather ashen photo of a starving woman]
An auction is said to be incentive compatible, or truthful, if it is in every bidders' best interest to reveal (bid) their true valuations to the auctioneer. That is to say that given arbitrary bids from all the other bidders, I will always be better off revealing my true valuations to the auction. Here is an example. It is well known that traditional first price, sealed-bid auctions for a single item are not truthful. Here is why. Suppose Van Gogh's "Starry Nights" was being auctioned at the MoMA in New York. Assume that the auction is one where bidders submit sealed bids to the auctioneer, and that the painting is sold off to the highest bidder at the revealed bid. For this example, suppose that there are only two bidders at this auction: You and me. You value the exquisite masterpiece at a million dollars (feel good: you're a millionaire!), and let us say that I value it at two million dollars. In this auction setup, it is not always in my best interest to reveal my true valuation. In particular, if you bid a million dollars for the painting, I could get away by bidding one more than a million dollars and win over the picture for much cheaper than is actually my true valuation. So the traditional single-item sealed bid first price auction is not incentive compatible.
If you've used ebay, or know of Google's real time AdWords, you would know that the auction framework of these sites is a second-price auction. In a second price auction, the highest bidder is awarded the item, but is asked only to pay an amount equal to the second highest bid. It turns out that one can show, mathematically, that no matter what the other bidders do, my best bet is to reveal my true valuation in a second price auction.
So the point is, enforcing truth is not free (hence the title of this post). In the example that I gave here, there is a loss in revenue to the auctioneer if he wishes to enforce truthfulness. Of course, one might argue that in practice, auction environments are extremely competitive, and it is almost always the case that the second highest bid is almost as high as the highest bid, with the margin being really small, and so the loss in revenue is insignificant in comparison to the value of the item being auctioned.
So my talk yesterday had to deal with precisely this issue, except that the kind of auctions that I had to study were somewhat more complicated [multi-unit, multi-item combinatorial auctions]. Without imposing truthfulness, there is a certain maximum revenue that the auctioneer could hope to make. But the moment you want to enforce an auction mechanism that is truthful, you immediately lose some amount of money in revenue, and this loss is precisely what the paper investigated. So, it really was about 'How Costly is it to Enforce Truth Telling'.
Truth often finds its way to the mind close muffled in robes of sleep, and then speaks with uncompromising directness of matters in regard to which we practice an unconscious self-deception during our waking moments.So how costly is the truth?
A negative nihilist (do positive nihilists exist?) might say 'It's never worth it'. To an Apollonian moralist, truth may be everything. A scholar pilloried to reason, rationality and reality (and the relations therein) might conceive the 'pursuit of the discovery of truth' and the 'quest for knowledge' as perhaps the very reasons for her existence. To a gloomy artist, it might be, as is remarkably expressed by the gifted twelve year old Avijit (from Born Into Brothels) [when asked for his opinion on a rather ashen photo of a starving woman]
It's sad, but we can't look away, because it's true.What's fascinating to me is that these musings have profound philosophical underpinnings. Yesterday, I gave a technical talk at our department on "The Price of Truthfulness". The talk was based on a conference paper by a group of researchers in the computer science community (at U Wash) titled 'Beyond VCG: Frugality of Truthful Auctions'. And what these people want to understand and precisely quantify, is how much incentive does one need to offer bidders in a complex auction environment, to ensure that they reveal their true valuations to the auctioneer.
An auction is said to be incentive compatible, or truthful, if it is in every bidders' best interest to reveal (bid) their true valuations to the auctioneer. That is to say that given arbitrary bids from all the other bidders, I will always be better off revealing my true valuations to the auction. Here is an example. It is well known that traditional first price, sealed-bid auctions for a single item are not truthful. Here is why. Suppose Van Gogh's "Starry Nights" was being auctioned at the MoMA in New York. Assume that the auction is one where bidders submit sealed bids to the auctioneer, and that the painting is sold off to the highest bidder at the revealed bid. For this example, suppose that there are only two bidders at this auction: You and me. You value the exquisite masterpiece at a million dollars (feel good: you're a millionaire!), and let us say that I value it at two million dollars. In this auction setup, it is not always in my best interest to reveal my true valuation. In particular, if you bid a million dollars for the painting, I could get away by bidding one more than a million dollars and win over the picture for much cheaper than is actually my true valuation. So the traditional single-item sealed bid first price auction is not incentive compatible.
If you've used ebay, or know of Google's real time AdWords, you would know that the auction framework of these sites is a second-price auction. In a second price auction, the highest bidder is awarded the item, but is asked only to pay an amount equal to the second highest bid. It turns out that one can show, mathematically, that no matter what the other bidders do, my best bet is to reveal my true valuation in a second price auction.
So the point is, enforcing truth is not free (hence the title of this post). In the example that I gave here, there is a loss in revenue to the auctioneer if he wishes to enforce truthfulness. Of course, one might argue that in practice, auction environments are extremely competitive, and it is almost always the case that the second highest bid is almost as high as the highest bid, with the margin being really small, and so the loss in revenue is insignificant in comparison to the value of the item being auctioned.
So my talk yesterday had to deal with precisely this issue, except that the kind of auctions that I had to study were somewhat more complicated [multi-unit, multi-item combinatorial auctions]. Without imposing truthfulness, there is a certain maximum revenue that the auctioneer could hope to make. But the moment you want to enforce an auction mechanism that is truthful, you immediately lose some amount of money in revenue, and this loss is precisely what the paper investigated. So, it really was about 'How Costly is it to Enforce Truth Telling'.
posted by Ashish.rastogi@gmail.com | 2:28 PM
12 Comments:
Are 'truthful' auctions always less revenue generating than highest price acutions? If so why would it be worth it to enforce truthfulness?
In a sealed bid auction, since you do not in fact know how much the other bidders value the item, are you not likely to bid close to your true valuation?
Yes, truthful auctions always generate revenue that is less than or equal to the revenue that the auction could generate had everyone revealed their true preferences. But in the absence of a mechanism that enforces truthfulness, one is not guaranteed that bidders will reveal their true valuations [since it might not be in their best interest to do so]. It is worth it to enforce truthfulness because if you don't enforce it and carry out a highest price auction, then bidders may underreport their valuations, and you might therefore lose more in revenue than you might if the mechanism were truthful.
For your second question, your reasoning is correct intuitively. But mathematically, to argue truthfulness, one needs to show that there does not exist any combination of bids from the other bidders such that it is in your best interest to misreport your valuation.
This post has been removed by a blog administrator.
This post has been removed by a blog administrator.
This post has been removed by a blog administrator.
This post has been removed by a blog administrator.
This post has been removed by a blog administrator.
Great site!
Interesting post, I randomly found it in the description of a vehicle on ebay motors! Can't really see how it would push the sale?
Still whatever a good read - thanks :)
Nice post. Well if you have the time check this too : Directory submission
I was browsing the web for something like this and found it here on cs.nyu.edu. Nice original thought.
Thanks for bringing this "How Costly is The Truth?" up. Keep 'em coming.
Tim Dillard
Relationship between directory submissions and search engine rankings: One way links and search engine rankings have a great cause and effect relationship. Think of it as a business referral system. The business with the more referrals is most popular and hence, search engines rank them higher.
Post a Comment
<< Home