Feeds:
Posts

## New paper on cake-cutting

A paper “On the complexity of envy-free cake cutting” by Xiaotie Deng, Qi Qi, and Amin Saberi was recently uploaded to the archive.  This paper seems to finalize the adoption of the “cake-cutting” literature (see presentation by Ulle Endris or survey by Brams and Taylor) into main stream algorithmic game theory.

Abstract: We study the envy-free cake-cutting problem for $d+1$ players with $d$ cuts, for both the oracle function model and the polynomial time function model. For the former, we derive a $\theta(({1\over\epsilon})^{d-1})$ time matching bound for the query complexity of $d+1$ player cake cutting with Lipschitz utilities for any $d> 1$. When the utility functions are given by a polynomial time algorithm, we prove the problem to be PPAD-complete.  For measurable utility functions, we find a fully polynomial-time algorithm for finding an approximate envy-free allocation of a cake among three people using two cuts.

## Shahar Dobzinski reports from EC

### Guest post by Shahar Dobzinski, reporting from EC:

EC took place last week at Stanford. For me EC is not necessarily the place to hear new results; I already read or heard talks about most of the papers that interest me in the program. The best thing about EC is that it is a meeting place for the algorithmic game theory community (with quite a few attendees that do not coauthor a paper in the proceedings).

The EC audience is quite diverse and consists mainly of Theory and AI people, but there are also some economists and attendees from other areas. Though it seems that everybody is quite happy with this diversity, I couldn’t avoid noticing that theory people tend to complain that there are too much AI papers, AI guys complain that there are too much theory papers, and both complain that there are too many computer scientists who are doing pure economics. Economists seem to be too polite to complain (at least when I am around). Optimists would interpret this as a sign that the mix of papers is correct.

One disappointing feature of this conference is the horrible meeting room. The room is huge, full with round tables. Hard to even hear hear the questions asked by the audience, so the poor session chair has to run with a microphone to the other side of the room whenever there is a question. I have never been to a wedding in the US, but in Israel this room could be a great wedding hall.

So what are the trends in EC? Adwords seems like a hot trend, although my feeling is that it was hotter last year. Many papers model different issues in selling ad auctions, and even more papers with adwords as their claimed motivation and inspiration. Adwords are an important application of algorithmic game theory, but in some sessions it looked as if this is the only application. On the other hand, relatively not too many equilibria computation papers were presented.  Price-of-anarchy type of results were not too popular either. Still, approximately 10 percent of the papers in the conference had the phrase “price of” in their title, and a few more have it in the abstract. Termed in 2001 by Papadimitriou, the “price of anarchy” is surely a great, catchy name. Unfortunately, by now it might be overused: an hypothetical list of the difference “prices” defined by now would probably be about the same size of Garey and Johnson’s NP-complete problems list. We should consider a definition freeze for at least a year or two.

Two papers won the outstanding paper award. Nicolas Lambert gave a very good talk on his paper with Yoav Shoam. The paper shows how to design payment schemes that motivate experts to answer truthfully multiple-choice questions. The expert is being asked, for example, ”what is the mean of a random variable X?” and is getting paid according to the realization of X.  They provide a complete characterization of the possible mechanisms. The paper also got the best student paper award.

The second winning paper was my joint paper with Itai Ashlagi and Ron Lavi. We considered the problem of truthful scheduling of jobs on unrelated machines to minimize the makespan, that was introduced by Nisan and Ronen in their “Algorithmic Mechanism Design” paper. We showed that no anonymous mechanism can provide a more-than-trivial approximation ratio (a mechanism is anonymous, if, roughly speaking, the names of the machines does not matter).

EC’10 will take place at Harvard, with  Moshe Tennenholtz and Chris Dellarocas as chairs. Hopefully it will be at least as good as EC’09.

## SAGT 2009 accepted papers

SAGT (Symposium on Algorithmic Game Theory) 2009 will take place in Paphos (Cyprus) on October 18-20.   Here is the list of accepted papers.

## Report from ICALP

While EC is taking place in Palo-Alto, I’m just returning from ICALP in Rhodes.  ICALP is the main Thoeretical CS European confernce and is a
friendly and relaxed event with somewhat over 200 participants, many of them being old friends for me.
Many came with families and many spent some of their time on the beach or in other tourist
attractions rather than in the talks.  The program consists of 3 tracks: the largest on Algorithms and Complexity, the
&quot;European CS&quot; track on Logic, Automata, and Languages,
and the new Internet-related track, with the 3 tracks fitting into two parallel sessions.
The main special event during this ICALP was a workshop celebrating Christos Papadimitriou’s 60th birthday.  Dick Karp talked about several
algorithmic problems arising from computational biology.  Laci Lovasz talked about a surprising elegant notion of a limit of a sequence
of graphs.  The idea is that we can say that a sequence of graphs $G_1, G_2, ...$, where $G_n$ is a graph on $n$ vertices, is convergent
if for every finite $k$-vertex graph, the fraction of induced $k$-vertex subgraphs of $G_n$ that equals it, has a limit.  For
such convergent sequences, an infinite limit object can naturally be defined, where this object is a measurable function $f: [0,1]^2 \rightarrow [0,1]$, and
it maintains various properties of the graphs in the sequence. The next two talks were related to Christos’s current field, Algorithmic Game Theory.  I talked
about budgets in multi-unit auctions, and Tim Roughgarden gave an amazingly crisp talk about the robustness of the price of anarchy in congestion games.  He pointed out
a cannonical method used for proving most price-of-anarchy results, and showed that it also bounded the loss incurred in a much wider variety of
equilibrium-like solutions, not just pure-Nash equilibria.  He also showed that this cannonical method is &quot;complete&quot; for congestion games.  The last talk
of the workshop was given by Christos’s long-time collaborator, Mihalis Yannakakis, who gave an interesting narrative that went over
many of the complexity classes that Christos defined
throughout his career (such as approximation classes and PPAD). The whole event was really warm and lovely.
Among the regular talks I attended, the one that caught my imagination most was by John Reif who has been working on &quot;self-assembly&quot;
for the last 10 years and is rarely seen in CS conferences anymore.  The idea is to study
and mimic natural processes where simple building blocks arrange themselves into complex structures (e.g. into DNA).  Theoretical models
for this usually involve 2-dimesional tiles that can fit togther according ot some rules, and this talk gave a probabilistic variant where 1-dimensional tiles
also exhibit some capabilities of this form.
Besides the talk I gave during the workshop, I gave another invited talk describing Google’s auction for TV-ads.

While EC is taking place in Palo-Alto, I just returned from ICALP in Rhodes.  ICALP is the main Theoretical CS European conference and is a friendly, relaxed, and fun event with somewhat over 200 participants.   Many came with families and many spent some of their time on the beach or in other tourist attractions rather than in the talks.  The program consists of 3 tracks: the largest on “Algorithms, automata, complexity and games”, the  “European CS” track on “Logic, semantics and theory of programming”, and the new track on “Foundations of networked computation”, with the 3 tracks fitting into two parallel sessions.

The main special event during this ICALP was a workshop celebrating Christos Papadimitriou’s 60th birthday.  Dick Karp talked about several algorithmic problems arising from computational biology.  Laci Lovasz talked about an elegant notion of a limit of a sequence of graphs.  The idea is that we can say that a sequence of graphs $G_1, G_2, ...$, where $G_n$ is a graph on $n$ vertices, is convergent if for every finite $k$-vertex graph, the fraction of induced $k$-vertex subgraphs of $G_n$ that equals it, has a limit.  For such convergent sequences, an infinite limit object can naturally be defined, where this object turnsa out to be  a measurable function $f: [0,1]^2 \rightarrow [0,1]$, and it maintains various properties of the graphs in the sequence. The next two talks were related to Christos’s current field, Algorithmic Game Theory.  I talked about budgets in multi-unit auctions (paper, presentation), and Tim Roughgarden gave an amazingly crisp talk about the robustness of the price of anarchy in congestion games.  He pointed out a canonical method used for proving most price-of-anarchy results, and showed that it also bounded the loss incurred in a much wider variety of equilibrium-like solutions, not just pure-Nash equilibria.  He also showed that this canonical method is “complete” for congestion games.  The last talk of the workshop was given by Christos’s long-time collaborator, Mihalis Yannakakis, who gave an interesting narrative that went over many of the complexity classes that Christos defined throughout his career (such as approximation classes and PPAD). Ending with a few words from Christos, the whole event was really warm and lovely.

Among the regular talks I attended, the one that caught my imagination was by John Reif who has been working on “self-assembly” for the last 10 years and is rarely seen in CS conferences anymore.  The idea is to study and mimic natural processes where simple building blocks arrange themselves into complex structures (e.g. into DNA).  Theoretical models for this usually involve 2-dimensional tiles that can fit together according to some rules, and this talk gave a probabilistic variant where 1-dimensional tiles also exhibit some capabilities of this form.

Besides the talk I gave during the workshop, I gave another invited talk describing Google’s auction for TV-ads (presentation, paper).

## Report from Euro 2009

I’m currently on my way from EURO in Bonn to ICALP in Rhodes.  Euro is the main Operations Research conference
in Europe and I was invited to  give a (semi-)keynote talk in it.  I’ve never been in an OR conference before,
and while I never totally understood what OR is, I always had the feeling that Algorithmic Game Theory should in principle fit squarely into OR,
since these are the guys that anyway mix CS-ey optimization with economic considerations (and they’re really into LP to boot).
Of course, in reality there has been very little contact between the Algorithmic Game Theory community and OR (well, yeh, Rakesh.)
So, not only was I happy to give a talk, but I was also curious to find out everything about the OR field (spoiler: I failed).
Well, first the conference is huge: about 2,500 attendees (of which I personally only knew three…).
The sessions are 45-way paralell.  I understand that the North-American OR conference, INFORMS, is
even larger.  So, it seems that OR is thriving.  The attendees looked about the same as I’m
used to in TCS confernces, many of them young, the usual O(20%) female, dress-code more often casual than
suited, but with very few North-Americans and a more varied European presence (including many from Spain, France and Turkey).
The “opening session” was a pretty heavy event, starting with Beethoven’s Ode de Joy, several addresses by conference officials, as well as
by the Mayor of Bonn (kudos to him for paying such attention to a scientific conference), performence by an Opera singer (who’s getting a Ph.D. in OR), and
the announcements of various awards.  The most signifcant ones are the “Euro gold medal” awarded to Jacques Benders for his pioneering work in the 1960’s on decomposition
in linear programming as well as to Frank Kelly for his work on networks, which had a strong influence on Algorithmic Game Theory too.  Michael Trick’s blog post
gives more details from an insider’s point of view.
The main keynote talks were by Reinhard Selten, a Nobel laurete economist, and by our own (?) Christos Papadimitriou.  Selten described, in much detail, an
economic experiment that studies “goal formation” in the sense of Herbert Simon.  Christos gave the current version of his usual talk on the complexity of equilibria.
While the title remains the same, the contents keep being updated as Christos obtains new results.  (As Christos says, this is better than giving the same talk but with
changing titles.)  Since the last time that I heard this talk, the focus has moved from the basic PPAD-hardness impossibility results, to the various ways
of dealing with them: approximation, special cases, and so on.  Christos’s talk, as usual, was full of inspiring “one-liners”, some of which you can read in
Michael Trick’s post.  My favorite take home was the term “the third compromise”: approximation due to NP-hardness being the first compromise of CS,
online algorithms due to partial information being the second, and equilibria due to non-cooperative behavior being the third.  The last part of his talk was
devoted to sexual optimization, somewhat off-topic but certainly entertaining.
Given 45 parallel tracks, I missed over 97% of all regular talks (well, ok, more than 98%), but a glance at the nicely colour-coded “master track schedule”
can give some sense of what is OR today: many X-programming and X-optimization sessions,
for x in {linear, non-linear, quadratic, convex, non-convex, mathematical, stochastic, boolean, semi-infinite, non-smooth, …};
Various applications in transportation, health-care,
agriculture, finance, logistics, and more (but nothing I could find in advertsing).
Scheduling is still significant, as are data mining and knowledge discovery, supply chains,
stochastic stuff (i’m not sure what), as well as various initials that I don’t understand: MCDA, DEA, AHP, and DSS.

I’m currently on my way from EURO in Bonn to ICALP in Rhodes.  Euro is the main Operations Research conference in Europe and I was invited to  give a (semi-)keynote talk in it.  I’ve never been in an OR conference before, and while I never totally understood what OR is, I always had the feeling that Algorithmic Game Theory should in principle fit squarely into OR, since these are the guys that anyway mix CS-ey optimization with economic considerations (and they’re really into LP to boot). Of course, in reality there has been very little contact between the Algorithmic Game Theory community and OR (well, yeh, Rakesh.)  So, not only was I happy to give a talk, but I was also curious to find out everything about the OR field (spoiler: I failed).

Well, first the conference is huge: about 2,500 attendees (of which I personally only knew three…). The sessions are 45-way parallel.  I understand that the North-American OR conference, INFORMS, is even larger.  So, it seems that OR is thriving.  The attendees looked about the same as I’m used to in TCS conferences, many of them young, the usual O(20%) female, dress-code more often casual than suited, but with very few North-Americans and a more varied European presence (including many from Spain, France and Turkey).  The “opening session” was a pretty heavy event, starting with Beethoven’s Ode to Joy, several addresses by conference officials, as well as by the Mayor of Bonn (kudos to him for paying attention to a scientific conference), performance by an Opera singer (who’s getting a Ph.D. in OR), and the announcements of various awards.  The most significant ones are the “Euro gold medal” awarded to Jacques Benders for his pioneering work in the 1960’s on decomposition in linear programming as well as to Frank Kelly for his work on networks, which had a strong influence on Algorithmic Game Theory too. Michael Trick’s blog post gives more details from an insider’s point of view.

The main keynote talks were by Reinhard Selten, a Nobel laureate economist, and by our own (?) Christos Papadimitriou.  Selten described, in much detail, an economic experiment that studies “goal formation” in the sense of Herbert Simon.  Christos gave the current version of his usual talk on the complexity of equilibria.  While the title remains the same, the contents keep being updated as Christos obtains new results.  (As Christos says, this is better than giving the same talk but with changing titles.)  Since the last time that I heard this talk, the focus has moved from the basic PPAD-hardness impossibility results, to the various ways of dealing with them: approximation, special cases, and so on.  Christos’s talk, as usual, was full of inspiring “one-liners”, some of which you can read in Michael Trick’s blog post.  My favorite take home was the term “the third compromise”: approximation due to NP-hardness being the first compromise of CS, online algorithms due to partial information being the second, and equilibria due to non-cooperative behavior being the third.  The last part of his talk was devoted to sexual optimization, somewhat off-topic but certainly entertaining.

Given 45 parallel tracks, I missed over 97% of all regular talks (well, ok, more than 98%), but a glance at the nicely colour-coded “master track schedule” can give some sense of what is OR today: many X-programming and X-optimization sessions, for X in {linear, non-linear, quadratic, convex, non-convex, mathematical, stochastic, boolean, semi-infinite, non-smooth, …}.  Various applications in transportation, health-care, agriculture, finance, logistics, and more (but nothing I could find in advertsing). Scheduling gets several sessions, as well as data mining and knowledge discovery, supply chains, stochastic stuff (i’m not sure what), as well as various initials that I don’t understand: MCDA, DEA, AHP, and DSS.  Well, that’s about what learned about OR this time.

## FOCS 2009 accepted papers

FOCS 2009 accepted papers have been posted.  The following seem to be in the general area of algorithmic game theory:

1. The Complexity of Rationalizing Network Formation by Shankar Kalyanaraman and Christopher Umans.
2. Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks by Yossi Azar, Benjamin Birnbaum, L. Elisa Celis, Nikhil R. Devanur and Yuval Peres.
3. On the Power of Randomization in Algorithmic Mechanism Design by Shahar Dobzinski and Shaddin Dughmi.  (A link to the paper and some discussion in this blog post.)
4. On Allocating Goods to Maximize Fairness by Deeparnab Chakrabarty, Julia Chuzhoy and Sanjeev Khanna.
5. Reducibility Among Fractional Stability Problems by Shiva Kintali, Laura Poplawski, Rajmohan Rajaraman, Ravi Sundaram and Shang-Hua Teng. (A link to the paper and some discussion in this blog post.)
6. Online Stochastic Matching: Beating 1-1/e by Jon Feldman, Aranyak Mehta, Vahab Mirrokni and S. Muthukrishnan.  (A link to the paper hides in this related blog post.)
7. Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities by Xi Chen, Decheng Dai, Ye Du and Shang-Hua Teng. (A link to the paper and some discussion in this blog post.)
8. Convergence to Equilibrium in Local Interaction Games byAndrea Montanari and Amin Saberi.
9. Dynamic and Non-Uniform Pricing Strategies for Revenue Maximization byTanmoy Chakraborty, Zhiyi Huang and Sanjeev Khanna.
10. Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions by Gagan Goel, Chinmay Karande, Pushkar Tripathi and Lei Wang.