Ron Lavi



http://ie.technion.ac.il/%7Eronlavi/pic.bmp

Associate Professor
Faculty of Industrial Engineering and Management
Technion -- Israel Institute of Technology
Israel

E-mail:  ronlavi@ie.technion.ac.il
Office: Bloomfield 302
Phone: 04-8294410

 

I am currently visiting UC Berkeley until summer 2015, hosted by Christos Papadimitriou.
In the academic year 2012/13 I was on sabbatical, visiting Yahoo! Labs.

 

Research Interests

I'm working on subjects on the border of Computer Science, Game Theory, and Economics. This broad research area is usually called Algorithmic Game Theory.

I study models that integrate computational and algorithmic theory with game theory and microeconomic theory. Some representative questions that my research explores are: (i) What are the limits of ex-post implementability in private value settings. (ii) What other solution concepts can we successfully use  in a distribution free analysis? (iii) What types of dynamic and detail free mechanisms can we construct? The motivation for these questions arise from Auction Theory, a research area with theoretical as well as practical relevance. Here is a more detailed research statement.

Few relevant links:

Short Bibliography

I have a PhD in Computer Science from the Hebrew University of Jerusalem.
After graduating, I did a post-doc at Caltech's Social and Information Sciences Laboratory (SISL). I joined the Technion in August 2006. Here is a full CV, and, on the informal side, some pictures.

Courses

Auction Theory (96573)
Auction Theory for MBA (98753)
Introduction to Financial Management (94564)

Students

Marina May (M.Sc. 2011, "The Incompatibility of Strategy-proofness and Pareto-optimality in Quasi-linear Settings with Public Budget Constraints")

Liri Finkelstein (M.Sc. 2011, "Two Algorithms for the Matroid Secretary Problem ")

Alex Bogautov (M.Sc. 2011, "Iterated Deletion of Dominated Strategies in Discrete Position Auctions")

Ira Shein (M.Sc. 2010, "Bayesian Analysis of Sequential Auctions Under Future Uncertainties")

Students that are interested in doing research on the above mentioned subjects are welcomed to apply.

Especially talented students may get extra funding on top of Technion's funding.

 

Working Papers

Competition among Asymmetric Sellers with Fixed Supply
By Uriel Feige, Ron Lavi, and Moshe Tennenholtz

PowerPoint Presentation
(abstract in EC'13)


Sequential Voting with Externalities: Herding in Social Networks
By Noga Alon, Moshe Babaioff, Ron Karidi, Ron Lavi, and Moshe Tennenholtz
(abstract in EC'12)


Ascending Auctions and Walrasian Equilibrium
By Oren Ben-Zwi, Ron Lavi, Ilan Newman


Composition Games for Distributed Systems: the EU Grant games
By Shay Kutten, Ron Lavi, and Amitabh Trehan

(Brief announcement in DISC'11 and NetEcon'12, extended abstract in AAAI'13)

 

Job Security, Stability and Production Efficiency
By Hu Fu, Robert D. Kleinberg, Ron Lavi, and Rann Smorodinsky
Presentation
(older version from EC'12 is here, and a slides for that older version)

Efficiency Levels in Sequential Auctions with Dynamic Arrivals
By Ron Lavi and Ella Segev
PowerPoint Presentation
(abstract of this paper plus new results with O. Compte in EC'12. See the full version here)

Journal Publications

Side-Communication Yields Efficiency of Ascending Auctions: The Two-Items Case
By Ron Lavi and Sigal Oren
Games and Economic Behavior, 76(2): 439-456, 2012.

PowerPoint Presentation

An Optimal Lower Bound for Anonymous Scheduling
By Itai Ashlagi, Shahar Dobzinski, and Ron Lavi
Mathematics of Operations Research , 37(2): 244-258, 2012.

PowerPoint Presentation

Multi-unit Auctions with Budget Limits
By Shahar Dobzinski, Ron Lavi, and Noam Nisan

Games and Economic Behavior, 74, pp. 486503, 2012.

A Note on the Incompatibility of Strategy-proofness and Pareto-optimality in Quasi-linear Settings with Public Budgets
By Ron Lavi and Marina May

Economics Letters 115, pp. 100-103, 2012

PowerPoint Presentation

 

Truthful and Near-optimal Mechanism Design via Linear Programming
By Ron Lavi and Chaitanya Swamy

Journal of the ACM, 58(6), 2011

PowerPoint Presentation

Position Auctions with Budgets: Existence and Uniqueness
By Itai Ashlagi, Mark Braverman, Avinatan Hassidim, Ron Lavi, and Moshe Tennenholtz
The B.E. Journal of Theoretical Economics (Advances), 10(1), Article 20, 2010
PowerPoint Presentation

Truthful Mechanism Design for Multi-Dimensional Scheduling via Cycle Monotonicity
By Ron Lavi and Chaitanya Swamy
Games and Economic Behavior, 67(1), pp. 99 -- 124, 2009.
PowerPoint Presentation

Two Simplified Proofs for Roberts' Theorem
By Ron Lavi, Ahuva Mu'alem, and Noam Nisan
Social Choice and Welfare, 32, pp. 407 -- 423, 2009.
A clarification to the proof of Claim 6, kindly suggested by Alexey Kushnir and Shuo Liu.

Single Value Combinatorial Auctions and Implementation in Undominated Strategies
By Moshe Babaioff, Ron Lavi, and Elan Pavlov
Journal of the ACM, 56(1), pp. 4:1 -- 4:32, 2009.
PowerPoint Presentation

Weak Monotonicity characterizes deterministic dominant strategy implementation
By S. Bikhchandani, S. Chatterji, R. Lavi, A. Mu'alem, N. Nisan, and A. Sen
Econometrica, 74(4), pp. 1109 -- 1132, 2006.
See also the supplementary material for this paper.

Competitive Analysis of Incentive Compatible On-Line Auctions
By Ron Lavi and Noam Nisan
Theoretical Computer Science 310(1), pp. 159-180, 2004.
PowerPoint Presentation

Book Chapters and Review Papers

Mechanism Design
By Ron Lavi
Encyclopedia of Complexity and System Science, Springer, 2009

Algorithmic Mechanism Design
By Ron Lavi
Encyclopedia of Algorithms, Springer, 2008

Computationally-Efficient Approximation Mechanisms
By Ron Lavi
Algorithmic Game Theory, Cambridge University Press, 2007

Searching for the Possibility Impossibility Border of Truthful Mechanism Design
By Ron Lavi
ACM SIGecom Exchanges 7(1), 2007

 

Publications in Refereed Conferences

 

Competition among Asymmetric Sellers with Fixed Supply (abstract only; full version here)
By Uriel Feige, Ron Lavi, and Moshe Tennenholtz
Proceedings of the 14th ACM Conference on Electronic Commerce (EC'13)

 

Composition Games for Distributed Systems: the EU Grant games
By Shay Kutten, Ron Lavi, and Amitabh Trehan

Proceedings of the 27th National Conference on Artificial Intelligence (AAAI'13), 2013

 

Sequential Voting with Externalities: Herding in Social Networks (abstract only; full version here)

By Noga Alon, Moshe Babaioff, Ron Karidi, Ron Lavi, and Moshe Tennenholtz
Proceedings of the 13th ACM Conference on Electronic Commerce (EC'12)

 

Conditional Equilibrium Outcomes via Ascending Price Processes (abstract only; full version here)
By Hu Fu, Robert D. Kleinberg, and Ron Lavi

Proceedings of the 13th ACM Conference on Electronic Commerce (EC'12)

 

Efficiency Levels in Sequential Auctions with Dynamic Arrivals (abstract only; full version here)
By Olivier Compte, Ron Lavi, and Ella Segev

Proceedings of the 13th ACM Conference on Electronic Commerce (EC'12)

A Note on the Incompatibility of Strategy-proofness and Pareto-optimality in Quasi-linear Settings with Public Budgets
By Ron Lavi and Marina May

Proceedings of the 7th Workshop on Internet and Network Economics (WINE), 2011

 

Composition Games for Distributed Systems: the EU Grant games (brief announcement)
By Shay Kutten, Ron Lavi and Amitabh Trehan

Proceedings of the 25th International Symposium on Distributed Computing (DISC), 2011

 

Side-Communication Yields Efficiency of Ascending Auctions: The Two-Items Case
By Ron Lavi and Sigal Oren
Proceedings of the Second Conference on Auctions, Market Mechanisms and Their Applications (AMMA), 2011

 

An Optimal Lower Bound for Anonymous Scheduling
By Itai Ashlagi, Shahar Dobzinski, and Ron Lavi
Proceedings of the 10th ACM Conference on Electronic Commerce (EC'09), 2009

Winner of an Outstanding paper award

Multi-unit Auctions with Budget Limits
By Shahar Dobzinski, Ron Lavi, and Noam Nisan
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS'08), 2008

Truthful Mechanism Design for Multi-Dimensional Scheduling via Cycle Monotonicity
By Ron Lavi and Chaitanya Swamy
Proceedings of the 8th ACM Conference on Electronic Commerce (EC'07), 2007

Impersonation-Based Mechanisms
By Moshe Babaioff, Ron Lavi, and Elan Pavlov
Proceedings of the 21st National Conference on Artificial Intelligence (AAAI'06), 2006

Single Value Combinatorial Auctions and Implementation in Undominated Strategies
By Moshe Babaioff, Ron Lavi, and Elan Pavlov
Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA'06), 2006

Truthful and Near-optimal Mechanism Design via Linear Programming
By Ron Lavi and Chaitanya Swamy
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005
PowerPoint Presentation

Mechanism Design for Single-Value Domains
By Moshe Babaioff, Ron Lavi, and Elan Pavlov
Proceedings of the 20th National Conference on Artificial Intelligence (AAAI'05), 2005

Online Ascending Auctions for Gradually Expiring Items
By Ron Lavi and Noam Nisan
Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA'05), 2005
PowerPoint Presentation  and  a more detailed version of the paper.

Online competitive algorithms for maximizing weighted throughput of unit jobs
By Y. Bartal, F.Y.L. Chin, M. Chrobak, S.P.Y. Fung, W. Jawor, R. Lavi, J. Sgall, T. Tichy
Proceedings of the 21st Symposium on Theoretical Aspects of Computer Science (STACS'04), 2004

Towards a Characterization of Truthful Combinatorial Auctions
By Ron Lavi, Ahuva Mu'alem, and Noam Nisan
Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003
PowerPoint Presentation  and  a more detailed version of the paper.

Competitive Analysis of Incentive Compatible On-Line Auctions
By Ron Lavi and Noam Nisan
Proceedings of the 2nd ACM Conference on Electronic Commerce (EC'00), 2000

The Home Model and Competitive Algorithms for Load Balancing in a Computing Cluster
By Ron Lavi and Amnon Barak
Proceedings of the 21st International Conference on Distributed Computing Systems (ICDCS'01), 2001

Improving the PVM Daemon Network Performance by Direct Network Access
By Ron Lavi and Amnon Barak.
Proceedings of the 5th EuroPVM/MPI'98, LNCS 1497, pp. 44-51, Springer-Verlag, 1998.

 

Theses

Ph.D. thesis: Auction Theory in Computational Settings , August 2004.
M.Sc. thesis: The Home Model for Load Balancing in a Computing Cluster , October 1999.