<p>Such discussions are difficult without properly defining what we are discussing. What do you mean by &quot;implement&quot;? What do you mean by &quot;Bayesian mechanism&quot;? 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.</p>
<p>In the video, I believe, they mean that a social choice function <span class="math-container">$f$</span> (mapping types into outcomes) is implemented by a mechanisms (an action space <span class="math-container">$A$</span> and an outcome function <span class="math-container">$o$</span>, mapping actions into outcomes) if there exists a Bayesian Nash equilibrium <span class="math-container">$\sigma$</span> (mapping types into actions) such that for any type vector <span class="math-container">$\theta$</span>, we have <span class="math-container">$f(\theta)=o(\sigma(\theta))$</span>. 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 &quot;plays the indirect mechanism's equilibrium for them&quot;, i.e., we can simply define a direct mechanism in which the action space is simply the type space and the outcome function <span class="math-container">$g'$</span> simply is such that <span class="math-container">$g'(\theta)=g(\sigma(\theta))$</span>. This direct mechanism is Byesian incentive-compatible because <span class="math-container">$\sigma$</span> is a Bayesian Nash equilibrium.</p>
<p>Note that &quot;implement&quot; 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 <span class="math-container">$\sigma$</span> of the indirect mechanism--corresponding to one social choice function-- and the equivalent direct mechanism has ONE equilium <span class="math-container">$\sigma'$</span> that always leads to the same outcome as <span class="math-container">$\sigma$</span> in the indirect mechanism, <span class="math-container">$f(\theta)=g(\sigma(\theta)=g'(\theta)$</span>. However, both mechanisms may have other equilibria.</p>
<p>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 <span class="math-container">$f(\theta)$</span>. Moreover, the notion of implementation is that the SC rule is implemented if, for all <span class="math-container">$\theta$</span>, the outcomes of ALL equilibria are a subset of the SC set <span class="math-container">$f(\theta)$</span>. This is a different notion compared to above.</p>

CC BY-SA 4.0
2022-03-03T14:59:20.987Z
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".
Francis
CC BY-SA 4.0
2022-03-03T15:05:35.197Z
(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].
Francis
CC BY-SA 4.0
2022-03-03T15:19:28.410Z
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))$.
Bayesian
CC BY-SA 4.0
2022-03-03T16:23:37.990Z
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?
Francis
CC BY-SA 4.0
2022-03-04T09:52:35.877Z
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.
Bayesian
CC BY-SA 4.0
2022-03-03T13:52:56.663Z
2022-03-03T13:52:56.663Z
Bayesian
<p>I am finding the revelation principle very confusing. So I was watching the <a href="https://www.game-theory-class.org/" rel="nofollow noreferrer">Game Theory online</a> course by Stanford and UBC. In their <a href="https://www.youtube.com/watch?v=fTgxpLEt0EU" rel="nofollow noreferrer">video about revelation principle</a>, here are the original words from the slides about revelation principle:</p>
<blockquote>
<p>It turns out that any social choice function that can be implemented by any mechanism can be implemented by a truthful, direct mechanism.</p>
</blockquote>
<p>Is this a correct statement? I feel like it is too strong. As far as I can understand from<a href="https://www.jstor.org/stable/3689266?seq=1#metadata_info_tab_contents" rel="nofollow noreferrer"> [Myerson 1981]</a>'s result, it seems the revelation principle there only hold for the indirect <em><strong>Bayesian</strong></em> mechanism, not &quot;any&quot; indirect mechanism.</p>
<p>Also, another paper by <a href="https://scholar.harvard.edu/files/maskin/files/the_implementation_of_social_choice....pdf" rel="nofollow noreferrer">[Maskin et al. 1979]</a> has the following statements from their paper:</p>
<blockquote>
<p>[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.</p>
</blockquote>
<p>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 <a href="https://www.youtube.com/watch?v=fTgxpLEt0EU" rel="nofollow noreferrer">online course</a>? I am wondering which of them is wrong, or did I misunderstand something?</p>

<game-theory><mechanism-design>
A question about revelation principle from the game theory online course
Francis
# A question about revelation principle from the game theory online course

(Asked by: username_0 on 2022-03-03)

I am finding the revelation principle very confusing. So I was watching the [Game Theory online](https://www.game-theory-class.org/) course by Stanford and UBC. In their [video about revelation principle](https://www.youtube.com/watch?v=fTgxpLEt0EU), 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]](https://www.jstor.org/stable/3689266?seq=1#metadata_info_tab_contents)'s result, it seems the revelation principle there only hold for the indirect ***username_1*** mechanism, not "any" indirect mechanism.

Also, another paper by [[Maskin et al. 1979]](https://scholar.harvard.edu/files/maskin/files/the_implementation_of_social_choice....pdf) 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](https://www.youtube.com/watch?v=fTgxpLEt0EU)? I am wondering which of them is wrong, or did I misunderstand something?

**Tags:** game-theory, mechanism-design


---

## 1 answers

### Answer by username_1 on 2022-03-03. Score: 1

Such discussions are difficult without properly defining what we are discussing. What do you mean by "implement"? What do you mean by "username_1 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 username_1 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 username_1 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.

> **Comments:**
> **username_0**: 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".  
> **username_0**: (2) about what did I mean by username_1 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 username_1 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 username_1 Nash equilibrium has equivalent direct mechanism makes sense to me, it is also mentioned as Theorem 5.2 in [Maksin et al. 1979].  
> **username_1**: 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))$.  
> **username_0**: 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?  
> **username_1**: 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.  

---

