# Salary Negotiation Problem

Imagine Alice is applying for a new job. Alice has an idea of the minimum salary that she is willing to accept—let's call this value A. Bob, the hiring manager for a company that Alice is applying to, also has a number in mind: the maximum acceptable salary that he is willing to pay to fill the position—let's call this value B.

• Bob wants be sure that at least B >= A is true before spending the time to interview Alice.
• Bob does not want Alice to know the exact value of B, because then she would be in a superior position to negotiate a salary as close to B as possible.
• Alice would also like to know if B >= A is true, for the same reasons as Bob.
• Likewise, Alice does not want Bob to know the exact value of A, because then Bob would be in a superior position to negotiate a salary as close to A as possible.

I'm curious if there is a known cryptographic protocol that would allow Alice and Bob to exchange some information and conclusively determine the result of B >= A, without revealing any additional information about the actual value of B to Alice or the value of A to Bob.

Caveats:

• The use of a third party is not allowed.
• Ignore the fact that the repeated use of such an algorithm with different values of A would allow Alice could learn the approximate value of B. Assume that neither party is allowed to change their value.

Does such an algorithm exist? If not, is such a solution even possible?

• See Yao's Millionaires' Problem, and more generally the class of problems and protocols which fall under the heading of Secure Multiparty Computation.
– sju
Nov 5, 2015 at 3:44
• @sju but that would need multiple queries, for Alice to come close to B's number. Nov 5, 2015 at 4:07
• @sashank I'm sorry, I don't follow. Alice being able to approximate $b$ is not desired, and further Alice's ability to approach it with arbitrarily many queries would be a consequence of any solution to the problem (at least within the problem space of salary negotiations). The original question noted that computation of the inequality would be limited to one occurance, so as to ignore that case.
– sju
Nov 5, 2015 at 4:30