Ron Lavi

Associate Professor

Faculty of Industrial Engineering and Management

Technion --

E-mail: ronlavi@ie.technion.ac.il

Office:

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.

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:

- A short article (in Hebrew) that explains what Game Theory is, and what is it good for.
- A nice presentation (session IP4) on the general area of Algorithmic Game Theory that surveys many of the research questions that interest me.
- A nice blog on Algorithmic Game Theory, also a good place to find many relevant links.

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.

Auction
Theory (96573)

Auction Theory
for MBA (98753)

Introduction to
Financial Management (94564)

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.

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)

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.

An Optimal
Lower Bound for Anonymous Scheduling

By Itai Ashlagi, Shahar Dobzinski, and Ron Lavi

*Mathematics of Operations Research*
, 37(2): 244-258, 2012.

Multi-unit
Auctions with Budget Limits

By Shahar Dobzinski, Ron Lavi, and Noam Nisan

*Games
and Economic Behavior*, 74, pp. 486–503, 2012.

A
Note on the Incompatibility of Strategy-proofness and Pareto-optimality in
Quasi-linear Settings with Public Budgets

By Ron Lavi and

*Economics
Letters* 115, pp. 100-103, 2012

Truthful and
Near-optimal Mechanism Design via Linear Programming

By Ron Lavi and Chaitanya Swamy

*Journal of the ACM*,
58(6), 2011

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

PowerPoint Presentation

Two Simplified Proofs for Roberts' Theorem

By Ron Lavi, Ahuva Mu'alem, and Noam Nisan

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

PowerPoint Presentation

Weak Monotonicity characterizes deterministic dominant strategy implementation

By S. Bikhchandani, S. Chatterji, R. Lavi, A. Mu'alem, N. Nisan, and A. Sen

See also the supplementary material for this paper.

Competitive Analysis of Incentive Compatible On-Line Auctions

By Ron Lavi and Noam Nisan

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

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

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

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

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

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

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.