In Quest of Truth and Justice

Guest post by Ariel Procaccia

Three of the papers uploaded to the archives on March 30 have a common theme: they deal with truth and justice (a.k.a. fairness). In the scientific jargon “paper after paper” means “two papers” and “a series of papers” means “three papers”; since there is also a bonus fourth paper, I can therefore declare a new “trend”.

Two of the arXiv papers are by Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, and Svetlana Olonetsky. Both papers study mechanisms with payments for the allocation of goods. The first paper asks (and answers) the following question: for which allocation rules are there payments such that the resulting mechanism is, at the same time, truthful and envy free? The latter property means that each player weakly prefers his own outcome (bundle+payments) to the outcome of any other player. Interestingly, the fact that an allocation has payments leading to truthfulness, and different payments leading to envy freeness, does not imply that there is a single payment scheme that leads to both. The second paper focuses on a setting where players have a limit on the number of goods they may receive; the main result is that (under additive valuations) the VCG Mechanism with Clark Pivot payments, which is of course truthful, also has the property that a higher capacity agent never envies a lower capacity agent. This implies envy freeness in the natural special case where all agents have the same capacity.

The third paper is by Elchanan Mossel and Omer Tamuz. The first part of the paper deals with cake cutting, informally known as “allocation of divisible goods”. Curiously, most of the literature on cake cutting is concerned with fairness, while truthfulness has so far been largely overlooked. Mossel and Tamuz are interested in mechanisms (without payments this time) that are, again, truthful and fair, but this time the notion of fairness is proportionality: each of the n players is allocated a piece of cake worth at least 1/n according to his valuation. They present a simple randomized mechanism that is truthful (in expectation) and proportional. To be precise, they show that there exists such a mechanism, since the construction relies on a well known nonconstructive existence result. The mechanism is then extended to yield (the existence of) a randomized mechanism that is truthful and guarantees each player a piece worth more than 1/n of the entire cake in expectation (assuming some of the players have different valuation functions). The second part of the papers applies these insights to the allocation of indivisible goods.

Incidentally, I recently wrote a paper with Yiling Chen, John Lai, and David Parkes where we independently asked questions that are very similar to the ones raised by Mossel and Tamuz, but our answers are very different (modulo a small overlap). In our paper we want it all: truthfulness, envy freeness, and proportionality (which in our setting is not implied by envy freeness). Envy free cake cutting is notoriously difficult, and in fact there is no known protocol that achieves an envy-free division with a bounded number of steps. In order to get constructive results we therefore focus on restricted valuation functions where achieving fairness is trivial and the richness of the problem comes from the additional truthfulness requirement. Our main result is a deterministic mechanism that is truthful, envy free, proportional, and polynomial-time, assuming the valuations are what we call piecewise constant. The paper will appear in AAAI’10; in observance of the time honored AAAI tradition the current version is super dense and most proofs are omitted. This is another similarity to the Mossel-Tamuz paper: they have proofs of existence and we have nonexistent proofs! (In fact the proofs do exist, and the full version is coming soon.)

I’ll finish with a word of caution from my AI conscience. The problems that we study in AGT are often justified by assuming that our players are computational agents (e.g., in the scheduling domain). It is clear why lack of truthfulness may lead to socially undesirable outcomes in a multiagent system. In contrast, envy freeness seems to be desirable for philosophical or psychological reasons; it is a priori unclear why we would look for envy freeness in a multiagent system. A nice challenge is to come up with a model that relates envy freeness to the stability of the system, for example in terms of the robustness to random failures.

Advertisement