Palo Alto Talks
Last week was a whirl of talks.
- Bob Tarjan started his lectures on algorithms+data structures with amortized analysis. The simple example of counting the number of bit operations needed to increment n times, led to potential function based analysis and nice exercises of getting worst case bounds (via redundant codes, still with O(log n) bits). Qiqi Yan asked if there was a way to appeal to LP Duality to get worst case bounds in general. Then, Bob introduced different "heap" representations from the standard to tournament (n values are leaves of a tournament), half full (replace winners by empty slots), right full (make all empties the left branch), compressed (keep links to successive winners), and finally to half ordered representation by linking the siblings. Those who know Bob or read his monograph know, he is superbly efficient with his words. I mentored myself from his monograph when I was a graduate student, and this is now an in-person treat!
- Vijay Vazirani spoke about markets. He started with the Arrow-Debreu (AD) model that shows that there are prices for a supply that will satisfy every demand and clear the market precisely. This result has many implications and issues (not unique even beyond scaling, pareto optimality, every pareto optimal allocation comes from equilibrium after redistribution of wealth, dynamics? etc). Vijay spoke about his joint work with Kamal Jain on studying this problem with digital goods with no cost to infinite supplies and challenge is to envision a nontrivial market that doesn't allow equilibriums when everyone gets every copy of the digital good. He proposed a model that involved grouping items into semantic categories with full substitutability within each for uniform prices, and a rich context with cardinal and ordinal preferences. Now supply/demand constraints become more intricate, some bundles are forbidden, and the entire edifice of AD has to be reconstructed. This is a grand problem where Vijay's natural ebullience keeps the audience engaged through the myraid details of formulations. He left open even grander problems of pricing items like theorems, financial advice and innovations.