M. Benisch and T. Sandholm, 2008, A theory of expressiveness in mechanisms, AAAI 2008

Posted by Katherine Skirving Larson on Tuesday 15 May 2012 at 16:50

M. Benisch and T. Sandholm, 2008, A theory of expressiveness in mechanisms, AAAI 2008

Posted by Katherine Skirving Larson on Tuesday 15 May 2012 at 16:50

Comments

This paper gives two measures for expressiveness and then ties these measures to the effectiveness of a mechanism.

The first measure is called maximum impact dimension, which is equal to maximum number of ways that a single agent can change the outcome of a mechanism. This measure is computed when the agent has the maximum control on outcome because of the input of other agents. The second measure is based on the concept of shattering. This measure is called shatterable outcome dimension, which is the size of the largest outcome space that an agent can shatter.

Then the authors derive a bound for effectiveness, which is a function of expressiveness. This bound is analyzed without solving the problem and driving equilibrium. The first claim of the paper is this bound is strictly increasing with expressiveness until the bound reaches full efficiency. For a specific class of mechanisms, channel-based auctions with non-overlapping bundles, they show that full efficiency will happen when agents have full information. This means that these types of auctions are inefficient considering any set of information.

The first measure is called maximum impact dimension, which is equal to maximum number of ways that a single agent can change the outcome of a mechanism. This measure is computed when the agent has the maximum control on outcome because of the input of other agents. The second measure is based on the concept of shattering. This measure is called shatterable outcome dimension, which is the size of the largest outcome space that an agent can shatter.

Then the authors derive a bound for effectiveness, which is a function of expressiveness. This bound is analyzed without solving the problem and driving equilibrium. The first claim of the paper is this bound is strictly increasing with expressiveness until the bound reaches full efficiency. For a specific class of mechanisms, channel-based auctions with non-overlapping bundles, they show that full efficiency will happen when agents have full information. This means that these types of auctions are inefficient considering any set of information.

Posted by Laleh Makarem on Wednesday 16 May 2012 at 11:51

Paper introduces general model of expressiveness based on two measure: maximum impact dimension and shatterable outcome dimension. The first one is related to the number of different ways an agent can impact the system, while the other one is an equivalent of the shattering measure from the field of computational learning theory.

Paper connects the expressiveness model with the efficiency: the main result is the derived upper bound on the most efficient Nash equilibrium which depends only on the impact an agent has on the mechanism. Because of that, one doesn't need to find the best equilibrium in order to analyze bound itself. Moreover, bound includes the most efficient equilibrium, so one does not need to worry about the existence of multiple equilibria. It is also important to note that this bound increases strictly with the increase of the expressiveness. Finally, authors show that in some case it is possible to have arbitrarily large increase in the bound with small increase in expressiveness.

Paper connects the expressiveness model with the efficiency: the main result is the derived upper bound on the most efficient Nash equilibrium which depends only on the impact an agent has on the mechanism. Because of that, one doesn't need to find the best equilibrium in order to analyze bound itself. Moreover, bound includes the most efficient equilibrium, so one does not need to worry about the existence of multiple equilibria. It is also important to note that this bound increases strictly with the increase of the expressiveness. Finally, authors show that in some case it is possible to have arbitrarily large increase in the bound with small increase in expressiveness.

Posted by Goran Radanovic on Wednesday 16 May 2012 at 13:43

{Summary: }

This paper introduce on how to characterize an expresiveness of a mechanism.

To the best of my knowledge this paper is the first one which explicitly disscuss about it.

It introduces two characterization which basically measure how powerful an agent can be such that she is able to influence the final outcome only with her declared type.

The first one is the number of outcome sets that can be differentiated based on the agent declared types (impact-based expressiveness), and the other one is the number of outcomes that can be shattered from the complete outcome space (shattering-based expressivness).

{Concern: }

Their proposed new mechanism, "channel-based mechanism" basically is giving value to any subset of outcome space (or at least subsumed by this mechanism).

I'm not so sure why they give it a special name.

{Critic: }

This paper has a lot of definitions without example (or not-so-clear example) which make it difficult to understand.

This paper introduce on how to characterize an expresiveness of a mechanism.

To the best of my knowledge this paper is the first one which explicitly disscuss about it.

It introduces two characterization which basically measure how powerful an agent can be such that she is able to influence the final outcome only with her declared type.

The first one is the number of outcome sets that can be differentiated based on the agent declared types (impact-based expressiveness), and the other one is the number of outcomes that can be shattered from the complete outcome space (shattering-based expressivness).

{Concern: }

Their proposed new mechanism, "channel-based mechanism" basically is giving value to any subset of outcome space (or at least subsumed by this mechanism).

I'm not so sure why they give it a special name.

{Critic: }

This paper has a lot of definitions without example (or not-so-clear example) which make it difficult to understand.

Posted by Tri Kurniawan Wijaya on Tuesday 22 May 2012 at 11:24