# digital_good_exchange__194e108f.pdf

Digital Good Exchange

Wenyi Fang and Pingzhong Tang and Song Zuo Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China

{fangwythu, kenshinping, songzuo.z}@gmail.com

Over the past decade, computer-automated barter exchange has become one of the most successful applications at the intersection of AI and economics. Standard exchange models, such as house allocation and kidney exchange cannot be applied to an emerging industrial application, coined digital good exchange, where an agent still possesses her initial endowment after exchanging with others. However, her valuation toward her endowment decreases as it is possessed by more agents. We put forward game theoretical models tailored for digital good exchange. In the first part of the paper, we first consider a natural class of games where agents can choose either a subset of other participants items or no participation at all. It turns out that this class of games can be modeled as a variant of congestion games. We prove that it is in general NP-complete to determine whether there exists a non-trivial pure Nash equilibrium where at least some agent chooses a nonempty subset of items. However, we show that in a subset of games for single-minded agents with unit demand, there exist non-trivial Pure Nash equilibria and put forward an efficient algorithm to find such equilibria. In the second part of the paper, we investigate digital good exchange from a mechanism design perspective. We ask if there is a truthful mechanism in this setting that can achieve good social welfare guarantee. To this end, we design a randomized fixed-price-exchange mechanism that is individually rational and truthful, and for two-player case yields a tight log-approximation with respect to any individually rational allocation.

1 Introduction Over the past decade, computer-automated barter exchanges have become one of the most successful applications at the in-

This work was supported by the National Basic Research Program of China Grant 2011CBA00300, 2011CBA00301, the Natural Science Foundation of China Grant 61033001, 61361136003, 61303077, 61561146398, a Tsinghua Initiative Scientific Research Grant and a China Youth 1000-talent program.

tersection of AI and economics. In the stylized model, agents enter the exchange with some endowments and exchange their endowments for better allocations without monetary transfers. Standard examples include house allocation [Shapley and Scarf, 1974; Abdulkadiro glu and S onmez, 1998; 1999], kidney exchange [Roth et al., 2004; 2005; Abraham et al., 2007; Unver, 2010] and such applications have been extended to the domain of lung exchanges [Luo and Tang, 2015] and U.S. military contract [S onmez and Switzer, 2013].

Standard models of barter exchanges have certain limitations. For one, agents lose ownerships of their endowments once the exchange takes place. This is not the case with exchanges of digital goods [Goldberg et al., 2001; Fiat et al., 2002; Goldberg and Hartline, 2003; Hartline and Mc Grew, 2005; Alaei et al., 2009], in which case agents still possess one copy of their endowments even though the exchange has taken place. In addition, agents have negative externality for other agents to own their items, namely, an agent s valuation towards her endowment decreases as more agents possess her item.

A representative type of digital good is data. The owner can produce as many copies of data as possible, however, it is commonly believed that her value of data decreases as it is owned by more agents, due to the fact that her market power on possessing data decreases as it is shared with more agents.

Over the past few years, digital good exchange has become a common industrial practice, as a part of the sharing economy tsunami. As Bloomberg reports, A market for data swaps is rapidly emerging. Factual, a Los Angeles-based startup, has put together a database that houses location data and details on retailers and restaurants. Access to the database costs companies money, but they can accrue discounts by agreeing to contribute some of their own information. 1

Another successful example of data exchange is www. datatang.com, which encourages individual data owners to share their data in a centralized database and in return awards them a discount, or limited-time free access for obtaining other data sets in their wish lists. Similar data sharing sites abound, including http://new.thedataexchange.com and http: //xor.exchange as well-known examples.

To our best knowledge, there has been no theoretical model

1http://www.bloomberg.com/bw/articles/2012-11-15/databartering-is-everywhere

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16)

tailored for this domain. In this paper, we put forward several game-theoretical models for digital good exchange and investigate their properties. Our goal is to model and analyze existing digital exchange mechanisms, as well as to provide theoretical and practical guidelines for designing new mechanisms in this domain. We make the following contributions:

We first consider a natural class of games where agents can either choose a subset of other participants endowments or no participation at all. This class of games captures basic features of several aforementioned data exchange websites. We model this class of games as an extension of standard congestion games, coined player-specific congestion game with endowments, that allows player-specific preferences and endowments.

Next, we prove that for this class of games, (1) it is in general NP-complete to determine whether there exists a nontrivial pure Nash equilibrium; (2) there always exist nontrivial Pure Nash equilibria for a subset of games for singleminded players with unit demand and we put forward an efficient algorithm to find such equilibria.

The complexity result in the previous model motivates us to think about this problem from a mechanism design perspective. We ask if there is a dominant strategy truthful mechanism in this setting that can achieve good social welfare guarantee. To this end, we design a randomized fixedprice-exchange mechanism that is individually rational, truthful, and for two-player case yields a tight log-approximation with respect to any individually rational allocation regardless of truthfulness.

Additional Related Work In the literature of traditional barter exchanges, [Shapley and Scarf, 1974] introduce the house allocation problem and solve it by an efficient and truthful mechanism, Gale s Top Trading Cycle mechanism. [Ashlagi and Roth, 2011; Dickerson et al., 2013; Dickerson, 2014; Li et al., 2014; Liu et al., 2014; Fang et al., 2015] focus on mechanism design and implementation for different variants of kidney exchange.

Another related literature is the congestion games. In a standard congestion game [Shoham and Leyton-Brown, 2008], there are a set of players and a set of resources. The payoff of each player depends on the resources she chooses and the number of players choosing the same resource. The basic model is extended to the one with player-specific payoff [Milchtaich, 1996]. Our model can be regarded as an extension of [Milchtaich, 1996] by adding endowments.

Let A = {a1, . . . , an} be a set of n agents, and D = {d1, . . . , dn} be the corresponding set of digital goods (or simply goods), where di is initially owned by agent ai. Note that it is without loss of generality to assume that the number of goods equals the number of agents, since it is WLOG to add dummy goods (towards which every agent has zero valuation) or dummy agents (who demand nothing).

Let xj = (x1j, ..., xnj) 2 {0, 1}n be a deterministic allocation of good dj over all agents and vij(xj) be the valuation of agent ai over allocation xj, in this way, we let agent ai s

valuation over good dj explicitly depend on the allocation of dj. All agents have additive, quasi-linear utility functions,

vij(xj), 8i 2 [n].

As described in the introduction, agents never lose ownerships of their endowments, so the following feasibility constraint (1) is imposed on each deterministic allocation.

xii = 1, 8i 2 [n] (1) Besides, an agent s valuation toward a digital good decreases as it is owned by more agents. Let Supp(xj) = {i|xij = 1}. The valuation functions satisfy the following vij(xj) = 0, i /2 Supp(xj) vij(xj) vij(x0

j), i 2 Supp(xj) Supp(x0

Particularly, we let ij denote the agent ai s valuation of exclusively owning good dj, i.e., ij = vij

, where ei contains only zeros except a single 1 on its i-th coordinate. This value is the upper bound of the agent ai s valuation of any allocation of good dj.

We further extend our definition to randomized allocation Xj, which is a probability mixture over all deterministic allocations. We assume that all the agents are risk neutral, that is, the valuation of the randomized allocation is naturally defined as the expected valuation, i.e.,

vij(Xj) = Exj Xjvij(xj), where we overload notation vij and use it for the valuation function of randomized allocations as well.

3 Player-specific Congestion Game with Endowments One common feature of the data exchange websites mentioned in the introduction can be summarized as follows: Agents share their own goods to exchange for the rights to download others data. This interesting feature can be captured by a natural simple game as follows. In this game, an agent s action is either to choose a subset of other agents endowments or no participation; the allocation of each agent is then the subset of her selections whose owners choose to participate the game. Formally, the game is defined as follows. Definition 1 (Digital Exchange Game). Suppose that each agent ai 2 A has endowment di. The game G = (A, S, u) is defined as follows,

The set of actions Si of agent ai is to either choose

a subset (must include ai) of all the goods (agents), or exit this game (denoted by ?). For strategy profile S = (S1, . . . , Sn), the set of goods allocated to ai is,

{di}, Si = ? {dj|aj 2 Si, Sj 6= ?}, Si 6= ? .

The utility function ui of agent ai is as follows, where x

is the deterministic allocation induced by the game play.

dj2Ti vij(xj) ii Si 6= ?

Note that the utility function of agent ai is normalized by subtracting ii, so that the utility of choosing ? is 0.

If the agent chooses exit , it will not share its good nor get anything from others. If the agent ai chooses a subset Si A, ai 2 Si, then it will get goods in Ti, and share its own good di to anyone who has chosen it. We say agent ai chooses good dj (agent aj) , if aj 2 Si.

Notice that there is no monetary transfer in this game, hence the utility functions are uniquely described by the valuation functions vij. We only specify the definition of pure strategies and utility functions of deterministic outcomes. The definition extends to randomizations by standard means.

The above game has an interesting congestion-game interpretation [Shoham and Leyton-Brown, 2008]: The resources are the set of agents endowments; the agents can choose a subset of resources; the payoff of each agent is the additive valuation of the resources she chooses and her payoff decreases as more agents choose the same resource. The major difference lies in the fact that each agent enter the game with endowment in digital good game while resources are initially publicly-owned in the basic congestion game. Besides, the option to exit ensures individual rationality to play the digital good game but this is not the case with the basic congestion game. Therefore, we need to extend the definition of congestion games to handle these features. We coin this game as player-specific congestion game with endowments .

3.1 The Pure Nash Equilibria

The digital exchange game defined above is related to the player-specific congestion game defined in [Milchtaich, 1996], which is shown to have a PNE that can be found in polynomial time for some special cases.

A natural question is whether this game always has a PNE? First of all, it is straightforward to observe that nonparticipation for all agents forms a PNE.

Claim 1. The game always has a trivial PNE, where each agent chooses Si = ?. Meanwhile, choosing Si = A always weakly dominates choosing any other subsets (except for choosing ?).

However, determining whether there is a non-trivial PNE, where at least one agent participates, is hard.

Theorem 1. Given an instance of the digital exchange game, determining if there is a non-trivial PNE is NP-complete.

Proof. This problem is in NP, because to decide if a given strategy profile S is a non-trivial PNE can be done by checking whether each agent s strategy is no worse than ? and A (by Claim 1).

To prove the NP-hardness, we first introduce a four-agent gadget such that there could be a non-trivial PNE if and only if one special agent, aφ, participates (see Lemma 1). Then we reduce the 3-SAT problem to whether the special agent aφ participates in a carefully constructed game (see Lemma 2).

For ease of presentation, we use the following valuation functions for agents except a and aβ, where (i, j) = ij (defined at the end of Section 2) and vij(xj) only depends on (i, j) and the support size of xj. Therefore the utility

functions u can be defined within polynomial size.

vij(xj) = (i, j) |Supp(xj)|.

Lemma 1. There is a gadget containing four agents (a0, a , aβ, aφ), such that there could be a non-trivial PNE, if and only if aφ participates.

Proof. Consider the construction of valuation functions for the agents as follows.

(0, 0) = 0, for any i 6= 0, (0, i) > 0. Hence a0 must

participate in all non-trivial PNEs, if any. a has valuation 1 for d0, valuation 3 for dφ, and valua-

tion 0 for all other goods. If its own good is shared with aβ, its utility will decrease by 2. aβ has valuation 2 for d and valuation 0 for all other

goods. If its own good is shared with a0, its utility will decrease by 1. Then if aφ participates, both a and aβ are willing to participate and form a non-trivial PNE; otherwise only trivial PNE exists (see Figure 1).

{a0} ! {a0, a } a comes aβ leaves " # aβ comes a leaves {a0, aβ} {a0, a , aβ}

Figure 1: No non-trivial PNE, if aφ does not participate. Agents in the set are those who participate. Neither of these four cases is a PNE, because at least one agent will deviate, hence transfer to the next case along the arrows.

Lemma 2. Given any instance of 3-SAT, φ, we can efficiently construct an instance of our game, G, where agent aφ is willing to participate the game if and only if φ is satisfiable.

Proof. We start the proof with a high level sketch of the reduction idea to help readers to understand the construction details. Consider an instance of 3-SAT with n variables,

ck, ck = lk1 _ lk2 _ lk3, l 2 {x1, x1, . . . , xn, xn}.

For each clause ck, we construct one agent ack such that it is willing to participate, if and only if ck is satisfied. For each variable x, we construct one variable agent ax and two literal agents, ax F, ax T. That ax F participates and that ax T participates stand for x = False and x = True respectively. ax is used to ensure that exactly one of ax F and ax T participates. Hence the evaluation of variable x is valid.

Finally, we make sure that: (1) aφ participates, if and only if all of m clause agents participate; (2) each clause agent ack participates, if and only if at least one of the 3 corresponding literal agents participates; (3) all variable agents participate.

If all these properties are satisfied, then we finish the reduction. The rest of the proof is to carefully assign values to

ac1 a0 chooses all the other agents

3 dummy agents

m dummy agents

Each literal agent is chosen by at most m clause agents

m clause agents ac2 acm

ax T ax F ax T

Figure 2: Illustration of construction for Lemma 2.

v(i, j) s and add some auxiliary agents to ensure the above properties being satisfied.

Step 1: Let any (i, j) not specified be 0. Step 2: a0 (introduced in Lemma 1) always participates in all non-trivial PNEs, if any.

Step 3: For each variable x, (x, x) = 0 and (x, 0) > 0; (xb, xb) = 1, (xb, x) = 3, for b 2 {F, T}. Creating 3 dummy agents always choosing ax F and ax T, then the loss for xb to participate is at least 4/5 (by sharing dxb with a0, itself, and three dummy agents), while the gain for xb is 1 by sharing dx with a0, ax, and itself, or 3/4 (less than 4/5) by additionally sharing dx with axb. Hence for any non-trivial PNE, ax always participates, and exactly one of ax F, ax T participates.

Step 4: For each clause, say ck = x_x0 _x00. (ck, ck) = 1, (ck, x T) = (ck, x0

F) = (ck, x00

T) = m + 6. Hence agent ack is willing to participate, if and only if at least one of ax T, ax0

T participates. (Note that there are at most m clauses, 3 dummy agents, a0, the literal agent itself sharing the literal agent s good. Then the gain for ack in this case is at least (m + 6)/(m + 5) > 1.)

Step 5: Finally, for the formula φ, we let (φ, φ) = m, and (φ, ck) = 3 for each clause ck. By creating m dummy agents always choosing aφ, the loss for aφ to participate is greater than m 1 and less than m. Meanwhile, the gain from choosing each participating clause agent is 3/3 = 1 (by sharing the clause agent s good with a0, the clause agent, and aφ). Therefore aφ participates, if and only if all of these m clause agents simultaneously participate.

The following corollary states that the problem is still hard, even if we restrict the size of action set |Si|, or the valuation functions to be positive. Corollary 1. If (1) each agent is limited to choosing at most two goods, (2) or has strictly positive valuation over goods, determining if there is a non-trivial PNE is NP-hard.

3.2 A Case for Efficiently Computable PNEs Despite of the hardness of finding a non-trivial PNE for general cases, we derive positive results for a natural special case: single-minded agents with unit demand. In this section, we need the following technical assumption, so that the input of the problem can be compactly represented. Assumption 1 (Symmetric Negative Externality). The valuation function vij decreases as the number of agents sharing the good dj increases, regardless of which agents share the good, i.e.,

8i 2 Supp(xj), vij(xj) = ˆvij

and ˆvij is decreasing.

Single-minded Agents with Unit Demand We consider the case where each agent has positive valuation towards exactly one item besides its own endowment, i.e.,

8ai, 9j 6= i, s.t. ij > 0, 8j0 6= i, j, ij0 = 0.

In this section, we consider efficient PNEs. We use δ(i) = j for agent ai desires good dj. Then efficient means that in the PNE, S = (S1, . . . , Sn),

8ai 2 A, δ(i) = j, Si 2

{ai, aj}, {ai}, ?

and at least one exchange is performed.

Theorem 2. For single-minded agents with unit demand case, there is a dynamic program based algorithm to find or prove non-existence of efficient PNEs in polynomial time.2

We illustrate agents preferences by a directed graph. Each vertex i denotes the agent ai and each edge

denotes that agent ai desires good dδ(i), so each vertex has exactly one out degree.

Consequently, the preference graph must consist of one or more disconnected components, where each component is a tree with an extra edge, (see Figure 3). Without loss of generality, we can assume that there is only one component; otherwise we can treat each component as a sub-problem and the original problem has an efficient PNE if and only if at least one of the sub-problems has an efficient PNE.

Figure 3: Disconnected components, each of them contains exactly one cycle.

We make the following assumption, which restricts us to a subset of efficient PNEs for a clean presentation of the algorithm and is not necessary for finding efficient PNEs.

Assumption 2. If δ(i) = j, then ai participates, only if aj participates.

Note that in the light of Assumption 2, if there is an efficient PNE, all agents on the cycle must participate.

Finding Efficient PNEs via Dynamic Programming For each vertex i, we calculate a subset K

i is a subset of Ki = {i0|δ(i0) = i} (the set of agents who desires good di) that contains the agents who would participate if ai participates, i.e.,

ai participates =) agents in K

i participate.

2The Top-Trading-Cycle (TTC) algorithm does not work in this case, since each agent can get at most one good from others, but might share its good with any number of agents. (For TTC, the number of incoming goods equals the number of outgoing goods.)

The state update formulas ((2) and (3)) for the DP are given, where an auxiliary variable ki is used.

i Ki, s.t. 8i0 2 Ki,

i |; otherwise, ki0 < |K

i | + 1; (2)

***ˆviδ(i)(k) + ˆvii

i satisfying (2) can be calculated by Algorithm 1 efficiently. Note that ki is the maximum number of agents sharing good dδ(i) such that the best response for agent ai is still to participate (assuming aδ(i) participates).

Algorithm 1: Calculate K

i satisfying (2). input : Ki, ki0 for all i0 2 Ki output: K

i ;; sort i0 2 Ki in descending order of ki0; for sorted i0 2 Ki do

if ki0 > |K

i [ {i0}; else

There might be more than one possible K

i satisfying (2) and (3), but all of them must be of the same size.

There is one trouble of the DP process: if vertex i is on the cycle, calculating K

i recursively depends on ki, but ki is calculated based on K

i . One way to avoid the self dependence is to assume that for each vertex i on the cycle, ki = 1. By Assumption 2, if there is an efficient PNE, all agents on the cycle must participate. Therefore after calculating K

i for all i, the remaining work is to check whether the implied strategy profile S = (S1, . . . , Sn) is an efficient PNE.

The implied strategy profile S is defined as follows, where K is the set of agents who participate. (K initially includes vertexes on the cycle, and recursively merges K

i for all i 2 K.)

ai 2 K =) Si =

, ai /2 K =) Si = ?

Remark 1. As mentioned, Assumption 2 is not necessary for finding the efficient PNE. We omit the proof of correctness and the algorithm for general cases due to limited space.

4 Mechanism Design By our analysis, it is NP-complete to determine whether there is a non-trivial PNE for general digital exchange game. The negative result further motivates us to investigate this problem from a mechanism design perspective. In this section, we design an incentive compatible (IC) and individually rational (IR) mechanism to allocate digital goods to the agents with good social welfare guarantee.

By the revelation principle, it is without loss of generality to restrict attention to the direct mechanisms. Meanwhile, for our purpose, the mechanisms should be without money. Definition 2 (Direct Mechanism without Money). A direct mechanism without money is an allocation function that maps the reported valuation functions, {vij}n

i,j=1 to the allocation matrix, X 2 [0, 1]n n.

In order to employ randomized allocations, we need to define compact representations for them, because a randomized allocation is a probability mixture over an exponentially large number of (2O(|A|)) deterministic allocations.

Therefore throughout this section, we restrict attention to a special type of valuation functions, for which we can define compact representation zj = (z1j, . . . , znj) such that for each randomized allocation Xj,

vij(Xj) = ij zij. (4)

(4) then implies that valuation function vij maps two (probably) different randomized allocations, Xj, X 0

j, to the same value, if the corresponding compact representations, zj, z0

j, equal at the i-th coordinate, i.e., zij = z0

ij. We further require the compact representations to satisfy the following conditions, as if zij is the randomized allocation of irreplicable good j to agent i, i.e.,

zij 0, 8i, j; Pn

i=1 zij = 1, 8j; zij zi0j () Exj Xjxij xi0j 0, 8i, i0, j. (5)

Consequently, the feasibility constraint for the compact representations in our context is

8i, j, zjj zij. (6)

Definition 3 (Compact Representation). Valuation functions {vij}n

i,j=1 are compactly representable, if for each j there exists a mapping that maps each randomized allocation Xj to zj, satisfying (4) and (5).

A compact representation zj in fact represents a family of randomized allocations for good dj. In the rest of this section, we use allocation interchangeably with compact representation . As an instance, the following valuation function is compactly representable.3

vij(xj) = ijxij P

i0 xi0j zij = Exj Xj

4.1 Randomized FPE Mechanism The mechanism we put forward, coined Randomized FPE Mechanism (RFPE), is the expectation of parametric fixedprice-exchange (FPE) mechanisms with parameters drawn from some pre-specified distribution.

We start from introducing the FPE mechanism, which is a simplified version of fixed-price-trading [Barber a and Jackson, 1995]. In our case, each agent only has one type of endownment, and the exchange is conducted according to one single fixed exchange rate (fixed-price). The exchange amount is determined in an incentive compatible (utility maximizing) way. Formally, the fixed-price in FPE for n agents is a matrix = { ij}n

i,j=1 2 Rn n, satisfying

ii 0, ij 0, 8i 6= j Pn

i=1 ij = 0, 8j .

3We claim that the particular compactly representable valuation functions have fast reverse mapping to randomized allocations, but omit the proof details.

The FPE mechanism with fixed-price , FPE , is defined as

i,j=1 = I + ,

where the exchange amount 2 R+ is the maximum real number subject to the feasibility (8) and IR (9) constraints,

I + 2 [0, 1]n n, zjj zij, 8i, j; (8)

ij zij ii ()

ij ij 0, 8i. (9)

Mechanism 1 (Randomized FPE Mechanism). Given distribution F of fixed-price (F specified prior to the mechanism) the randomized FPE mechanism is defined as follows,

Theorem 3. Any RFPE mechanism is IC and IR.4

Particularly, for two-agent case, there is a tight bound of the social welfare approximation ratio against the optimal IR allocation (see Lemma 3).

Proof of IR and IC. Since RFPE is ex ante probability mixture of FPEs, we finish the proof by proving that any FPE is IR and IC. For any FPE, IR is guaranteed by (9), and IC coincides with IR because manipulating valuations only affect whether = 0 or 0.5

To study the approximation ratio, we first normalize the agents utilities to forbid scaling, such that every agent has exclusive value ii = 1 over its own data. In addition, we choose the optimal IR allocation (OPTIR) as the efficiency benchmark rather than simply the optimal allocation . Because any allocation satisfying IR has the same worst case bound against the optimal allocation.

For two-agent case, let = 12 and = 21. Note that the fixed-price can be fully described by a single parameter 2 [0, 1) under normalization 11 = 1, i.e.,

Lemma 3. The tight approximation ratio of the two-agent randomized FPE mechanisms is (ln M), where M is the given upper bound of and , i.e., , 2 [0, M].

Proof of Lemma 3. Lower bound.

If > 1 > , the following distribution F of on [1/M, em/M] admits a desired approximation ratio, where m is a parameter to be determined.

F( ) = (ln + ln M)/m (10)

In this case, both agents are willing to accept the exchange rate , if and only if 2 [1/ , ]. Hence the exchange amount = 1, and the utilities of the agents are,

u1 = , u2 = + 1 .

4We also conjecture that in fact the RFPEs include almost all the IR and IC mechanisms.

5(8) is independent of valuations, and (9) is equivalent to Pn

j=1 ij ij 0, 8i.

The conditional expected social welfare for instance ( , ) is

W| 2 [1/ , ]

d F( ) + 2 Pr

1 + 1/ + (ln 1) ln

while OPTIR = + 1.

Then it can be shown that EW = (1/m) OPTIR, when the exchange is performed, i.e., M/em.

When < M/em, no exchange happens ( = 0), and the approximation ratio is

W OPTIR = 2 + 1 2 M/em + 1 = (em/M).

Hence when > 1 > , the overall approximation ratio is

o mem=M ==== 1 m,

where 1/m = em/M () m + ln m = ln M.

For the general case, where , 2 [0, M], the randomized FPE mechanism guarantees the desired approximation ratio, (1/m) = (1/ ln M), when is chosen as

Pr[ F] = Pr[1/ F] = Pr[ = 1] = 1/3. Upper bound.

For the upper bound, we use Yao s minmax principle [Yao, 1977]. All we need to do is to show that any deterministic mechanism is bad for a constructed distribution over the instance ( , ), while = µ/ (µ is such that µ ln µ = ln M 6).

G( ) = ln /(ln M ln µ) Then for any deterministic fixed-price 2 [µ/M, 1/µ],

( + 1)d G( ) + 2 Pr

/2 [1/ , µ/ ]

ln µ/ ln 1/

ln M ln µ (µ 1) + 2

ln µ ln µµ ln µ(µ 1) + 2

µ + 1 = 3 µ + 1 = O(1/ ln M)

Hence the tight bound (1/ ln M), where the sign hides some factors of polynomial in terms of ln ln M.

5 Conclusion Standard models of barter exchanges cannot deal with the digital good exchange, where the goods are freely replicable but incurring negative externality. We modeled this type of exchange and proved that it is NP-complete to determine the existence of a non-trivial PNE in general. However, such equilibria can be efficiently found for a special case. On the other side, we took a mechanism design perspective for this domain and put forward a randomized fixed-price-exchange mechanism, which admits a tight log-approximation for twoplayer instances.

Further research would involve the generalization of the mechanism to more agents, and the problem with monetary transfers, such as markets.

6µ > ln M/ ln ln M.

References [Abdulkadiro glu and S onmez, 1998] Atila Abdulkadiro glu and Tayfun S onmez. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, pages 689 701, 1998. [Abdulkadiro glu and S onmez, 1999] Atila Abdulkadiro glu and Tayfun S onmez. House allocation with existing tenants. Journal of Economic Theory, 88(2):233 260, 1999. [Abraham et al., 2007] David J Abraham, Avrim Blum, and

Tuomas Sandholm. Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. In Proceedings of the 8th ACM conference on Electronic commerce, pages 295 304. ACM, 2007. [Alaei et al., 2009] Saeed Alaei, Azarakhsh Malekian, and

Aravind Srinivasan. On random sampling auctions for digital goods. In Proceedings of the 10th ACM conference on Electronic commerce, pages 187 196. ACM, 2009. [Ashlagi and Roth, 2011] Itai Ashlagi and Alvin Roth. Indi-

vidual rationality and participation in large scale, multihospital kidney exchange. In Proceedings of the 12th ACM conference on Electronic commerce, pages 321 322. ACM, 2011. [Barber a and Jackson, 1995] Salvador Barber a and Matthew O Jackson. Strategy-proof exchange. Econometrica: Journal of the Econometric Society, pages 51 87, 1995. [Dickerson et al., 2013] John P Dickerson, Ariel D Procac-

cia, and Tuomas Sandholm. Failure-aware kidney exchange. In Proceedings of the fourteenth ACM conference on Electronic commerce, pages 323 340. ACM, 2013. [Dickerson, 2014] John P Dickerson. Robust dynamic opti-

mization with application to kidney exchange. In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems, pages 1701 1702. International Foundation for Autonomous Agents and Multiagent Systems, 2014. [Fang et al., 2015] Wenyi Fang, Aris Filos-Ratsikas, Søren

Kristoffer Stiil Frederiksen, Pingzhong Tang, and Song Zuo. Randomized assignments for barter exchanges: Fairness vs. efficiency. In Algorithmic Decision Theory, pages 537 552. Springer, 2015. [Fiat et al., 2002] Amos Fiat, Andrew V Goldberg, Jason D

Hartline, and Anna R Karlin. Competitive generalized auctions. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 72 81. ACM, 2002. [Goldberg and Hartline, 2003] Andrew V Goldberg and Ja-

son D Hartline. Envy-free auctions for digital goods. In Proceedings of the 4th ACM conference on Electronic commerce, pages 29 35. ACM, 2003. [Goldberg et al., 2001] Andrew V Goldberg, Jason D Hart-

line, and Andrew Wright. Competitive auctions and digital goods. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 735 744. Society for Industrial and Applied Mathematics, 2001.

[Hartline and Mc Grew, 2005] Jason D Hartline and Robert

Mc Grew. From optimal limited to unlimited supply auctions. In Proceedings of the 6th ACM Conference on Electronic Commerce, pages 175 182. ACM, 2005. [Li et al., 2014] Jian Li, Yicheng Liu, Lingxiao Huang, and

Pingzhong Tang. Egalitarian pairwise kidney exchange: fast algorithms vialinear programming and parametric flow. In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems, pages 445 452. International Foundation for Autonomous Agents and Multiagent Systems, 2014. [Liu et al., 2014] Yicheng Liu, Pingzhong Tang, and Wenyi

Fang. Internally stable matchings and exchanges. In AAAI Conference on Artificial Intelligence (AAAI), pages 1433 1439, 2014. [Luo and Tang, 2015] Suiqian Luo and Pingzhong Tang.

Mechanism design and implementation for lung exchange. In IJCAI, 2015. [Milchtaich, 1996] Igal Milchtaich. Congestion games with

player-specific payoff functions. Games and economic behavior, 13(1):111 124, 1996. [Roth et al., 2004] Alvin E Roth, Tayfun S onmez, and M Unver. Kidney exchange. The Quarterly Journal of Economics, 119(2):457 488, 2004. [Roth et al., 2005] Alvin E Roth, Tayfun S onmez, and M Utku Unver. A kidney exchange clearinghouse in new england. American Economic Review, pages 376 380, 2005. [Shapley and Scarf, 1974] Lloyd Shapley and Herbert Scarf.

On cores and indivisibility. Journal of mathematical economics, 1(1):23 37, 1974. [Shoham and Leyton-Brown, 2008] Yoav Shoham and Kevin Leyton-Brown. Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008. [S onmez and Switzer, 2013] Tayfun S onmez and Tobias B

Switzer. Matching with (branch-of-choice) contracts at the united states military academy. Econometrica, 81(2):451 488, 2013. [ Unver, 2010] M Utku Unver. Dynamic kidney exchange. The Review of Economic Studies, 77(1):372 414, 2010. [Yao, 1977] Andrew Chi-Chin Yao. Probabilistic computa-

tions: Toward a unified measure of complexity. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science, FOCS 77, pages 222 227, Washington, DC, USA, 1977. IEEE Computer Society.