This project seeks a better understanding of the behavior of decentralized systems such as markets and traffic networks, via effective resource allocation and price determination for these systems. This focusses on several problems: equilibrium market price discovery, measurement and control of traffic behavior, auctions for expiring resources, two-sided auctions for ordered goods and bidders (such as web advertisements).
The goal of the price discovery work is to explain why price changes in market economies might work effectively by showing simple, independent, distributed algorithms that cause prices to converge quickly toward equilibrium values. The traffic work examines how network performance degrades in the presence of multiple large, selfish network users, and study methods to control this. The two-sided auction work investigates the design of markets where the buyers have agreed preferences for objects to be sold, and sellers have agreed preferences for who to sell to. The goal is to design real-time price and allocation mechanisms that allow bids from both buyers and sellers, while insuring both profitability and market efficiency. The work on auctions for expiring items attempts to assign renewable resources to those bidders (that arrive and depart over time) who can derive the highest value from them. The goal is to design auctions in which it is in the bidders' best interests to bid their true valuation. Auctions with this property are easier both for bidders to figure out their optimal bid, and for auction designers to understand and predict the behavior of bidders.
This grant supported the training of five graduate students in computer science.It help support the training of two post doctoral researchers. It supported the research education and training of four undergraduate students. Training included: learning to read and analyze research papers, learning to do new research, learning both oral and written communication and presentation skills for presenting their own and others work, problem solving skills, learning how to select research problems, learning to evaluate and write formal evaluations of other people's work, learning to mentor more junior researchers, and the use of computation to test theoretical ideas. It supported research collaboration with researchers at other institutions including New York University, Rensallear Polytechnic Institute, and Google. People supported on this grant have gone on to postdocs or industry positions in computer science, including California Institute of Technology and Google, and jobs in financial services and software development. The research supported by this grant includes fundamental studies of how economic markets converge to market prices; of how traffic patterns emerge and what form they take in new and existing models of traffic (vehicular or communication) networks; and of new methods to obtain improved quality guarantees on machine scheduling, load balancing, facility location, and partitioning problems. This has led to the publication of 13 papers in competitive conferences and/or journals, and over 30 presentations, several of which were in international venues. More specifically, a subset of the results include: 1) a simple model in which prices converge to equilibrium prices in polynomial time in a function of the utilities of traders. The time bound is independent both of the number of traders and the number of goods. 2) a complete characterization of which traffic networks have unique traffic equilibria when there are users with large market share of network traffic. 3) Tight approximation guarantees (complexity lower bounds that match polynomial time achievable upper bounds) for natural generalizations of partitioning and load balancing problems. 4) demonstration that certain traffic objectives can have good equilibrium behavior in a model of network traffic that allows for the time it takes to travel in the network.
