The intersection of Computer Science and Economics has become increasingly important to the development of both fields. Today's software often must handle multiple individuals with their own interests in mind, bringing incentive issues to the forefront in algorithm design. Economic problems, especially in electronic commerce, increasingly involve large numbers of goods and buyers as well as unknown and complex market conditions, making algorithms and machine learning of key importance. This project aims to address fundamental questions at the heart of the intersection of these two fields. These include problems of modeling and influencing behavior in systems with large numbers of agents and components, problems of optimization under complex and changing preferences and constraints in electronic commerce, and problems of efficiently computing and estimating basic economic quantities.
This project specifically has three main thrusts. The first is development of algorithms and analysis techniques for positively influencing dynamics in systems with large numbers of interacting agents. For example, if behavior is currently at a poor-quality equilibrium, when can additional information or few targeted incentives be used "nudge" behavior towards a good equilibrium? This applies not only to self-interested agents but also to components in a distributed system acting on local information (such as sensors in a sensor network). The second thrust is development of algorithms for efficiently computing or estimating important economic quantities. This includes approximately computing Nash equilibria in large interactions, and learning submodular functions and other common valuation classes from observations of behavior or experimentation. The third thrust is developing mathematical frameworks for understanding and solving problems of pricing and resource allocation in settings with unknown and changing market conditions. These frameworks are crucial for next-generation markets of resources such as computing power and network bandwidth.
This project advanced the state of the art in foundations and algorithms for computer systems designed to help multiple users get the goods and services they need, as well as systems for computers to interact and get the information they need. We highlight three specific results of this project here. The first is a new algorithm to aid in paired-donation kidney exchange, for determining useful cross-match tests to perform in order to maximize the number of successful transplants. Cross-match tests, which test whether a donated kidney will be rejected, must be performed before transplants can take place. They are currently done after a pairing between donors and patients has been identified, and only between donors and patients in that pairing. In this work we consider a different approach in which several cross-match tests are performed per patient, with the final pairing between donors and patients made based on these test results, which has the potential to yield a greater number of successful transplants. In this work we develop and analyze algorithms to determine which tests would be most useful to perform. A second result of a quite different nature is an algorithm for communication among sensors in a noisy sensor network, designed to significantly reduce noise while preserving the true signal. The goal here is to then allow for a distant monitor to quickly and accurately determine the true conditions being observed by the sensors. This work analyzed the conditions needed for this algorithm to operate successfully, and showed in simulation that it could provide a significant benefit. Finally, the last result is an algorithm for scenarios in which multiple agents need to make decisions but (a) the best decision to make depends on the decisions made by others, and yet (b) agents are also privacy-sensitive and do not want their decisions to be known to others. The algorithm addresses this difficulty by giving a new way to provide summary information that both preserves privacy in a formal sense known as joint-differential-privacy, while at the same time keeping the summaries fairly accurate. Other results in the project include algorithms for allocating goods to a series of clients arriving online when different types of goods satisfy economies of scale, and algorithms for learning about preferences of bidders by observing the outcome of a series of auctions.
