Privacy Preserving Tâtonnement
A Cryptographic Construction of an Incentive Compatible
MarketJohn Ross Wallrabenstein and Chris Clifton
Dept. of Computer Science, Purdue University, USA{jwallrab,clifton}@cs.purdue.edu

Abstract. Léon Walras’ theory of general equilibrium put forth the notion of tâtonnement as a process by which equilibrium prices are determined. Recently, Cole and Fleischer provided tâtonnement algorithms forboth the classic One-Time and Ongoing Markets with guaranteed bounds
for convergence to equilibrium prices. However, in order to reach equilibrium, trade must occur outside of equilibrium prices, which violates
the underlying Walrasian Auction model. We propose a cryptographic
solution to this game theoretic problem, and demonstrate that a secure
multiparty computation protocol for the One-Time Market allows buyers and sellers to jointly compute equilibrium prices by simulating tradeoutside of equilibrium. This approach keeps the utility functions of allparties private, revealing only the final equilibrium price. Our approach
has a real world application, as a similar market exists in the Tokyo Commodity Exchange where a trusted third party is employed. We prove thatthe protocol is inherently incentive compatible, such that no party has
an incentive to use a dishonest utility function. We demonstrate security
under the standard semi-honest model, as well as an extension to thestronger Accountable Computing framework.
Keywords. Secure Multi-Party Computation, Privacy Preserving Protocol, Tâtonnement, Game Theory.

1

Introduction

Open markets balance supply and demand by converging to a price where thetwo are equal. For example, oil is a commodity where increasing supply becomes
progressively more expensive, and increasing price reduces demand. Absent otherdisturbing factors, oil supply and demand would eventually stabilize. However,this takes time, and in the meantime prices rise and fall, leading to unnecessary investment in uneconomical production based on an expectation of highprices, or investment in consumption based on expectation of low prices. Fasterconvergence or lower volatility in prices can have significant benefits.
Economic models generally accepted as valid representations of real-world
market behavior tend to have underlying computationally tractable algorithms.
It follows naturally to propose that these algorithms could be evaluated by parties to arrive at the result deemed to accurately reflect the outcome of a givenmarket phenomenon. The work of Cole and Fleischer studies the market equilibrium problem from an algorithmic perspective, and they give tractable priceupdate algorithms that do not rely on global information [7].
The algorithms of Cole and Fleischer [7] follow the Walrasian Auction model:
prices are adjusted according to a tâtonnement process, where prices iteratively
rise or fall in response to changes in demand [27]. In the Walrasian Auction
model, trade occurs only once equilibrium has been established. In real-world
markets, it is trade that dictates demand and, thus, how prices are adjusted
to converge toward equilibrium. However, Cole and Fleischer’s algorithms allow
trade outside of equilibrium.
As specified, the Walrasian Auction model is limited to the theoretical domain unless a trusted third party is invoked to serve as a mediator between thebuyers and sellers. Not only must the mediator be trusted to faithfully represent
the interests of all parties involved, it must be trusted with substantial information about each party’s private utility function. As a utility function defines aparty’s preferences over goods with respect to both quantity and price, it reveals
valuable information that parties would prefer to keep private. Further, there
are no guarantees that the parties will truthfully report their valuations of thegood. This problem becomes particularly pronounced when independent buyers
collude to reduce the final equilibrium price.
The recent work of Dodis et al. [10] considered a similar game theoretic
problem: implementing the mediator for rational players to arrive at a correlated
equilibrium. In game theory, a correlated equilibrium is selected when a mediator recommends a strategy to each player such that, given the recommended
strategy, no player can improve their utility1 by choosing a different strategy.
Further, the payoff may exist outside the convex hull of standard Nash equilibria, yielding more utility than when a mediator is not present. Dodis et al.
demonstrate that secure multiparty computation (SMPC) can replace the mediator with a protocol among the players, removing the necessity of a trusted third
party. In this work, we use SMPC to find Walrasian equilibria without invoking
a mediator or allowing trade to occur prior to arriving at a stable price.
Further, we are able to make strong claims of incentive compatibility. In
the standard security model, a monolithic adversary A corrupts a subset of theparticipants. In rational cryptography, each player acts solely in their own selfinterest, and thus have an associated local adversary controlling their deviations[5]. The move to local adversaries has important consequences on the stability ofcoalitions for rational player. Not even protocols secure in the malicious modelcannot guarantee that a malicious party will not manipulate its input to theprotocol, as a monolithic adversary may force the equilibrium price to be deflated through centralized control of corrupted parties. We demonstrate that our
protocols are resilient against this behavior in the presence of local, independent
rational adversaries seeking to maximize their utility.
1

A utility function describes an agent’s preferences over outcomes, and can informallybe considered a mapping between events and agent happiness.

2

Our Contribution

Drawing on recent work from both the cryptographic and game theoretic literature [1, 16–18, 20–22], we propose a privacy preserving protocol that allows
buyers and sellers to arrive at an equilibrium price using the tâtonnement process
without trade occurring outside of equilibrium. This approach has the auxiliary
benefit of keeping the utility functions of all parties private; only the final equilibrium price is revealed. Further, we show that our construction is incentive
compatible: the strategy of reporting truthful private valuations weakly dominates all other strategies for both buyers and seller.
A protocol that arrives at the equilibrium price for a good is beneficial to boththe buyers and sellers involved. A participant’s utility function must be evaluatedmany times throughout the tâtonnement process in order for appropriate priceupdates to occur. This is a potential disincentive to engaging in the protocol,
as the participant’s utility function contains their preferences for a good, andmany individual points from their utility function are evaluated and publicly
disclosed. A malicious agent could use this information to alter their behavior
for personal gain. SMPC allows two or more mutually distrustful parties toengage in a collaborative protocol to compute the result of a function securely[14, 28]. Our approach allows the tâtonnement process to be evaluated privately,
revealing only the final equilibrium price.
SMPC has had real-world use, very much in the scenario we suggest. Bogetoft
et al. [3] deploy a privacy preserving protocol to evaluate a double auction modelfor Danish commodity trading. However, they assume that all parties behave
honestly in using the system, and do not explore the possibility that a malicious
party could manipulate the equilibrium price to its advantage. In fact, they state“we did not explicitly implement any security against cheating bidders”, although
they were only discussing semi-honest vs. malicious behavior in the traditional
sense. Further, the authors surveyed the farmers’ views on the privacy of theirutility functions, and found that nearly all preferred that information to remain
private.
We go well beyond this, exploring lying about the input to the protocol itself :a behavior that even the malicious model does not prevent. Previous work has
demonstrated this idea, although the authors only consider a two-party protocol,and showed incentive compatibility only for an approximation of the real-world
problem [6]. We show that this approach can be used to enable SMPC to address
the full range of malicious behavior in a real-world, multi-party problem.
As another example, the Tokyo Commodity Exchange uses the itayose mechanism, similar to tâtonnement, to reach equilibrium. In fact, this existing market
circumvents the restriction of disallowed trade until equilibrium is reached by
invoking a trusted third party: an auctioneer that adjusts prices based on excess
demand [11]. Our approach requires no trusted third party, resulting in the minimum possible disclosure of information regarding each party’s utility function.
Thus, there is clear real-world application and tangible benefit from our results,
similar to those of Bogetoft et al. [3].

Note that our model makes a stronger statement than that of a Bayes-Nashequilibrium, where participants have an incentive to be truthful if and only ifothers are acting truthfully as well. We show that acting honestly is the dominant strategy in our protocol regardless of the actions of the other players. The
work by Eaves et al. [11] provides further evidence for our claims of incentive
compatibility, based on the fact that agents engage in the protocol repeatedly.
However, our results hold without the assumption of repeated interaction.
To ensure parties deviating from the protocol will be caught, it is secure under
the accountable computing (AC) framework proposed by Jiang and Clifton [19].
Note that we first show security under the standard semi-honest model, andthen extend this to the AC-framework. The AC-framework provides the ability toverify that a party correctly followed the protocol; contractual penalties can thenbe used to ensure that correctly following the protocol is incentive compatible.
Typical semi-honest protocols provide no such guarantee; a malicious party may
be able to manipulate the protocol to their benefit. Protocols secure under the
malicious model (forcing participants to correctly follow the protocol) typicallyhave much greater computational cost. By demonstrating security under theAC-framework, detected deviations are punishable by other participants forcing
the minmax utility 2 on the deviating parties [10]. We also use commitments toensure that parties use their true utility function with the protocol; this prevents
parties from supplying one input to the protocol (e.g., a low demand) to give an
artificially beneficial price, then purchasing greater quantities at the resulting
price.
We show that the utility functions and actions of all agents remain private,with the equilibrium price revealed to all agents at the conclusion of the protocol.
The knowledge gain is only the information that can be derived from the resultof the function, and knowledge of the function itself. This satisfies the standard
definition of semi-honest security in that the protocol emulates the existenceof a trusted third party, without actually requiring such an entity [13]. This
property is ideal, as a universally trusted third party rarely exists for a given setof parties. Our work considers only the case of the oblivious One-Time Market
setting. That is, we consider the market where all parameters are assumed not
to be global information. Rather, agents compute the price updates based solely
on local information.
We begin by defining the market problem and reviewing the oblivious OneTime Market algorithm in Section 3. We review the cryptographic primitives
used in Section 4, and give a construction3 based on an additively homomorphic
cryptosystem in Section 5. Finally, we demonstrate that the resulting protocol
is incentive compatible in Section 6. All proofs are provided in Appendix A.

2

The minmax punishment approach forces the outcome yielding the minimum utility
to the deviator, while maximizing the utility of the other participants.
3
Our protocol can also be implemented using frameworks for the GMW protocol [14],such as FairPlayMP [2], VIFF [9] or SEPIA [4].

3The Market Problem

Our SMPC protocol computes the equilibrium for a single seller offering a single
good to a set of buyers, which we extend to the general definition of the problem
following the notation from Cole and Fleischer [7]. The market under consideration contains a set of infinitely divisible goods G, where |G| = n, and a setof agents A, where |A| = m. Agent l has quantity wil of good i at the start ofthe protocol and has a corresponding utility function µl (x1l , . . . , xnl ) that gives
their preferences for all goods i ∈ G. Note that the initial allocation wil may
consist solely of currency; it is a measure of the agent’s wealth. We make thensimplifying assumption that µl (x1l , . . . , xnl ) = Σi=1µ(xil ); the utility of a basketof goods is the sum of the utility of each individual good. Each good i has acollection of prices pi , 1 ≤ i ≤ n. Each agent l selects a basket with xil units ofgood i soPthat ul is a P
maximum and is affordable given their initial allocation.
nmThat is: i=1 xil pi ≤ i=1 wil pi . The prices p = (p1 , p2 , . . . , pn ) are in equilibrium if the P
demand for all goods i ∈ G is bounded by the supply for good i:Pmm
l=1 xil ≤l=1 wil .PP
We define wi = l wil to be the supply of good i, and xi = l xil to be
the corresponding demand. We define zi = xi − wi to be the excess
Pdemand ofgood i. At a given set of prices p, the wealth of agent l is vl (p) = i wil pi . By
definition, w is from the market specification while v, x and z are computed withrespect to the vector of prices. The wealth of an agent l is computed directlyfrom a given price vector p, whereas x and z are computed by agents maximizing
their utility functions under the constraints imposed by v.
The model put forth by Cole and Fleischer is based upon a series of iterative
price and demand updates. We omit discussion of the proofs of bounded convergence time and refer the reader to their original work [7]. In each iteration r,
the price of a good i ∈ Gr is updated by its price setter using knowledge of only
pi , zi , and their history. Here, a price setter is a virtual entity that governs theprice adjustments. However, the price adjustments are governed by changes indemand in the algorithms. After the price setters have released the new prices pr ,the buying agents compute the set of goods that maximizes their utility under
the constraint of their wealth given the current prices, vl (p). We consider only
the oblivious One-Time Market price update rule, which is as follows:
zi
})
(1)
wi
The current round r is bounded prior to the start of the protocol by fixing
the terminal round r∗ . At the conclusion of the protocol, we will have computed
the equilibrium price and demand, p∗ and x∗ , respectively.
To construct a privacy preserving protocol, we show how buyers compute
their demand based on the current price pi , and how sellers compute the priceupdate given the demand xi from the buyers. In our privacy preserving protocol,
the buyers compute the update for each round locally to prevent the seller fromlearning intermediate prices. Symmetrically, neither the price nor the demand is
known to either the buyers or seller until the conclusion of the protocol. Finally,pi ← pi · (1 +12dlog4 ri e

· min{1,we must account for the fact that wzii may be less than 1, which cannot be
represented properly in the field Zn . To handle this, prices are represented in
integer units corresponding to the minimum increment (e.g., cents). We use thedivision protocol δ of Dahl et al. [8] to compute wzii , which we discuss further
in Section 4.1. As the degree of Walrasian auction utility functions is 1 withoverwhelming probability [27], all buyers are modeled as having Cobb-Doublas
utility functions. As noted by Cole and Fleischer, under these conditions theprice update rule converges in a single round [7], so r∗ ← 1.
Our work is certainly not the first to apply SMPC principles to economic
and game theory. Previous work has shown that SMPC removes potential disincentives from bartering to auctions [12, 23]. Additionally, recent work has shown
the potential of combining cryptography with game theoretic principles [1, 16–
18, 20–22]. However, no attempt has been made to remedy the paradox of theWalrasian Auction model using SMPC techniques. In this way, we not only remove disincentives from engaging in the protocol, we allow the model to exist
in reality. That is, our protocol allows the participants to evaluate the iterative price update function on the basis of the buyers’ demand without actually
revealing the demand through trade or invoking a trusted third party. Additionally, we show that our construction constitutes an incentive compatible market
with respect to both buyers and sellers.
We review the One-Time Market Oblivious tâtonnement algorithm proposedby Cole and Fleischer [7]. The original algorithm is a protocol between a set ofbuyers bl ∈ B and a set of sellers sl ∈ S. We assume that for each buyer bl ∈ B
they have an associated utility function µbl (i), where i is the good offered forsale from S. Recall that the seller S has knowledge of their supply of i, given
by wi . The task of the set of buyers B is to compute the excess demand forgood i, given by zi = xi − wi , where xi = Σl xil is the sum of the demand of all
buyers bl ∈ B. The original protocol by Cole and Fleischer is given formally by
Algorithm 1.

Algorithm 1 Model by Cole and Fleischer
for ri = 0; ri < r; + + ni dofor sl ∈ S dopi ← pi + 2dlog14 ri e pi · min{1, wzii }end forfor all bl ∈ B do
xi ← xi + µbl (pi )end forzi ← x i − w i
end forp∗ = pix∗ = xi
return (p∗ , x∗ )The algorithm fixes a price pi for the good, uses the utility functions of thebuyers to determine the excess demand xi at that price, and sets the price for the
next round. The key contribution of Cole and Fleischer is to prove that the given
update rule gives a guaranteed convergence rate. Beyond simply bounding thenumber of required rounds, as Walrasian markets typically have Cobb-Douglas
utility functions, the algorithm converges in one round [7].

4

Building Blocks

To build the privacy preserving protocol, we build on a collection of cryptographic primitives.
We require an additively homomorphic public-key encryption scheme E, withthe additional property of semantic security [15]. Such a scheme was proposed
by Paillier [25]. We denote the encryption of some plaintext x with Bob’s public
key as Eb (x), and the decryption of some ciphertext c = Eb (x) as Db (c). We
require that our cryptosystem’s homomorphic property is additive, which meansthat the following operations are supported:
Eb (x) · Eb (y) = Eb (x + y),(Eb (x))c ≡ Eb (x)c = Eb (x · c)(2)Here, c is an unencrypted plaintext constant. Note that we omit the enclosing
parentheses and treat Eb (x) as a distinct term. The construction of the additively
homomorphic encryption scheme allows mathematical operations over encrypted
data to be performed, and provides the foundation for our protocol.
4.1

Division Protocol δ

The price update rule requires computing the quotient of the excess demand and−wi. Dahl et al. give a protocol for securely computing integer dithe supply, xiw
ivision under the Paillier cryptosystem without requiring a bit-decomposition [8].
For l-bit values, the constant round protocol requires O(l) arithmetic operationsin O(1) rounds.

5

Protocol Construction

We consider a set of k buyers bl ∈ B interacting with a single seller S of a goodi. The protocol π securely implements the functionality f (µ1 , · · · , µk , pS ) 7→
hp∗ , x∗ i. Here, µl is the utility function of buyer bl ∈ B. The full WalrasianMarket (composed of more than a single seller and good) is modeled by instantiating an instance of Protocol 5.1 for each pair of seller and good (S, i), and theassociated set of buyers. Note that our protocol centers around specific utility
functions known as Marshallian or Walrasian demand functions. That is, theparticipant’s utility function is modeled as a polynomial, and defines the quantity demanded for a single good over all possible prices. Overwhelmingly, thedegree of a Walrasian demand function will be one [27]. Thus, a buyer’s utility

function µbi has the form µbi (pi ) = cpi where the coefficient c is a constant,satisfying the definition of a Cobb-Douglas utility function. The final argument
to the functionality is the initial price pi specified by the seller. A Paillier-basedalgorithm for computing the Walrasian equilibrium is given by Protocol 5.1. To
increase scalability, this simple ring-based protocol could be replaced with an
implementation using a state-of-the-art framework for the GMW protocol [14],such as FairPlayMP [2], VIFF [9] or SEPIA [4]. We defer the proof of security
to Appendix A.

Buyers 1 ≤ l ≤ k: All buyers issue commitments (e.g. Pedersen [26]) to their private
utility function coefficients. This is necessary for the verification
stage of the AC-Framework [19].
Seller S:
Set pi as the Seller’s initial price for good i.
Set wi as the supply of good i.
Send ES (pi ) to all buyers.
Buyer 1 :The first buyer computes the initial demand as ES (xi ) ←µb1 (ES (pi ))† , where µb1 is the initial buyer’s utility function.
The first buyer forwards ES (xi ) to the next buyer, so that they
can update the demand xi based on their utility function.
Buyers 1 < l ≤ k: Each buyer updates the demand at the current price pi based on
their utility function µbl by computing ES (xi ) ← µbl (ES (pi ))† .
Buyer k:
The final buyer bk must perform additional updates before sending the results of the current round to either buyer 1 (if r < r∗ )or the seller (if the terminal round r∗ has been reached).
The final buyer updates the excess demand zi by computing
ES (zi ) ← ES (xi ) · ES (wi )−1 .
The final buyer computes the price update coefficient yi ..= wzii ,the fraction of excess demand to supply, using the division protocol of Dahl et al. [8]: yi ← δ(ES (zi ), ES (wi )).
by
The final buyer updates the current round price pri to pr+1icomputing ES (pr+1) ← ES (pri ) · ES (yi ).
i
If r = r∗ , where r∗ is the final round, buyer bk sends
hES (pi ), ES (xi )i to the seller. Otherwise, this tuple is forwarded
to buyer 1 and the next round begins.
Seller S:
After receiving hES (pi ), ES (xi )i in the final round, the seller computes the equilibrium price p∗ ← DS (ES (pi )) and the final demand x∗ ← DS (ES (xi )).
The seller forwards p∗ to all of the buyers.
Protocol 5.1. Additively Homomorphic Encryption Algorithm for Tâtonnement

In the next section, we prove that if a player is unable to deviate from theprotocol without being caught (e.g., a protocol secure in the AC-Framework),then the dominant strategy is for parties to provide their true utility functions.
†Here, we evaluate µbl (ES (pi )) as ES (pi ) · ES (c), where c is the buyer’s coefficientterm in µbl .

6Incentive Compatibility

We claim that Protocol 5.1 is inherently incentive compatible with respect toprotocol inputs from the perspectives of both buyers and sellers. That is, eachplayer has no incentive to maliciously modify their actual input (utility function).
We assume that malicious buyers have the option to either inflate or deflate theirdemand for a given price relative to their actual utility function. We show thatwhile this can influence the price, it works to their detriment. We demonstratethat a seller only sets the initial price, and that their choice does not affect the
final equilibrium price, so deviating provides no utility gain.
6.1

Utility Function Assumptions

In order to simplify the game theoretic analysis of the protocol, we write µ+ todenote positive utility, µ− to denote negative utility, and µ0 to denote neutral
utility gain. We assume that the magnitude of preference for all µi are equal(i.e., µ+ + µ− = µ0 ). Similarly, we assume that µ represents only a marginalutility gain. That is, µ+ > µ > µ0 .
Additionally, we assume that (pi − p∗i ) ∈ {µ+ , µ− , µ }, although this value
depends on how much the reported utility function µ∗l differs from an agent bl ’s
actual utility function µl . Clearly there is an inverse relationship between how
much an agent can under-inflate µ∗l (which subsequently reduces the equilibrium
price p∗i ), and the likelihood of a trade occurring between the agent and the seller.
As the agent is involved in the protocol, we assume that they prefer a trade occur.
If not, they would have abstained from the protocol entirely. Thus, it is natural
to assume the agent’s utility function assigns the same range to both of these
preferences. This assumption does not affect our analysis, and is solely to ease
the exposition.
Definition 1. Let rl be the reward that a buyer bl gains by reporting µ∗l in lieu
of their actual utility function µl . Where p∗i (resp. pi ) is the resulting equilibrium
price when µ∗l (resp. µl ) is reported, bl ’s reward is given by: (pi − p∗i ) < 0 : µ∗l > µl
: µ∗l = µlrl = 0∗(pi − pi ) > 0 : µ∗l < µl(3)

We make the natural assumption that each buyer prefers some (possibly
large) quantity of the seller’s good to their initial allocation, otherwise theywould not engage in the protocol.
Definition 2. Define the utility gained through trade as µτ :

µτ =

µ+
: trade occurs
τ
µ−
:
trade
does
not occur
τ

(4)

Similarly, a buyer offering a higher price has increased control over the quantity of the good they can demand, subject to the seller’s supply wi . That is, theseller prefers to sell to the set of buyers {bl |pli ≥ pm
i , l 6= m} offering the highest
price. Thus, a highest price buyer bm can command min(wi , wm ) units of goodi, where wi is the seller’s supply and wm is the initial allocation of resources forbuyer bm .
Definition 3. Define buyer bl ’s utility gained from control over quantity received, µq,l , as follows:µq,l =lmµ+q,l : ∀m, pi > pi , l 6= m−l
µq,l : ∀m, pi ≤ pm
i , l 6= m

(5)−That is, bl receives µ+q if bl is offering the highest price pi , and µq otherwise.

Definition 4. Let rl be the reward for buyer bl , let µτ,l be bl ’s trade utility, andlet µq,l be bl ’s quantity control utility. We define bl ’s total reward ρl as follows:ρl = rl + µτ,l + µq,l(6)Without loss of generality, consider a coalition of buyers with utility functions satisfying the above constraints. Let al = {au , at , ao } denote bl ’s action set,
where au denotes under-inflating, ao denotes over-inflating, and at denotes reporting the buyer’s true utility function ul rather than a modified utility functionu∗l .
We assume that a rational seller will agree to sell their entire allocation of
goods to the buyer whose utility function ub gives the highest valuation for the
good, thus maximizing their profit. Thus, for all buyers bk ∈/ {bl |pli ≥ pm
i , l 6= m},−
we have that µτ,k = µq,k = µ . Note the following:– A buyer playing au in the presence of a buyer playing {at , ao } does not havequantity control– A buyer playing au in the presence of a buyer playing {at , ao } does notreceive any goods– A unique buyer playing {at , ao } in the presence of buyers playing only au
has quantity control
We begin by reviewing the formal definition for weakly dominated strategies
as given by Katz [20], where a player can never increase their utility by playing
a weakly dominated strategy.
Definition 5. Given a game Γ = ({Al }kl=1 , {µl }kl=1 ), where A = A1 × · · · × Ak
is a set of actions, with a = (a1 , . . . , ak ) ∈ A being a strategy and {µl } is a set
of utility functions, we say that action a0l ∈ Al is weakly dominated by al ∈ Al
if µl (al ) ≥ µl (a0l ). That is, player Pl never improves their payoff by playing a0l ,but can sometimes improve their payoff by playing al .

To show that our construction is incentive compatible, we iteratively delete
weakly dominated strategies to arrive at the stable Nash equilibrium [24]. The
process of iteratively deleting weakly dominated strategies is criticized because,in some cases, the order of deletion affects the final result [21]. In this analysis, weakly dominated strategies can be removed in an arbitrary order without
affecting the result.
We present a simplified payoff matrix in Table 1. The strategy ao of overinflating the utility function is removed for clarity, as au , the strategy of underinflating, is a much more intuitive deviation for maximizing utility. However, weformally demonstrate that ao is weakly dominated in lemma 1.
Table 1. Total Payoff Matrix

a0u
+

a0t
+

−

au (µ ,µ ) (µ ,2µ+ )at (2µ+ ,µ− ) (µ+ ,µ+ )Lemma 1. The strategy ao of reporting an over-inflated utility function u∗i isweakly dominated by at .
Proof. We show that the action of over-inflating the buyer’s true utility function
is weakly dominated by truthfully reporting the utility function, demonstratingthat ao is weakly dominated by at . Recall that buyer bl ’s total reward is definedas ρl = rl +µτ,l +µq,l . For convenience, we will parameterize ρl (·) with the action
being played. This notation is convenient for comparing the total payoff yieldedfrom different actions.
We begin by deriving the maximum utility that could be gained by playing
ao , the action of over-inflating the true utility function. As buyer bl is playing ao ,we have that µ∗l > µl . From Equation 3, we have ρl (ao ) = (pi −p∗i )+µτ,l +µq,l . As
(pi − p∗i ) < 0, we write µ− for concreteness. Given that bl is over-inflating theirtrue utility function µl , they are more likely to effect a trade. Clearly the seller S
prefers the higher price p∗i to bl ’s true valuation, pi . By Equation 2, we have thatρl (ao ) = µ− +µ+τ,l +µq,l . Similarly, by over-inflating their true utility function, bl
is more likely to have control over the quantity of the good they receive, as they
are offering a higher price. By Equation 3, we have that: ρl (ao ) = µ− + µ+
τ,l +
+
+
+
µq,l = µ . Thus, we have that max(µl (ao )) = µ . We now derive the maximum
utility that could be gained by playing at , where buyer bl reports the true utility
function µl . By Equation 3, we have that ρl (at ) = µ0 + µτ,l + µq,l as pi = p∗i so(pi − p∗i ) = µ0 . Buyer bl maximizes their utility when a trade occurs, and they
can control the quantity of the good they receive. Following the same derivationthat was used for ao , we have from Equation 2 that ρl (at ) = µ0 + µ+
τ,l + µq,l .
++Similarly, by Equation 3 we have that ρl (at ) = µ0 + µ+
+
µ
=
2µ
.
We haveτ,lq,lthat max(µl (at )) = 2µ+ , and it follows that max(µl (at )) > max(µl (ao )). Thus,a buyer always does at least as well or better by playing at , and we say that at
weakly dominates strategy ao .
Lemma 2. The strategy au of reporting an under-inflated utility function u∗l is
weakly dominated by at .
Proof. We demonstrate that the action au is weakly dominated by at when
considering both individual buyers and members of a buyer coalition that collude
to lower the equilibrium price p∗ .
Consider an individual buyer bl that is not a member of a coalition. As bl
reports µ∗l , µ∗l < µl , by Equation 3 we have that ρl (au ) = (pi − p∗i ) + µτ,l + µq,l .
Again, as (pi − p∗i ) > 0, we assume (pi − p∗i ) = µ+ for concreteness. Similarly, we
assume that under-inflating µl reduces the chances of bl effecting a trade with S,
as bl is offering a lower price. By Equation 2, we have that ρl (au ) = µ+ µ−
τ,l +µq,l .
Playing action au also reduces the chances of bl having control over the quantityof the good received, if any is received at all. By Equation 3, we have that−−−ρl (au ) = µ+ µ−
τ,l + µq,l = µ . Thus, max(µl (au )) = µ , and it follows thatmax(µl (at )) > max(µl (au )). Thus, a (non-coalition) buyer always does at least
as well or better by playing at , and we say that at weakly dominates strategy
au .
We now consider a coalition of unique buyers under-reporting µl as µ∗l < µl ,colluding to decrease the resulting equilibrium price p∗ of the good. That is,the coalition is not controlled by a monolithic adversary as is common in thestandard security model: they are independent buyers in competition, modeled
under the local adversary framework of Canetti [5]. In the game theoretic literature, this is referred to as the cartel problem. Note that the best response of any
member of the coalition is to report µ∗l +  for any positive . In doing so, theyreceive the goods at a price p0 < p∗ while the other coalition members receive nogoods. Applying backward induction, we demonstrate that the best response of
all buyers in a coalition is to report µl , as µ∗l +  converges to their true utility
function µl .
Suppose all coalition members agree to collude by reporting µ∗l < µl , and all
members play this strategy. For any buyer bl in the coalition, we have that µ∗l <µl and by Equation 3 we have that ρl (au ) = (pi −p∗i )+µτ,l +µq,l . As (pi −p∗i ) > 0,
we set (pi − p∗i ) = µ+ to denote a positive utility gain. As the coalition consistsof more than a single buyer, all members of the coalition are more likely to effecta trade. From Equation 2, we have that ρl (au ) = µ+ + µ+
τ,l + µq,l . However, as
all members of the coalition are offering the same price for the good, they haveno control over the quantity of the good they receive. By Equation 3, we have−++that ρl (au ) = µ+ + µ+
τ,l + µq,l = µ . Thus, max(µl (au )) = µ for all coalition
members. However, consider the case where a coalition member reports a utility
function µ0l = µ∗l + ,  > 0. That is, some bl in the coalition increases the pricethey are willing to pay for the good by any positive amount . From Equation
3, we have thatρl (au + ) = ((pi − (p∗i + )) + µτ,l + µq,l = µ(+)− + µτ,l + µq,l

However, now bl is more likely to effect a trade, as p∗i +  > p∗i . By Equation 2,
we have that ρl (au + ) = µ(+)− + µ+
τ,l + µq,l . Similarly, bl has control over thequantity of the good received as bl is offering  more than the coalition members.
From Equation 3, we have++ρl (au + ) = µ(+)− + µ+
τ,l + µq,l > 2µ > max(µl (au ))Thus, max(µl (au + )) > max(µl (au )), as µ(+)− = µ+ + µ− > µ0 . However, allcoalition members are aware of this fact. Applying backward induction, it is notdifficult to see that action au converges to at by increasing  until µ∗l = µl , andthat at weakly dominates au .
Corollary 1. The strategy at of reporting the true utility function ul weakly
dominates {au , ao } for all buyers.
Proof. A buyer’s action set is defined as al ∈ {au , at , ao }. By lemma 1, we havethat ao is a weakly dominated strategy, and can be eliminated. By lemma 2,
we have that au is a weakly dominated strategy, and can be eliminated. Thus,
reporting the true utility function µl as denoted by action at is a stable Nashequilibrium.
Theorem 1. The strategy at of reporting the true utility function ul weakly
dominates {au , ao } for the seller.
Proof. As noted in the original paper, the update protocol converges on theequilibrium price p∗ from any arbitrary initial price pi [7]. Given that the seller’s
only influence on the equilibrium price is through setting the initial price pi ,there is no incentive to report some p0i 6= pi , as p∗ is unaffected in doing so.

7

Conclusion

We have presented a privacy preserving, incentive compatible market construction that is secure against malicious parties, going beyond the standard security
model to protect against malicious input to the protocol. To do this, we demonstrated that by securely computing the Oblivious One-Time Market protocol
given by Cole and Fleischer [7], no agent has an incentive to report false valuations of the goods in the market. Thus, SMPC solves a long-standing problem in
economic theory, as it allows Léon Walras’ tâtonnement process for arriving at
equilibrium to be computed while conforming to the constraints of the WalrasianAuction model. In this way, trade does not occur outside of equilibrium, and yet
the final equilibrium price is computed and made available to all agents in themarket.

References
1. Asharov, G., Canetti, R., Hazay, C.: Towards a game theoretic view of secure computation. In: Proceedings of the 30th Annual international conference on Theory
and applications of cryptographic techniques: advances in cryptology. pp. 426–445.
EUROCRYPT’11, Springer-Verlag, Berlin, Heidelberg (2011)

2. Ben-David, A., Nisan, N., Pinkas, B.: Fairplaymp: a system for secure multi-party
computation. In: Proceedings of the 15th ACM conference on Computer and communications security. pp. 257–266. CCS ’08, ACM, New York, NY, USA (2008)
3. Bogetoft, P., Christensen, D., Damgärd, I., Geisler, M., Jakobsen, T., Krigaard, M.,
Nielsen, J., Nielsen, J., Nielsen, K., Pagter, J., Schwartzbach, M., Toft, T.: Secure
multiparty computation goes live. In: Dingledine, R., Golle, P. (eds.) Financial
Cryptography and Data Security, Lecture Notes in Computer Science, vol. 5628,
pp. 325–343. Springer Berlin Heidelberg (2009)
4. Burkhart, M., Strasser, M., Many, D., Dimitropoulos, X.: Sepia: privacy-preserving
aggregation of multi-domain network events and statistics. In: Proceedings of the
19th USENIX conference on Security. pp. 15–15. USENIX Security’10, USENIX
Association, Berkeley, CA, USA (2010)
5. Canetti, R., Vald, M.: Universally composable security with local adversaries. In:
Visconti, I., Prisco, R. (eds.) Security and Cryptography for Networks, Lecture
Notes in Computer Science, vol. 7485, pp. 281–301. Springer Berlin Heidelberg(2012)
6. Clifton, C., Iyer, A., Cho, R., Jiang, W., Kantarcıoğlu, M., Vaidya, J.: An approach
to identifying beneficial collaboration securely in decentralized logistics systems.
Management & Service Operations Management 10(1), 108–125 (Winter 2008),
http://dx.doi.org/10.1287/msom.1070.0167
7. Cole, R., Fleischer, L.: Fast-converging tatonnement algorithms for one-time andongoing market problems. In: STOC ’08: Proceedings of the 40th annual ACM
symposium on Theory of computing. pp. 315–324. ACM, New York, NY, USA(2008)
8. Dahl, M., Ning, C., Toft, T.: On secure two-party integer division. In: Keromytis,
A. (ed.) Financial Cryptography and Data Security, Lecture Notes in Computer
Science, vol. 7397, pp. 164–178. Springer Berlin Heidelberg (2012)
9. Damgård, I., Geisler, M., Krøigaard, M., Nielsen, J.B.: Asynchronous multiparty
computation: Theory and implementation. In: Jarecki, S., Tsudik, G. (eds.) Public
Key Cryptography. Lecture Notes in Computer Science, vol. 5443, pp. 160–179.
Springer (2009)
10. Dodis, Y., Halevi, S., Rabin, T.: A cryptographic solution to a game theoretic
problem. In: Bellare, M. (ed.) Advances in Cryptology CRYPTO 2000, Lecture
Notes in Computer Science, vol. 1880, pp. 112–130. Springer Berlin Heidelberg(2000)
11. Eaves, J., Williams, J.C.: Walrasian ttonnement auctions on the tokyo
grain exchange. Review of Financial Studies 20(4), 1183–1218 (2007),
http://EconPapers.repec.org/RePEc:oup:rfinst:v:20:y:2007:i:4:p:1183-1218
12. Frikken, K., Opyrchal, L.: Pbs: Private bartering systems. In: Financial Cryptography and Data Security: 12th International Conference, FC 2008, Cozumel, Mexico, January 28-31, 2008. Revised Selected Papers. pp. 113–127. Springer-Verlag,
Berlin, Heidelberg (2008)
13. Goldreich, O.: Foundations of Cryptography, vol. 2. Cambridge University Press(2004)
14. Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: STOC
’87: Proceedings of the nineteenth annual ACM symposium on Theory of computing. pp. 218–229. ACM, New York, NY, USA (1987)
15. Goldwasser,
S.,
Micali,S.:
Probabilistic
encryption.
Journalof Computer and System Sciences 28(2), 270 – 299 (1984),
http://www.sciencedirect.com/science/article/B6WJ0-4B4RWB917/2/3926c7a6afdab2e2dda0b6fdead72b4e

16. Gradwohl, R., Livne, N., Rosen, A.: Sequential rationality in cryptographic protocols. In: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations ofComputer Science. pp. 623–632. FOCS ’10, IEEE Computer Society, Washington,
DC, USA (2010)
17. Halpern, J.Y., Pass, R.: Game theory with costly computation. Proceedings of the
Behavioral and Quantitative Game Theory on Conference on Future Directions
BQGT 10 pp. 1–1 (2008)
18. Izmalkov, S., Micali, S., Lepinski, M.: Rational secure computation and ideal mechanism design. In: Proceedings of the 46th Annual IEEE Symposium on Foundationsof Computer Science. pp. 585–595. FOCS ’05, IEEE Computer Society, Washington, DC, USA (2005)
19. Jiang, W., Clifton, C.: Ac-framework for privacy-preserving collaboration. In: Proceedings of the Seventh SIAM International Conference on Data Mining, April
26-28, 2007, Minneapolis, Minnesota, USA. SIAM (2007)
20. Katz, J.: Bridging game theory and cryptography: Recent results and future directions. In: Canetti, R. (ed.) TCC. Lecture Notes in Computer Science, vol. 4948,
pp. 251–272. Springer (2008)
21. Kol, G., Naor, M.: Games for exchanging information. In: Proceedings of the 40th
annual ACM symposium on Theory of computing. pp. 423–432. STOC ’08, ACM,
New York, NY, USA (2008), http://doi.acm.org/10.1145/1374376.1374437
22. Lysyanskaya, A., Triandopoulos, N.: Rationality and adversarial behavior in multiparty computation. In: Dwork, C. (ed.) CRYPTO. Lecture Notes in Computer
Science, vol. 4117, pp. 180–197. Springer (2006)
23. Naor, M., Pinkas, B., Sumner, R.: Privacy preserving auctions and mechanism
design. In: EC ’99: Proceedings of the 1st ACM conference on Electronic commerce.
pp. 129–139. ACM, New York, NY, USA (1999)
24. Nash, J.: Non-Cooperative Games. The Annals of Mathematics 54(2), 286–295(Sep 1951)
25. Paillier, P.: Public-key cryptosystems based on composite degree residuosity
classes. In: EUROCRYPT’99: Proceedings of the 17th international conference on
Theory and application of cryptographic techniques. pp. 223–238. Springer-Verlag,
Berlin, Heidelberg (1999)
26. Pedersen, T.: Non-interactive and information-theoretic secure verifiable secretsharing. In: Feigenbaum, J. (ed.) Advances in Cryptology CRYPTO 91, Lecture Notes in Computer Science, vol. 576, pp. 129–140. Springer Berlin Heidelberg(1992)
27. Walras, L.: Élements d’Economie Politique or Elements of Pure Economics; translated by William Jaffe (1874)
28. Yao, A.C.: How to generate and exchange secrets. In: SFCS ’86: Proceedings ofthe 27th Annual Symposium on Foundations of Computer Science. pp. 162–167.
IEEE Computer Society, Washington, DC, USA (1986)

A

Security under the AC-Framework

The Accountable Computing (AC) -framework [19] considers adversaries in the
gap between the semi-honest and malicious models. The AC-framework guarantees that an honest party can catch malicious behavior (unlike Aumann’s covert
model, which requires that such behavior be caught); honest parties can choose
not to verify that behavior is correct (thus saving computation), verify if they

do not trust the results, or probabilistically verify sufficiently often to ensure
incentives for correct behavior. We now show that our protocol satisfies the conditions necessary under the AC-framework. As part of this, we formally provethat the protocol is secure under the semi-honest model (Theorem 2), as security
under the standard semi-honest model is a requirement for satisfying security
under the AC-Framework.
The definition as given by Jiang and Clifton [19] is as follows:
Definition 6. (AC-protocol) An AC-protocol Φ must satisfy the following threerequirements:
1. Basic Security: Without consideration of the verification process, Φ satisfies the security requirements of a SSMC-protocol (a SMC-protocol secure
under the semi-honest model).
2. Basic Structure: The execution of Φ consists of two phases:– Computation phase: Compute the prescribed functionality and store
information needed for the verification process.
– Verification phase: An honest party (we name such a party as a prover
hereafter) can succeed in verifying an accountable behavior.
3. Sound Verification: Φ is sound providing that the verification phase cannot
be fabricated by a malicious party.
We now demonstrate that Φ satisfies all requirements of the AC-framework.
Theorem 2. Basic Security Given an adversary A’s private inputs IA andoutput OA , A’s view of the protocol can be efficiently simulated.
Proof. We follow the simulation proof of semi-honest security characterized byGoldreich [13]. Consider the case where A is a buyer. With the exception of A’s
private input and the result of Φ, all messages are encrypted with the seller’s
public key of an additively homomorphic encryption scheme E. It follows naturally that a simulator could generate and send a series of random elements inZ∗n2 to A. The encryption scheme E is semantically secure, which implies that
A is unable to distinguish the random elements of Z∗n2 from true encryptions.
Thus, A’s view of Φ is efficiently simulatable. Consider next the case where A
is the seller. A sees only the final message ES (pi ), which is the output of the
protocol. Thus, OA = ES (pi ) can be efficiently simulated by encrypting the final result pi with the seller’s public key (known to the seller/simulator) to get
ES (pi ). Thus, Φ does not reveal any additional information to A through theintermediary messages.
Lemma 3. (Basic Structure: Computation) Φ stores sufficient information to
support the verification phase.
Proof. In the case of the seller S, the initial price pinitial as well as all internalcoin tosses used for encryption are stored. In the case of a buyer, the committed(e.g. Pedersen’s scheme [26]) coefficients, all encrypted price updates, as well as
all internal coin tosses are stored.

Lemma 4. (Basic Structure: Verification) An honest party in Φ can succeed inverifying an accountable behavior while revealing only that information in β.
Proof. Let TΦ represent the entire protocol transcript. Consider the case where
an honest buyer bl wishes to demonstrate accountable behavior. In this case,all intermediate prices pi are revealed. A verifier uses the internal coin tosses of
bl to reconstruct ES (µbl (pi )). For each committed coefficient cl , we reconstructt
ES (µbl (pi )) ∈ TΦ by computing Πj=1
ES (cl )pi using the internal coin tosses of
bl . The encryptions of ES (µbl (pi )) will have identical representations in Z∗n2 , asthey were generated with the same randomness. Thus, the encrypted elements
can be compared bitwise for equality. If the price updates of bl ∈ TΦ matchthe reconstructed values, bl demonstrates accountable behavior. Consider thecase of the seller S. A seller needs to demonstrate that the final decrypted pricepr = DS (ES (pr )) in the final round is equal to the reported final price p∗r . Anyverifier can compute a seller verification value VS = ES (R2 ·(R1 −pr )) = (ES (pr )·ES (−R1 ))R2 , where R1 , R2 are chosen uniformly at random from Zn , and ask S
to decrypt the value. If R2 · (R1 − pr ) = R2 · (R1 − p∗r ), the seller demonstrates
accountable behavior. Each buyer signs ES (pr ) to prevent a dishonest buyer
from recanting in order to falsely implicate an honest seller.
Theorem 3. Φ satisfies the sound verification phase.
Proof. Consider the case of a malicious buyer bm . If any of bm ’s price updates
were not computed using the committed coefficients of bm ’s utility function, thereconstructed encrypted update will not match the update in TΦ . Further, there
does not exist a series of coin tosses that allow bm to represent an altered update
ES (µ∗bm (pi )) as the actual update ES (µbm (pi )) ∈ TΦ , as this would prevent
deterministic decryption.Thus, no malicious buyer bm can forge a legitimate
verification. In the case of a malicious seller Sm , the blinded value of pr prevents
Sm from constructing a response VS0 6= VS such that some p∗r can be reported inlieu of the actual equilibrium price pr .
Theorem 4. Basic Structure (buyer) Let Φ represent Protocol 5.1 for the
Walrasian Auction problem. Assuming an honest majority, an honest buyer canbe verified by any honest party (including an independent verifier) other than theseller.
Proof. The verifier is provided with the commitment of coefficients by all buyers(with the majority agreeing). The buyer bl being verified provides their input andoutput values of each round; the following buyer bl+1 also provides their input
for each round. bl also provides the random value used in encryption during eachround. The verifier can then duplicate the calculations of bl , ensuring that theoutput of each round is consistent with the committed coefficients. If not, bl isdishonest.
If the output reported by bl does not match the input reported by bl+1 , theneither bl is dishonest, or bl+1 is reporting an incorrect value to the verifier. In
the latter case, bl+1 can be required to verify, if it succeeds, then bl is dishonest.

Theorem 5. Sound Verification (buyer) A rational malicious buyer bl cannot fabricate verification provided bl+1 is honest.
Proof. If bl+1 correctly reports the value received from bl , then bl must provide
the same value to the verifier, and this must be the value generated from bl ’s
input. Generating this input from the output violates the assumption that theencryption is semantically secure. If bl uses an incorrect input in the protocol(thus generating a matching output, but not following the protocol), the actual
value and thus the impact on the outcome is completely unpredictable due tothe security of the encryption, violating the assumption of a rational party.
Lemma 5. Φ computes the equilibrium value of the Walrasian Auction modeland stores sufficient information for verification to occur.
Proof. Note that given the set V = {ES (pinitial ), ES (winitial )} and the seller S’s
private decryption key DS , the entire protocol can be executed by a participatingparty. By revealing DS , the seller only exposes the verification set V and no otherprivate data. Given this, the participating-party can verify the correctness of theoutput of Φ by retrieving the demand xi −xp from the remaining buyers througha trivial protocol (where xp is the demand of the participating-party performing
the verification). The participating-party is thus able to execute Φ to verify thecorrectness of the equilibrium price p∗ .
Theorem 6. Accountability (seller) A rational seller S will not behave dishonestly in Φ.
Proof. This follows from the proof of Theorem 1, as the seller’s input has noeffect on the final equilibrium price.
Given the previous two lemma’s, we can conclude that Φ satisfies the Basic
Structure condition.
Theorem 7. Sound Verification The verification phase of Φ cannot be fabricated by a malicious party.
Proof. At the beginning of Φ, the seller S distributes the set V , where V ={ES (pinitial ), ES (winitial )} to all buyers b ∈ B. It follows naturally that once
this commitment is made, the seller is unable to alter the commitments. Should
the seller provide an erroneous decryption key DS∗ 6= DS , the commitments will∗
decrypt to values p∗initial 6= pinitial and winitial
6= winitial which defeats theseller’s intention to fabricate the verification. Thus, we can conclude that theseller cannot succeed in fabricating the result of the verification process.
With this, we can conclude that our protocol is secure under the AC-framework,
thus enabling malicious behaviour to be caught and contractual incentives put
into place to ensure that semi-honest behavior is incentive compatible.