<p>This might be a very simple doubt, but I am not able to prove or disprove it rigorously. </p>

<p>Canetti's work on "Security and Composition of Multiparty Cryptographic Protocols: JoC 2000" allows us to prove results of the following form: Let $g, f_1, f_2, \cdots, f_m$ be $n$-party functions and $\pi$ can securely compute $g$ in $(f_1, \cdots , f_m)$ hybrid model. Let $\rho_i$ computes $f_i$ securely, then the composed protocol $\Pi$ by replacing the ideal call to $f_i$ by a subroutine call to $\rho_i$ securely evaluates $g$. </p>

<p>Does this result translate equally well if we consider Nash equilibrium or any game-theoretic equilibrium instead of secure computation? To be more precise, suppose instead of securely evaluating the function, we have a protocol that is Nash equilibrium in $(f_1, \cdots , f_m)$hybrid model, then can we construct a protocol that is Nash equilibrium in the real world?</p>

<p>What I mean by that a protocol is a Nash equilibrium in a setting X (X=ideal, hybrid, or real world) is the following. Suppose the strategy profile of player $i$ be $\Sigma_i$ for $i \in [n]$. Running the protocol is a (strict) Nash equilibrium with a strategy ($\sigma_1, \sigma_2, \cdots, \sigma_n) \in \Sigma_1 \times \cdots \times \Sigma_n$ in the setting X if any deviation of the players from the strategy prescribed in the protocol leads to a (strict) decrease in their utility.</p>

CC BY-SA 3.0
2011-11-18T21:17:45.250Z
I do not understand the phrases "Nash equilibrium in a hybrid model" and "Nash equilibrium in the real world"
Sasho Nikolov
CC BY-SA 3.0
2011-11-20T01:08:06.953Z
What I mean by that a protocol is a Nash equilibrium in a setting X (X=ideal, hybrid, or real world) is the following. Suppose the strategy profile of player i be $\Sigma_i$ for i∈[n]. Running the protocol is a (strict) Nash equilibrium with a strategy $(\sigma_1,⋯,\sigma_n) \in \Sigma_1 \times ⋯ \times \Sigma_n$ in the setting X if any deviation of the players from the strategy prescribed in the protocol leads to a (strict) decrease in their utility.
Jalaj
CC BY-SA 3.0
2011-11-20T20:47:51.067Z
that sounds like standard nash equilibrium, but i still don't see where the setting comes in. could your question be something like "if a game G is in some sense (what sense?) composed from games F1, F2, ..., Fn, then is the composition (how do you compose strategies?) of nash equilibria of F1, ..., Fn a nash equilibrium of G?"
Sasho Nikolov
CC BY-SA 3.0
2011-11-21T02:12:01.083Z
It is standard Nash equilibrium. One of the motivation of the setting is the following cryptographic application where one tries to incorporate fairness in a two party secure computation. Let say we are trying to compute a function $f(x_1,x_2)$, where $x_i$ is private input to party $i$. One way to construct a protocol is to divide the private input among the two party (can be seen as a preprocessing state) and then use a secret reconstruction phase to compute the share and then the function. (continued...)
Jalaj
CC BY-SA 3.0
2011-11-21T02:13:29.007Z
If the first step is taken care by a trusted party (implicitly fair) and if Canetti's composition is true for game-theoretic concept, then showing that continuing the complete protocol is a Nash equilibrium boils down to the complete protocol is  all one need to show that step 2 is Nash equilibrium, which is simple. You can see that the analysis is in hybrid model because we consider the trusted party to do the preprocessing step.
Jalaj
CC BY-SA 3.0
2012-01-03T03:06:29.113Z
I think you would have to define your terms more carefully (e.g., can utilities depend on the protocol transcript, or do they only depend on players' outputs?) in order to formally prove something either way.
user6584
CC BY-SA 3.0
2012-01-27T05:26:41.870Z
Well, for that, I can give you the reference of the paper by Groce and Katz (http://eprint.iacr.org/2011/396). The problem I stated is said to hold on page 8 of the paper, but I don't quiet follow it.
Jalaj
<cr.crypto-security><gt.game-theory>
Can Canetti's composition theorem be used to prove composition of Nash equilibrium?
Jalaj
# Can Canetti's composition theorem be used to prove composition of Nash equilibrium?

(Asked by: username_0 on 2011-11-18)

This might be a very simple doubt, but I am not able to prove or disprove it rigorously.

Canetti's work on "Security and Composition of Multiparty Cryptographic Protocols: JoC 2000" allows us to prove results of the following form: Let $g, f\_1, f\_2, \cdots, f\_m$ be $n$-party functions and $\pi$ can securely compute $g$ in $(f\_1, \cdots , f\_m)$ hybrid model. Let $\rho\_i$ computes $f\_i$ securely, then the composed protocol $\Pi$ by replacing the ideal call to $f\_i$ by a subroutine call to $\rho\_i$ securely evaluates $g$.

Does this result translate equally well if we consider Nash equilibrium or any game-theoretic equilibrium instead of secure computation? To be more precise, suppose instead of securely evaluating the function, we have a protocol that is Nash equilibrium in $(f\_1, \cdots , f\_m)$hybrid model, then can we construct a protocol that is Nash equilibrium in the real world?

What I mean by that a protocol is a Nash equilibrium in a setting X (X=ideal, hybrid, or real world) is the following. Suppose the strategy profile of player $i$ be $\Sigma\_i$ for $i \in [n]$. Running the protocol is a (strict) Nash equilibrium with a strategy ($\sigma\_1, \sigma\_2, \cdots, \sigma\_n) \in \Sigma\_1 \times \cdots \times \Sigma\_n$ in the setting X if any deviation of the players from the strategy prescribed in the protocol leads to a (strict) decrease in their utility.

**Tags:** cr.crypto-security, gt.game-theory
> **Comments:**
> **username_1**: I do not understand the phrases "Nash equilibrium in a hybrid model" and "Nash equilibrium in the real world"  
> **username_0**: What I mean by that a protocol is a Nash equilibrium in a setting X (X=ideal, hybrid, or real world) is the following. Suppose the strategy profile of player i be $\Sigma_i$ for i∈[n]. Running the protocol is a (strict) Nash equilibrium with a strategy $(\sigma_1,⋯,\sigma_n) \in \Sigma_1 \times ⋯ \times \Sigma_n$ in the setting X if any deviation of the players from the strategy prescribed in the protocol leads to a (strict) decrease in their utility.  
> **username_1**: that sounds like standard nash equilibrium, but i still don't see where the setting comes in. could your question be something like "if a game G is in some sense (what sense?) composed from games F1, F2, ..., Fn, then is the composition (how do you compose strategies?) of nash equilibria of F1, ..., Fn a nash equilibrium of G?"  
> **username_0**: It is standard Nash equilibrium. One of the motivation of the setting is the following cryptographic application where one tries to incorporate fairness in a two party secure computation. Let say we are trying to compute a function $f(x_1,x_2)$, where $x_i$ is private input to party $i$. One way to construct a protocol is to divide the private input among the two party (can be seen as a preprocessing state) and then use a secret reconstruction phase to compute the share and then the function. (continued...)  
> **username_0**: If the first step is taken care by a trusted party (implicitly fair) and if Canetti's composition is true for game-theoretic concept, then showing that continuing the complete protocol is a Nash equilibrium boils down to the complete protocol is  all one need to show that step 2 is Nash equilibrium, which is simple. You can see that the analysis is in hybrid model because we consider the trusted party to do the preprocessing step.  
> **username_2**: I think you would have to define your terms more carefully (e.g., can utilities depend on the protocol transcript, or do they only depend on players' outputs?) in order to formally prove something either way.  
> **username_0**: Well, for that, I can give you the reference of the paper by Groce and Katz (http://eprint.iacr.org/2011/396). The problem I stated is said to hold on page 8 of the paper, but I don't quiet follow it.  

---

## 0 answers

