[Lowerbounds, Upperbounds]

Title: Auctions for dynamic environments: WiFi, last-minute tickets and grid computing
Speaker: MohammadTaghi Hajiaghayi,
Affiliation: Carnegie Mellon University

We consider the problem of auction design for dynamic environments, in which agents arrive and depart dynamically and in which goods are inherently temporal. Motivating examples are drawn from the problem of WiFi allocation in coffee houses, last-minute tickets, and scientific grid computing. We provide a characterization for the design of truthful online auctions, such that it is a domnant strategy equilibrium for bidders to reveal their true value for resources immediately upon arrival into a system. The auctions are online, in the sense that they make allocation decisions without knowledge of the future. In a setting without priors, we provide an e-competitive (for efficiency) truthful auction for a limited-supply unit-demand problem, drawing an analogy with the classic secretary problem. We also present a 2-competitive auction (wrt efficiency) for a setting with a reusable resource, and describe a randomized online auction that achieves a competitive ratio for revenue of O(log h), where h is the ratio of maximum value to minimum value among the agents. In closing, we discuss envy-pricing and the concept of “fair equilibrium” versus “dominant equilibrium”and their relation to online auctions, and we end with several interesting directions for future work.

This is from some papers which are joint work with Erik D. Demaine (MIT), Uriel Feige (MSR), David C. Parkes (Harvard), R.D. Kleinberg (Cornell), Mohammad R. Salavatipour (U. Alberta).

Following the suggestion of Mike Dinitz, I have started to investigate Google Calendar. As some of you already know, this blog server exports an ICS file that can be used for many calendar clients. I have just made it easier with a non-https URL:

http://jasmine.aladdin.cs.cmu.edu/Calendar/aladdin.ics

(There is a long story behind why this was in https in the past. Now all you need to know is that this is no longer the case.)

I see that there are still some space quoting issues to be fixed, but at least it is already in a somewhat usable stage. Also, note that Google Calendar seems to update remote calendar once a day or so. Therefore, you don’t see new events that are entered very recently.

I thank Mike for the suggestion. Maybe I will switch to Google Calendar soon. Currently I still use Rainlander on my X40 Tablet but Google Calendar has been growing on me, except that it doesn’t seem to allow me to maintain a TODO list…

Speaker: Jonathan Derryberry

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Lower Bounds for the Binary Search Tree Model

Abstract:

This talk considers the problem of bounding below the cost of accessing a sequence of keys in a binary search tree. We develop a simple lower bound framework for this problem that applies to any binary search tree algorithm, including self-adjusting and offline ones. This new framework can be used to derive two previously known lower bounds.