tag:blogger.com,1999:blog-25562705.post5939371418891282033..comments2023-10-20T12:34:59.317-04:00Comments on Adventures in Computation: Auctions with Unknown SupplyAaronhttp://www.blogger.com/profile/09952936358739421126noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-25562705.post-25499882125786115512008-11-18T14:55:00.000-05:002008-11-18T14:55:00.000-05:00Hi Jonathan,My answer has two parts: I left out so...Hi Jonathan,<BR/><BR/>My answer has two parts: I left out some details, and my motivation is not purely practical.<BR/><BR/>Sticking with the practical motivation: Actually, if you are a company like Google selling things to customers, you really want to do so in a non-discriminatory way so that you don't piss your customers off. The mechanisms we give are in a natural class that we call "online envy-free", which basically means that bidders who are given exactly the same thing shouldn't be charged different prices. If you stick to mechanisms like this, then we strengthen our lower bound to ~Ω(log n) (up to a loglog factor -- and this is tight). Since we're talking about things like pageviews and clicks on popular websites, log(n) is now starting to look pretty big.<BR/><BR/>But I don't want to pretend that we've designed a completely realistic model, because we haven't -- we've chosen a simple model that gets to the heart of the issue we want to study: online supply. And that answer, I think, sells the field of mechanism design a bit short: auctions are interesting mathematical structures in their own right, not only because they are useful for making money. Cute introductory paragraphs aside, it is interesting what restrictions the semantic constraint of truthfulness places on algorithms. If we ignore incentive issues, the problem we study is trivial: the greedy algorithm which assigns items as they come in to the highest unsatisfied bidders achieves optimal social welfare, even in the adversarial setting. But truthfulness turns out to be a real barrier in this online setting: one that can't be overcome in the adversarial setting, but which can be in the stochastic setting. <BR/><BR/>So my real answer is this: I think that the constraints that semantic restrictions like truthfulness place on computation are interesting in the same way that time and space constraints are. These problems often relate to making money, but thats not the only reason we should study them.Aaronhttps://www.blogger.com/profile/09952936358739421126noreply@blogger.comtag:blogger.com,1999:blog-25562705.post-30368184808133939822008-11-18T14:11:00.000-05:002008-11-18T14:11:00.000-05:00Interesting post. But since the motivation is prac...Interesting post. But since the motivation is practical, I have a question: for any reasonable system, wouldn't log log n be less than 16?Jonathan Katzhttps://www.blogger.com/profile/07362776979218585818noreply@blogger.com