Zero-Knowledge Negotiation Protocol

November 11, 2016 11:58 AM

Can we do a deal?

Suppose you have two people negotiating to buy / sell something. Seller has a maximum they're willing to pay, and Buyer has a minimum they're willing to accept. They can keep going back and forth with bids to try to agree, but is there a protocol by which they can get a yes/no answer to the question, "is the other side's limit higher/lower than my limit?" It doesn't have to (shouldn't!) say what the limits are, just that there exists an overlap between the highest bid and the lowest ask.

Obviously, if you know that there is an overlap, and the size of the overlap, you can calculate the other side's number. So the protocol needs to hide the size of the overlap from both parties, and just produce "Overlap Yes" or "Overlap No."

One simple solution would be to use a trusted third party, but is there a protocol that the buyer and seller can do on their own?

posted by spacewrench to Grab Bag (13 answers total)

Best answer: This sounds like it's equivalent to determining which of two secret numbers is larger without revealing either of them. In which case it's the same as Yao's Millionaire's Problem (not that I fully understand it). If the buyer's number is greater or equal to the seller's number, a deal is possible.
posted by aubilenon at 12:11 PM on November 11, 2016 [4 favorites]

the only way to really do this without a third party is for each party to submit a single sealed bid and agree that it is binding if there is overlap.

the seller writes down the lowest they will accept in an envelope.
then the buyer writes the highest they will pay in a another envelope.
you open them at the same time and if there's overlap then the price is the average of the two numbers.
posted by noloveforned at 12:11 PM on November 11, 2016 [2 favorites]

Response by poster: That's perfect, thanks aubilenon! It'll take me a while to go through the article carefully enough to understand how to do it (and it may turn out that I can't explain it well enough to get the buyer and seller to go along) but it seems to do what I want.

The envelope trick doesn't keep the people from knowing the other side's number, and it enforces the "average of the limits" that neither side wants -- the whole reason buyer & seller are negotiating is because they both think they can do a deal that's more favorable to them than just "split the baby."
posted by spacewrench at 12:55 PM on November 11, 2016

. you open them at the same time and if there's overlap then the price is the average of the two numbers.

That doesn't work, because there's no guarantee the overlap includes the average.
posted by the agents of KAOS at 1:20 PM on November 11, 2016

There is a technique called homomorphic encryption that allows you to perform arithmetic operations on encrypted information, decrypt the result, and get the correct number. I don't know that much about it, but if you can perform a comparison operation on the encrypted numbers and get a true/false result, you don't need to reveal anything other than whether buyers-max > sellers-min
posted by adamrice at 1:25 PM on November 11, 2016

if the overlap doesn't contain the average, there is no overlap.

lowest price buyer will accept = x
highest price seller will pay (assuming there is overlap) = x + y

average of two prices = .5(x) + .5(x+y) = x + .5 y.

if y is positive, which it must be for there to be an overlap then-

x < x + .5 y < x + y
posted by noloveforned at 1:28 PM on November 11, 2016 [2 favorites]

Yeah, good luck getting humans to do that without software assistance. And if they're already trusting software they might as well just have a software where they can secretly type the numbers in and it'll tell them whose is bigger, without saving any logs or whatever.
posted by aubilenon at 2:12 PM on November 11, 2016

First, I think it should be the buyer has a max to pay and the seller a minimum they will take not the way it is written in the question.

Second, there is a presumption that if there is an overlap in the highest the buyer will pay versus the lowest the seller will take that there will be a deal. Even if you know there is an overlap, but not how much, if one side tries to capture too much of the overlap, the other side may balk.

I am sure through some sort of calculation that you could determine without divulging the information to the either side, that there is or is not an overlap. It is over my head, but the above calculations seem likely to be helpful on that front.

In the real world, here is how I overcame the situation while buying a car. I went on line and searched the inventory of the dealer and found a truck I was willing to buy based on the options, color, make, model, etc. I knew every option on the car (but one it turns out). I did a calculation and determined the highest price I was willing to pay. I am disciplined in that I would not pay one dollar higher than what I determined.

I went to the dealer and told the salesman the exact truck on his lot I wanted to buy and that I was leaving the showroom in exactly 30 minutes with or without a deal. I then gave him the option of giving me a take it or leave it number or me giving him a take it or leave it bid. There would be no negotiation. It was a one number negotiation. He chose to hear my take it or leave it number. Makes sense from his standpoint because he might be capturing the overlap that way.

I did not care because I had a price I was willing to pay and it did not matter to me if the dealer captured more than I could squeeze him for. I gave him the number and he said he doubted it, but had to talk to his manager. I told him to play whatever game he wanted, but I was leaving, now in 23 minutes and was not paying one penny more. With 4 minutes to go, he came out and asked if I would pay a higher price. I looked at him, said, "Seriously?" and packed up my stuff and started walking out. I got as far as getting into my car when he banged on the window frantically trying to take my offer. It was now 1 minute past my deadline. I told him my new offer was $100 less than the one he heard 31 minutes ago. He took it on the spot.

Well, what did I learn? There was definitely an overlap. I captured $100 of that overlap. I do not know if there was any more, but when I went to pick up the truck and they tried to charge me for the bedliner they had installed, I told them to take it out. They left it in for the original price so I captured that value too.

My point is that if a buyer is willing to pay an amount or a seller is willing to sell for an amount, what the other party might capture above or below their own best price is not really relevant. If the goal is simply to maximize your own price (or minimize) that is different from the goal being to do a transaction at a price that I am willing to do a transaction.

And, I suspect that in almost every transaction there is an overlap that is captured by one side or the other. If I walk into Carvel on a hot summer day to get a soft serve chocolate cone and the price is say $3.00, the truth is I would probably pay $4.00 and the owner would probably sell it for $2.75 if he was being economically rational. Go to a sporting event or a concert and see how the concessions attempt to capture 100% of the overlap. I would never pay $6 for a can of Old Style in a bar or grocery, but in the bleachers at Wrigley on a hot summer day, $6 is a bargain.
posted by AugustWest at 3:26 PM on November 11, 2016 [5 favorites]

Each person has a sealed box filled with weights equivalent to their bid (I.e. $1234 = 1.234 kg). They put each box onto each side of a pair of scales. Whoever tips the scales had the higher bid. I just made that up and haven't thought it through at all. Alternatively write a simple computer program that both parties can understand even if they're non-technical (e.g. IF(a>b) PRINT "a bid higher" ELSE PRINT "b bid higher"). Perhaps both of these count as a 'trusted third party' but it doesn't have to involve an extra human.
posted by askmeaboutboardgames at 3:47 PM on November 11, 2016

Response by poster: AugustWest is correct: I stupidly switched "buyer" and "seller." And in a real negotiation, you might get into the overlap range and have both sides keep going back and forth, even though either one of them would be happy to stop at any point. (This corresponds to the parties trying to capture more than just half of the overlap.)

The point of doing this (and of the question) is, if there is no overlap, then theoretically you'll never be able to get to a number that one side or the other will stop at, so why bother see-sawing at all? But I suppose realistically, after going back and forth for a while, one side or the other might agree to the other side's number, despite it being lower (or higher) than the "best bid/ask" they thought they would take.

So I suppose there's a point to going back and forth after all, even if you don't know whether there's any overlap.
posted by spacewrench at 4:27 PM on November 11, 2016

Clarification question: after an overlap is established, how do you want the final price to be agreed upon? Some random point in the overlap interval? Should the parties remain ignorant of the true reserve points even after the transaction is complete? Do these two negotiators have future transactions to do, giving them incentives to hide information?

(Side notes: Computer 3rd party does seem to be the easiest way to implement a lot of this :) also, most people aren't rational negotiators and change their true reserve as steps in negotiation increase, due to sunk cost, perceived unfairness, etc.)
posted by gregglind at 4:46 PM on November 11, 2016

Here's more pointers & discussion of the problem in Stack Exchange's crypto forum. Outside my expertise but it may help clarify things for you.
posted by scalefree at 5:29 PM on November 11, 2016

if the overlap doesn't contain the average, there is no overlap.
you're right, I don't know what I was thinking

posted by the agents of KAOS at 8:02 PM on November 11, 2016