Better Strategyproof Mechanisms without Payments or Prior - An Analytic Approach

1 Introduction

Competition for resources is one of the most primitive activities of human. The problems of distributing resources among competing agents are found wherever human exists. We have developed various systems and tools, e.g., economic markets, auctions/mechanisms, voting systems and money, to facilitate the distributions and exchanges of resources. The study of these problems in various settings is now a popular topic concerning both computer scientists and economists, in the field coined as Multiagent Resource Allocation; see [Chevaleyre et al., 2006] for a fairly recent survey.

While money is provably reducing the complexity of many such problems, in many scenarios monetary transfer is inapplicable; canonical examples include hospital/facility location determination, peer-to-peer sharing network, and distribution of computing resources among staffs in the same company. Mechanism design problems without monetary transfer are thus naturally motivated. Briefly speaking, a mechanism is a combination of a communication protocol and an algorithm, for agents to reveal their preferences to an auctioneer, and for the auctioneer to determine a good allocation of resources. There are different ways to interpret the meaning of "good allocation", including social welfare, various measures of fairness (often coined as "cake cutting"), or revenue of the auctioneer (when monetary transfer is feasible). Independent of the interpretation, a favourable feature of a mechanism is strategyproofness - the mechanism motivates the agents to reveal their preferences truthfully. Strategyproof (SP) mechanism design without monetary transfer has been studied under various contexts, e.g.,[Schummer and Vohra, 2002; Procaccia and Tennenholtz, 2009; Dokow et al., 2012; Dughmi and Ghosh, 2010].

We focus on the problem formulated by Guo and Conitzer [2010]: design SP mechanisms to allocate divisible items among two agents who have linear preferences over the items. The target is to attain social welfares which are competitive against those in the first-best mechanism (which is not SP).

In contrast to most of the prior work, we take on an analytic approach for the problem. While all known SP mechanisms (which we will discuss next) are somewhat naturally motivated, they do not shed any insight on how an optimal mechanism should look like. We will present results obtained using analytic methods, which will suggest that analytical insights are necessary for seeking the optimal mechanisms.

Related Work. Guo and Conitzer [2010] considered a subclass of SP mechanisms called Swap-Dictatorial mechanisms, in which each agent is a dictator with probability 12 , who chooses her favourite allocation from a predefined set of allowable allocations, and the other agent is allocated the remaining items. 1 They studied two sub-classes of Swap- Dictatorial mechanisms, Increasing-Price (IP) mechanisms and Linear-Increasing-Price (LIP) mechanisms. For the case with two items, they showed that there is a LIP mechanism which is 0▷828-competitive against the first-best mechanism; they used a linear program to show that no SP mechanism is better than 0▷841-competitive. They also showed that as the number of items grows, IP and LIP mechanisms have maximal competitiveness of 12 .

1 Swap-Dictatorial mechanisms can be generalized to more than

Han et al. [2011] showed a number of upper bound results on the competitiveness of SP mechanisms, when the numbers of agents and/or items increase. In particular, they showed that no swap-dictatorial mechanism can be better than ( 12 + om(1))-competitive for m items. They proved the following characterization result: in the case with two items, if a symmetric mechanism A is second order continuously differentiable, then A is SP if and only if A is swap-dictatorial.

Cole, Gkatzelis and Goel [2013a] proposed another subclass of SP mechanisms (for any number of agents) called Partial Allocation (PA) mechanisms, which are not swapdictatorial. They showed in another work [2013b] that a variant of PA mechanism is 23 -competitive for two agents and any number of items.

Recently, non-SP resource allocation mechanisms are under study. The mechanisms are viewed as games and the agents' bids are strategies. The canonical measure of efficiency is the Price of Anarchy. See [Feldman et al., 2009; Brˆanzei et al., 2014] and the references therein for details.

In a swap-dictatorial mechanism, items are always completely allocated among the agents - the auctioneer never holds some of the items from being allocated. However, this is not true in PA mechanism. We say a mechanism is full if items are always completely allocated among the agents, and say it is partial otherwise.

Our Contribution. Our main contribution is to use analytic methods to derive SP mechanisms with competitiveness better than those previously known. We also improve a linearprogram (LP) based proof to show new upper bounds on the competitive ratios for SP full and partial mechanisms. In addition, we provide the first compact upper bound proof.

In Sections 3-6, we focus on the case with two agents and two items. In Section 3, we first prove a characterization of symmetric SP mechanisms, which is essentially the same as the Rochet's characterization [1985]. Then we provide a set of sufficient conditions for symmetric SP mechanisms. We note that while our set of sufficient conditions and the characterization in [Han et al., 2011] are both of analytical flavor, the two results are not comparable: their result focuses on conditions that yield equivalence between SP and swap-dictatorial mechanisms (which must be full mechanisms), while our result is applicable for a broad sub-class of partial mechanisms, and also mechanisms which are not second order continuously differentiable.

In Section 4, we look into the solution to a LP of Guo and Contizer [2010] for making a few observations and heuristic assumptions, which allow us to derive a 56 -competitive full mechanism; we believe it is an optimal full mechanism. 2 In Section 5, by using our set of sufficient conditions, we consider a sub-family of SP partial mechanisms, and show that one of such mechanisms is strictly better than 56 -competitive. This may be surprising to some practitioners, since it suggests that in general, the competitiveness can be improved by suitably holding a fraction of items from being allocated.

two agents, by first generating a random order of the agents, and then each agent takes turn to choose her favourite allocation.

Guo and Conitzer used the LP to show an upper bound of 0▷841 on the competitiveness of SP full mechanisms. We will discuss how to prune out a lot of unnecessary constraints from their LP. This allows us to solve the LP with much refined resolution, and to improve the upper bound to 56 + ✏, where ✏ < 10-9 ; we believe the final answer is 56 . With a minor modification to their LP, we show an upper bound of 0▷8644 on the competitiveness of SP partial mechanisms.

While the LP-based upper bound proofs are legitimate, they may look unsatisfactory to some researchers, due to two reasons. First, such proofs are hardly verifiable by researchers without the use of a computer. Second, such LPs are extremely huge for three or more items and thus not solvable in practice, so they shed no insight for providing a better upper bound when the number of items increases. Therefore, a compact upper bound proof, i.e., a proof which can be easily verifiable by researchers, is preferred. In Section 6, we use the SP characterization of Rochet to provide the first compact proof; the upper bound is 0▷9523. While this upper bound is worse than those yielded by LP-based proofs, the compact proof is worth an attention since it might shed insight for generalizations.

In Section 7, we consider the cases with two agents and any number of items. By taking a suitable average of some PA mechanisms of Cole et al. [2013a; 2013b], we design a SP mechanismwhich is at least 0▷67776-competitive.

In Section 8, we propose a new sub-class of SP mechanisms for any number of agents and items, called DynamicIncreasing-Price (DIP) mechanisms. DIP mechanism is similar to IP mechanism in the sense that both introduce virtual money and virtual prices. However, there is no dictatorswapping process in DIP, and DIP is not swap-dictatorial in general. Also, the prices in an IP mechanism are independent of agents' preferences, but in a DIP mechanism, for each agent, the prices of the items depend on other agents' preferences. In other words, a DIP mechanism enforces all agents to be complete price takers. We note that DIP is well motivated by the classical context of markets: when the scale of the market is large, each agent in the market has tiny effect on the prices, so the prices she face are almost completely depending on other agents preferences. We show that the 56 - competitive mechanism is a DIP mechanism.

Due to space constraint, some of the proofs are deferred to the full version [Cheung, 2016].

2 Preliminaries

Problem Setting. We study the problem of allocating m ≥ 2 divisible items, each of one unit, among two agents, referred to as agents 1 and 2. A vector (c1↪ · · · ↪ cm) is normalized if each cj ≥ 0 and Pmj=1 cj = 1. Each agent i has a normalized 3 linear utility function ui(~xi) = Pmj=1 uijxij, where Pmj=1 uij = 1; her utility function is identified to the normalized utility vector ~ui := (ui1↪ · · · ↪ uim). Each agent i reports to mechanismA a normalized bid vector~bi = (bi1↪ · · · ↪ bim). The mechanism then allocates Aij(~b1↪~b2) unit of item j to agent i. The allocation must be feasible, i.e., for any i↪ j, Aij(~b1↪~b2) ≥ 0 and for any j, A1j(~b1↪~b2)+A2j(~b1↪~b2)  1.

2 There may be more than one optimal full mechanisms.

Let uAi (~b1↪~b2) := Pmj=1 uij · Aij(~b1↪~b2), which is the utility attained by agent i when agent 1 bids ~b1 and agent 2 bids ~b2. Mechanism A is strategyproof (SP) if for any agent i and for any normalized vectors ~bi↪~b3-i, uAi (~ui↪~b3-i) ≥ uAi (~bi↪~b3-i), i.e., agent i is always better off to bid her true utility vector. Strategyproofness is generally accepted as a favourable feature, since it discourages agents from having strategic consideration for reporting bids.

Let SWA(~u1↪ ~u2) := uA1 (~u1↪ ~u2) + uA2 (~u1↪ ~u2), which is the social welfare when both agents bid truthfully to mechanism A. Let SWOPT(u1↪ u2) := Pmj=1 max¶u1j↪ u2j♦, which is the maximum possible social welfare among all feasible allocations; the feasible allocation that attains the maximum possible social welfare is called the first-best allocation. A SP mechanism A is ↵-competitive if for any ~u1↪ ~u2, SWA(~u1↪ ~u2) ≥ ↵ · SWOPT(u1↪ u2). Our target is to design SP mechanisms with high competitive ratios.

Useful Definitions, Facts and Tool. It is known that every ↵- competitive SP mechanism has a corresponding symmetricover-agents and symmetric-over-items ↵-competitive SP mechanism [Guo and Conitzer, 2010, Claim 1]. Thus, from now on we focus only on such symmetric SP mechanisms.

When the agents' utility functions are linear, any weighted average over SP mechanisms is also SP: if A1 ↪ · · · ↪Ak are SP mechanisms, then ¯ A, defined by the allocation rule

where the β`'s are positive and Pk`=1 β` = 1, is also SP. We will write ¯ A as Pk`=1 β` · A` .

For any utility functions u1↪ u2, let their attainable utility region (AUR), denoted by AUR(u1↪ u2), be

Proposition 1. If u1↪ u2 are increasing, concave and continuous functions, then AUR(u1↪ u2) is a convex subset of R2 .

3 A Set of Sufficient Conditions for Strategyproofness

In Sections 3-6, we focus on the case with two items. In this case, each normalized utility vector has the form (t↪ 1 - t), which is essentially single-parameter. We assume that each agent i bids a number bi 2 [0↪ 1], which is supposed to be the first entry of her normalized utility vector. A symmetric mechanism A can be described by a single function A : [0↪ 1]2 !R+, such that

3 See [Guo and Conitzer, 2010, Section 2] for an explanation on why the utility functions are normalized.

In this section, we give a characterization of symmetric SP mechanisms (Theorem 2), which follows directly from a characterization result of Rochet [1985, Theorem 1]; a selfcontained proof is in the full version. Then we use the characterization to provide a set of sufficient conditions for strategyproofness (Theorem 3), which will be used in the next three sections.

Let ˆuA(b1↪ b2) := b1·A(b1↪ b2)+(1-b1)·A(1-b1↪ 1-b2), which is the utility attained by agent 1 if her true utility vector is (b1↪ 1 - b1), she bids truthfully, and agent 2 bids b2.

Theorem 2 ([Rochet, 1985, Theorem 1]). Let A be a symmetric mechanism for two items. A is SP iff

• (a) for any fixed b2 2 [0↪ 1], ˆuA(b1↪ b2) is a convex function of b1, and
• (b) for any fixed b2 2 [0↪ 1], z := A(t1↪ b2)-A(1-t1↪ 1-b2) is a sub-gradient of ˆuA(b1↪ b2) at b1 = t1, i.e., for any b1 2 [0↪ 1],

Theorem 3. Let A be a symmetric mechanism, described by function A(b1↪ b2). If for any fixed b2, A(b1↪ b2) is increasing, continuous and piecewise continuously differentiable w.r.t. b1, and if for any t1↪ t2 2 [0↪ 1], the equality 4

holds within each piecewise interval, then A is SP.

Proof. Recall the definition of ˆuA(b1↪ b2). By the assumptions on A, @ˆuA @b1 (t1↪ t2) exists everywhere (except perhaps at the endpoints of the piecewise intervals), and its value is

The final two terms cancel out due to (1). Hence,

Since A is continuous and piecewise continuously differentiable w.r.t. its first parameter, at any endpoint (t1↪ t2) of a piecewise interval, the left and right partial derivatives of ˆuA w.r.t. its first parameter are equal, i.e., @ˆuA @b1 (t1↪ t2) exists at the endpoint too.

When t1 increases, A(t1↪ t2) increases but A(1-t1↪ 1-t2) decreases. By (2), @ˆuA @b1 (t1↪ t2) increases with t1 within each piecewise interval. Thus, ˆuA(b1↪ b2) is convex w.r.t. b1, i.e., condition (a) in Theorem 2 holds.

4 A clarification: at any specific point (y1↪ y2), @A @b1 (y1↪ y2) is the value of the partial derivative of A w.r.t. its first parameter at that point, i.e., @A @b1 (y1↪ y2) = limδ!0 A(y1+δ↪y2)-A(y1↪y2) δ .

Note that the allocation functions of Partial Allocation mechanisms in Cole et al. [2013a; 2013b] are discontinuous, so Theorem 3 is not applicable.

4 A 56 -Competitive Full Mechanism

Guo and Conitzer [2010] introduced the linear program (LP) below, which represents the optimal full mechanism when the bids are restricted to be multiples of 1◁N for some integer N. Let [N] denote the set of all multiples of 1◁N which are between zero and one.

max λ

They solved the LP with N = 50. The optimal λ value, which is 0▷841, is an upper bound on the optimal competitiveness of SP full mechanisms for two items.

The LP has ⇥(N 2 ) variables and ⇥(N 3 ) constraints, which is efficiently solvable only for small N. However, one would expect that the strategyproofness constraints with large ♣t1 - t01 ♣ are unnecessary. So we keep only those constraints with ♣t1 -t01 ♣ = 1◁N. This reduces the number of constraints to ⇥(N 2 ), allowing us to solve the LP with a much refined resolution of N = 400. The upper bound is improved to 56 +✏, where ✏ < 10-9 . We believe that 56 is the final answer.

We make two observations from the solution to the LP, and make two heuristic assumptions. We then use the observations and assumptions to derive a full mechanism which is 56 -competitive.

Observation 1. There exists a function f : [0↪ 1] ! R such that A(t1↪ t2) = f(t1)-f(t2)+ 12 . Furthermore, f is increasing, continuous and piecewise differentiable.

Observation 2. For all t 2 [0↪ 1◁5], f(t) = 0. For all t 2 [4◁5↪ 1], f(t) is a constant.

Assumption 3. The function A(t1↪ t2) satisfies the equality (1), except at points where t1 2 ¶1◁5↪ 4◁5♦.

With the observations and assumption, (1) yields

With Observation 2, the social welfare attained when t2 = 0 is 1 + t1 (f(t1) - f(1 - t1) + 12 ), and SWOPT(t1↪ t2) = 1 + t1. The following inequality must hold for A to be 56 - competitive: 1 + t1 (f(t1) - f(1- t1) + 12 ) ≥ 56 (1 + t1), or

Observe that by (4), once the values of f(t) for 0  t  12 are known, the values of f(t) for 12  t  1 can be determined. We now state the final heuristic assumption: in (5), the equality holds for t 2 [1◁5↪ 1◁2].

With (5) and Assumption 4, we can solve f using calculus, which is:

Theorem 4. The full mechanism A as described in Assumption 1 and (6) is feasible, SP and 56 -competitive.

Proof. Feasibility trivially holds. Strategyproofness follows from Assumption 3 and Theorem 3.

For competitiveness, note that SWA(t1↪ t2) equals

Showing that A is 56 -competitive is equivalent to showing that SWA(t1↪ t2) ≥ 56 (1 + ♣t1 - t2♣), which can be done with an appropriate case analysis (which is needed due to the piecewise definition of f ) and simple calculus; we defer the details to the full version.

5 A Partial Mechanism-Strictly Better than 56 -Competitive

By changing the equality sign in (3) to a  sign, that LP covers partial mechanisms also. The modified LP provides an upper bound of 0▷8644. We look into its solution, as we did in Section 4, but we do not recognize a nice pattern.

Since we solve the modified LP with high resolution, we believe that an optimal partial mechanism attains competitiveness close to 0▷8644, beating the 56 + ✏ upper bound for full mechanism. Yet, to formally prove that an optimal partial mechanism is strictly better than an optimal full mechanism, we ought to provide a concrete, and preferably compact, SP partial mechanism which is strictly better than ( 56 + ✏)- competitive. This is the purpose of the current section.

Let f1 : [0↪ 1◁2] ! R and f2 : [1◁2↪ 1] ! R be two increasing and continuously differentiable functions such that 8t 2 [0↪ 1◁2], tf 01 (t) = (1 - t)f 02 (1 - t), and f1(0) = f2 (1◁2) = 0. Also, let Q↪R : [0↪ 1] ! R+ be two functions. Then define the function A(t1↪ t2)

It is easy to verify that the above function A satisfies all conditions required in Theorem 3, and thus it yields a SP mechanism, modulo feasibility constraint.

Our strategy is to pick some choice of f1↪ f2, and then use an LP to find out Q↪R such that A is feasible and attains good competitiveness. As before, we formulate the LP with bids restricted to be in [N]. The LP is stated below; note that we impose a slightly stricter feasibility constraint, in which only (1 - δ) fraction, for some δ > 0, of each item can be allocated. The reason will be clear later.

Lacking further insight on how a good choice of f1↪ f2 should be, we try the natural candidate f1(t) := t, and hence f2(t) := ln(2t) - t + 1◁2. Then we solve the above LP with resolution N = 1000 and δ = 2▷92◁2000. The optimal λ is larger than 0▷835524. Let the optimal solution be Q⇤ ↪ R⇤ . We note that the maximum entry in Q⇤ is less than 1▷46. Now, we are ready to describe the desired symmetric SP mechanism ˜ A. ˜ A takes t1↪ t2 as bids. Let ˜ ti be the value by rounding ti to its nearest multiple of 1◁N. ˜ A(t1↪ t2) equals

It is easy to verify that the above program is a LP with variables Q(t)↪ R(t) for t 2 [N], plus variable λ.

The rounding is needed because the domains of Q⇤ ↪ R⇤ are [N]. It does not destroy strategyproofness; one can verify that ˜ A is SP using Theorem 3. 5

Since the maximum entry of Q⇤ is less than 1▷46, and since the derivatives of f1↪ f2 are bounded by 1, @ ˜ A @b1 (b1↪ b2) < 1▷46 always. Also, note that ♣ti - ˜ ti♣  1 2000 . Due to the first constraint of the LP above, ˜ A(˜ t1↪ ˜ t2) + ˜ A(˜ t2↪ ˜ t1)  1 - δ. Thus,

which is at most 1. This verifies the feasibility of ˜ A.

To bound the competitiveness of ˜ A, first note that by Theorem 2, ˆu ˜ A(t1↪ ˜ t2) ≥ ˆu ˜ A(˜ t1↪ ˜ t2) - 1 2000 and ˆu ˜ A(t2↪ ˜ t1) ≥ ˆu ˜ A(˜ t2↪ ˜ t1) - 1 2000 . From the LP, we have

With the above two sets of inequalities, we proceed a simple error analysis to show that

which is strictly larger than 56 + ✏.

To program mechanism ˜ A, we need to store the values of Q⇤ ↪R⇤ at 1001 discrete values, and to compute f1↪ f2 at arbitrary real values in their domain. While this may not look compact to some people, ˜ A is a concrete SP partial mechanism that breaks the 56 barrier.

5 In general, if an allocation function for agent i, denoted by A0i(~ui↪ ~u-i), yields a SP mechanism, then any other allocation function A00 i (~ui↪ ~u-i) ⌘ A0i(~ui↪ T(~u-i)), where T is an arbitrary function with range compatible with the domain of the second parameter of A0i, yields a SP mechanism too.

6 ACompact Upper Bound Proof

In this section, we provide some high-level intuitions for our compact proof for the following theorem; we defer the complete proof to the full version.

Theorem 5. For the case with two items, no SP mechanism is better than 0▷9523-competitive.

We make the following qualitative observation. Suppose ~ui = (ti↪ 1 - ti). For some t1↪ t2, if agent 1 earns a too high utility from the mechanism, then the utility earned by agent 2 has to be very low, forcing a low competitive ratio; conversely, if agent 1 earns too low a utility, this forces a low competitive ratio too. Thus, to attain a high competitive ratio h, there is a restricted range of utility values that each agent can earn. Geometrically, the utilities earned by the agents must lie in the intersection of AUR(t1↪ t2) and the set ¶(r1↪ r2) ♣ r1 + r2 ≥ h · SWOPT(t1↪ t2)♦.

Briefly, our proof strategy is: for some h↪ t1↪ t2, since the utilities earned by both agents are restricted to certain range, the allocations are restricted too. Due to Theorem 2, the subgradients of ˆuA at certain points are also restricted. We then show that if h is too high, the above restrictions add up to forbid the existence of ˆuA.

7 A 0▷67776-Competitive Mechanism for Any Number of Items

Cole et al. [2013a] introduced a family of SP mechanisms called Partial Allocation (PA) mechanisms, which work for multiple agents and multiple items. We describe the twoagent version PAc below. 6 In [2013b], they showed that a variant of a PA mechanism, which we denote by PAmax, is SP and it is 23 -competitive for two agents and multiple items. We will show that by taking a suitable weighted average of two PA mechanisms and PAmax, we break the 23 barrier.

PAc(~u1↪ ~u2) for 0 < c < 1:

1. Compute the feasible allocation (~a1↪~a2) that maximizes u1(~a1) · u2(~a2)c . Let W(u1↪ u2) denote the maximal value.
2. Allocate u2(~a2)c fraction of ~a1 to agent 1; allocate u1(~a1)1◁c fraction of ~a2 to agent 2. (See footnote 6).

PAmax(~u1↪ ~u2):

1. Compute the allocation of PA1(~u1↪ ~u2).
2. Compute the allocation in which each item is split evenly among the two agents.
3. Output the allocation that yields higher social welfare.

To build up an intuition on why this might work, we look at an almost worst case scenario for PAmax, where there are two items, ~u1 = (0▷99↪ 0▷01) and ~u2 = (0▷5↪ 0▷5). In PA1, ~a1 = (1↪ 0) and ~a2 = (0↪ 1), u1(~a1) = 0▷99 and u2(~a2) = 0▷5. The eventual allocation to agent 1 is 12 ~a1, i.e., reducing

6 Since the utility functions are normalized, 0 < u2(~a2)c ↪ u1(~a1)1◁c  1. So Step 2 of PAc is legitimate. Also, we note that the eventual utility attained by agent 1 is u1(~a1) · u2(~a2)c = W(u1↪ u2), and the eventual utility attained by agent 2 is u1(~a1)1◁c · u2(~a2) = W(u1↪ u2)1◁c .

~a1 by half. This reduction harms the eventual social welfare hugely.

If we consider PAc for some c less than 1, say c = 0▷5, the eventual allocation to agent 1 is much better, which is 0▷50▷5~a1 ⇡ 0▷707~a1. The eventual allocation to agent 2 in PA0▷5 is 0▷992~a2, which is slightly worse than 0▷99~a2, the eventual allocation to agent 2 in PA1. But overall, the social welfare in PA0▷5 is much better.

However, there are bad scenarios for PA0▷5, e.g., when the utility functions of the two agents in the last paragraph are swapped. To attain an overall good competitiveness, we consider some weighted average of ( 12 · PAc + 12 · PA1◁c ) and PAmax. For each choice of c and the weights, by using the tool of AUR, we can compute the competitive ratio with math software. We find that for a suitable choice of c and the weights, a competitive ratio of 0▷67776 is attained. The proof of the theorem below is deferred to the full version.

Theorem 6. The mechanism

where c = 0▷421, is SP and is at least 0▷67776-competitive.

8 Dynamic-Increasing-Price Mechanisms

In this section, we propose a sub-class of SP mechanisms for any number of agents and items. For simplicity, we describe the general form of DIP mechanisms for the case with two agents. It is easy to see how to generalize to the cases with any number of agents.

Recall that the number of items is m. For each agent i, she has one unit of virtual money. For each item j, agent i will be given a price function P u3-i j : [0↪ 1] ! R+ [ ¶0↪+1♦, which is an increasing function that depends on the utility function of the agent 3 - i. We will write P -i j as a shorthand for P u3-i j . The value P -i j (y) describes the marginal price when agent i has already purchased y units of item j. In other words, if agent i purchases xj units of item j, she needs to pay T -i j (xj) := R xj 0 P -i j (y) dy unit of her virtual money. Agent i will purchase an allocation ~x = (x1↪ x2↪ · · · ↪ xm) which is in

A DIP mechanism is obviously SP, since each agent is accepting prices which she herself cannot influence, and uses them to decide an optimal purchase. Yet, feasibility is a delicate issue, particularly when m is large.

While DIP and IP mechanisms are apparently similar, we note that there is no process of dictator-swapping in DIP, and DIP is not swap-dictatorial and not full in general. Another difference between DIP and IP is that in DIP the price functions are price versus quantity of item already purchased, while in IP they are price versus virtual money already spent.

DIP is well motivated. In the first-best allocation, if u1j > u2j, then agent 1 gets all of item j. When u1j is high but u2j is low, ideally we want to construct the price function P -1 j ↪ P -2 j such that P -2 j is lower to encourage agent 1 to purchase more item j, but P -1 j is higher to discourage agent 2 from purchasing more item j. Adjusting the prices dynamically in this manner might help pushing the allocation in DIP towards the first best allocation, and therefore might be hopeful to attain better competitiveness.

The way that DIP works is similar to price taking in Fisher market: suppose an agent enters a Fisher market where items are sold, the prices she takes surely depend on other agents' preferences, while she herself can also have influence on the prices - as a mechanism, DIP deliberately removes such influence by herself. In a non-rigorous sense, we may say that DIP is a rescue for Fisher markets from being nonstrategyproof.

We note that [Cole et al., 2013b, Theorem 1] proved that when there are two agents and multiple items, Fisher market equilibrium allocation (which is also the proportional fair allocation) is highly competitive against the first-best allocation.

Proposition 7. The 56 -competitive mechanism given in Section 4 is a DIP mechanism.

We give the price functions for agent 1 on item 1 below; other price functions are defined symmetrically. Recall that ~u2 = (t2↪ 1 - t2), and also the definition of f in (6). Let ⌧ = 12 - f(t2). Then

where g(y) denotes the unique value of z 2 ⇥ 15 ↪ 12 ⇤ such that f(1-z)-f(t2)+ 12 = y, and C is the positive constant such that R 1-f(t2) 0 P -1 1 (y) dy = 1.

9 Discussion and Open Problems

The most important problem for future research is to seek optimal competitive mechanisms. As we have already seen, even for the case with two items, where the setting is essentially single-parameter, the use of analytical tools seems unavoidable - for instance, it looks unlikely to have a natural interpretation of the 56 -competitive mechanism, which we believe to be an optimal full mechanism. In the study of revenue-optimal mechanisms with prior, more advanced analytical tools, including duality theory and variational calculus, have played key roles. See, e.g., [Papadimitriou and Pierrakos, 2011] and Giannakopoulos and Koutsoupias [2014; 2015]. We believe that such tools will be useful for our problem too; for instance, duality theory is likely to be useful for showing that the upper bound for full mechanism is exactly 56 .

In Section 6, we use Rochet's characterization to prove a non-trivial upper bound. The proof only considers the restrictions to two cross sections of ˆuA, so clearly it has not yet fully exploited the power of the characterization. An interesting research agenda is to seek a more sophisticated use of the characterization for proving better upper bounds, for either the case with two items, or for those with more items.

Acknowledgments

This work has received funding from the Vienna Science and Technology Fund (WWTF) through project ICT10-002, and from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013) / ERC Grant Agreement no. 340506.

The author thanks the anonymous reviewers for their thoughtful suggestions which help improving the structure and presentation of this paper.