2
$\begingroup$

I am finding the revelation principle very confusing. So I was watching the Game Theory online course by Stanford and UBC. In their video about revelation principle, here are the original words from the slides about revelation principle:

It turns out that any social choice function that can be implemented by any mechanism can be implemented by a truthful, direct mechanism.

Is this a correct statement? I feel like it is too strong. As far as I can understand from [Myerson 1981]'s result, it seems the revelation principle there only hold for the indirect Bayesian mechanism, not "any" indirect mechanism.

Also, another paper by [Maskin et al. 1979] has the following statements from their paper:

[From Paragraph after Proof of Theorem 7.1.1] Yet there is an even more compelling reason for turning our attention to indirect mechanisms, which is that there are some important Social Choice Rules which cannot be implemented in Nash strategies by direct mechanisms but which can be implemented by appealing to indirect mechanisms.

Does this paragraph from Maskin et al's paper mean there exist some social choice functions that cannot be implemented by a direct mechanism but can be implemented by an indirect mechanism? Isn't this contradicting with the online course? I am wondering which of them is wrong, or did I misunderstand something?

$\endgroup$

1 Answer 1

1
$\begingroup$

Such discussions are difficult without properly defining what we are discussing. What do you mean by "implement"? What do you mean by "Bayesian mechanism"? I guess that in the video (I didn't watch it) they use a different definition than in the paper (I haven't read it). Maybe my comment still helps.

In the video, I believe, they mean that a social choice function $f$ (mapping types into outcomes) is implemented by a mechanisms (an action space $A$ and an outcome function $o$, mapping actions into outcomes) if there exists a Bayesian Nash equilibrium $\sigma$ (mapping types into actions) such that for any type vector $\theta$, we have $f(\theta)=o(\sigma(\theta))$. In this setting, the quoted sentence is correct: the revelation principle trivially holds in the sense that we can always define a direct mechanism that asks players for their types and then "plays the indirect mechanism's equilibrium for them", i.e., we can simply define a direct mechanism in which the action space is simply the type space and the outcome function $g'$ simply is such that $g'(\theta)=g(\sigma(\theta))$. This direct mechanism is Byesian incentive-compatible because $\sigma$ is a Bayesian Nash equilibrium.

Note that "implement" applied in this sense only requires that some equilibrium exists, not that it is unique. That is, we can define an equivalent direct mechanism for ONE equilibrium $\sigma$ of the indirect mechanism--corresponding to one social choice function-- and the equivalent direct mechanism has ONE equilium $\sigma'$ that always leads to the same outcome as $\sigma$ in the indirect mechanism, $f(\theta)=g(\sigma(\theta)=g'(\theta)$. However, both mechanisms may have other equilibria.

I haven't read the paper, but I looked at the definitions. Note that the paper has social choice rules that are correspondences, not functions. That is, such a SC rule may not map into a single outcome, but an entire set of outcomes, the SC set $f(\theta)$. Moreover, the notion of implementation is that the SC rule is implemented if, for all $\theta$, the outcomes of ALL equilibria are a subset of the SC set $f(\theta)$. This is a different notion compared to above.

$\endgroup$
5
  • $\begingroup$ Thanks for your comment. Two questions: (1) about the difference between SC Rule and SC function, are they the same when the SC Rule set $|f(\theta)| = 1$, i.e. SC rule only maps into a single outcome? I feel like they are the same, and in [Maksin et al. 1979], they defined this as Singleton SC Rule (SSCR), and their example 7.1.2 is an example of SSCR (which I think is the same as SC function) that "can be implemented only by appealing to indirect mechanisms". $\endgroup$
    – Francis
    Commented Mar 3, 2022 at 14:59
  • $\begingroup$ (2) about what did I mean by Bayesian mechanism, I think I meant exactly the same as your example of $g$ and $g'$. As you said in your example, the $\sigma$ is a Bayesian Nash equilibrium. I am wondering if your argument still holds when $\sigma$ is Nash equilibrium? Because [Maksin et al. 1979]'s Example 7.1.2 is also about Nash equilibrium strategies. I think the argument about Bayesian Nash equilibrium has equivalent direct mechanism makes sense to me, it is also mentioned as Theorem 5.2 in [Maksin et al. 1979]. $\endgroup$
    – Francis
    Commented Mar 3, 2022 at 15:05
  • $\begingroup$ The SC rule/correspondence vs. SC function is not so much the issue. It is more the difference in the definition of "implement." With an SSCR it must be that all equilibria $\sigma_1,\sigma_2,...$ of the indirect mechanism must have outcomes $g(\sigma_i(\theta))=f(\theta)$, but if the direct mechanism has two equilibria $\sigma'_1, \sigma'_2$ it does not impelent $f$ if $g'(\sigma'_1(\theta))\neq g'(\sigma'_2(\theta))$. $\endgroup$
    – Bayesian
    Commented Mar 3, 2022 at 15:19
  • $\begingroup$ Ok I see, that is your point. But actually, their definition of implementing a direct mechanism is "Truthful Implementation" (See the definition at the end of Section 2, [Maskin et al. 1979]). Truthful Implementation only requires $g'(\theta) = f(\theta)$, and it does not care about other equilibrium states in the direct mechanism. Since they mentioned, "It has commonly been assumed that, if truthfulness is an equilibrium strategy for an agent in a direct mechanism, then that agent will choose to be truthful.". Does this definition of "implementation" make sense? $\endgroup$
    – Francis
    Commented Mar 3, 2022 at 16:23
  • $\begingroup$ I was referring to p.188, part (ii), $g(E(\theta)) \subseteq f(\theta)$, which to me seems as if they are saying that the outcomes of ALL equilibria need to be in the SC set. In this sense, a direct mechanism may have a truthful equilibrium that truthfully implements f, but also a non-truthful equilibrium that does not implement f. $\endgroup$
    – Bayesian
    Commented Mar 4, 2022 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.