Ariel Procaccia

I am an Associate Professor in the Computer Science Department at Carnegie Mellon University. I am also affiliated with the Machine Learning Department, and a member of the theory group and the ACO program.

I usually work on problems at the interface of computer science and economics. I write papers, teach courses, serve on various editorial boards and program committees, and, best of all, advise wonderful students and postdocs.

Applications

spliddit4
rovovote2

Talks

comsoc_video
extreme_video

Opinions

wp3
wired_alt

News

My former PhD student Nika Haghtalab (co-advised with Avrim Blum) won the SCS Distinguished Dissertation Award, given annually for the best PhD thesis in the School of Computer Science. Her thesis is entitled “Foundation of Machine Learning, by the People, for the People.”

Congratulations to Nika Haghtalab for accepting a faculty position at Cornell University! She will join Cornell as Assistant Professor of Computer Science in fall 2019. Nika has been a PhD student in the Computer Science Department since 2013, and is co-advised by Avrim Blum and myself.

Our paper “The Provable Virtue of Laziness in Motion Planning” has been selected to receive the best paper award at the 28th International Conference on Automated Planning and Scheduling, out of 209 submissions. The paper is joint work with Nika Haghtalab (CMU), Simon Mackenzie (CMU), Oren Salzman (CMU), and Sidd Srinivasa (UW).

Abstract: The Lazy Shortest Path (LazySP) class consists of motion-planning algorithms that only evaluate edges along shortest paths between the source and target. These algorithms were designed to minimize the number of edge evaluations in settings where edge evaluation dominates the running time of the algorithm; but how close to optimal are LazySP algorithms in terms of this objective? Our main result is an analytical upper bound, in a probabilistic model, on the number of edge evaluations required by LazySP algorithms; a matching lower bound shows that these algorithms are asymptotically optimal in the worst case.

I am honored to have been named a Guggenheim fellow, together with 172 other scholars, artists, and scientists.

An op-ed that I wrote with Wes Pegden was published by the Washington Post. We discuss our cake-cutting-inspired redistricting protocol, which we presented and analyzed in our paper with Dingli Yu.

 

 

In a new paper with Wes Pegden and Dingli Yu, we propose a political redistricting protocol with provable guarantees. This work was covered by the Pittsburgh Post-GazetteNew ScientistAxios, and the Wisconsin Public Radio.

Update: Wes and I gave a live interview on WDET’s Detroit Today with Stephen Henderson. It’s available here, from 24:51 until 35:25.

Update: New story in Slate.

Our new paper, A Voting-Based System for Ethical Decision Making, is the topic of a nice story by Jon Christian in The Outline (which led to an especially lively discussion on Reddit). Pradeep Ravikumar also gave a great interview about this project on the radio show AirTalk.

Update: See also the Axios story and the Bloomberg opinion piece.

New Scientist published a story about our EC’16 rent division paper, which will also be presented at the IJCAI’17 Sister Conference Track. (The story was subsequently picked up by the UK tabloid Metro.)

New Scientist just published a nice story about our IJCAI’17 paper with the catchy title “Why You Should Charge Your Friends for Borrowing Your Stuff” (short answer: because in a game where non-rivalrous goods are bought and shared on a network, equilibria are more efficient, in theory and experiments, when access costs are imposed).

Here are some other random topics I’ve weighed in on recently (not covered by other news):

* Aziz and Mackenzie’s breakthrough result on bounded envy-free cake cutting, in the Sydney Morning Herald and Quanta Magazine.

* AI and online dating, in the Boston Globe.

 

Congratulations to Swaprava Nath, who will join the Indian Institute of Technology, Kanpur, as Assistant Professor in July. I’ve hosted Swaprava as a postdoc since 2015; he is supported by the Fulbright-Nehru postdoctoral fellowship.

My former PhD student Nisarg Shah won the Victor Lesser Distinguished Dissertation Award, given annually for the best thesis in the area of autonomous agents and multiagent systems. His thesis is entitled “Optimal Social Decision Making.” He will present his thesis research in a plenary talk at AAMAS-17 in Brazil.

An opinion piece that I wrote was published today in Wired. It’s about computational social choice (although I don’t call it that) and a bit of politics.

I was interviewed by Tim Grant from the Pittsburgh Post-Gazette about RoboVote and voting more generally. Worth checking out, if only for the bizarre portrait photo with the hovering phones!

RoboVote (http://robovote.org), a not-for-profit voting website that provides optimization-driven methods for making collective decisions, has launched today! Check out RoboVote’s about page for (somewhat AI-centric) information about the website, its algorithms, and the theory underlying them, as well as info about the amazing team.

Press coverage (newest to oldest): Wired, Pittsburgh Post-Gazette, ExtremeTech, Daily Mail, Digital Trends, Marketplace, CMU homepage

Our paper “Which Is the Fairest (Rent Division) of Them All” has been selected to receive the best paper award at the 17th ACM Conference on Economics and Computation, out of 242 submissions. The paper is joint work with Kobi Gal and Moshik Mash of Ben Gurion University, and my postdoc Yair Zick.

Abstract: What is a fair way to assign rooms to several housemates, and divide the rent between them? This is not just a theoretical question: many people have used the Spliddit website to obtain envy-free solutions to rent division instances. But envy freeness, in and of itself, is insufficient to guarantee outcomes that people view as intuitive and acceptable. We therefore focus on solutions that optimize a criterion of social justice, subject to the envy freeness constraint, in order to pinpoint the “fairest” solutions. We develop a general algorithmic framework that enables the computation of such solutions in polynomial time. We then study the relations between natural optimization objectives, and identify the maximin solution, which maximizes the minimum utility subject to envy freeness, as the most attractive. We demonstrate, in theory and using experiments on real data from Spliddit, that the maximin solution gives rise to significant gains in terms of our optimization objectives. Finally, a user study with Spliddit users as subjects demonstrates that people find the maximin solution to be significantly fairer than arbitrary envy-free solutions; this user study is unprecedented in that it asks people about their real-world rent division instances. Based on these results, the maximin solution has been deployed on Spliddit since April 2015.

Congratulations to Nisarg Shah, who has accepted a tenure-track faculty position in the Department of Computer Science at the University of Toronto! He will join U of T in fall 2017, after spending a year as a postdoc at Harvard’s Center for Research in Computation and Society. I have had the privilege of advising Nisarg since he joined our PhD program in fall 2011 (which is the same time I myself joined CMU); he is defending on June 28.

The Handbook of Computational Social Choice, which I have co-edited together with Felix Brandt, Vince Conitzer, Ulle Endriss, and Jerome Lang, has been officially published.

Description: The rapidly growing field of computational social choice, at the intersection of computer science and economics, deals with the computational aspects of collective decision making. This handbook, written by thirty-six prominent members of the computational social choice community, covers the field comprehensively. Chapters devoted to each of the field’s major themes offer detailed introductions. Topics include voting theory (such as the computational complexity of winner determination and manipulation in elections), fair allocation (such as algorithms for dividing divisible and indivisible goods), coalition formation (such as matching and hedonic games), and many more. Graduate students, researchers, and professionals in computer science, economics, mathematics, political science, and philosophy will benefit from this accessible and self-contained book.

A PDF of the book is freely available online. To open the document, please enter the password cam1CSC (strangely enough, this password can be disseminated legally, so you are encouraged to shout it from the rooftops). The link is here:

http://www.cambridge.org/download_file/898428

Alternatively, the book can be purchased through the Cambridge University Press website (http://www.cambridge.org/9781107060432), Amazon, and other retailers.

Congratulations to Yair Zick for accepting a faculty position at the National University of Singapore! He will join NUS as Assistant Professor of Computer Science in the summer. Yair has been a postdoc at CMU since April 2014, jointly hosted by Anupam Datta and me. Before that he completed his PhD at Nanyang Technological University, Singapore, where he worked with Edith Elkind.

Congratulations to Nika Haghtalab for winning a 2016-2018 Microsoft Research PhD fellowship. Nika is co-advised by Avrim Blum and me.

Together with Yonathan Aumann, Steven Brams, and  Jérôme Lang, I am organizing a Dagstuhl workshop on Fair Division. The workshop will take place on June 6-10, 2016.

New Scientist published a “one minute interview” with me about AI and fair division.

I received the IJCAI Computers and Thought Award at IJCAI’15 in Buenos Aires. A narrated video of my presentation at the conference is now available online.

A new version of Spliddit, featuring two new apps and improvements to the old ones, has officially launched!
Press coverage (newest to oldest): Metro, New Scientist #2, Quanta Magazine, The New York Times #2, New Scientist #1, Pittsburgh Magazine, GeekWire, NSF podcast, Fast Company, Pittsburgh Post-Gazette, Lifehacker, Slashdot, Gizmodo, Nautilus Magazine, The New York Times #1.

Congratulations to Nika Haghtalab for winning a 2015-2016 IBM PhD fellowship, with a statement entitled “Learning Theory for Societal Good”. Nika is co-advised by Avrim Blum and me.

I was named a Sloan Research Fellow, together with 125 other young researchers in chemistry, computer science, economics, mathematics, computational and evolutionary molecular biology, neuroscience, ocean sciences, and physics.

Congratulations to Junxing Wang for winning the best student paper award at EC-14, for our joint paper “Fair Enough: Guaranteeing Approximate Maximin Shares”.

The New York Times published a story about the rent division problem — they even implemented the algorithm of Francis Su, and illustrated Sperner’s lemma! The story includes a paragraph about Spliddit, and a rather inarticulate quote from me.

Congratulations to Nisarg Shah for winning a 2014-2015 Facebook PhD fellowship, with a statement entitled “Economic Foundations of Social Computing”.  There are 11 winners overall, 3 of whom are from CMU!

Please check back later for more fascinating news!

Contact Information

  •    arielpro@cs.cmu.edu
  •   
  •    Computer Science Dept.
  •    Carnegie Mellon University
  •    Pittsburgh, PA 15213
  •   
  •    Gates-Hillman Center
  •    Office #7002