Digital Good Exchange

1 Introduction

Over the past decade, computer-automated barter exchanges have become one of the most successful applications at the intersection 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].

⇤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.

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 McGrew, 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 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:

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

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.

2 Model

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, As described in the introduction, agents never lose ownerships of their endowments, so the following feasibility constraint (1) is imposed on each deterministic allocation.

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

Particularly, we let ⌫ij denote the agent ai's valuation of exclusively owning good dj, i.e., ⌫ij = vij (ei )↪ 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.,

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,
• ÷ The utility function ui of agent ai is as follows, where x is the deterministic allocation induced by the game play.

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.

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 valuation 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).

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,

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, axF ↪ axT . That axF participates and that axT participates stand for x = False and x = True respectively. ax is used to ensure that exactly one of axF and axT 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 v(i↪ j)'s and add some auxiliary agents to ensure the above properties being satisfied.

Step 2: a0 (introduced in Lemma 1) always participates in all non-trivial PNEs, if any.

Step 1: Let any ⌫(i↪ j) not specified be 0.

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 axF and axT , 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 axF ↪ axT participates.

Step 4: For each clause, say ck = x_x0 _x00 . ⌫(ck↪ ck) = 1, ⌫(ck↪ xT) = ⌫(ck↪ x0F ) = ⌫(ck↪ x00T) = m + 6. Hence agent ack is willing to participate, if and only if at least one of axT ↪ ax0F ↪ ax00 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 ACase 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.,

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.,

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),

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 (i↪ δ(i)) 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.

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 by DP. 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.,

2 The 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.

K⇤ 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 K⇤ i ;; sort i0 2 Ki in descending order of ki0 ; for sorted i0 2 Ki do if ki0 > ♣K⇤ i ♣ then K⇤ i K⇤ i [ ¶i0 ♦; else return K⇤ i ;

There might be more than one possible K⇤ i satisfying (2) and (3), but all of themmust 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↪ aδ(i) ↪ 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 MechanismDesign

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♦ni↪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 ,

(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↪ z0j , equal at the i-th coordinate, i.e., zij = z0ij .

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.,

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

Definition 3 (Compact Representation). Valuation functions ¶vij♦ni↪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

4.1 Randomized FPEMechanism

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♦ni↪j=1 2 Rn⇥n , satisfying

▷

3 We 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

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

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 ˜⇥(lnM), 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.

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,

4 We 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 ⇢ Pnj=1 ⌫ij⇡ij ≥ 0↪ 8i.

The conditional expected social welfare for instance (✓↪ ⌘) is

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

Hence when ✓ > 1 > ⌘, the overall approximation ratio is

where 1◁m = em◁M () m+ lnm = lnM.

For the general case, where ✓↪ ⌘ 2 [0↪M], the randomized FPE mechanism guarantees the desired approximation ratio, ⌦(1◁m) = ⌦(1◁ lnM), when ↵ is chosen as

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 θ = lnM 6 ).

Then for any deterministic fixed-price ↵ 2 [θ◁M↪ 1◁θ],

Hence the tight bound ˜⇥(1◁ lnM), where the ˜ sign hides some factors of polynomial in terms of ln lnM.

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θ > lnM◁ ln lnM.