Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
I do not understand the phrases "Nash equilibrium in a hybrid model" and "Nash equilibrium in the real world" –  Sasho Nikolov Nov 18 '11 at 21:17
    
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 Nov 20 '11 at 1:08
    
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 Nov 20 '11 at 20:47
    
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 Nov 21 '11 at 2:12
1  
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. –  user686 Jan 3 '12 at 3:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.