Moshe Babaioff


		Researcher
		Microsoft Research, Silicon Valley
		1065 La Avenida
		Mountain View, CA 94043
		U.S.A.
		Email:
		Tel: +1 650 693 3367

I am a Researcher at Microsoft Research, Silicon Valley (SVC). Till July 2007 I was a post-doc at the University of California at Berkeley, working with Prof. John Chuang. I was a graduate student at the School of Computer Science and Engineering at the Hebrew University, Jerusalem, Israel, my advisor was Prof. Noam Nisan. My PhD thesis was on "Strategic Aspects of Computational Markets". I have a M.Sc. in Computer Science and a B.Sc. in Computer Science and Mathematics, both from the Hebrew University.

Research Interests:

My research interests are in subjects on the border of Computer Science Theory, Game Theory, and Microeconomic Theory. In particular, I am interested in the theoretical foundations of Electronic Commerce. I work on combining techniques from the fields of Economics and Computer Science to create computationally feasible, distributed trade mechanisms.

Academic service:

Program Committee Fourth Workshop on Ad Auctions (SSA workshop 2008)
Program Committee ACM conference on Electronic Commerce (ACM EC 2008)
Program Committee Twenty-Third AAAI Conference on Artificial Intelligence (AAAI 2008)

I am co-organizing The Bay Algorithmic Game Theory Symposium (BAGT).
BAGT 1: Microsoft Research (Mountain View, CA) on February 17, 2006.
BAGT 2: U.C. Berkeley on September 29, 2006.
BAGT 3: Stanford University on April 20, 2007.
BAGT 4: Yahoo! on October 12, 2007.
BAGT 5: Google on April 11, 2008.

Research:

Book Chapters and Surveys:

Encyclopedia Entry:Truthful Mechanisms for One-Parameter Agents.
Moshe Babaioff.
Encyclopedia of Algorithms, June 2008.
Online Auctions and Generalized Secretary Problems.
Moshe Babaioff, Nicole Immorlica, David Kempe and Robert Kleinberg.
SIGecom Exchanges 7(2), June 2008. (pdf)
Incentives in Peer-to-Peer Systems.
Moshe Babaioff, John Chuang and Michal Feldman
Chapter 23 in the book Algorithmic Game Theory.
Editors: Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani.
Cambridge University Press; 2007.
Incentive-Compatible Supply Chain Auctions.
Moshe Babaioff and William E. Walsh
Chapter 12 in the book Multiagent-Based Supply Chain Management.
Editors: B. Chaib-draa and J. P. Muller.
Springer; August 2006.

Working Papers:

Free-Riding and Free-Labor in Combinatorial Agency.
Moshe Babaioff, Michal Feldman and Noam Nisan.

Conference Papers:

Secretary Problems: Weights and Discounts.
Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, and Kunal Talwar.
To appear at the ACM-SIAM Symposium on Discrete Algorithms, 2009 (SODA'09).
Selling Banner Ads: Online Algorithms with Buyback.
Moshe Babaioff, Jason Hartline and Robert Kleinberg.
The Fourth Workshop on Ad Auctions (SSA workshop 2008) (pdf).
Informational Overhead of Incentive Compatibility.
Moshe Babaioff, Liad Blumrosen , Moni Naor and Michael Schapira.
The 9th ACM Conference on Electronic Commerce 2008 (EC'08): 88-97. (pdf)
On the Approximability of Combinatorial Exchange Problems.
Moshe Babaioff, Patrick Briest and Piotr Krysta.
First International Symposium on Algorithmic Game Theory, 2008(SAGT '08): 83-94. (Full version pdf)
A Knapsack Secretary Problem with Applications.
Moshe Babaioff, Nicole Immorlica, David Kempe and Robert Kleinberg.
10-th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems 2007(APPROX'07): 16-28. (pdf, bibTex)
Congestion Games with Malicious Players.
Moshe Babaioff, Robert Kleinberg and Christos H. Papadimitriou.
Proceedings of the 8-th ACM Conference on Electronic Commerce 2007 (EC'07): 103-112. (pdf, bibTex)
On the Optimality and Interconnection of Valiant Load-Balancing Networks.
Moshe Babaioff and John Chuang.
IEEE Conference on Computer Communications 2007 (IEEE INFOCOM'07): 80-88. (conference version: pdf, bibTex)
Matroids, Secretary Problems, and Online Mechanisms.
Moshe Babaioff, Nicole Immorlica and Robert Kleinberg.
ACM-SIAM Symposium on Discrete Algorithms, 2007 (SODA'07): 434-443. (conference version: ps, pdf, bibTex)
Also presented (by R. Kleinberg) in The Second Bertinoro Workshop on Algorithmic GAme ThEory (AGATE 2006) (Bertinoro, Italy. July 2-6, 2006)
Mixed Strategies in Combinatorial Agency.
Moshe Babaioff, Michal Feldman and Noam Nisan.
2nd international Workshop on Internet & Network Economics 2006 (WINE'06). LNCS Vol. 4286, pages 353-364. (conference version: pdf, bibTex, full version: pdf)
Also presented in The Second Bertinoro Workshop on Algorithmic GAme ThEory (AGATE 2006) (Bertinoro, Italy. July 2-6, 2006)
Impersonation-Based Mechanisms.
Moshe Babaioff, Ron Lavi and Elan Pavlov.
21st National Conference on Artificial Intelligence 2006 (AAAI'06). (pdf, bibTex)
Combinatorial Agency.
Moshe Babaioff, Michal Feldman and Noam Nisan.
Proceedings of the 7th ACM Conference on Electronic Commerce 2006 (EC'06): 18-28. (conference version: ps, pdf, bibTex, full version: ps, pdf, extended journal version (draft): pdf)
Presented in The 1st Bay Algorithmic Game Theory Symposium (BAGT) (Microsoft Research, Mountain View, California. February 17, 2006).
Single-Value Combinatorial Auctions and Implementation in Undominated Strategies.
Moshe Babaioff, Ron Lavi and Elan Pavlov.
ACM-SIAM Symposium on Discrete Algorithms, 2006 (SODA'06): 1054-1063. (ps, pdf, bibTex)
Presented in Dagstuhl-Seminar on "Computing and Markets" (Dagstuhl, Germany. January 3-7, 2005), and in
DIMACS workshop on "Large Scale Games", (Northwestern University. April 17 - 19, 2005).
Mechanism Design for Single-Value Domains.
Moshe Babaioff, Ron Lavi and Elan Pavlov.
20th National Conference on Artificial Intelligence 2005 (AAAI'05): 241-247.(full version ps, pdf, bibTex)
Presented in INFORMS Annual Meeting, San Francisco, CA. November 2005.
Computationally Feasible Auctions for Convex Bundles.
Moshe Babaioff and Liad Blumrosen.
7th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX+RANDOM) 2004.
LNCS Vol. 3122, Pages 27-38 (full version ps, pdf, bibTex)
Mechanisms for a Spatially Distributed Market.
Moshe Babaioff, Noam Nisan and Elan Pavlov.
Proceedings of the Fifth ACM Conference on Electronic Commerce 2004 (EC'04): 9-20. (conference version: ps, full version: ps, pdf, bibTex)
Incentive-Compatible, Budget-Balanced, yet Highly Efficient Auctions for Supply Chain Formation.
Moshe Babaioff and William E. Walsh
Proceedings of the Fourth ACM Conference on Electronic Commerce 2003 (EC'03): 64-75. (ps, pdf, bibTex)
Concurrent Auctions Across the Supply Chain.
Moshe Babaioff and Noam Nisan.
Proceedings of the Third ACM Conference on Electronic Commerce 2001 (EC'01): 1-10. (ps, pdf, bibTex)
Presented in Dagstuhl-Seminar on "Electronic Market Design" (Dagstuhl, Germany. June 10-14, 2002)

Journal Papers:

Mechanisms for a Spatially Distributed Market.
Moshe Babaioff, Noam Nisan and Elan Pavlov.
To Appear in Games and Economic Behavior (GEB), 2008. (pdf)
Congestion Games with Malicious Players.
Moshe Babaioff, Robert Kleinberg and Christos H. Papadimitriou.
To Appear in Games and Economic Behavior (GEB), 2008. (pdf)
Computationally Feasible Auctions for Convex Bundles.
Moshe Babaioff and Liad Blumrosen.
Games and Economic Behavior (GEB), Volume 63 Issue 2, pages 588-620, July 2008. (a draft: ps, pdf)
Incentive-Compatible, Budget-Balanced, yet Highly Efficient Auctions for Supply Chain Formation.
Moshe Babaioff and William E. Walsh
Decision Support Systems (DSS), Volume 39, Issue 1, pages 123-149, 2005. (ps, pdf, bibTex)
Concurrent Auctions Across the Supply Chain.
Moshe Babaioff and Noam Nisan.
Journal of Artificial Intelligence Research (JAIR), Volume 21, pages 595-629, 2004. (ps, pdf, bibTex)

Thesis:

Ph.D. : Strategic Aspects of Computational Markets, Hebrew University 2005. (ps, pdf)

M.Sc. : Concurrent Auctions Across the Supply Chain, Hebrew University 2001. (ps, pdf)