Computing Socially-Efficient Cake Divisions
In the classic “cake cutting” setting, a continuous, heterogeneous cake is to be divided between a number of players, each of which having possibly-different valuations for different parts of the cake. Classically, this setting was used for studying questions related to fair divisions, e.g. can we guarantee each player a piece of value 
More recently, some works also started considering social welfare issues in cake cutting. The first such work (at least to the best of my knowledge) was by Caragiannis et al., and studied the trade-off between fairness and social efficiency (or “the Price of Fairness”). Since then, a few more works have considered some welfare aspects in cake cutting problems. However, one fundamental question was not formally addressed: Given a social welfare function and the preferences of the players, how can one compute a socially-efficient division of the cake?
The question above is the subject of a new paper by Yonatan Aumann, Avinatan Hassidim and myself, which was submitted to EC. As in my previous works, we concentrate mainly on divisions in which each player needs to get a single contiguous piece from the cake. For such divisions, we show that while utilitarian and egalitarian optima do exist (whenever the preferences of the players can be described by non-atomic measures), deciding whether some level of welfare can be achieved is (strongly) NP-hard; this holds even if the players valuations are very simple (piecewise uniform) and are given explicitly to the algorithm. For utilitarian welfare, however, we are able to show a constant factor approximation algorithm, which also works in the more general oracle input model. We also give fixed-parameter tractable approximation schemes (w.r.t. the number of players) that can approximate the utilitarian or egalitarian welfare to any factor, in time that is exponential in the number of players
A Facelift for the (Formerly) AGT/Econ Blog
As you may have noticed, Noam Nisan’s blog has disappeared from the (short) list of links on the right column. Actually, it wasn’t me; the blog has gotten a facelift for the new year, and is now a group blog, with five very respected writers: Bobby Kleinberg, Elias Koutsoupias, Noam Nisan, Ariel Procaccia and Tim Roughgarden. After changing the name (following a discussion by Ariel, and finally choosing “Turing’s Invisible Hand”, as suggested by Felix Fischer) the first “real” post was published a few days ago, bringing the impressions of Bobby Kleinberg from ITCS. The new looks and set of writers seem very promising, so if you haven’t been following that blog so far, check it out.
A Talk at the HUJI EconCS Seminar
Next month (December 18) I am going to give a talk at the Computation and Economics Seminar at the Hebrew University of Jerusalem. While the exact title and abstract are still not written (I hope to update them in the next few days), the talk is going to be about cake cutting with connected pieces, and in particular the question of economic efficiency, and the relation between this and fairness. I plan to present some results about the Price of Fairness of such divisions and the Dumping Paradox, as well as some newer results concerning computation of socially-efficient divisions.
Impressions from SAGT 2011
I just came back a few days ago, after spending 10 days in Italy and attending SAGT 2011, the fourth Symposium on Algorithmic Game Theory. As for Italy — the stories of its beauty and of its delicious food (and great cheap wine) turned out to be very true; in addition, we (that is Ety Khaitsin from TAU, who traveled with me, and myself) enjoyed really excellent weather throughout our stay, which made things even nicer.
The conference itself was located in Amalfi, a small and beautiful town on the coast a little southeast of Naples (called Amalfi Coast), and consisted of two and a half days of lectures, including two invited talks. The first invited talk, given by Bruno Codenotti and opening the first day of lectures, concentrated mainly on the very basics of GT and AGT, touching upon more advanced complexity issues towards the end. The second, given in the second day by Xiaotie Deng, was concerned with equilibria in matching markets, and compared this setting to the more studied (at least in AGT) setting of auctions. Besides these talks, 26 papers were presented. As seems to be the tradition, the papers in SAGT tend more to the theoretical perspective (i.e. studying things mainly through percise mathematical models and their analysis, rather than conducting experiments) compared to other similar conferences like WINE. My impression, which (at least judging by my conversations with some of the other attendees) was shared by many others as well, was that despite of the somewhat-small venue, the level of the accepted works was quite high. Continue Reading →
My Paper Accepted to SAGT 2011
My paper “Throw One’s Cake — and Eat It Too” was accepted to SAGT 2011, the fourth international symposium on algorithmic game theory, taking place October 17-19 in Salerno, Italy.
This paper, co-authored with my advisor, Prof. Yonatan Aumann, and with Orit Arzi, shows that there are cases in which throwing away some cake allows us to achieve envy-free divisions of the cake that are socially-preferable to any envy-free division of the entire cake. More surprising is the increase in welfare that may be achieved this way: we show that for utilitarian welfare, this increase may be as high as 
