NOTE TO USERS This reproduction is the best copy available. ® UMI EMPIRICAL APPROACH TO THE COMPLEXITY OF HARD PROBLEMS A DISSERTATION SUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCE AND THE COMMITTEE ON GRADUATE STUDIES OF STANFORD UNIVERSITY IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY Eugene Nudelman October 2005 UMI Number: 3197488 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted.
Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3197488 Copyright 2006 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.
ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 © Copyright by Eugene Nudelman 2006 All Rights Reserved il I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. V Yoav Shoham Principal Adviser I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. DL NY Andrew Ng Ũ I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy.
3 %~= Bart Selman (Computer Science Department, Cornell University) Approved for the University Committee on Graduate Studies. ili To my parents and grandparents 1V Abstract Traditionally, computer scientists have considered computational problems and al- gorithms as artificial formal objects that can be studied theoretically. In this work we propose a different view of algorithms as natural phenomena that can be studied using empirical methods. In the first part, we propose a methodology for using ma- chine learning techniques to create accurate statistical models of running times of a given algorithm on particular problem instances.
Rather than focus on the traditional aggregate notions of hardness, such as worst-case or average-case complexity, these models provide a much more comprehensive picture of algorithms’ performance. We demonstrate that such models can indeed be constructed for two notoriously hard domains: winner determination problem for combinatorial auctions and satisfiability of Boolean formulae. In both cases the models can be analyzed to shed light on the characteristics of these problems that make them hard. We also demonstrate two con- crete applications of empirical hardness models.
First, these models can be used to construct efficient algorithm portfolios that select correct algorithm on a per-instance basis. Second, the models can be used to induce harder benchmarks. In the second part of this work we take a more traditional view of an algorithm as a tool for studying the underlying problem. We consider a very challenging problem of finding a sample Nash equilibrium (NE) of a normal-form game.
For this domain, we first present a novel benchmark suite that is more representative of the problem than traditionally-used random games. We also present a very simple search algorithm for finding NEs. The simplicity of that algorithm allows us to draw interesting conclusions about the underlying nature of the problem based on its empirical performance. In particular, we conclude that most structured games of interest have either pure- strategy equilibria or equilibria with very small supports.
Acknowledgements None of the work presented in this thesis would have been possible without many people who have continuously supported, guided, and influenced me in more ways than I can think of. Above all I am grateful to Yoav Shoham, my advisor. Yoav gave me something invaluable for a graduate student: an enormous amount of freedom to choose what I want to do and how do I want to do it. I felt his full support even when my research clearly took me to whole new fields, quite different from what I thought I would do working with Yoav.
Freedom by itself can be dangerous. I was also fortunate to have strict expectations of progress to make sure that I move along in whatever direction I chose. I felt firm guidance whenever I needed it, and could always tap Yoav for solid advice. He never ceased to amaze me with his ability to very quickly get to the heart of any problem that was thrown at him, immediately identify weakest points, and generate countless possible extensions.
I felt that Yoav would be a good match for me as an advisor when I aligned with him during my first quarter at Stanford: after five years this conviction is stronger than ever. It is impossible to overstate the influence of my good friend, co-author, and of- ficemate Kevin Leyton-Brown. I would be tempted to call him my co-advisor if I did not, in the course of our relationship. witness his transformation from a long-haired second-year Ph.
student striving to understand the basics of AI for his qual to a suc- cessful and respected professor, an expert in everything he works on. A vast portion of the work presented in this thesis was born out of endless heated arguments between Kevin and myself; arguments that took place over beers, on ski runs, in hotels, and. of course, during many a late night in our office — first in person, and, later, over the vì phone. These could be long and frustrating — sometimes due to our stubbornness and sometimes because initially we did not really understand what we were talking about; all were very fruitful in the end.
Kevin taught me a great deal about research, presentation of ideas, the workings of the academic world, attention to minute details such as colors and fonts, as well as ways to fix those, the list goes on. Nevertheless, it is our endless late-night debates from which you could see Understanding being born that I'll miss the most. The work culminating in this thesis started when Yoav sent Kevin and myself to Cornell, where we met with Carla Gomes, Bart Selman, Henry Kautz, Felip Mana, and Ioannis Vetsikas. There Carla and Bart told us about phase transitions and heavy-tailed phenomena, and Kevin talked about combinatorial auctions.
I learned about both. This trip inspired us to try to figure out a way to get similar results for the winner determination problem, even after it became quite clear that existing approaches were infeasible. I am very grateful to Yoav for sending me on this trip when it wasn’t at all obvious what I would learn, and it was quite probable that I wouldn’t contribute much. That trip defined my whole research path.
I'd like to express special thank you to Carla Gomes and Bart Selman. who have been very supportive over these years. They followed our work with interest ever since the first visit to Cornell, always happy to provide invaluable advice and to teach us about all the things we didn’t understand. Needless to say, a lot of work contained here has been published in various forms and places.
I was lucky to have a great number of co-authors who contributed to these publications. Chapters 2 and 3 are based mostly on ideas developed with Kevin Leyton-Brown. They are based on material that previously appeared in [Leyton- Brown et al. 2002; Leyton-Brown et al.
2003b; Leyton-Brown et al. 2003a]) with some ideas taken from [Nudelman et al. Galen Andrew and Jim McFadden contributed greatly to [Leyton-Brown et al. 2003b] and [Leyton-Brown et al.
Ramon Béjar provided original code for calculating the clustering coefficient. Chapter 4 is based on [Nudelman et al. 2004a], joint work with Kevin Leyton- Brown, Alex Devkar, Holger Hoos, and Yoav Shoham. I'd like to acknowledge very helpful assistance from Nando de Freitas, and our indebtedness to the authors of the algorithms in the SATzilla portfolio.
This work also benefited from helpful comments by anonymous reviewers. Chapter 6 is based on [Nudelman et al. 2004b], which is joint work with Kevin Leyton-Brown, Jenn Wortman, and Yoav Shoham. Id especially like to acknowledge Jenn’s contribution to this project.
She single-handedly filtered vast amounts of liter- ature, distilling only the things that were worth looking at. She is also responsible for a major fraction of GAMUT’s code. I’d also like to thank Bob Wilson for identifying many useful references and for sharing his insights into the space of games, and Rob Powers for providing us with implementations of multiagent learning algorithms. Finally, Chapter 7 is based on [Porter et al.
to appear]!, joint work with Ryan Porter and Yoav Shoham. Td like to particularly thank Ryan, who, besides being a co-author, was also an officemate and a friend. From Ryan I learned a lot about American way of thinking; he was also my only source for baseball and football news. After a couple of years, he was relocated to a different office.
Even though it was only next door, in practice that meant many fewer non-lunchtime conversations — something that I still occasionally miss. Ryan undertook the bulk of implementation work for this project while I was tied up with GAMUT, which was integral to our experimental evaluation. Even when we weren't working on a project together, Ryan was always there ready to bounce ideas back and forth. He has had definite influence on all work presented in this thesis.
Returning to Chapter 7, I’d like to once again thank Bob Wilson, and Christian Shelton for many useful comments and discussions. One definite advantage of being at Stanford was constant interaction with a lot of very strong people. I'd like to thank all past and present members and visitors of Yoav's Multiagent group; all of my work benefited from your discussions, comments, and suggestions. Partly due to spacial proximity, and, partly, to aligned interests, I also constantly interacted with members of DAGS—Daphne Koller’s research group.
They were always an invaluable resource whenever I needed to learn something on pretty much any topic in AI. I'd also like to mention Bob McGrew, Qi Sun, and Sam Ieong (another valued officemate), my co-authors on [Ieong et al. 2005], which is not part of this thesis. It was very refreshing to be involved in something so 1A slightly shorter version has been published as [Porter et al.
vill non-experimental. I was very lucky to count two other members in the department, Michael Brudno and Daniel Faria, among my close friends. Together, we were able to navigate through the CS program, and celebrate all milestones. They were always there whenever I needed to bounce new ideas off somebody.
They also exposed me to a lot of inter- esting research in areas quite distant from AI: computational biology and wireless networking. More importantly, sometimes they allowed me to forget about work. I would also like to thank members of my Ph. committees, without whom neither my defense, nor this thesis would have been possible: Andrew Ng, together with Yoav Shoham and Bart Selman on the reading committee, and Serafim Batzouglu and Yossi Feinberg on orals.
The work in this thesis represents enormous investment of computational time. I have come to regard the clusters that I used to run these experiments as essentially my co-authors; they certainly seem to have different moods, personalities, their personal ups and downs. Initial experiments were run on the unforgettable “zippies” in Cornell, kindly provided to us by Carla and Bart. Eventually, we built our own cluster — the “Nashes”.
I’m extremely grateful to our system administrator, Miles Davis, for keeping Nashes healthy from their birth. His initial reaction, when we approached him about building the cluster, was: “It’s gonna be so cool!”.