Multi-agent Mechanism Design without Money - Duke's Fuqua School [PDF]

Mar 6, 2017 - The fact that the first-best allocation can be approximated may not be surprising, .... alizations of the

0 downloads 3 Views 1MB Size

Recommend Stories


School Money Parent Guide
If you feel beautiful, then you are. Even if you don't, you still are. Terri Guillemets

PDF Download Graphic Design School
I want to sing like the birds sing, not worrying about who hears or what they think. Rumi

Design Your Own Money
The happiest people don't have the best of everything, they just make the best of everything. Anony

Theory of Mechanism Design
Come let us be friends for once. Let us make life easy on us. Let us be loved ones and lovers. The earth

Mechanism Design Experiments
Ego says, "Once everything falls into place, I'll feel peace." Spirit says "Find your peace, and then

the dukes of mazovia route
If you want to become full, let yourself be empty. Lao Tzu

State v. Dukes
Happiness doesn't result from what we get, but from what we give. Ben Carson

Mechanism Design in Social Networks
If your life's work can be accomplished in your lifetime, you're not thinking big enough. Wes Jacks

Multiagent Systems
The beauty of a living thing is not the atoms that go into it, but the way those atoms are put together.

Multiagent Systems
At the end of your life, you will never regret not having passed one more test, not winning one more

Idea Transcript


Multi-agent Mechanism Design without Money Santiago R. Balseiro, Huseyin Gurkan, Peng Sun∗ Fuqua School of Business, Duke University [email protected], [email protected], [email protected]

March 6, 2017 Abstract We consider a principal repeatedly allocating a single resource in each period to one of multiple agents without relying on monetary payments over an infinite horizon. Agents’ private values are independent and identically distributed. We show that as the discount factor approaches one, the optimal dynamic mechanism without money achieves the first-best efficient allocation (the welfare-maximizing allocation as if values are public). As part of the proof, we provide an incentive compatible dynamic mechanism that achieves asymptotic optimality. Keywords: dynamic mechanism design, social efficiency, multi-agent games, resource allocation without money

1

Introduction

Mechanism design for resource allocation with asymmetric information have been extensively studied in economics and, more recently, in computer science (see, for example, Nisan et al., 2007) and operations research (see, for example, Vohra, 2011; Li et al., 2012; Zhang, 2012a,b). Most of these studies allow, and often rely on, monetary transfers as part of the mechanism. In certain problem settings, especially with repeated interactions between agents, monetary transfers may not be practical. For example, monetary transfers may be inconvenient when allocating CPU or memory resources in shared computing environments; using money to manage incentives may sound awkward when an organization is deciding on the allocation of an internal resource, such as scheduling a conference room; in some ∗ The authors are grateful to Ozan Candogan, Xing Hu, Jacob Leshno, Giuseppe Lopomo and Saˇsa Pekeˇc for their valuable comments.

1

medical resource allocation settings, monetary transfer may be a source of controversy. In the examples above, resource allocation occurs repeatedly, and agents’ values for the resource might change over time. In this paper, we study the problem of a socially maximizing planner repeatedly allocating a single resource without relying on monetary transfers. Specifically, we consider a discrete time infinite horizon setting where agents’ private utility valuations for the resource over time are independent and identically distributed. The planner is able to commit to a long term allocation mechanism, but is not able to collect monetary transfers from agents or transfer money between agents. Both the planner and agents share the same time discount factor. The objective of the planner is to maximize allocation efficiency, that is, the expected total discounted utilities from the resource in all periods. If agents can pay for the resource with money, repeatedly implementing the standard Vickrey– Clarke–Groves (VCG) mechanism achieves the “first-best” allocation (also referred to as the “efficient allocation”). That is, the resource is allocated to the agent with the highest value in every period. Obviously, first-best can also be achieved in settings where valuations are publicly observable. Without monetary payment, however, agents have the natural tendency of claiming that their values for the resource are the highest possible. In this case, if the resource is allocated only once, the planner can do no better than randomly allocating the resource to an agent. Repeated interactions, however, allow the planner to leverage future allocations when eliciting current period values, which may improve efficiency. In this paper, we design mechanisms without monetary transfers which induce agents to truthfully reveal private information via promises/threats of future favorable/unfavorable allocations. Moreover, we show that our mechanism asymptotically achieves the “first-best” allocation as players become more patient. The fact that the first-best allocation can be approximated may not be surprising, given the Folk Theorem established in Fudenberg et al. (1994). In comparison, however, our paper takes an operational focus. In particular, while Fudenberg et al. (1994) implies the existence of an approximately efficient mechanism as the discount factor is close enough to one, we present a specific, easy to implement, mechanism for given time discount factors. Furthermore, our construction and analysis yields the convergence rate for the approximation. The equilibrium strategy for each agent in the game under our mechanism is also quite simple: each agent truthfully reports the valuation in each period. 2

1.1

An Overview of Our Approach

Invoking the revelation principle, we focus on direct dynamic mechanisms in which allocations in each period depends on reported private values over time. A direct dynamic mechanism induces a game between agents. Our solution concept for this game is perfect Bayesian equilibrium (PBE). Without loss of generality, we restrict attention to so-called incentive compatible mechanisms, under which all agents reporting truthfully regardless of past history is a PBE. We consider the set of all achievable utilities, that is, the set of vectors representing all agents’ total discounted expected utilities that can be attained by incentive compatible dynamic mechanisms. Using the set of achievable utilities one could readily optimize any objective involving the total expected utility of each agent, and, in particular, identify the most efficient mechanism. Characterizing the set of achievable utilities by analyzing all dynamic mechanisms directly appears impossible because the dimensionality of the history grows exponentially with time. Therefore, we provide an alternative characterization of the mechanism and set of achievable utilities using the so-called “promised utility” framework, which allows us to represent long term contracts recursively (Spear and Srivastava, 1987; Thomas and Worrall, 1990). In this framework, agents’ total discounted utilities, also referred to as promised utilities, are state variables. In each time period, the planner selects a “stage mechanism” consisting of an allocation function as well as a future promise function, both depending on the current promised utility state and reported values. These functions map the current time period’s reports to an allocation and promised utilities for the next time period, respectively. A stage mechanism is incentive compatible if each agent’s total expected utility from the current period’s allocation and the discounted future promise is maximized by reporting truthfully. Furthermore, the stage mechanism needs to satisfy “promise keeping” constraints, which impose that the total expected utility delivered by the mechanism is equal to the current promised utility. Therefore, implementing an incentive compatible stage mechanism recursively delivers the promised utility for each agent. Following Abreu et al. (1990), we provide a recursive formulation in the spirit of dynamic programming to characterize the set of achievable utilities. Specifically, we define a Bellman-like operator that maps a target set of future promised utilities to a set of current period promised utilities. The mapping specifies that there exists an incentive compatible stage mechanism that achieves every current

3

promised utility with future promises lying in the target set. The set of achievable utilities is, therefore, a fixed-point of this Bellman-like operator for sets. Our main contribution is the construction of an incentive compatible mechanism that can attain, as the discount factor approaches one, the “perfect information” (PI) achievable set, i.e., the set of utilities attainable when values are publicly observable. It is clear that the vector of first-best utilities following efficient allocation is in the PI achievable set. Our approach, therefore, provides a constructive proof that first-best is asymptotically achievable in repeated settings without monetary transfers. Although our mechanism is not necessarily optimal for a fixed discount factor, it is relatively simple to implement, in the sense that one does not need to solve for a fixed-point of the aforementioned Bellman-like operator. In order to establish our result, we cannot just rely on the previous theoretical characterization of achievable sets. Leveraging convexity of these sets of achievable utilities, we propose an equivalent representation of the sets in terms of their support functions. This representation is amenable to numerical procedures, and allows us to characterize the efficient frontier of a set, which provides a foundation for the proof of our asymptotic results. More specifically, our mechanism allocates the resource to the agent with the largest weighted value, where weights are dynamically adjusted based on promised utilities. This allocation function is inspired by the PI achievable set: Because every point in the efficient frontier of the PI achievable set can be attained by a weighted allocation, our mechanism seeks to maximize efficiency by setting the weights according to the “closest” point in the efficient frontier of the PI achievable set. The design of future promise functions resembles the d’Aspremont–G´erard-Varet–Arrow mechanism (d’Aspremont and G´erard-Varet, 1979; Arrow, 1979) and the risk free transfers of Es¨o and Futo (1999). Fixing the allocation rule, the interim future promises are uniquely determined from the incentive compatibility constraints. To implement ex-post future promises, we try to minimize the risk of the next time period’s promised utilities lying outside the achievable set. The proof that the proposed mechanism is incentive compatible is geometric in nature and relies on ideas from convex optimization, which is quite involved and resembles the equilibrium construction for the Folk Theorem in Fudenberg et al. (1994). The essential intuition of our mechanism, however, is clear. Reporting a higher value increases an agent’s chance of receiving the resource in the current period, while lowering the agent’s future promised utility. A lower promised utility, in turn, leads to a lower chance of allocating the 4

resource to this agent in the future.

1.2

Related Literature

There is an extensive literature on dynamic mechanism design problems. Most of the literature focuses on settings in which monetary transfers are allowed. Settings under consideration include dynamically changing populations with fixed information, and fixed populations with dynamically changing information. Under these environments, the efficient outcome can be implemented using natural generalizations of the static VCG mechanism to dynamic setting (see, e.g., Parkes and Singh 2004; Gershkov and Moldovanu 2010; Bergemann and V¨ alim¨aki 2010). These mechanisms maintain efficient allocation of resources while incentivizing truthful reporting by choosing transfers that are equal to the externality that an agent imposes on others. In our setting, however, incentives cannot be readily aligned with transfers and the efficient outcome is not implementable in general. We refer the reader to the survey by Bergemann and Said (2011) for a more in depth discussion on dynamic mechanism design problems with monetary transfers. There is a recent stream of studies considering dynamic mechanism design without money. Guo et al. (2015) consider the problem of repeatedly allocating a costly resource to a single agent whose values evolve according to a two-state Markov chain, and they provide the optimal allocation rule. In our setting where the marginal cost of resource is zero, the problem becomes trivial with a single agent. This is because it is optimal to always allocate the resource to the agent in each period. Guo et al. (2009) study the design of dynamic mechanisms with multiple agents and provide a mechanism that achieves at least 75% of the efficient allocation. While their mechanism is guaranteed to attain a fixed proportion of the efficient allocation for all discount factors larger than a threshold, it does not necessarily achieve the first-best allocation as the discount rate converges to one. Johnson (2014) studies a similar problem with multiple agents and discrete private values, and provides some numerical evidence that the optimal mechanism achieves higher social welfare as the discount factor increases. In our paper, we provide a relatively simple mechanism in quasi-closed form and analytically prove that it achieves first-best asymptotically. In addition, agents’ values are continuous in our model, which leads to some technical difficulties in characterizing the optimal mechanism, in exchange for simpler mechanisms without complicated tie-breaking randomization. Gorokh et al. (2016) also study a similar setting with a finite number of periods and discrete values. They provide a mechanism that can be 5

implemented via artificial currencies and show that the performance of their mechanism approximately achieves the first-best. Different from ours, the mechanism in Gorokh et al. (2016) satisfy incentive compatibility constraints approximately. In particular, it guarantees agents’ truthful reporting only in the limit as the number of periods approaches infinity. In comparison, our mechanism is guaranteed to be incentive compatible. Our model and analysis relies on the promised utility framework (Spear and Srivastava, 1987; Abreu et al., 1990; Thomas and Worrall, 1990). In settings with momentary transfers, any nonnegative promised utility can be achieved by having the planner transfer money to the agents. Thus, constructing feasible incentive compatible mechanism is relatively straightforward, and the problem of the planner reduces to that of optimizing certain objective. When monetary transfers are not allowed, however, the planner can no longer subsidize agents. Constructing a feasible incentive compatible mechanism is challenging in this case because the planner needs to guarantee that future promises can be delivered exclusively via allocations. Abreu et al. (1990) introduce a recursive approach to study pure strategy sequential equilibria of repeated games with imperfect monitoring. In the paper, they characterize a self-generating set of sequential equilibria payoffs. We extend their recursive approach to characterize a self-generating set of utilities that can be achieved by incentive compatible mechanisms. Although our setting, which is focused on adverse selection (private signal) issues in mechanism design, is different from that of Abreu et al. (1990), some of their proof techniques related to self-generating sets are helpful. Fudenberg et al. (1994) builds upon the dynamic programming framework of Abreu et al. (1990) to establish Folk Theorems for finite repeated games under imperfect information. In particular, Theorem 8.1 of Fudenberg et al. (1994) implies that in a setting similar to ours (except that the valuation set is finite), agents’ payoff under efficient allocation can be approximated as long as the time discount factor is close enough to one. Fudenberg et al. (1994), however, does not provide an explicit description of such a direct mechanism. For potentially indirect mechanisms (for example, “allocating to the agent with the highest report”), describing agents’ equilibrium reporting strategies to sustain the Folk Theorem approximation appears non-trivial. In comparison, our mechanism is well specified. It turns out that some steps in our construction resemble the steps used in Fudenberg et al. (1994) to prove existence of an asymptotically efficient equilibrium, and we will point them out in our paper. Another advantage of our mechanism is that the equilibrium strategy for agents is straightforward: reporting the true 6

value in each period. Furthermore, our construction and analysis explicitly characterize the rate of convergence to first-best of the mechanism’s social welfare in terms of the time discount factor. Another stream of literature that is related to our work is the study of “scrip systems,” which are non-monetary trade economies for the exchange of resources (Friedman et al., 2006; Kash et al., 2007, 2012, 2015; Johnson et al., 2014). In these systems, scrips are used in place of government issued money, and the resource is priced at a fixed amount of scrips whenever trade occurs. The promised utilities in our model can be perceived as scrips. According to our mechanism, the agent who receives the resource in a period sees his promised utility decreases while others’ increase. The exchange of promised utilities according to our mechanism, however, is not fixed. In fact, it depends on the current promised utilities of all agents. From this perspective, our mechanism is more general than the ones considered in the existing studies of scrip systems. The remaining of the paper is organized as the following. We first introduce the model, its recursive formulation, and various concepts related to self-generating sets in Section 2. In Section 3, we present the main phase of our mechanism. We then focus on the two-agent case and complete the description of the mechanism for the boundary region in Section 4. In Section 5, we describe the intuition behind the truthfulness and asymptotic efficiency of our mechanism. The general case of more than two agents is discussed in Section 6. Finally, Section 7 concludes the paper with comments on potential future directions. Proofs for results in Sections 2 to 6 are presented in Appendices A to E, respectively.

2

Model and Problem Formulation

We consider a discrete time infinite horizon setting where a social planner repeatedly allocates a single resource to one of multiple agents in each period without relying on monetary transfers. We index agents by i ∈ {1, . . . , n} and denote random vector vt = (vi,t )ni=1 to represent agents’ (private) values for the resource in period t ≥ 1. Agents’ values in each period are independent and identically distributed with cumulative distribution function F (·) and density function f (·). Values are supported in the bounded set [0, v¯] and the density is bounded in its domain, i.e., 0 < f ≤ f (v) ≤ f¯ < ∞ for all v ∈ [0, v¯]. The planner and agents share the same discount factor β ∈ (0, 1). An agent’s overall utility is given by the discounted sum of the valuations generated by the allocations of the resource across the horizon. The objective of the planner is to maximize the expected discounted sum of total valuations

7

in all periods.

to represent the ith

n ∞

t n×∞ , we denote a ∈ R = a ∈ Rt i,1:t i,τ i=1 t=1 τ =1 n t components of the 1-st to the t-th vectors, and a1:t = ai,τ i=1 τ =1 ∈ Rn×t the

Notation. For a sequence of vectors a =

ai,t

entire 1-st to the t-th vectors. For a given vector x, we denote x−i to represent the vector obtained by removing xi from x, and xT its transpose. For any two vectors x and y in Rn , the inequality x ≤ (≥)y represents that xi ≤ (≥)yi for each component i. For any function g : Rn → R, we use ∇g to represent its gradient. We use 1{·} to represent the indicator function.

2.1

Dynamic Mechanisms and Achievable Utilities

We assume that the planner commits to a direct dynamic mechanism. That is, in each period, the agents learn their valuations of the resource, and each reports a value to the planner. The planner, in turn, determines the allocation of the resource for the period based on the entire history of reports and allocations, and publicly announces all agents’ reports and allocations in the end of the period.

Non-anticipating Mechanisms and Strategies. Formally, a dynamic mechanism π is a sequence n ∞ of allocation rules π = πi,t i=1 t=1 , where πi,t is the probability that the resource is allocated to agent i in period t. We denote P ⊆ Rn to represent the set of n dimensional feasible allocations i.e., n o P P , π ∈ [0, 1]n : π ≥ 0, ni=1 πi ≤ 1 , and restrict that π t ∈ P for all t. Any mechanism π induces a dynamic game among agents, in which each agent i submits a report vˆi,t ∈ [0, v¯] in each period t n and receives an allocation πi,t . We define the history available at time t, ht = hi,t i=1 , as all reports  and previous allocations up to time t, where hi,t = vˆi,1:t−1 , πi,1:t−1 .1 We define the set of all possible Q histories that can be observed in periods t ≥ 2 as Ht = ni=1 Hi,t where Hi,t = [0, v¯]t−1 × [0, 1]t−1 , and H1 = {∅}. We assume that the planner discloses the reports and the allocations after each round, so n that the history is publicly observed. A non-anticipating strategy profile σ = (σi,t )∞ t=1 i=1 for agents consists of reporting functions for each period, σi,t : [0, v¯] × Ht → [0, v¯], that depend only on the value  vi,t of agent i in period t, and the public history ht up to that period, i.e., σi,t vi,t , ht = vˆi,t . We say 1

Note that if some components of the allocation π t are strictly between 0 and 1, we assume here that π t , and not the actual resource allocation in the end of the period, is publicly observable. More generally, the planner can decide what information to reveal to the agents in each period, and base the resource allocation rule on previous realized allocations. Given the type of results that we provide in this paper, it is clear that asymptotically the planner can do no better through such manipulations.

8

ˆ t and a dynamic mechanism π is non-anticipating if πi,t depends only on the current period reports v the history ht , that is, π t : [0, v¯]n × Ht → P. Since agents’ values in each period are independent, we restrict attention to non-anticipating mechanisms and reporting strategies that depend on past reports and allocations, but not on past values. Because players’ actions and planner’s allocations are only conditioned on previous reports and allocations, and this information is publicly observed, players do not need to form beliefs about the past actions of competitors.

Direct Mechanisms and Truthful Reporting. By the Revelation Principle, without loss of generality, we can focus on direct mechanisms in which agents report their values truthfully to the planner. In particular, for the game induced by a mechanism, we consider perfect Bayesian equilibria (PBE) in truthful reporting strategies, with beliefs that assign probability one to the event that other agents report truthfully. Therefore, we enforce interim incentive compatibility constraints, which ensure that an agent is better off adopting the truthful reporting strategy than any other reporting strategy when other agents report their values truthfully under mechanism π. To elaborate, we introduce some notations. We denote Vi,t to represent agent i’s utility-to-go in period t when the planner implements mechanism π, all agents employ strategy profile σ, agent i’s value for the resource is vi,t , and the history is ht . That is, " ˆ t , ht + Vi,t π, σ|vi,t , ht ,(1 − β)Eπ,σ vi,t πi,t v 



∞ X

# ˜ τ | vi,t , ht , ˆτ , h β τ −t vi,τ πi,τ v 

τ =t+1

˜ τ )τ >t induced by the mechwhere Eπ,σ [−|vi,t , ht ] represents the expectation with respect to histories (h anism π and the strategy profile σ, given that the value of agent i at time t is vi,t and an initial history ˜ τ ) to represent agent i’s reported value in period τ , with ht . For τ ≥ t, we denote vˆi,τ = σi,τ (vi,τ , h   ˜ τ recursively defined as h ˜τ = h ˜ τ −1 , v ˜ τ −1 ) starting from h ˜ t = ht . In ˆ τ −1 , π τ −1 (ˆ history h vτ −1 , h order to facilitate comparisons across different discount factor, in the expression for Vi,t we multiply by 1 − β to obtain an “average” discounted utility-to-go. Using this notation, the interim incentive compatibility constraints on mechanism π are given as follows:     Vi,t π, i|vi,t , ht ≥ Vi,t π, (σi , i−i )|vi,t , ht ,

∀vi,t , σi , ht , i, t ,

(1)

where ii represents the truthful reporting strategy for agent i, i.e., ii,t (vi,t , ht ) = vi,t . Hereafter, we 9

say a non-anticipating mechanism π is perfect Bayesian incentive compatible (PBIC) if π satisfies (1). These constraints enforce that, at every point in time, each agent is better off reporting truthfully when other agents report truthfully, regardless of past reports and allocations. We next define the set of achievable utilities, Uβ as the following. Uβ , {u ∈ Rn | ui = Vi (π, i), for a PBIC mechanism π} ,

(2)

where Vi (π, σ) , Evi,1 [Vi,1 (π, σ|vi,1 , ∅)] is the total expected utility of agent i when the planner implements mechanism π, and agents employ strategy profile σ. For any state u = (ui )ni=1 in Uβ , there must exists a non-anticipating direct (dynamic) PBIC mechanism π which achieves utility ui for all players i = 1, . . . , n. Specifically, when the planner implements mechanism π, every player truthfully reporting each period’s value while believing with probability 1 that others report truthfully is a PBE. Moreover, the corresponding expected discounted sum of the valuations generated by π for agent i is equal to ui . Because social welfare is the expected discounted sum of total valuations, the component sum of u corresponds to the social welfare obtained by π. Therefore, the maximum social welfare that can be P P obtained by a PBIC mechanism is Jβ∗ = maxu∈Uβ ni=1 ui . We denote vector u∗β ∈ arg maxu∈Uβ ni=1 ui to represent the utilities of the agents under an optimal mechanism. The above characterization of Uβ allows us to readily optimize any objective involving the total expected utility of each agent. Although in this paper, we only focus on the maximum achievable social welfare, other objectives can be easily accommodated accordingly from the feasible set Uβ . Unfortunately, characterizing Uβ directly by analyzing all non-anticipating mechanisms is not possible in general, because the dimensionality of the history grows exponentially with time. Therefore, in the following section, we provide an equivalent, recursive definition of Uβ using the promised utility framework.

2.2

Promised Utility Framework

Because the planner has commitment power and values are independent, we can employ the promised utility framework to recursively formulate the set of achievable utilities, Uβ . We first present the framework and then show its equivalence with the definition (2) in the end of this subsection.

10

Note that in order to determine if an allocation for the current time period is incentive compatible, the planner needs to understand the impact of today’s actions on the continuation game induced by the mechanism. The promised utility framework builds on the observation that, because agents are expected value maximizers, the next period’s continuation utilities constitute a sufficient statistic for the problem of determining if an allocation for the current time period is incentive compatible. Loosely speaking, we denote state ut = (ui,t )ni=1 to represent the vector of expected discounted total future values starting from period t. That is, " ui,t = (1 − β)E

∞ X

# β

τ −t

vi,τ πi,τ

.

τ =t

In the beginning of period t, the planner needs to fulfill the current state ut as a promise to agents through future allocations. We enforce this recursively by having the planner determine the current period’s allocation of the resource, as well as next period’s promised utilities ut+1 . For each agent, the expected value of the current’s period allocation plus the next period’s promised utility has to equal the current’s period promised utility. We refer to the mechanism associated to the allocation of a single resource in a time period as a stage mechanism. More formally, for any given state u ∈ Rn , a stage mechanism is given by an allocation function p(·|u) : [0, v¯]n → P and a future promise function w(·|u) : [0, v¯]n → Rn , which map the vector of agents’ reports in the current period to an allocation vector p and a next state w, respectively. We drop the dependence on u when referring to a fixed state.2 A stage mechanism (p, w) should satisfy the following constraints. First, the allocation function should be feasible. That is, n X

pi (v) ≤ 1 and p(v) ≥ 0, ∀v .

(FA)

i=1

Additionally, the mechanism should satisfy the following promise keeping constraint, ui = E[(1 − β)vi pi (v) + βwi (v)], i ,

(PK(u))

We assume that p and w lie in the space L∞ , L∞ ([0, v¯]n , (Rn , k · k1 )) of essentially bounded vector functions (see Appendix A.3). This is required to show that the recursive approach delineated in Proposition 2.3 and Corollary 2.1 converges to the set of achievable utilities Uβ . Since the space L∞ is an equivalence class of functions which agree almost everywhere, all point-wise inequalities are understood to hold almost everywhere (a.e.). To simplify the exposition we drop the “almost everywhere” qualifier in the rest of the paper. 2

11

which guarantees that the promised utility u is fulfilled by the mechanism. Finally, an agent should not have an incentive to misreport the true type. The following interim incentive compatibility constraint imposes that, for each agent, reporting the value truthfully yields an expected utility at least as large as any other strategy, when other players report truthfully. Denote Pi (v) , Ev−i [pi (v, v−i )] to represent the interim allocation, and Wi (v) , Ev−i [wi (v, v−i )] the interim future promise of agent i. The incentive compatibility constraints are given by: (1 − β)vPi (v) + βWi (v) ≥ (1 − β)vPi (v 0 ) + βWi (v 0 ), ∀i, v, v 0 . n

(IC) n

Using the constraints defined above, we next define the set operator Bβ : 2R+ → 2R+ for a given set A ⊂ Rn+ as follows: Bβ (A) = {u ∈ Rn+ | ∃(p, w) satisfying (IC), (FA), (PK(u)), and w(v) ∈ A for all v} .

(3)

Essentially, set Bβ (A) contains all promised utilities u that can be supported by future promise functions w in set A, while satisfying feasibility and incentive compatibility constraints. Although the operator Bβ is analogous to operator B in Abreu et al. (1990, p. 1047), the specific constraints used in our definition are different. Abreu et al. (1990) study sequential equilibria of repeated games with imperfect monitoring, in which each player has a finite action space. In our setting, however, the stage game itself is induced by the stage mechanism selected by the planner. In this game, each agent has an uncountable action space because agents’ private values are continuous. The operator Bβ provides a certificate to check whether a given set is a subset of Uβ , according to the following result. Proposition 2.1. If a set A satisfies A ⊆ Bβ (A), then we have Bβ (A) ⊆ Uβ . The proof of Proposition 2.1 is constructive: we show that every point u ∈ Bβ (A) lies in Uβ by constructing a PBIC mechanism that achieves utility u. The construction proceeds as follows for a fixed sample path of reports (ˆ vt )t≥1 . Because u ∈ Bβ (A), we can pick an allocation function p1 and future promise function w1 for the first time period such that w1 (ˆ v1 ) ∈ A. The condition A ⊆ Bβ (A) allows us to sequentially pick allocations functions pt and future promise functions wt for each time period t > 1, while guaranteeing that all future states wt (ˆ vt ) remain in A. The promise keeping constraints imply that the expected utility of the agents under truthful reporting is equal to u. The 12

resulting mechanism is PBIC from (IC), because from the one-shot deviation principle it is sufficient to consider single-period deviations. Following Abreu et al. (1990), we refer to sets that satisfy A ⊆ Bβ (A) as self-generating. That is, all the promised utilities in such a set A can be fulfilled with future promises from within the same set. Proposition 2.1 implies that any state in a self-generating set can be achieved by a PBIC mechanism, because this state is in the set Uβ . Furthermore, if there exists a specific mechanism (p, w) that satisfies (IC), (FA), (PK(u)) for all u ∈ A, and w(v|u) ∈ A for all v and u ∈ A, then we call the set A to be self-generating with respect to mechanism (p, w).  Pn Remark 2.1. It is worth noting that the “lower triangle” set L , u ∈ Rn+ | i=1 ui ≤ E[v] is selfgenerating. In fact, for any state u ∈ L, consider the random allocation rule pLi (v|u) , ui /E[v] regardless of the value v. Such an allocation rule pL , together with the future promise functions wL (v|u) , u, achieves utilities u, i.e., satisfy (PK(u)). Therefore, the lower triangle set L is self-generating with respect to mechanism (pL , wL ), and, therefore, is a subset of Uβ for any discount factor β. Proposition 2.1 states that any self-generating set is a subset of the set of achievable utilities, Uβ . The following result further demonstrates that set Uβ itself is self-generating, and, therefore, a fixed point of the operator Bβ . The result implies that the set of achievable utilities, Uβ , defined according to summations of allocations over an infinite horizon, can be equivalently represented through stage mechanisms. In particular, the stage mechanisms satisfy constraints (PK(u)) and (IC) in a recursive manner, and with the future promise functions w lying in the same set Uβ . Proposition 2.2. The set of achievable utilities, Uβ , satisfies Uβ ⊆ Bβ (Uβ ). Therefore, Uβ = Bβ (Uβ ). We prove the result by showing that for every point u ∈ Uβ there exists a stage mechanism (p, w) satisfying the conditions in (3). Because u ∈ Uβ , there exists a PBIC mechanism π with ui = Vi (π, i) for all i, and we can set the candidate stage mechanism to the allocation and continuation values of ˆ 1 , set p(ˆ π for the first time period. That is, for reports for the first period v v1 ) = π 1 (ˆ v1 , h1 ) with h  i h1 = ∅ and wi (ˆ v1 ) = Evi,2 Vi,2 π, i|vi,2 , h2 with h2 = (ˆ v1 , π 1 (ˆ v1 , h1 )). The candidate mechanism trivially satisfies (IC), (FA) and (PK(u)). We prove w(ˆ v1 ) ∈ Uβ by showing that the shifted mechanism obtained by implementing at time t the allocation of mechanism π at t + 1 given fixed first period ˆ 1 , is PBIC and achieves utilities w(ˆ reports v v1 ). Finally, we show that the set Uβ can be obtained through repeatedly applying operator Bβ . 13

 n Proposition 2.3. Let U 0 = 0, E[v] and U k = Bβ (U k−1 ) for all k ≥ 1. Then, we have U k ⊆ U k−1 and lim U k = Uβ . k→∞

The set U 0 can be understood as the achievable utilities of a relaxation in which the resource can be simultaneously allocated to all agents in every period. It is not hard to see that the operator Bβ is monotone, and Bβ (U0 ) ⊆ U0 . This implies that the sequence U k is monotone and converges to a set U ∞ . We prove the result by showing that Uβ ⊆ U ∞ and U ∞ ⊆ Uβ . For the first part, notice that because Uβ ⊆ U 0 and Uβ is a fixed-point of Bβ , monotonicity of the operator Bβ implies that Uβ ⊆ U k for all k, and therefore its limit. For the second part, it suffices to show, following Proposition 2.1, that U ∞ is self-generating. This last step of the proof is technical and relies on the topological properties of the space of stage mechanisms. Specifically, because U ∞ ⊆ U k , for each u ∈ U ∞ we can construct a sequence of stage mechanisms (pk , wk ) satisfying (IC), (FA), (PK(u)), and wk (v) ∈ U k−1 for all v. Because the space of stage mechanisms satisfying these conditions is compact (under an appropriate topology), we can construct a stage mechanism (p, w) satisfying (IC), (FA), (PK(u)), and w(v) ∈ U ∞ for all v by taking limits.

2.3

Support Function Representation

The iterative procedure described in Proposition 2.3 is of theoretical interest, but does not directly yield a straightforward numerical procedure due to the difficulty of determining set Bβ (A) from a set A. In this section, we present an equivalent, support function representation of the set Uβ . This support function representation is not only amenable to numerical procedures, but also provides a foundation for the proof of our asymptotic results. First, we present some basic properties of the set Uβ , which enable us to obtain its support function representation. The next result shows that the set of achievable utilities is convex and compact. The result follows from Proposition 2.3, and the fact that U 0 is convex and compact, and that the operator Bβ preserves convexity and compactness. Lemma 2.1. The set of achievable utilities, Uβ , is convex and compact, and satisfies Uβ = Rn+ ∩hyp(Uβ ) ¯ , ∃¯ where hyp(Uβ ) = {u ∈ Rn | u ≤ u u ∈ Uβ }. Following Luenberger (1969, p. 44), any convex set Uβ can be represented by its support functions.

14

In particular, for any fixed α ∈ Rn such that kαk1 = 1, the support function of set Uβ is given by φβ (α) , sup αT u .

(4)

u∈Uβ

Furthermore, we focus on α ≥ 0, because all nonnegative Pareto dominated points lie in Uβ , following Lemma 2.1. Proposition 2.3 allows us to obtain a recursive representation of the support function φβ (α). To that end, for a generic function ψ(α), define operator Tβ as: [Tβ ψ](α) = sup E (p,w)

" n X



 αi (1 − β)vi pi (v) + βwi (v)

#

i=1

s.t. (IC), (FA), ˜ T w(v) ≤ ψ(α) ˜ , ∀v ∈ [0, v¯]n , α ˜ ∈ Rn+ . α

(5)

The definition of operator Tβ involves an infinite-dimensional linear optimization problem. We can ˜ on a grid, such that α ˜ ≥ 0 solve it approximately by considering constraints (5) only for v and α ˜ 1 = 1. Furthermore, we can define the operator of recursively implementing operator Tβ and kαk as Tβk ψ , Tβ (Tβk−1 ψ). The following result states that φβ can be obtained by repeatedly applying operator Tβ . The proof, again, follows from Proposition 2.3, and the fact that convergence of convex and compact sets is equivalent to convergence of support functions. Corollary 2.1. The support function φβ is a fixed point of Tβ , i.e., φβ = Tβ φβ . Furthermore, we have φβ (α) = lim [Tβk φ0 ](α) for all α, starting from φ0 (α) = E[v]. k→∞

Figure 1a demonstrates the set of achievable utilities, Uβ with two agents. The lines in the graph are the supporting hyperplanes, which are computed from the iterative procedure described in Corollary 2.1. The blank area outlined by the supporting hyperplanes is the set Uβ . Although the procedure described in Corollary 2.1 generates the achievable set Uβ , it does not directly provide PBIC mechanisms achieving each state in the set. Later in our paper, we provide a mechanism along with a subset of Uβ such that the subset is self-generating with respect to the mechanism. In order to establish our main result that efficient allocation is achievable asymptotically as the discount factor approaches one, we first propose a “perfect information achievable set” that provides an upper bound to the set of achievable utilities. 15

0.5

0.45

0.45

0.4

0.4

0.35

0.35

0.3

0.3

u2

u2

0.5

0.25

U U0.6 U0.8 L

0.25

0.2

0.2

0.15

0.15

0.1

0.1

0.05

0.05 0

0 0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

0

0.1

0.2

0.3

u1

u1

(a)

(b)

0.4

0.5

Figure 1: Illustration of achievable sets in a two-agent case. Figure 1a depicts the achievable set Uβ with β = 0.8 and its supporting hyperplanes. Figure 1b depicts efficient frontiers of sets Uβ with β = 0.6 and β = 0.8, and the perfect information achievable set U and the lower triangle set L. Here values of v follow a uniform [0, 1] distribution with E[v] = 0.5.

2.4

Perfect Information Achievable Set

We define the perfect information (PI) achievable set, U, as the set of utilities attainable when values are publicly observable by the planner. This set is given by: U , {u ∈ Rn+ | ui = E[vi pi (v)] for all i, for some p satisfying (FA)} .

(6)

Clearly, for any β ∈ [0, 1) we have that Uβ ⊆ U. Similar to (4), for any α ∈ Rn+ with kαk1 = 1, define the support function of the convex perfect information achievable set U as follows: T

φ(α) , sup α u =

sup

u∈U

p s.t. (FA)

n X

 Ev [αi vi pi (v)] = Ev

i=1

 max αi vi ,

i=1,...,n

(7)

where the second equation follows from the definition of the PI achievable set, and the third from optimizing pointwise over values. Numerically, one can start the iterative algorithm of Corollary 2.1 from φ, instead of φ0 , which leads to faster convergence. In fact, Figure 1a is generated by starting from φ.

16

The support function φ satisfies the following properties. Proposition 2.4. The support function φ(α) given in (7) is convex, differentiable for α ∈ Rn+ and twice differentiable for α ∈ Rn+ such that α > 0. Moreover, the partial derivatives for all i are given by  n o ∂φ . (α) = Ev vi 1 αi vi ≥ max αj vj j6=i ∂αi Differentiability of the support function follows because values are absolutely continuous. The gradient ∇φ of the support function for any α corresponds to a point on the efficient frontier of the set U. Specifically, for any convex set A ⊂ Rn , define E(A) to represent its efficient frontier:  E(A) , u ∈ A | for all u0 ∈ A with u0 6= u, ∃i such that u0i < ui . Because the support function is differentiable and the set U is convex and closed, for every state u  on the efficient frontier of U there exists some α such that ∇φ α = u (see, e.g., Schneider 2013, Corollary 1.7.3 on p. 47). Furthermore, Proposition 2.4 implies that all points on the efficient frontier of the PI set are n o achievable by allocations of the form pi (v) = 1 αi vi ≥ maxj6=i αj vj . That is, the resource is allocated to the agent with the highest α-weighted value. More generally, for any point u ∈ U, not necessarily on the efficient frontier, we can define α(u) as α(u) ∈

xT u − φ(x) .

arg max

(8)

x:kxk1 =1,x≥0

 It is easy to verify that for any u ∈ E(U), we have ∇φ α(u) = u. The first-best total utility, J FB , is achieved by allocating the resource to the agent that values it   FB most in each period, i.e., J = E max vi . Because the first-best utility is attained by the allocation i=1,...,n n o 3 rule pi (v) = 1 vi ≥ max vj , and Uβ ⊆ U, we must have j6=i

J FB = max u∈U

n X

ui ≥ max u∈Uβ

i=1

n X

ui = Jβ∗ .

(9)

i=1

Figure 1b compares the boundaries of sets U and Uβ for different β values. The set Uβ is monotonically 3

In our setting, the probability of having a tie is zero.

17

increasing as β increases, and, therefore, the planner is able to achieve higher total utility. Furthermore, it appears that as the time discount factor approaches one, the set Uβ approaches the full information achievable set U. We now provide a high level summary our approach.

An Overview of Our Approach.

If the set Uβ converges to U as the discount factor β approaches one,

inequality (9) implies that the optimal social welfare, Jβ∗ , converges to the first-best, J FB . However, the set Uβ is hard to study directly. Therefore, we design a factor, Fβ ∈ [0, 1], to obtain the following “sandwich” condition for set Uβ : Fβ U ⊆ Uβ ⊆ U , in which Fβ U , {Fβ u | u ∈ U} .

(10)

In particular, the sequence of factors Fβ is designed to converge to one as β converges to one, which implies our result. Following Proposition 2.1, in order to establish the condition Fβ U ⊆ Uβ , we only need to show that the set Fβ U is self-generating, or, Fβ U ⊆ Bβ (Fβ U). In the rest of the paper, we propose a mechanism ˆ such that the set Fβ is self-generating with respect to the mechanism (ˆ ˆ Consequently, (ˆ p, w), p, w). every state in Fβ U is achievable following this incentive compatible mechanism.

3

Central Region and Main Phase Mechanism

The main phase of the mechanism is defined for a so-called central region, Uˆβ , defined through a pair of scalars uβ ∈ [0, E[v]] and Fβ ∈ [0, 1]. The specific values of those scalars depend on the number of agents involved and the distribution of values, and are deferred to the following sections. For this section, it is sufficient to keep in mind that uβ approaches zero and Fβ approaches one as β approaches one. Define the central region Uˆβ as Uˆβ = Fβ U ∩ {u ∈ Rn | ui ≥ uβ , ∀i} ,

(11)

which is a subset of Fβ U that includes states that are component-wise higher than the threshold uβ . Figure 2a illustrates such a central region, where we implement the main phase mechanism, to be described next. ˆ (·|u) : [0, v¯]n → P and future promise The main phase mechanism consists of allocation functions p 18

0.5

0.5

0.45 0.4

E[v] − uβ

U Fβ U uβ

0.35

0.4 0.35 0.3

u2

u2

0.3

U Fβ U uβ L

0.45

0.25

0.25

0.2

0.2

0.15

0.15

0.1

0.1

0.05

0.05

0

0 0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

0

0.05

0.1

0.15

0.2

u1

0.25

u1

(a) Central Region

0.3

0.35

0.4

0.45

0.5

E[v] − uβ

(b) Boundary Region

Figure 2: The central region and boundary region in a two-agent case. Values of v are uniformly distributed in [0, 1], and Fβ = 0.8 and uβ = 0.1. The solid curve is the efficient frontier of the perfect information achievable set U. The dashed lines represent the threshold uβ , and the dotted dashed curve represents the scaled set, Fβ U. In Figure 2a, the shaded area represents the central region, Uˆβ . In Figure 2b, the shaded area represents the boundary region within the lower triangle set L. In this case E[v] = 0.5 and E[v] − uβ = 0.4. ˆ ˆ functions w(·|u) : [0, v¯]n → Fβ U for all u ∈ Uˆβ , which satisfy (IC), (PK(u)), and w(v|u) ∈ Fβ U for all v. Next we explain them separately for any state u in the central region. ˆ . Note that for any point u on the efficient frontier E(Fβ U) of the set Fβ U, the state Allocation p u/Fβ is on the efficient frontier E(U). Recall from the discussion in the last section, with perfect information, promised utilities u/Fβ can be achieved with allocations that weigh values according to α(u/Fβ ) defined in (8). Motivated from this, for any state u in the central region Uˆβ defined in (11), we define the allocation function to be n o pˆi (v|u) = 1 αi (u/Fβ )vi ≥ max αj (u/Fβ )vj , j6=i

(12)

ˆ corresponds to allocating the resource to the agent with the largest That is, the allocation function p weighted value, where the weights are associated to the efficient frontier of the perfect information achievable set. By Proposition 2.4, the expected utility of this allocation satisfies Ev [vi pˆi (v|u)] =  ∂φ α(u/Fβ ) , i.e., the allocation delivers the utility of the point on the efficient frontier of the set U ∂αi 19

with normal α(u/Fβ ).

0.5

0.5

α(u/Fβ )

U Fβ U uβ

u/Fβ + µe

0.45 0.4

0.4

u + Fβ µe

0.35

U Fβ U uβ

0.45

0.35 A B

u

0.3

C

0.3

u2

u2

D 0.25

0.25

0.2

0.2

0.15

0.15

0.1

0.1

0.05

0.05

0

0 0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

0

u1

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

u1

ˆ (b) Illustration of the future promises w(v|u)

(a) Illustration of the weight α(u/Fβ )

Figure 3: Figure 3a illustrates the weight α(u/Fβ ) in a two-agent case with Fβ = 0.8, uβ = 0.1, and u = (0.125, 0.325). In this case α(u/Fβ ) = (0.3675, 0.6325), and µ = 0.03. Figure 3b illustrates the ˆ future promises w(v|u) given in (14) for some choices of v in a two-agent case, with β = 0.9, Fβ = 0.8, uβ = 0.1, u = (0.125, 0.325). Points A, B, C and D correspond to v taking values (1, 0), (0, 0), (1, 1), and (0, 1), respectively. (For the purpose of illustration , the value of Fβ here is not calculated according to the formula presented in Section 4.)

Remark 3.1. It is worth illustrating geometrically how the weights α(u/Fβ ) are determined. According to the optimality conditions for (8), for any state u ∈ Fβ U, we must have u/Fβ = ∇φ(α(u/Fβ )) − µe for some nonnegative scalar µ, where e is the vector of 1’s in Rn . (Here µ corresponds to the dual variable of the kxk1 = 1 constraint.) Furthermore, as explained before, the vector Fβ ∇φ(α(u/Fβ )) is on the efficient frontier of set Fβ U. Therefore, as illustrated in Figure 3a, the weights α(u/Fβ ) are determined by first projecting the state u along the “45 degree line” up to the point u + Fβ µe on the efficient frontier of Fβ U. Then we scale this point by 1/Fβ to obtain a point u/Fβ + µe on the efficient frontier of U. Weights α(u/Fβ ) correspond to the normal vector of the hyperplane supporting the point u/Fβ + µe on the efficient frontier of U. ˆ First, it straightforward to determine the interim future promise funcFuture Promise Function w. ˆ i (vi |u) , Ev [w tion W −i ˆi (v|u)] for each agent i from the incentive compatibility constraints. Following the standard argument of Myerson (1981), the (IC) constraints uniquely determine an expression for 20

ˆ i (vi |u) in terms of the interim allocation Pˆi (vi |u) , Ev [ˆ W −i pi (v|u)] and the interim promise for the ˆ i (0|u). Further removing W ˆ i (0|u) using the (PK(u)) constraints yields the following lowest type W interim future promise function: ˆ i (vi |u) = 1 W β

 Z ui + (1 − β)

vi

Pˆi (y|u)dy − Pˆi (vi |u)vi −

0

Z



F¯ (y)Pˆi (y|u)dy

 , ∀i .

(13)

0

Because the interim allocation is increasing in an agent’s report, equation (13) is necessary and sufficient to guarantee incentive compatibility. ˆ in (13) are uniquely determined by p ˆ , the exAlthough the interim future promise functions W ˆ may not be uniquely determined given p ˆ . This is because multiple post future promise functions w ex-post future promise functions may correspond to the same interim future promise function. For example, we can set the ex-post future promise function w ˆi (vi , v−i |u) to the interim future promise ˆ i (vi |u) for all v−i . This choice, however, does not guarantee that starting from an initial function W state u ∈ Fβ U, the future promises remain in Fβ U for all possible reports. In fact, if the state u is sufficiently close to the efficient frontier E(Fβ U), there exist values of v such that the future promise ˆ falls outside the set Fβ U. If so, state u cannot be achieved using such a mechanism. W The key consideration, therefore, is that for any value v ∈ [0, v¯]n and state u ∈ Fβ U, we must ensure ˆ is feasible, i.e., w(v|u) ˆ that the future promise function w ∈ Fβ U, so as the set Fβ U is self-generating ˆ Specifically, the ex-post future promises need to be (i) nonnegative with respect to mechanism (ˆ p, w). and (ii) within the efficient frontier of Fβ U. In this section, we address the design issue (ii), and leave the issue (i) to Sections 4 and 6. In fact, the threshold uβ is designed to resolve issue (i). In order to guarantee condition (ii), we implement interim future promises so as to minimize the risk of the next time period’s promise utilities lying outside the achievable set Fβ U. The ex-post future promise function for any state u in the central region Uˆβ and value v ∈ [0, 1]n is given by: ˆ i (vi |u) − w ˆi (v|u) = W

i 1 X αj (u/Fβ ) h ˆ ˆ j (˜ Wj (vj |u) − Ev˜j [W vj |u)] . n−1 αi (u/Fβ )

(14)

j6=i

The design of the future promise functions resembles the d’Aspremont–G´erard-Varet–Arrow mechanism (d’Aspremont and G´erard-Varet, 1979; Arrow, 1979) and the risk free transfers of Es¨o and Futo (1999). In the context of a risk-averse seller in a static setting, Es¨o and Futo (1999) propose a similar transfer rule that gives rise to a constant ex-post revenue. Analogously, our choice of future promise 21

functions guarantees that the weighted sum of the ex-post future promises is constant. The following result shows that the future promises lie in a plane with normal α(u/Fβ ). ˆ Proposition 3.1. For any given state u ∈ Uˆβ , the future promise vector w(v|u) lies within a plane in Rn for all v. Specifically, the plane is described by the following equation,  1−β   ˆ α(u/Fβ )T u − w(v|u) = α(u/Fβ )T ∇φ α(u/Fβ ) − u ≥ 0 . β The fact that our future promises lie on a plane resembles the concept of “enforceability with respect to hyperplanes” in Fudenberg et al. (1994). Furthermore, our plane being parallel to a support function of the (PI) achievable set echoes the construction of future promises given in the proof of Lemma 6.1 in Fudenberg et al. (1994). ˆ The properties stated in Proposition 3.1 are useful towards establishing that future promises w(v|u) fall in the set Fβ U. Recall that α(u/Fβ ) gives the normal of the supporting hyperplane of a point u on the efficient frontier of Fβ U. Interpreting α(u/Fβ )T (u − x) as the “signed directional distance” ˆ of a point x ∈ Rn to the hyperplane supporting u, we obtain that α(u/Fβ )T (u − w(v|u)) measures how close the future promises are to the hyperplane supporting u. Among all ex-post future promise ˆ i (vi |u), the one according to expression functions which satisfy the interim future promise functions W (14) is “pushed” the farthest from the efficient frontier E(Fβ U). This is formalized in the next result. ˆ i (vi |u) be the interim future promise given in Proposition 3.2. Fix a state u ∈ E(Uˆβ ), and let W ˆ (13). Then, the ex-post future promise w(v|u) defined in (14) is an optimal solution of the following optimization problem: max ˜ w(·)

s.t.

˜ min α(u/Fβ )T (u − w(v)) v

(15)

ˆ i (vi |u) ∀vi , i Ev−i [w ˜i (vi , v−i )] = W

where α(·) is defined in (8). ˆ Proposition 3.1 shows that the signed directional distance between w(v|u) and the hyperplane supporting the projection of u onto E(Fβ U) is independent of v and strictly positive. This provides ˆ lies within the efficient frontier of Fβ U. As in Fudenberg et al. (1994), we show some indication that w ˆ that this is the case by carefully balancing the “step size” w(v|u) − u against the curvature of the efficient frontier at the projection of u onto E(Fβ U). We formally establish this for the two-agent case 22

in the next section. ˆ Figure 3b demonstrates, in a two-agent case, the future promised function w(v|u) starting from a ˆ state u ∈ Uˆβ . The figure shows that the realized future promise w(v|u) ranges on a line when we vary ˆ values of v. Moreover, we also observe that for some values of v, the ex-post future promise w(v|u) may fall out of the central region Uˆβ , but remains in the set Fβ U.

4

Boundary Region and Mechanism for the Two Agent Case

ˆ for the central region. In order to In the previous section we have described the mechanism (ˆ p, w) complete the description of the mechanism, we need to specify the mechanism for the “boundary region,” or, when any of the initial state ui is below the threshold uβ . As it turns out, the two-agent case is much simpler to describe compared with the general n > 2 case. In this section, we focus on the two-agent case. We generalize the analysis to larger n in Section 6. We start by specifying the scalars Fβ and uβ as follows: Fβ = 1 −

uβ and uβ = ξ(1 − β) , E[v]

(16)

where ξ is a constant scalar independent of β, and is given in equation (33) in the appendix. In fact, the threshold uβ is determined so that the efficient frontier E(Fβ U) intersects with each axis at the point E[v] − uβ . Therefore, for any u in the boundary region of Fβ U, that is, when either u1 or u2 is below the threshold uβ , the state u must be within the lower triangle set L. See Figure 2b for an illustration. ˆ for the central region in the previous section. We have already described the mechanism (ˆ p, w) For a state u in the boundary region, because it is also in the lower triangle region, we define the mechanism to be, simply, random allocation. That is, ˆ (v|u) = pL (v|u) = u/E[v], and w(v|u) ˆ p = wL (v|u) = u , if ∃ui < uβ , i ∈ {1, 2}. ˆ satisfies (IC), (FA), (PK(u)) for u in the boundary Following Remark 2.1, the mechanism (ˆ p, w) region. Furthermore, it is obvious that future promises remain in the set Fβ U in this region. Therefore, ˆ the boundary region is self-generating with respect to mechanism (ˆ p, w).

23

ˆ for all initial state u ∈ Fβ U, we are Now we have completed the description of mechanism (ˆ p, w) ready to proceed with the claim that the set Fβ U is self-generating with respect to the mechanism ˆ What remains to be shown is that following the definitions of Fβ and uβ in (16), the future (ˆ p, w). promises indeed remain in set Fβ U according to the main phase mechanism. This is formally established in the following result. Proposition 4.1. Let β ∈ (0, 1) be such that Fβ ≥ 0.5. For any β ≥ β and initial state u ∈ Fβ U, the ˆ ex-post future promise function w(v|u) ∈ Fβ U. The above key result of our paper relies crucially on the design of the constant ξ in (16), which determines the scaling factor Fβ and the lower bound uβ . First of all, the lower bound uβ has to be ˆ high enough so that the future promises w(v|u), defined in (14), remain positive. To achieve this we ˆ first provide an upper bound on kw(v|u) − uk2 , which measures the distance between current and future promised utilities, in terms of β and other model parameters. Using this bound we show that future promises remain positive for all u with ui ≥ uβ , when ξ is suitably chosen. Second, and perhaps more importantly, we need to make sure that the boundary of the convex central region Fβ U (its efficient frontier) is “flat” enough so that starting from a point u very close to ˆ the boundary, the next point w(v|u) does not fall outside of it. Bounding the curvature of the efficient frontier E(Fβ U) is not easy. We instead work with the signed distance function between a point u and the convex set U, which is defined as IU (u) =

max

xT u − φ(x) .

(17)

x:kxk1 =1,x≥0

The signed distance IU (u) measures the distance of a point to the efficient frontier of the PI set U. It is positive if the point lies outside the set, zero if on the efficient frontier of the set, and negative otherwise. Following (8), we obtain that IU (u) = α(u)T u−φ(α(u)) = α(u)T (u − ∇φ(α(u))), because φ(α) = ∇φ(α)T α. Recall that ∇φ(α) corresponds to a point on the efficient frontier of the PI set with normal α. Therefore, the signed distance function measures the “directional distance” of a point u to the “closest” point on the efficient frontier. The signed distance between any point u and the scaled set Fβ U is given by IU (u/Fβ ). We design ˆ ˆ the constant Fβ so that IU (w(v|u)/F lie in the β ) ≤ 0, which guarantees that future promises w(v|u) ˆ = w(v|u). ˆ scaled set Fβ U. Here are some intuitions using the shorthand notation w Consider the 24

following quadratic approximation of the signed distance function at the current state u/Fβ ,  IU

ˆ w Fβ



 ≈ IU

u Fβ



 + ∇IU

u Fβ

T 

ˆ −u w Fβ

 +

1 2



ˆ −u w Fβ

T

 Hess IU

u Fβ



ˆ −u w Fβ

 ,

where Hess IU (u) ∈ Rn×n represents the Hessian of function IU evaluated at u. The zeroth-order term is nonnegative because the current state u lies in Fβ U. The Envelope Theorem implies that ∇IU (u) = ˆ according to Proposition 3.1. α(u). Thus, the first-order term is negative and independent of w, Because the signed distance function IU is convex, the second-order term is nonnegative. We control the contribution of the second-order term by bounding the maximum eigenvalue of the Hessian matrix ˆ − uk2 . As it turns out, our in terms of model parameters and using the aforementioned bound on kw ˆ is at most 0. Therefore, design of the constant ξ allows us to ensure that the signed distance of w ˆ fall below the efficient frontier E(Fβ U) starting from any point u ∈ Fβ U. future promises w Proposition 4.1 implies that starting from any state u ∈ Fβ U, we can construct a sequence of allocation and future promises which delivers that initial state. That is, every state in Fβ U is achievable following this mechanism. In particular, consider the state that maximizes u1 + u2 in Fβ U. The ˆ is able to achieve the social welfare given by mechanism (ˆ p, w) Jβ , max (u1 + u2 ) = Fβ max (u1 + u2 ) = Fβ J FB , u∈Fβ U

u∈U

because u ∈ Fβ U if and only if u/Fβ ∈ U. Because the set Fβ U is self-generating, it is a subset of Uβ , following Proposition 2.1. Therefore, the total social welfare satisfies Jβ ≤ Jβ∗ = max (u1 + u2 ). u∈Uβ

Overall, we have the following main theorem. Theorem 4.1. Let β ∈ (0, 1) be such that Fβ ≥ 0.5. For any β ≥ β, we have Fβ J FB = Jβ ≤ Jβ∗ ≤ J FB . It is clear that Fβ as defined in (16) approaches one as β approaches one. Therefore, the achievable set Fβ U approaches the perfect information set U, and, correspondingly, the optimally achievable social welfare Jβ approaches the first-best social welfare J FB . In particular, the convergence rate of our ˆ to efficiency is 1 − Fβ = O(1 − β). Additionally, because Fβ U converges to the PI mechanism (ˆ p, w) achievable set U as β approaches one, every point in the PI achievable set is asymptotically achievable

25

according to our mechanism. Now that we have completed the description of our mechanism, in the next section we provide some economic insights into our mechanism, before we proceed with the mechanism for the general n agent case.

5

Economic Insights

In this section, we shed light on the economic insights derived from our mechanism. In particular, we explain, intuitively, why our main phase mechanism is dynamically incentive compatible (inducing agents to report truthfully) and approximately efficient (approaching first-best social welfare as the discount factor converges to one).

Incentive Compatibility The main phase mechanism achieves incentive compatibility by introducing intertemporal substitution of consumptions. That is, according to our mechanism, reporting a high value today reduces the chance of receiving the resource in the future. Consequently, if today’s value is not as high, agents may forego today’s allocation in view of more valuable future opportunities. This effect stems from the following results. First, according to (12), in each period the allocation is determined by the comparison of weighted values among agents. The weights are determined by the promised utilities u. Following Remark 3.1, it is clear that for any u in the central region Fβ U, if agent i’s promised utility is larger than agent j’s, i.e., ui > uj , then αi > αj . This implies that the higher an agent’s promised utility, the higher the chance that the agent receives the resource. Furthermore, (IC) implies that higher valuation vi also increases agent i’s chance of receiving the resource. This is summarized in the following result. Proposition 5.1. Agent i’s allocation pˆi (v|u) is non-decreasing in the agent’s report vi (for fixed v−i and u), and non-decreasing in the agent’s promised utility ui (for fixed v and u−i ). Incentive compatibility implies that the interim future promise function of each agent is nonincreasing in his own report. That is, an agent’s future promised utility tends to be lower if the current period report is higher. The following result characterizes the ex-post future promise function.

26

Proposition 5.2. The future promise function w ˆi (v|u) is non-increasing in vi and non-decreasing in vj for j 6= i (for fixed u). As a result, reporting a higher value entails a higher chance of receiving the resource in the current period, at the expense of a lower future promised utility. This, in turn, translates to a lower chance of receiving the resource in the future. This provides an intuitive explanation on how the mechanism ensures that agents do not report higher than their true values. Furthermore, it is interesting to see how other agents’ reports affect a focal agent’s future promise. Figure 3b illustrates such a point. Compare, for example, points A and C, or B and D. As agent 2’s value increases from 0 to 1, agent 1’s future promised utility w1 increases. Intuitively, if another agent other than i reports a higher value, it decreases agent i’s chance of receiving the resource in the current period. Agent i is then compensated with a higher future utility, to be fulfilled by future allocations.

Efficiency The main phase mechanism starts at the state Fβ u∗ , where u∗ is the vector of agents’ utilities under the efficient allocation. That is, u∗i = Ev [vi 1 {vi ≥ maxj6=i vj }]. Therefore, the mechanism starts at the state with the largest component sum in the scaled set Fβ U. At this state, the allocation is efficient. ˆ (v|u) is always In fact, if a state u has equal components, i.e., ui = uj for all i, j, then the allocation p efficient, because the weights αi (u/Fβ ) are the same for all i. In Figure 4, we plot sample trajectories of promised utilities starting at state Fβ u∗ following our mechanism. As we can see, the sample trajectories concentrate around the 45 degree line. Correspondingly, the weights αi of all agents tend to be close to each other along these trajectories. As a result, the resource is allocated almost efficiently, until it reaches the boundary region. In Figure 4a, all trajectories reach the boundary region within 450 time periods. As agents become more patient and the discount factor β increases, the step size between current ˆ decreases (see Lemma C.2 in the Appendix). In Figure 4b, promised utility u and future promises w the first 250 steps of each trajectory are marked black while later steps are colored grey. As we can see, after 250 time periods the promised utilities are still concentrated around the initial state, and it takes longer to reach the boundary region in this case. Figure 5 illustrates the expected social welfare per round generated by our mechanism, which is

27

(a) Fβ = 0.8, uβ = 0.1 and β = 0.9969

(b) Fβ = 0.9, uβ = 0.05 β = 0.9985

Figure 4: Each figure demonstrates 100 sample trajectories. P given by Eut ,vt [ ni=1 vi,t pˆi (vt |ut )], as a function of time. During the first time periods, the mechanism is in the main phase and the expected social welfare per round is very close to that of the efficient allocation. Over time, trajectories drift to the boundary region where the expected social welfare per round drops significantly because there the allocation is highly inefficient. The boundary mechanism, albeit inefficient, is necessary to ensure that the incentive compatibility and promise keeping constraints are sustained. Furthermore, as the discount factor increases, the mechanism remains in the main phase for more time periods. As we can see from Figure 5a, it takes between 400 and 500 periods for all trajectories to reach the boundary region. In comparison, for a higher discount factor, Figure 5b shows that it takes between 1000 and 1500 time periods to reach the boundary region. As the time discount factor approaches one, the boundary mechanism is pushed further into the future and the mechanism allocates approximately efficiently for most of the horizon.

6

Generalization to n Agents

In this section, we generalize the analysis to settings with n agents, where n > 2. In this case, we need to carefully design the scaling factor and lower bound, and the boundary mechanism depending on the

28

0.9

0.9 Our Mechanism Efficient Allocation

Our Mechanism Efficient Allocation

0.8

0.7

Average Welfare per Round

Average Welfare per Round

0.8

0.6 0.5 0.4 0.3 0.2 0.1

0.7 0.6 0.5 0.4 0.3 0.2 0.1

0

0 500

1000

1500

2000

2500

500

Time

1000

1500

2000

2500

Time

(a) Fβ = 0.8, uβ = 0.1 and β = 0.9969

(b) Fβ = 0.9, uβ = 0.05 and β = 0.9985

Figure 5: In both figures, the main phase mechanism allocates efficiently until the state reaches the boundary region. In Figure 5a, the average time to reach the boundary region is 409, whereas this amount is 1396 in Figure 5b. number n of agents involved. We first describe the difficulties that arise in the general case, and then provide our mechanism and analysis. First of all, the boundary mechanism for the two-agent setting no longer works for the general setting. When there are only two agents, in the boundary region we use the randomization mechanism ˆ L ). If n > 2, however, the boundary region is not always contained within the lower triangle set (ˆ pL , w (n)

L anymore, as long as the lower bound for the n agent case, uβ , approaches zero with β approaching one. As a result, the randomized allocation is no longer feasible for the boundary region. Specifically, consider, for example, a three-agent setting as illustrated in Figure 6. Here we focus (3)

on a situation where one agent’s promised utility is below the threshold uβ . In Figure 6a, we plot the efficient frontier of the PI set E(U), its scaled version E(Fβ U), and the plane corresponding to (3)

u1 = 0.01 < uβ = 0.0167. Figure 6b demonstrates the intersections between the plane with efficient frontiers of sets U, Fβ U, and L, respectively. All points on the intersection of the plane and Fβ U lie in the boundary region. The state u represented by the circle, however, is outside the efficient frontier of the lower triangle set. At this state, u1 + u2 + u3 > E[v], which implies that the randomized allocation ˆ L is no longer feasible. p While the two-agent mechanism allocates the resource randomly when some agent’s promise utility lies in the boundary region, the three-agent mechanism shall allocate randomly only to the player

29

with low promised utility and implement the two-agent mechanism for the other players. Because the two-agent mechanism has been shown to attain every point in the two-agent PI achievable set as the discount factor increases, this construction allows us to attain points otherwise not achievable with random allocations. 0.5 0.5

0.45

0.4

0.4

U Fβ U u1 = 0.01

u1

0.3

U Fβ U L

0.35 0.3

u2

0.2

0.25 0.2

0.1

0.15 0 0

0.1

0.1 0.2 0.3 0.4

u2

0.5

0

0.1

0.2

0.3

0.4

0.05

0.5

0 0

u3

0.1

0.2

0.3

0.4

0.5

u3 (a) Efficient frontiers

(b) Level set

Figure 6: In Figure 6a, the outer surface with a solid mesh is E(U). The inner surface with a dotted mesh is the scaled efficient frontier E(Fβ U). The horizontal plane represents the slice corresponding (3) to u1 = 0.01, which is lower than the threshold uβ = 0.0167. Figure 6b plots the intersection of the surfaces in Figure 6a with level set u1 = 0.01 in the (u2 , u3 ) space. In both figures, the value (3) distributions are assumed to be uniform [0, 1], Fβ = 0.8, and uβ = 0.0167. More generally, suppose the main phase mechanism defined in Section 3 carries the promised utilities into a state in the boundary region, which means that at least some promised utility, say ui , is below (n)

the threshold uβ . By allocating the resource from this period on to agent i with probability ui /E[v], we can guarantee that agent i’s future promise w ˆi (u|v) remains at ui . As such, we convert the problem into one at a lower dimensional space. Therefore, when there are more than two players, the boundary region mechanism can be defined recursively, depending on how many players are still involved. (n)

Mechanism. We refer to the agents with promise utilities above the threshold uβ (n)

agents, in which uβ

is defined as 1

(n)

uβ = ξ (n) (1 − β) n+4 . 30

as the active

Here, ξ (n) is a constant scalar independent of β, provided in Definition E.2 in the appendix. At any point in time, the allocation and future promise for an inactive agent i are, simply, pˆi (v|u) = ui /E[v] and w ˆi (v|u) = ui , respectively. The mechanism for the active agents resembles the main phase mechanism described in Section 3. Consider a case with k active agents. That is, k out of the n components in the state vector u ∈ Rn (n)

are above the threshold uβ . Denote the subvector u(k) ∈ Rk to represent the promised utilities for the active agents. Further define the total probability that the resource is allocated to an active agent to be s(u) = 1 −

(n) n X ui 1{ui < uβ }

.

E[v]

i=1

Consider the k dimensional PI set U (k) , the corresponding support function φ(k) , and weights α(k) , as defined in (6), (7), and (8), respectively. (In these definitions the state vector u corresponds to a k (k,n)

dimensional vector.) Similar to Section 3, we scale the PI set U (k) with a factor s(u)Fβ (k,n)



, in which

is defined as the following (n)

(k,n) Fβ

,1−

n(k − 1)uβ

.

E[v]

Note that the scaling of the PI set needs to involve the factor s(u), because with probability 1 − s(u) the resource is allocated to the inactive agents. (n)

(n,n)

For the n agent case, the constants uβ and Fβ in Section 3 correspond to uβ and Fβ

, respectively.

In the boundary region with k active agents, the allocation of our mechanism for an active agent i is defined similarly to the main phase mechanism (12) for the k agent case. That is,         (k) (k) u u (k) (k)  vi ≥ max α(k)   vj . pi (v|u) = s(u)1 αi  j (k,n) (k,n)   j6=i s(u)F s(u)F β

(18)

β

The corresponding future utility is defined similar to (14), as  (k) αj  (k)

(k)

wi (v|u) = Wi (vi |u) −

1 k−1

X  j6=i

(k) αi 

u(k) (k,n)

s(u)Fβ

u(k) (k,n)

s(u)Fβ

31

  n h io  Wj(k) (vj |u) − Ev˜j Wj(k) (˜ vj |u) . 

(19)

(k)

Here, and the interim future promise function Wi

is as defined in (13) of Section 3, with the interim

allocation function defined accordingly. To summarize, at the beginning of each time period, the number of active agents k is updated to ˆ is defined as the following. reflect the remaining number of active agents. Then our mechanism (ˆ p, w) The allocation is given by

pˆi (v|u) =

   p(k) i (v|u) ,

if ui ≥ uβ ,

  ui /E[v] ,

otherwise.

   wi(k) (v|u) ,

if ui ≥ uβ ,

  ui ,

otherwise.

(n)

(20)

The future promise function is given by

w ˆi (v|u) =

(n)

(21)

(n,n)

Self-generating Set. Note that when the number of agents n is larger than 2, the set Fβ

U (n) is

not self-generating with respect to our mechanism. This is because as the number of active agents decreases to k < n, the PI achievable set U (k) is not a scaled version of the intersection between the ndimensional PI set and a subspace Rk . In Figure 6b, for example, the solid curve marks the boundary of the intersection between the 3-dimensional PI achievable set U (3) and the subspace u1 = 0.01. However, this set is different from the efficient frontier of the 2-dimensional PI achievable set U (2) , even with scaling. Consequently, when the number of active agents drops to k < n, there is a priori (k,n)

no guarantee that the promise utility lies in the set s(u)Fβ

U (k) .

Therefore, we define the following set Ωβ , which we show to be self-generating with respect to our ˆ Some additional notations are in order. For a vector u ∈ Rn and set κ ⊂ {1, . . . , N }, mechanism (ˆ p, w). we denote u(κ) to represent the subvector corresponding to components of u in the index set κ. We denote the complement of κ by κ ¯ . An inequality between a vector and a scalar means that each component of the vector satisfies this inequality. The set Ωβ is given by Ωβ =

[

n o (n) (n) (k,n) u ∈ Rn | u(κ) ≥ uβ , u(¯κ) < uβ , and u(κ) ∈ s(u)Fβ U (k) .

κ⊆{1,...,N } (k,n)

That is, for any state u in Ωβ with k active agents, the scaled PI achievable set s(u)Fβ

32

U (k) is

contained in the Ωβ set. The following proposition confirms that our construction of the lower bounds ensures that Ωβ is indeed self-generating. ˆ defined in (20)Proposition 6.1. The set Ωβ is self-generating with respect to the mechanism (ˆ p, w) (21). ˆ we need In order to show that Ωβ set is self-generating with respect to our mechanism (ˆ p, w), to argue that for all u in Ωβ , the mechanism given in (20)-(21) satisfies the conditions given in (3). The (IC), (FA), and (PK(u)) constraints follow by construction. The main step of the proof involves ˆ showing that future promises satisfy w(v|u) ∈ Ωβ for every report v. For any state u in Ωβ with k active agents, it is clear that future promised utilities of inactive agents remain in Ωβ . In the proof of Proposition 6.1, we first show that the subvector of future promises satisfies (k,n)

w(k) (v|u) ∈ s(u)Fβ

U (k) .

(22)

This step extends the geometric approach of Proposition 4.1 to higher dimensions by using the fact that the mechanism for active agents also satisfies the properties in Section 3. (In particular, in Appendix G we prove extensions of Propositions 3.1 and 3.2 that account for the scaling factor.) ˆ Condition (22) alone is not sufficient to establish our result because w(v|u) could involve fewer active agents than u. That is, in the next step the number of active agents may decrease to k 0 < k. 0

We need to show the stronger result that the subvector w(k ) (v|u), consisting of the components of (k0 ,n)

(n)

ˆ ˆ w(v|u) above the threshold uβ , lies in s(w(v|u))F β

(k,n)

accordingly such that the intersection between s(u)Fβ (k0 ,n)

ˆ agents is contained in s(w(v|u))F β

0

U (k ) . Therefore, we design the constant ξ (n) U (k) and the k 0 dimensional space of active

0

U (k ) . With this argument, (22) is sufficient to guarantee that

all future promises lie in Ωβ . Now we are ready to state the next theorem, which is the main result of this section. ˆ for n agents Theorem 6.1. There exists β ∈ (0, 1) such that for any β ≥ β the mechanism (ˆ p, w) satisfies (n,n)

Fβ (n,n)

Because the scaling factor Fβ

J FB ≤ Jβ ≤ Jβ∗ ≤ J FB .

converges to one as β approaches one, Theorem 6.1 implies that

ˆ approaches to the maximum expected discounted social welfare achieved by the mechanism (ˆ p, w) 33

(n,n)

first-best. In particular the convergence rate is 1 − Fβ

  1 = O (1 − β) n+4 . Similar to the two agent

(n)

case, because uβ converges to zero as β converges to one, set Ωβ converges to the PI achievable set U as β approaches one. Thus, every point in the PI achievable set is asymptotically achievable following our mechanism. Note that the convergence rate to first-best given in Theorem 6.1 for n = 2 is slower than the one in Theorem 4.1. The proof for the two-agent case given in Section 4 leverages some special structure of the problem, which is not present in the general case. One may be able to provide better convergence rates by tightening the analysis. We leave this to future research.

7

Conclusion and Extensions

In this paper, we study resource allocation with asymmetric information and no monetary transfer in a dynamic setting. The marginal cost for the resource is zero in each period. Therefore, the mechanism designer focuses on allocation efficiency. We propose a mechanism that achieves asymptotic efficiency as the time discount factor approaches one. Our analytical framework is focused on self-generating sets of agents’ promised utilities. The essence of our approach is to establish that a self-generating set with respect to our mechanism expands as the discount factor increases, and eventually approaches the set of utilities achievable when values are publicly observable. There are a number of potential extensions to our work. For example, in our current mechanism, future promises are determined only through the interim, and not ex-post, allocation. If we perceive promised utilities as money, our mechanism requires the planner to introduce lotteries, which may not be appealing in practice. It is, therefore, interesting to explore whether it is possible to asymptotically achieve efficiency with mechanisms in which future promises depend on the ex-post allocations. Such a mechanism, if exists, establishes an indirect implementation without lotteries. That is, the agent who receives the resource in a period pays with future promises, while other agents are potentially compensated by higher future promises. Along the line of thinking about ex-post versus interim promised utilities, we can also consider varying the incentive compatibility constraint. Currently we enforce incentive compatibility at the “interim” level. That is, truthful reporting is each agent’s best strategy, taking expectations with

34

respect to other agents’ values and assuming competitors report truthfully. Alternatively, one can enforce certain “ex-post” incentive compatibility. That is, truthful reporting could be weakly dominant for every player in each period regardless of other players’ reports (and assuming all agents report truthfully in the future). The optimal social welfare under ex-post incentive compatibility is less than or equal to that of our setting for any fixed discount factor, because there are more constraints in the definition of the self-generating set. It remains to see if one can still establish asymptotic efficiency in this case. Another extension is to consider a positive marginal production cost for the resource in each period. If the cost is positive, the mechanism designer needs to trade-off efficiency with production cost. In this case the planner may have to withhold the resource if agents’ valuations are low. In such a setting, merely studying the achievable set of promised utilities is no longer sufficient. In a companion paper, we establish that asymptotic optimality is still achievable in that environment.

35

References Abreu, D., Pearce, D. and Stacchetti, E. (1990), ‘Toward a theory of discounted repeated games with imperfect monitoring’, Econometrica: Journal of the Econometric Society pp. 1041–1063. Aliprantis, C. D. and Border, K. (2006), Infinite dimensional analysis: a hitchhiker’s guide, Springer Science & Business Media. Anderson, E. J. and Nash, P. (1987), Linear programming in infinite-dimensional spaces: theory and applications, John Wiley & Sons. Arrow, K. (1979), The property rights doctrine and demand revelation under incomplete information, Economics and human welfare. New York Academic Press. Bergemann, D. and Said, M. (2011), ‘Dynamic auctions’, Wiley Encyclopedia of Operations Research and Management Science . Bergemann, D. and V¨ alim¨ aki, J. (2010), ‘The dynamic pivot mechanism’, Econometrica 78(2), 771– 789. Boyd, S. and Vandenberghe, L. (2009), Convex Optimization, Cambridge University Press. d’Aspremont, C. and G´erard-Varet, L.-A. (1979), ‘Incentives and incomplete information’, Journal of Public economics 11(1), 25–45. Es¨o, P. and Futo, G. (1999), ‘Auction design with a risk averse seller’, Economics Letters 65(1), 71–74. Friedman, E. J., Halpern, J. Y. and Kash, I. (2006), Efficiency and nash equilibria in a scrip system for p2p networks, in ‘Proceedings of the 7th ACM conference on Electronic commerce’, ACM, pp. 140– 149. Fudenberg, D., Levine, D. and Maskin, E. (1994), ‘The folk theorem with imperfect public information’, Econometrica: Journal of the Econometric Society pp. 997–1039. Gershkov, A. and Moldovanu, B. (2010), ‘Efficient sequential assignment with incomplete information’, Games and Economic Behavior 68(1), 144–154.

36

Gorokh, A., Banerjee, S. and Iyer, K. (2016), ‘Near-efficient allocation using artificial currency in repeated settings’. Guo, M., Conitzer, V. and Reeves, D. M. (2009), Competitive repeated allocation without payments, in ‘International Workshop on Internet and Network Economics’, Springer, pp. 244–255. Guo, Y., H¨orner, J. et al. (2015), Dynamic mechanisms without money, Technical report, Cowles Foundation for Research in Economics, Yale University. Johnson, K., Simchi-Levi, D. and Sun, P. (2014), ‘Analyzing scrip systems’, Operations Research 62(3), 524–534. Johnson, T. R. (2014), Dynamic mechanism design without transfers: Promises and confidentiality, Technical report, Working paper. Kash, I. A., Friedman, E. J. and Halpern, J. Y. (2007), Optimizing scrip systems: Efficiency, crashes, hoarders, and altruists, in ‘Proceedings of the 8th ACM conference on Electronic commerce’, ACM, pp. 305–315. Kash, I. A., Friedman, E. J. and Halpern, J. Y. (2012), ‘Optimizing scrip systems: crashes, altruists, hoarders, sybils and collusion’, Distributed Computing 25(5), 335–357. Kash, I. A., Friedman, E. J. and Halpern, J. Y. (2015), ‘An equilibrium analysis of scrip systems’, ACM Transactions on Economics and Computation 3(3), 13. Li, H., Zhang, H. and Fine, C. (2012), ‘Dynamic business share allocation in a supply chain with competing suppliers’, Operations Research 61(2), 280–297. Luenberger, D. G. (1969), Optimization by Vector Space Methods, 1st edn, John Wiley & Sons, Inc., New York, NY, USA. Milgrom, P. and Segal, I. (2002), ‘Envelope theorems for arbitrary choice sets’, Econometrica 70(2), 583–601. Myerson, R. (1981), ‘Optimal auction design’, Mathematics of Operations Research 6(1), 58–73. Nisan, N., Roughgarden, T., Tardos, E. and Vazirani, V. V. (2007), Algorithmic game theory, Vol. 1, Cambridge University Press Cambridge. 37

Parkes, D. C. and Singh, S. (2004), ‘An mdp-based approach to online mechanism design’. Pringle, R. and Rayner, A. (1970), ‘Expressions for generalized inverses of a bordered matrix with application to the theory of constrained linear models’, Siam Review 12(1), 107–115. Salinetti, G. and Wets, R. J.-B. (1979), ‘On the convergence of sequences of convex sets in finite dimensions’, SIAM Review 21(1), 18–33. Schneider, R. (2013), Convex bodies: the Brunn–Minkowski theory, number 151, Cambridge University Press. Shapiro, A., Dentcheva, D. et al. (2014), Lectures on stochastic programming: modeling and theory, Vol. 16, SIAM. Spear, S. and Srivastava, S. (1987), ‘On repeated moral hazard with discounting’, Rev. Econ. Stud. 54(4), 599–617. Thomas, J. and Worrall, T. (1990), ‘Income fluctuation and asymmetric information: An example of a repeated principal-agent problem’, Journal of Economic Theory 51, 367–390. Vohra, R. V. (2011), Mechanism Design: A Linear Programming Approach, Cambridge University Press. Zhang, H. (2012a), ‘Analysis of a dynamic adverse selection model with asymptotic efficiency’, Mathematics of Operations Research 37(3), 450–474. Zhang, H. (2012b), ‘Solving a dynamic adverse selection model through finite policy graphs’, Operations Research 60(4), 850–864.

38

A A.1

Appendix for Section 2 Proof of Proposition 2.1

Proof. We need to show that if a set A satisfies A ⊆ Bβ (A), then Bβ (A) ⊆ Uβ . We prove this by constructing, for each point u ∈ Bβ (A), a mechanism π satisfying (1) such that ui = Vi (π, i). Step 1 (constructing mechanism π). Let (ˆ vt )t≥1 be a sequence of reports. We construct a mechanism recursively that depends exclusively on past reports (and not on the allocations) as follows. First, let u1 = u. Because u1 ∈ Bβ (A), there exists a pair of functions (pu1 1 , w1u1 ) satisfying (IC), (PK(u1 )), ut−1 (ˆ vt−1 ). Because and (FA) and w1u1 (v) ∈ A for all v. We proceed for t > 1 by setting ut = wt−1 ut ut ut ∈ A ⊆ Bβ (A), there exists a pair of functions (pt , wt ) satisfying (IC), (PK(ut )), and (FA) and ˆ 1:t−1 wtut (v) ∈ A for all v. The mechanism is thus given by π t (v, ht ) = put t (v) with the history ht = v given by the past reports (which recursively determines the promise utility ut ). Step 2 (mechanism π satisfies ui = Vi (π, i)). This result follows from the fact that (put t , wtut ) satisfy ut (PK(ut )) for all t ≥ 1. In particular, we replace the continuation values with each wi,t (v) by using ˆ t = vt , we obtain by the promise keeping constraints. More formally, when agents bid truthfully and v iterating up to a time τ < ∞ u1 ui = (1 − β)E[vi,1 pui,11 (v1 )] + βE[wi,1 (v1 )] = (1 − β)E[vi,1 pui,11 (v1 )] + βE[u2,1 ]

= (1 − β)

τ X

ut β t−1 E[vi,t pi,t (vt )] + β τ E[ui,τ +1 ]

t=1

= (1 − β)

τ X

β t−1 Eπ,i [vi,t πi,t (vt , ht )] + β τ E[ui,τ +1 ] ,

t=1

where the first, second and third equalities follow from the fact that (put t , wtut ) satisfy (PK(ut )) for all ut−1 t ≥ 1 and using that ut = wt−1 (vt−1 ) together with the fact that values are identically distributed; and the fourth equality follows from our definition of the mechanism π. Because values have finite means and β ∈ (0, 1), we obtain that the series in absolutely convergent. Taking τ to infinity, we conclude that ui = Vi (π, i). Step 3 (mechanism π is PBIC). Fix a time period t ≥ 1. We need to show that Vi,t (π, i|vi,t , ht ) ≥ Vi,t (π, (σi , i−i )|vi,t , ht ) ,

(23)

for every history ht and strategy σi . By the one-shot deviation principle, it suffices to show that agent i has no incentive to deviate at time t. Therefore, we restrict attention to strategies σi that reports σi,t (vi,t , ht ) = vˆi,t at time t and truthfully at time τ > t. Additionally, because the mechanism π only depends on the past reports via the promise utility ut , it suffices to consider ut as the state. Because under the strategies (σi , i−i ) the other agents report truthfully at time t and all agents report truthfully at times τ > t, we obtain using a similar argument to that of step 2 that ut Vi,t (π, (σi , i−i )|vi,t , ht ) = (1 − β)vi,t Ev−i,t [pui,tt (ˆ vi,t , v−i,t )] + βEv−i,t [wi,t (ˆ vi,t , v−i,t )] ,

where vˆi,τ = σi,τ (vi,τ , hτ ) is the report of agent i at time t. Therefore, we can write (23) as ut ut (ˆ vi,t , v−i,t )] , (1 − β)vi,t Ev−i,t [pui,tt (vt )] + βEv−i,t [wi,t (vt )] ≥ (1 − β)vi,t Ev−i,t [pui,tt (ˆ vi,t , v−i,t )] + βEv−i,t [wi,t

39

which follows because the mechanism (put t , wtut ) satisfies (IC) and agents’ values are identically distributed.

A.2

Proof of Proposition 2.2

Proof. Recall that the set of achievable utilities is given by Uβ , {u ∈ Rn |ui = Vi (π, i), for a PBIC mechanism π} , while the operator Bβ (·) is defined in (3). We prove that Uβ = Bβ (Uβ ) by showing that Uβ ⊆ Bβ (Uβ ), since by Proposition 2.1 the latter implies that Bβ (Uβ ) ⊆ Uβ . For a given point u ∈ Uβ , we show that u ∈ Bβ (Uβ ) by constructing an allocation function p(·) and a future promise function w(·), such that (p, w) satisfies (IC), (FA),(PK(u)) and w(v) ∈ Uβ for all v. Step 1 (constructing stage mechanism (p, w)). Because u ∈ Uβ , there exists a PBIC mechanism π satisfying (1) and π t ∈ P for all t, and ui = Vi (π, i). We use the first period allocation and the continuation values induced by mechanism π to construct the stage mechanism (p, w). For all v, we set p(v) = π 1 (v, ∅) and wi (v) = (1 − β)

∞ X

β τ −2 Eπ,i [vi,τ πi,τ (vτ , hτ )|h2 = (v, π 1 (v, ∅))] .

(24)

τ =2

Note that the function p trivially satisfies (FA) since p(v) = π 1 (v, ∅) and π 1 (v, ∅) ∈ P for all v. The promise keeping constraint holds because ui = Vi (π, i) = (1 − β)Ev [vi pi (v)] + βEv [wi (v)] , where the last equation follows from our definition of the allocation function p and the future promise function w. Thus the stage mechanism (p, w) satisfies (PK(u)). Step 2 (stage mechanism (p, w) satisfies (IC)). Since the mechanism π is PBIC, we obtain that at time t = 1 agent i has no incentive to misreport his value: Vi,1 (π, (σi , i−i )|vi,1 , ∅) ≤ Vi,1 (π, i|vi,1 , ∅), ∀vi,1 . Consider the strategy σi that reports σi,1 (vi,1 , ∅) = vˆi,1 at time t and truthfully at time t > 1. We obtain using our definition of the stage mechanism (p, w) that Vi,1 (π, (σi , i−i )|vi,1 , ∅) = (1 − β)vi,1 Ev−i,1 [pi (ˆ vi,1 , v−i,1 )] + βEv−i,1 [wi (ˆ vi,1 , v−i,1 )] , and Vi,1 (π, i|vi,1 , ∅) = (1 − β)vi,1 Ev−i,1 [pi (vi,1 , v−i,1 )] + βE[wi (vi,1 , v−i,1 )] . This implies that the stage mechanism (p, w) satisfies (IC). ˆ 1 ∈ [0, v¯]n for period 1. We prove that w(ˆ Step 3 (for all v, w(v) ∈ Uβ ). Fix a report v v1 ) ∈ U β , ¯ i). The proposed mechanism π ¯ ¯ such that wi (ˆ by constructing a PBIC mechanism π v1 ) = Vi (π, involves implementing at time t the allocation of mechanism π at t + 1 given that the reports of ¯ t ∈ Ht for ˆ 1 , that is, we shift all allocations one time period. For any history h the first period v ¯ consider the history ht+1 ∈ Ht+1 for the original mechanism π given by the shifted mechanism π 40

  ¯ t and h2 = (ˆ ht+1 = (ˆ v1 , π 1 (ˆ v1 , ∅)), h v1 , π 1 (ˆ v1 , ∅)). Using this notation, we can denote the shifted ¯ ¯ t (v, ht ) = π t+1 (v, ht+1 ) for all t ≥ 1. mechanism as π ¯ i). From (24), we have that First, we show that wi (ˆ v1 ) = Vi (π, wi (ˆ v1 ) =(1 − β)

∞ X

β τ −2 Eπ,i [vi,τ πi,τ (vτ , hτ )|h2 = (ˆ v1 , π 1 (ˆ v1 , ∅))]

τ =2

=(1 − β)

∞ X

β τ −1 Eπ,i [vi,τ πi,τ +1 (vτ , hτ +1 )|h2 = (ˆ v1 , π 1 (ˆ v1 , ∅))]

τ =1

=(1 − β)

∞ X

¯ i ¯ τ )|∅] = Vi (π, ¯ i) , β τ −1 Eπ, [vi,τ π ¯i,τ (vτ , h

τ =1

where the second equation follows from shifting the index in the summation and using that values are identically distributed, and the third equation follows from our definition of the shifted mechanism and its history. ¯ is PBIC. For any strategy σ Second, we show that the shifted mechanism π ¯i for the shifted mech¯ t) ¯ consider the strategy σi for the original mechanism π given by σi,t+1 (·, ht+1 ) = σ anism π ¯i,t (·, h that shifts reports by one time period (since we consider the original mechanism at times t > 1, the reports of the strategy σi,t at time t = 1 are irrelevant). Because players only condition their actions on previous reports and allocations, and this information is publicly observed, we claim that for all vi , ¯ t , i and t ≥ 1 σ ¯i , h  ¯ t = Vi,t+1 (π, (σi , i−i )|vi , ht+1 ) . ¯ (¯ Vi,t π, σi , i−i )|vi , h ¯ is PBIC, since the original mechanism π is PBIC. This readily implies that the shifted mechanism π We conclude by proving the claim. We have that Vi,t+1 (π, (σi , i−i )|vi , ht+1 ) = (I) + (II) where the first term is given by    (I) = (1 − β)vi Eπ,(σi ,i−i ) πi,t+1 (σi,t+1 (vi , ht+1 ), v−i,t+1 ), ht+1 |vi , ht+1    ¯ σi ,i−i ) ¯ t ), v−i,t ), h ¯ t |vi , h ¯t , = (1 − β)vi Eπ,(¯ π ¯i,t (¯ σi,t (vi , h where the second equality follows from our definition of the shifted strategy, mechanism and histories and using that values are identically distributed. The second term is given by (II) = (1 − β) = (1 − β) = (1 − β)

∞ X τ =t+2 ∞ X τ =t+1 ∞ X

   β τ −t−1 Eπ,(σi ,i−i ) vi,τ πi,τ (σi,τ (vi,τ , hτ ), v−i,τ ), hτ |vi , ht+1    β τ −t Eπ,(σi ,i−i ) vi,τ πi,τ +1 (σi,τ +1 (vi,τ , hτ +1 ), v−i,τ ), hτ +1 |vi , ht+1    ¯ σi ,i−i ) ¯ τ ), v−i,τ ), h ¯ τ |vi , h ¯t β τ −t Eπ,(¯ vi,τ π ¯i,τ (¯ σi,τ (vi,τ , h

τ =t+1

where the second equation follows from shifting the index in the summation and using that values are identically distributed, and the third equation follows from our definition of the shifted mechanism, the ¯t ¯ (¯ shifted strategies and the shifted history. We thus conclude that (I) + (II) = Vi,t π, σi , i−i )|vi , h and the claim follows.

41

A.3

Proof of Proposition 2.3

We provide some preliminary results before proving Proposition 2.3. First, we endow the space of stage mechanism with a topology and prove that the set of mechanism satisfying our constraints is compact. Second, we show that the operator B is monotone, and preserves convexity and compactness. We assume that the functions of the stage mechanism p and w lie in the space L∞ , L∞ ([0, v¯]n , (Rn , k· k1 )) of essentially bounded vector functions from [0, v¯]n to (Rn , k · k1 ), i.e, a measurable vector funcPn tion ρ : [0, v¯]n → Rn lies in L∞ if ess supv kρ(v)k1 < ∞ where kρ(v)k1 = |ρ (v)|. We dei=1 i 1 1 n n ∞ note L , L ([0, v¯] , (R , k · k∞R)) to represent the pre-dual of L , i.e., a measurable vector function ψ : [0, v¯]n → Rn lies in L1 if [0,¯v]n kψ(v)k∞ dv < ∞ where kρ(v)k∞ = maxni=1 |ρi (v)|. Since the spaces L∞ and L1 are equivalence classes of functions which agree almost everywhere, all point-wise inequalities are understood to hold almost everywhere (a.e.). To simplify the exposition we drop the “almost everywhere” qualifier. We endow L∞ with the weak-* topology, the coarsest topology under which every element ψ ∈ L1 corresponds to a continuous (linear) map. A sequence ρm ∈ L∞ converges to ρ in the weak-* topology if Z Z m ρ (v) · ψ(v)dv → ρ(v) · ψ(v)dv ∀ψ ∈ L1 , P where ρ(v) · ψ(v) = ni=1 ρi (v)ψi (v) denotes the standard inner product in Rn . In this case, one writes ρm * ρ as m → ∞. Lemma A.1. The stage mechanisms satisfy the following properties: 1. Let A ⊂ Rn be a closed and convex set. The set {w ∈ L∞ : w(v) ∈ A for almost all v ∈ [0, v¯]n } is weak-* closed. P 2. Let A ⊂ Rn be a compact and convex set. The set MA = {(p, w) ∈ L∞ × L∞ : ni=1 pi (v) ≤ 1, p(v) ≥ 0, and w(v) ∈ A for almost all v ∈ [0, v¯]n } is weak-* compact. 3. The set {(p, w) ∈ L∞ × L∞ : (p, w) satisfy (IC)} is weak-* closed. 4. The function E : L∞ × L∞ → Rn given by E(p, w) = (Ev [(1 − β)vi pi (v) + βwi (v)])ni=1 is weak-* continuous. We next provide some properties on the operator Bβ defined in (3). n

n

Lemma A.2. The operator Bβ : 2R → 2R satisfies the following properties: 1. (Bβ is monotone) If X ⊆ Y ⊂ Rn then Bβ (X ) ⊆ Bβ (Y). 2. (Bβ preserves convexity) If A ⊂ Rn is convex, then Bβ (A) is convex. 3. (Bβ preserves compactness) If A ⊂ Rn is compact and convex, then Bβ (A) is compact. We defer the proofs of these results to the end of the subsection. We are now in position to prove the main result. Proof of Proposition 2.3. Let U ∞ = lim U m with U 0 = [0, E[v]]n and U m = Bβ (U m−1 ) for all m ≥ 1. m→∞ We prove this result in two steps. We first prove that the limit U ∞ exists and that Uβ ⊆ U ∞ . We then show that U ∞ ⊆ Uβ .

42

Step 1. We first claim that (i) Bβ (U 0 ) ⊆ U 0 and (ii) Uβ ⊆ U 0 . Claim (i), together with Lemma A.2, item 1, implies that U m ⊆ U m−1 , and thus U ∞ = lim U m exists. Moreover, because Uβ is selfm→∞

generating we obtain by (ii) that Uβ ⊆ U m for all m. This implies that Uβ ⊆ U ∞ . We next prove the claims. We show that Bβ (U 0 ) ⊆ U 0 by proving that for all u ∈ Bβ (U 0 ) we have u ∈ U 0 . Because u ∈ Bβ (U 0 ), there exist functions (p, w) satisfying (IC), (PK(u)) and (FA) such that w(v) ∈ U 0 for all v. Since p satisfies (FA), it follows that u1 := (E[vi pi (v)])ni=1 satisfies u1 ∈ U 0 . Note that U 0 is a convex set. Thus, the fact that w(v) ∈ U 0 implies that u2 := (E[wi (v)])ni=1 satisfies u2 ∈ U 0 . Finally, (PK(u)) implies that u = (1 − β)u1 + βu2 and hence u ∈ U 0 because u is a convex combination of two points in U 0 . We argue that Uβ ⊆ U 0 . Fix a point u ∈ Uβ . Recognizing the definition of Uβ in (2) it follows that ui = Vi (π, i) for some PBIC mechanism π. Because mechanism π satisfies π t ∈ P, we conclude that ui ∈ [0, E[v]] for all i. The claim follows. Step 2. In this step, we prove the other direction, i.e., U ∞ ⊆ Uβ . By Proposition 2.1, it is sufficient to prove that U ∞ ⊆ Bβ (U ∞ ). Fix a point u ∈ U ∞ . In order to prove that u ∈ Bβ (U ∞ ), we need to show that there exists a pair of functions (p, w) satisfying (IC), (FA), (PK(u)) and w(v) ∈ U ∞ for all v. T As shown in the first step, U ∞ = m≥1 U m . Therefore, u ∈ U m for all m, and there exists a sequence of pairs of functions (pm , wm ) which satisfy (IC), (FA), (PK(u)) and wm (v) ∈ U m−1 ⊆ U0 . Because U0 is convex and compact, we obtain by Lemma A.1, item 2 that (pm , wm ) lie in the weak-* compact set MU0 with the set MU0 defined in Lemma A.1, item 2. By passing to a subsequence if necessary we obtain that pm and wm weak-* converge to some (p, w) ∈ MU0 . By Lemma A.1, item 3 the set of incentive compatible stage mechanisms is weak-* closed, and thus (p, w) is incentive compatible. For a fixed m, we have wj (v) ∈ U m for all j > m because the sequence U m is non-increasing. Because U 0 is convex and compact, we obtain that U m is convex and compact because the operator Bβ preserves convexity and compactness from Lemma A.2, items 2 and 3. Because the set U m is closed T and convex, we obtain by Lemma A.1, item 1 that weak limit verifies m w(v) ∈ U . Therefore, w(v) ∈ m≥1 U m = U ∞ . We conclude by showing that (p, w) satisfies the promise keeping constraint with u. For each m we have that the promised keeping constraint is equivalently given by u = E(pm , wm ) with the function E defined in Lemma A.1, item 4. Because the function E is weak-* continuous, we obtain by taking limits that u = E(p, w). Thus, u ∈ Bβ (U ∞ ) since the functions (p, w) satisfy (IC), (FA), (PK(u)) and w(v) ∈ U ∞ for all v. A.3.1

Proof of Lemma A.1

Proof. We prove each item at a time. Item 1. Let A ⊂ Rn be a closed and convex set. We need to show that the set C = {w ∈ L∞ : w(v) ∈ A for almost all v ∈ [0, v¯]n } is weak-* closed. Convexity of A implies that C is convex. Because A is closed, we obtain that the set C is (strongly) closed. Because C is convex and (strongly) closed, we obtain that C is weak-* closed by Hahn-Banach separation theorem (see Aliprantis and Border, 2006, Theorem 5.98 in p. 214). n ∞ ∞ Item Pn 2. Let A ⊂ R be a compact and convex set. We need to shownthat MA = {(p, w) ∈ L ×L : ¯] } is weak-* compact. We write i=1 pi (v) ≤ 1, p(v) ≥ 0, and w(v) ∈ A for almost all v ∈ [0, v

43

P MA = Mp × Mw , where Mp = {p ∈ L∞ : ni=1 pi (v) ≤ 1, p(v) ≥ 0 for almost all v ∈ [0, v¯]n } and Mw = {w ∈ L∞ : w(v) ∈ A for almost all v ∈ [0, v¯]n }. Because the pre-dual L1 is normed, following Alaoglu’s compactness theorem (see Aliprantis and Border, 2006, Theorem 5.105 in p. 218), we obtain that the closed unit ball in L∞ given by {ρ ∈ L∞ : ess supv kρ(v)k1 ≤ 1} is weak-* compact. Because A ⊂ Rn is a compact and convex set, item 1 implies that Mw is weak-* compact because the intersection of a weak-* compact set and a weak-* closed set is weak-* compact. A similar argument shows that Mp is weak-* compact. The result follows by Tychonoff product theorem (see Aliprantis and Border, 2006, Theorem 2.61 in p. 52) because the product space MA = Mp × Mw is also weak-* compact. Item 3. Let us assume that the interim functions of the stage mechanism for a single agent Wi (vi ) and Pi (vi ) lie in the space L∞,1 , L∞,1 ([0, v¯], (R, | · |)) of essentially bounded vector functions from [0, v¯] to (R, | · |), i.e., a measurable function ρ : [0, v¯] → R lies in L∞,1 if ess sup |ρ(v)| < ∞. Let v∈[0,¯ v]

T : L∞ → (L∞,1 )n be the interim operator that projects an element ρ ∈ L∞ to (T ρ)i (vi ) for each i = 1, . . . , n by taking expectations over the other agents’ values. This operator is given by Z Y (T ρ)i (vi ) = ρi (vi , v−i ) f (vj )dv−i . (25) [0,¯ v ]n−1

j6=i

We claim that T is weak-* continuous. Define the space of interim incentive compatible mechanisms for a single agent as follows: C 1 = {(ρ, ω) ∈ L∞,1 × L∞,1 : (1 − β)vρ(v) + βω(v) ≥ (1 − β)vρ(v 0 ) + βω(v 0 ) for almost all v, v 0 ∈ [0, v¯]} . Note that C 1 is convex and (strongly) closed. This follows because the constraints in C 1 correspond to closed halfspaces, so the set of points satisfying these constraints is closed and convex. This implies that C 1 is weak-* closed (see the proof of Lemma A.1, Item 1). Let C = {(p, w) ∈ L∞ × L∞ : (p, w) satisfy (IC)}. Then, we have that C = (T × T )−1 ((C 1 )n ). Because T is weak-* continuous, then the cartesian product of functions T × T is weak-* continuous in the product topology. Because T × T is weak-* continuous and the cartesian product (C 1 )n is weak-* closed, C is weak-* closed (see Aliprantis and Border, 2006, Theorem 2.27 in p. 36). The result follows. We now prove the claim that the interim operator T : L∞ → (L∞,1 )n is weak-* continuous. Following Proposition 4 in Anderson and Nash (1987, p. 37), it is sufficient to show that the adjoint T ∗ of the operator T maps the pre-dual of (L∞,1 )n into the pre-dual of L∞ . Let L1,1 , RL1,1 ([0, v¯], (R, | · |)) denote the pre-dual of L∞,1 , i.e., a measurable function ψ : [0, v¯] → R lies in L1,1 if [0,¯v] |ψ(v)|dv < ∞. The pre-dual of (L∞,1 )n Ris given by the space (L1,1 )n with the norm of a typical element (ψi (vi ))ni=1 ∈ (L1,1 )n given by max [0,¯v] |ψi (vi )|dvi . Specifically, we need to show that T ∗ ((ψi )ni=1 ) ∈ L1 where i=1,...,n

(ψi )ni=1 ∈ (L1,1 )n . We start with determining the adjoint T ∗ : (L1,1 )n → L1 . By definition, the adjoint satisfies the following property for all ρ ∈ L∞ and (ψi )ni=1 ∈ (L1,1 )n : n Z X i=1

[0,¯ v]

Z (T ρ)i (vi )ψi (vi )dvi = [0,¯ v ]n

44

T ∗ ((ψi )ni=1 )(v) · ρ(v)dv .

(26)

We need to find T ∗ satisfying the above condition. We claim that the adjoint is given by  n Y T ∗ ((ψi )ni=1 )(v) = ψi (vi ) f (vj ) . j6=i

(27)

i=1

This follows from equations (26) and (25) because n Z X i=1

(T ρ)i (vi )ψi (vi )dvi =

[0,¯ v]

n Z X i=1

Z ρi (vi , v−i ) [0,¯ v ]n−1

[0,¯ v] n X

Z =

[0,¯ v ]n i=1

Y

f (vj )dv−i ψi (vi )dvi

j6=i





ψi (vi )

Y

f (vj ) ρi (v)dv ,

j6=i

where we used Fubini’s theorem to change the order of integrals, because these functions are integrable; and exchanged summation with integration, because the sum is finite. We Rnext show that T ∗ ((ψi )ni=1 ) ∈ L1 for (ψi )ni=1 ∈ (L1,1 )n . Note that (ψi )ni=1 ∈ (L1,1 )n if max [0,¯v] |ψi (vi )|dvi < ∞. We have

i=1,...,n

Y ∗ n kT ((ψi )i=1 )(v)k∞ dv = max ψi (vi ) f (vj ) dv [0,¯ v ]n [0,¯ v ]n i=1,...,n j6=i Z n n Z X X Y ≤ |ψi (vi )| f (vj )dv =

Z

Z

[0,¯ v ]n i=1

j6=i

i=1

|ψi (vi )| dvi

[0,¯ v]

Z ≤ n max

i=1,...,n [0,¯ v]

|ψi (vi )|dvi < ∞ ,

where the first equation follows from (27); the first inequality because kxk∞ ≤ kxk1 for x ∈ Rn ; the second equation from exchanging summation with integration because the sum is finite, using Tonelli’s Theorem because the functions are nonnegative and using that f (·) is a density function; and the third inequality because kxk1 ≤ nkxk∞ for x ∈ Rn . Finally, since (ψi )ni=1 ∈ (L1,1 )n , the statement follows. Item 4. We need to show that the function E(p, w) = (Ev [(1 − β)vi pi (v) + βwi (v)])ni=1 is weak-* continuous. Consider Q pm * p and wm * w as m → ∞. For a fixed i, consider the function ψ p ∈ L1 p given by Q ψi (v) = vi ni=1 f (vj ) and ψjp (v) = 0 for all j 6= i, and the function ψ w ∈ L1 given by ψiw (v) = ni=1 f (vj ) and ψjw (v) = 0 for all j 6= i. By definition, we know that m Ev [vi pm i (v)] → Ev [vi pi (v)] and E[wi (v)] → E[wi (v)] .

This implies that E(pm , wm ) → E(p, w) as m → ∞. A.3.2

Proof of Lemma A.2

Proof. We prove each item at a time. Item 1 (Bβ is monotone). Fix a point u ∈ Bβ (X ) and let (p, w) be the functions corresponding to u satisfying (IC), (PK(u)), (FA), and w(v) ∈ X for all v. Since X ⊆ Y, it follows that w(v) ∈ Y

45

for all v. Thus, the existence of the functions (p, w) satisfying the previous requirements implies that u ∈ Bβ (Y). Item 2 (Bβ preserves convexity). Fix points u1 , u2 ∈ Bβ (A). We need to show that u = λ1 u1 + λ2 u2 ∈ Bβ (A) for λ1 , λ2 ≥ 0 with λ1 + λ2 = 1. For each uj with j = {1, 2} there exists some functions (pj , wj ) satisfying (IC), (PK(uj )), (FA), and wj (v) ∈ A for all v. Because constraints are linear, we have that functions (p, w) given by p(v) = λ1 p1 (v) + λ2 p2 (v) and w(v) = λ1 w1 (v) + λ2 w2 (v) satisfy (IC), (PK(u)) and (FA). We conclude that u ∈ Bβ (A) because w(v) ∈ A since A is convex. Item 3 (Bβ preserves compactness). Recall that, by Heine-Borel theorem, the set A ⊂ Rn is compact if and only if A is closed and bounded. Suppose that A is closed and bounded. We need show that Bβ (A) is closed and bounded. Boundedness follows trivially from the promise keeping constraint because the allocation is bounded and values have finite means. We next prove closedness. Consider a sequence um ∈ Bβ (A) converging to some u ∈ Rn . We need to show that u ∈ Bβ (A). For each m there exists functions (pm , wm ) which satisfy (IC), (FA), (PK(um )) and wm (v) ∈ A. Because A is convex and compact, we obtain by Lemma A.1, item 2 that (pm , wm ) lie in the weak-* compact set MA . By passing to a subsequence if necessary we obtain that pm and wm weak-* converge to some (p, w) ∈ MA . By Lemma A.1, item 3 the set of incentive compatible stage mechanisms is weak-* closed, and thus (p, w) is incentive compatible. Because A is closed and convex, we obtain by Lemma A.1, item 1 that w(v) ∈ A for almost all v ∈ [0, v¯]n . We conclude by showing that (p, w) satisfies the promise keeping constraint with u. For each m we have that the promised keeping constraint is equivalently given by um = E(pm , wm ) with the function E defined in Lemma A.1, item 4. Because the function E is weak-* continuous, we obtain by taking limits that u = E(p, w). Thus, u ∈ Bβ (A) since the functions (p, w) satisfy (IC), (FA), (PK(u)) and w(v) ∈ A.

A.4

Proof of Lemma 2.1

Proof. We first prove that Uβ is convex and compact, and then show that Uβ = Rn+ ∩ hyp(Uβ ). T Step 1 (Uβ is convex and compact). From Proposition 2.3 we have U ∞ = m≥1 U m with U 0 = [0, E[v]]n and U m = Bβ (U m−1 ) for all m ≥ 1. Because U 0 is convex and compact, we obtain that U m is convex and compact because the operator Bβ preserves convexity and compactness from Lemma A.2, items 2 and 3. Therefore, U ∞ is convex and compact, since the intersection of arbitrary convex and compact sets in Rn is convex and compact. Convexity and compactness of Uβ follows because U ∞ = Uβ from Proposition 2.3. Step 2 (Uβ = Rn+ ∩ hyp(Uβ )). Note that Uβ is a subset of Rn+ by definition. Moreover, any set is in its hypo-graph. Thus, we get Uβ ⊆ Rn+ ∩ hyp(Uβ ). To prove the converse, fix a point u ∈ Rn+ ∩ hyp(Uβ ). We need to show that u ∈ Uβ . Because u ∈ Rn+ ∩ hyp(Uβ ), this implies that u ≥ 0 and there exists ¯ ∈ Uβ such that u ¯ ≥ u. Let π ¯ be the mechanism corresponding to u ¯. u n ¯ with zero. Consider the 2 states that can be obtained by replacing each subset of components of u ¯ 0 = (0, 0), u ¯ 1 = (0, u ¯ 2 = (¯ ¯4 = u ¯ . All these 2n states are For example, when n = 2, we get u ¯2 ), u u1 , 0), u ¯ m , i) ¯ m , we can construct a PBIC mechanism π ¯ m satisfying u ¯m in Uβ . In particular, for a state u i = Vi (π ¯ m ∈ Uβ for all m. The for all i by setting π ¯im = 0 if u ¯m ¯im = π ¯i otherwise. Therefore, u i = 0 and π m n ¯ given by {˜ polytope whose extreme points are the states u u ∈ R+ : 0 ≤ u ˜i ≤ u ¯i ∀i} is a subset of Uβ because all extreme points are in Uβ and Uβ is convex. The result follows because u lies in this polytope.

46

A.5

Proof of Corollary 2.1

Proof. Because the set Uβ is convex by Lemma 2.1, we get that Uβ can be characterized in terms of its support function φβ . Proposition 2.2 implies that the support function φβ is a fixed point of T . In step 2 of the proof of Proposition 2.3 we showed that the sequence of sets U m = Bβm (U 0 ) is convex and compact, and converges to the set Uβ , which is convex and compact by Lemma 2.1. Therefore, we obtain from Salinetti and Wets (1979, Corollary P4.A in p.31) that φβ (α) = lim [T m φ0 ](α) for all m→∞ α.

A.6

Proof of Proposition 2.4

Proof. As noted by Boyd and Vandenberghe (2009), the convexity of support function follows because it is the point-wise supremum of a family of linear functions. We next show that φ is twice differentiable in the following steps. Step 1. In this step, we show that φ(α) is differentiable and provide its derivative with respect to α. Shapiro et al. (2014, Theorem 7.46, p. 371) show that a finite valued, well defined function, f (α) = Ev [F (α, v)], is differentiable at a point α0 if and only if the random function, F (α, v), is convex and differentiable at α0 with probability 1. Here, the convexity of the random function means that F (·, v) is convex for almost every v. In our case, the random function is maxi (αi vi ), and the corresponding expected value function is φ(α). First, note that φ(α) is well defined and finite valued because 0 ≤ φ(α) ≤ maxj αj E[maxi vi ] for all α ∈ Rn+ . Second, the random function maxi αi vi is a convex function of α for all v because it is maximum of linear functions of α (see Boyd and Vandenberghe, 2009). Moreover, it is differentiable at a fixed α0 with probability 1, because for a given v, the partial derivative of maxi αi vi with respect to αi at α0 does not exist only when α0,i vi = α0,j vj for some j 6= i; and the probability of this event is 0 for a continuous distribution of v. Therefore, the derivative of φ(α) exists and is given by hi (α) ,

h i ∂φ (α) = Ev vi 1{αi vi ≥ max αj vj } . j6=i ∂αi

Step 2. We next consider the second derivative.Taking expectation  of vi 1{αi vi ≥ maxj6=i αj vj } with   Y αi vi  respect to v−i in hi (α), we obtain hi (α) = Evi vi F . The derivatives of the integrand αj j6=i

with respect to αi and αj exist for almost all vi , and are given by     X v 2  αi vi  Y  αi vi  ∂  Y αi vi i  vi F f (vi ) = f 1{αi vi ≤ αj v¯} F f (vi ) , ∂αi αj αj αj αk j6=i j6=i k6=i,j       Y Y  αi vi  ∂  αi vi αi vi2 αi vi  vi F f (vi ) = − 2 f 1{αi vi ≤ αj v¯} F f (vi ) . ∂αj αj αj αk αj j6=i

k6=i,j

47

Moreover, these derivatives are locally integrable, that is, for all compact intervals [α, α] contained in Rn>0 the following integrals are finite. α Z v¯ X

Z

α

Z

0 α Z v¯

α

0

j6=i

vi2 f αj

αi vi2 f αj2





αi vi αj

αi vi αj

 1{αi vi ≤ αj v¯}

Y

 F

k6=i,j

 1{αi vi ≤ αj v¯}

Y

 F

k6=i,j

αi vi αk

αi vi αk

 f (vi )dvi dα ≤

n v¯3 f¯2 (n − 1) Y αj < ∞ min αj j=1

j=1...n

max αj

 f (vi )dvi dα ≤

j=1...n

min αj

j=1...n

3 ¯2

v¯ f

n Y

αj < ∞

j=1

In these inequalities, we use the fact that the density function f (·) is bounded by f¯ and the support of the values are bounded by v¯. Therefore Leibniz rule implies that hi (α) is differentiable and hence φ(α) is twice differentiable. Finally, we provide the components of the Hessian matrix of φ(α).    Y   Z v¯ min(αi ,αj ) 1 X 1 x x ∂hi x 2 (α) = x f f F dx , 3 ∂αi (αi ) αj 0 αi αj αt j6=i

∂hi αi (α) = − ∂αj (αj )2 (αi )3

t6=i,j

Z

v¯ min(αi ,αj )

2

x f 0

48



x αi

  Y   x x f F dx . αj αt t6=i,j

B B.1

Appendix for Section 3 Proof of Proposition 3.1

ˆ Proof. We show that there exist a and b such that aT w(v|u) + b = 0. Suppose that a = α(u/Fβ ) and n X   b= (1 − β)(∇φ(a))i − ui /β. i=1

n X T ˆ i (ˆ ˆ ˆ Using the definition of w(v|u), we obtain a w(v|u) = ai Evˆi [W vi |u)]. Moreover, (PK(u)) i=1 h i ˆ i (ˆ implies that βEvˆi [W vi |u)] = ui − (1 − β)E[vi 1{ai vi ≥ max aj vj }] . Finally, recall that the support j6=i   function φ(·) satisfies (∇φ(a))i = E vi 1{ai vi ≥ max aj vj } . Combining these three observations, it j6=i

ˆ follows that aT w(v|u) + b = 0. The second part of the proposition follows from the following properties of the support function φ(·). Note that xT ∇φ(x) = φ(x) for all x by the definition of φ(·). Furthermore, for a vector x, the support function satisfies that φ(x) ≥ xT z for all z ∈ Uˆβ (see Schneider, 2013). Because u ∈ Uˆβ , we obtain the following inequality, which concludes the proof.  T ∇φ(a − u a = ∇φ(a)T a − uT a = φ(a) − uT a ≥ 0 .

B.2

Proof of Proposition 3.2

Proof. For simplicity, we use a to represent α(u/Fβ ) in this proof. First, we reformulate problem (15) as the following linear programming problem: max

z

˜ w(·)

st.

ˆ i (vi |u) ∀vi , i E[w ˜i (vi , v−i )] = W ˜ z ≤ a (u − w(v)) T

∀v

(28) (29)

Next, we find an upper bound for this problem by relaxing the constraints over z. Because u ∈ ˆ E(Uβ ), we have u/Fβ ∈ E(U), which implies u/Fβ = ∇φ(a), i.e., ui = Fβ E[vi 1{ai vi ≥ maxj6=i aj vj }]. ˆ i (vi |u)], following (PK(u)). These two obMoreover, ui = (1 − β)E[vi 1{ai vi ≥ maxj6=i aj vj }] + βE[W βF β ˆ i (vi |u)], where τ = servations imply that ui = τ E[W . Therefore, constraint (29) becomes Fβ − (1 − β) Xn  ˆ i (vi |u)] − w z ≤ ai τ E[W ˜i (v) for all v. Because z has to satisfy this constraint for all v, we i=1 can relax it by replacing these constraints with a single constraint where the right hand side is the expectation over v. X This operation corresponds to taking expectation of w ˜X i (v). Following constraint n n ˆ ˆ i (vi |u)] (28), we obtain z ≤ ai (τ − 1)E[Wi (vi |u)]. Therefore, it follows that ai (τ − 1)E[W i=1 i=1 is an upper bound for the optimal value. ˆ ˆ To show w(v|u) is an optimal solution, we first show that w(v|u) is feasible, and the objective ˆ function evaluated at w(v|u) is equal to this upper bound. By its definition, the expectation of ˆ i (vi |u), which implies feasibility. By Proposition 3.1, we also know w ˆi (v|u) with respect to X v−i is W n ˆ i (vi |u)] which, in turn, implies that w(v|u) ˆ ˆ that aT (u − w(v|u)) = ai (τ − 1)E[W is an optimal i=1 solution for (15).

49

C

Appendix for Section 4

In Section 4, we introduce the signed distance function for the perfect information achievable set U, in (17). In fact, this function can be defined for any convex set C. In Appendix C.1 we provide the definition and a key property of the function, which is used to show that a point belongs to a set. We then focus on the signed distance function for (scaled) perfect information achievable sets, and prove the main results of Section 4.

C.1

Signed Distance Function for Convex Sets

For a convex set C ∈ Rn , Schneider (2013) defines its support function as ψ(λ) , sup{λT x : x ∈ C} . We further define the following function IC (x) ,

{xT λ − ψ(λ)} .

sup

λ≥0 ,kλk=1

The following lemma demonstrates that function IC is indeed a signed distance function. Lemma C.1. For any convex set C ⊂ Rn , we have ( ≤ 0 if x ∈ hyp(C) , IC (x) = > 0 if x ∈ / hyp(C) , ¯ , ∃¯ where hyp(C) = {x ∈ Rn : x ≤ x x ∈ C}. Proof. We prove this result by considering two separate cases which determines the sign of the indicator function. Step 1. In this step, we assume that x ∈ hyp(C). The definition of the hyp(C) implies the existence ¯ ∈ C satisfying x ≤ x ¯ . Fixing an arbitrary nonnegative vector λ satisfying kλk = 1, we have of x ¯ ≤ ψ(λ) . λT x ≤ λT x Therefore, we have IC (x) ≤ 0. Step 2. Now assume that x 6∈ hyp(C). The separating hyperplane theorem implies that there exists ¯ for all x ¯ ∈ hyp(C). We argue that λ ≥ 0, following the fact a nonzero vector λ satisfying λT x > λT x that hyp(C) is unbounded from below. Otherwise, for the component λi < 0, we can always find a low ¯. enough negative x ¯i to violate λT x > λT x ¯ ¯ ¯ ∈ hyp(C), we have Let λ , λ/kλk, such that kλk = 1. Moreover, for all x ¯ Tx > λ ¯ Tx ¯. λ ¯ T x > ψ(λ), ¯ thus IC (x) > 0. These observations together imply that λ

C.2

The Signed Distance Function for the Scaled Perfect Information Achievable Set

In this section, we consider the perfect information achievable set U defined in (6). We provide the signed distance function for this set and the sets obtained by scaling it down. First, we start by showing 50

that the perfect information achievable set and the sets obtained by scaling it down are convex. Proposition C.1. The perfect information achievable set U defined in (6) is a convex set. Moreover, for any s ∈ [0, 1], the set sU is also convex, and sU = hyp(sU) ∩ Rn+ . Proof. For any two points u0 , u00 ∈ U and a scalar x ∈ (0, 1), let p0 and p00 be the allocation functions corresponding to the points u0 and u00 , respectively. Then, the point xu0 + (1 − x)u00 is in U because xp0 + (1 − x)p00 is an allocation satisfying (FA), and xu0i + (1 − x)u00i = E[vi (xp0i (v) + (1 − x)p00i (v))]. Because U is convex, sU is also convex. Any set is a subset of its hypograph. And sU ⊆ Rn+ . Thus, it is sufficient to show that hyp(sU) ∩ ¯ ∈ sU such that u ¯ ≥ u. Rn+ ⊆ sU. Let u ∈ hyp(sU) ∩ Rn+ . This implies that u ≥ 0 and there exists u ¯ be the allocation corresponding to u ¯. Let p ¯ with Consider the 2n points that can be obtained by replacing each subset of components of u ¯ 0 = (0, 0), u ¯ 1 = (0, u ¯ 2 = (¯ ¯4 = u ¯ . All these 2n zero. For example, when n = 2, we get u ¯2 ), u u1 , 0), u ¯ m , we can construct a feasible allocation p ¯ m satisfying states are in sU. In particular, for a state u m ¯m ¯ m ∈ sU for u ¯m ¯m ¯m ¯i otherwise. Therefore, u i = E[vi pi (v)] for all i by setting p i = 0 if u i = 0 and p i =p m n ¯ given by {˜ all m. The polytope whose extreme points are the states u u ∈ R+ : 0 ≤ u ˜i ≤ u ¯i ∀i} is a subset of sU because all extreme points are in sU and sU is convex. The result follows because u lies in this polytope. We now provide the signed distance function corresponding to FU for a given scalar F as follows:  T  u u x J(u, F) , IU = sup − φ(x) , (30) F F kxk1 =1,x≥0 where φ(·) is the support function of U given in (7). By Lemma C.1 in Appendix C.1, for any nonnegative u, it follows that ( ≤ 0 u ∈ hyp(FU) , J(u, F) = >0 u∈ / hyp(FU) .

Corollary C.1. For a point u ∈ Rn+ , u ∈ FU if and only if J(u, F) ≤ 0. Proof. Proposition C.1 implies that FU = hyp(FU) ∩ Rn+ , thus for any u ≥ 0, u ∈ FU if and only if u ∈ hyp(FU). Moreover, Lemma C.1 implies that J(u, F) ≤ 0 if and only if u ∈ hyp(FU). Finally, we provide two properties of J(u, F) by the following propositions. Before stating these results, we introduce the following matrix that would be used in later results: Π(a) , Hess(φ(a)) + eeT , where a > 0 and e is the n dimensional vector of ones. For any scalar F ∈ (0, 1], define set S(F) ∈ Rn as S(F) , {z + ae : ∀a ≥ 0, z ∈ FU, and z > 0} . Set S(F) is useful in the following result as well as later in the Appendices. Proposition C.2. Let u ∈ S(F). We have α(u/F) > 0, in which α(u/F) is defined in (8).

51

(31)

Proof. Consider a point u = z + ae for some fixed z ∈ FU, z > 0 and a ≥ 0. The optimization problem in (8) becomes    T  (z + ae)T x a z x sup − φ(x) = + sup − φ(x) . F F kxk1 =1,x≥0 F kxk1 =1,x≥0 Therefore, α((z + ae)/F) = α(z/F). Now focus on z > 0 such that z ∈ FU. The Lagrangian is given by L(x, µ, ζ) = xT z − Fφ(x) − µ(1 − eT x) + ζ T x, where µ and ζ are the Lagrange multipliers corresponding to constraints kxk1 = 1 and x ≥ 0, respectively. Optimality implies that ∇x L(α(z/F), µ∗ , ζ ∗ ) = z − F∇φ(α(z/F)) + µ∗ e + ζ ∗ = 0. As discussed in Remark 3.1, the optimal value µ∗ is nonnegative for z ∈ FU. Suppose now there exists a component of α(z/F) such that αi (z/F) = 0. In this case, the optimality condition for i implies zi + µ∗ + ξi∗ = 0, because ∇φ(α(u/F)) i = 0. This is a contradiction because zi > 0, µ∗ ≥ 0 and ζi∗ ≥ 0. Therefore, we have the result. Proposition C.3. Let F be a positive scalar in [0, 1] and u ∈ S(F). Suppose also that Π(a) is positive definite for all a > 0. Then, the optimal solution α(u/F) is unique. Moreover, the function J(u, F) is twice differentiable, and the first and second derivatives are given as follows:   α(u/F) 1 eeT Π(α(u/F))−1 ∇J(u, F) = and Hess (J(u, F)) = 2 Π(α(u/F))−1 I − T , F F e Π(α(u/F))−1 e where I is the n × n identity matrix. Proof. We prove this result in three steps. Step 1. In this step, we show that the optimal solution α(u/F) of the maximization problem in J(u, F) is unique. In Proposition C.2, we show that an optimal solution is α(u/F) > 0 for u ∈ S(F), thus we can ignore the non-negativity constraints. Because x > 0, Proposition 2.4 implies that the objective is twice-differentiable with hessian −Hess(φ(x)). Note that the objective function is not strictly concave over Rn>0 because Hess(φ(a))a = 0 for any a 6= 0. However, we can show that the restriction of the objective function to the feasible set kxk1 = 1 is strictly concave. Let y ∈ Rn be a feasible direction satisfying eT y = 0. We obtain using (31) that y T Hess(φ(x))y = y T Π(x)y − (eT y)2 = y T Π(x)y > 0 , where the last inequality follows because Π(x) is positive definite for all x > 0. This implies that the optimal solution is unique. Step 2. In this step, we show that J(u, F) is differentiable with respect to u and provide ∇J(u, F). As noted by Milgrom and Segal (2002) in Corollary 3, the gradient of J(u, F) is well defined because (i) {x : kxk1 = 1, x ≥ 0} is a convex set, (ii) xT u/F − φ(x) is a concave function of x and u, and (iii) there is an optimal solution, α(u/F), such that ∇J(u, F) exists. Then, the gradient at u is given by ∇J(u, F) =

α(u/F) . F

(32)

Step 3. In this step, we show the existence of the second derivative and provide the Hessian matrix of J(u, F). In the previous step, the gradient of J(u, F) is given by α(u/F)/F. Therefore, the Hessian matrix consists of the derivatives of the optimal solution α(u/F) with respect to u. We next characterize the optimal solution using the KKT conditions of the optimization problem. 52

Because x > 0, we can write the Lagrangian of (30) as L(x, µ) = xT u−Fφ(x)−µ(1−eT x). Optimality implies ∇x L(α(u/F), µ∗ ) = u − F∇φ(α(u/F)) + µ∗ e = 0 and ∇µ L((α(u/F), µ∗ )) = eT α(u/F) − 1 = 0. Introduce an auxiliary function Q : Rn+1 → Rn+1 as follows: Qi (x, µ) , F(hi (x) − µ) = zi , n X Qn+1 (x, µ) , −F xi = zn+1 .

∀i = 1, . . . , n ,

i=1

For a given u, it follows that Q(α(u/F), µ∗ ) = [uT , −F]T . Inverse function theorem implies that if the Jacobian determinant of Q is non-zero, then Q is invertible. Specifically, if the Jacobian determinant of Q is non-zero, Q is invertible and thus the unique optimal solution is obtained by Q−1 (u, −F) = [α(u/F)T , µ∗ ]T . We next argue that the Jacobian determinant of Q, denoted by det(JQ (α(u/F), µ∗ )), is non-zero. The Jacobian matrix of Q, JQ (α(u/F)), is given as follows:   Hess(φ(α(u/F))) −e ∗ JQ (α(u/F), µ ) = F . −eT 0 Note that JQ (α(u/F), µ∗ ) is a block matrix thus its determinant is expressed in terms of the determinants of Hess(φ(α(u/F))) and Π(α(u/F)). We have that det(Π(a)) 6= 0 for all a > 0 because the matrix is positive definite. Moreover, it follows that det(Hess(φ(α(u/F)))) = 0 because Hess(φ(a))a = 0 for any a 6= 0. Therefore, we obtain det(JQ (α(u/F), µ∗ )) = det(Hess(φ(α(u/F)))) − det(Π(α(u/F))) = −det(Π(α(u/F))) 6= 0 . The inverse function theorem further implies that Q−1 is continuously differentiable. Moreover, the theorem implies JQ−1 (u, −F) = [JQ (α(u/F), µ∗ )]−1 , where JQ−1 is the Jacobian matrix of inverse function Q−1 . This system of equations implies the existence of Hess(J(u, F)) because ∂µ∗ Hess(J(u, F)) is the upper left sub-matrix of JQ−1 (u, −F). Specifically, denoting ci = and bi = ∂ui ∂αi (u/F) , we can equivalently express JQ−1 (u, −F) = [JQ (α(u/F), µ∗ )]−1 as follows: ∂zn+1  2   −1  −1 F Hess(J(u, F)) b Hess(φ(α(u/F))) −e ∗ = FJQ−1 (u, −F) = = F J (α(u/F), µ ) . Q cT 0 −eT 0 Following Lemma 3 in Pringle and Rayner (1970), we obtain the following closed form expression for Hess(J(u, F)):   eeT Π(α(u/F))−1 2 −1 F Hess(J(u, F)) = Π(α(u/F)) I− T . e Π(α(u/F))−1 e Proposition C.4. Let F be a positive scalar in [0, 1], u0 ∈ S(F) and u00 ∈ FU such that u00 > 0. Suppose Π(a) is positive definite for a > 0. Then J(u0 , F) is expressed via its quadratic expansion around u00 as follows: 1 J(u0 , F) = J(u00 , F) + ∇J(u00 , F)T (u0 − u00 ) + (u0 − u00 )T Hess(J(Θ, F))(u0 − u00 ) , 2 where Θ is a point between u0 and u00 . Proof. When Π(a) is positive definite for all a > 0, Proposition C.3 provides the gradient and the 53

Hessian of J for points in S(F). Thus, we next show that Θ ∈ S(F). We can express Θ as a convex combination of u0 and u00 , i.e., Θ = ωu0 + (1 − ω)u00 for some ω ∈ (0, 1) because Θ is a point between u0 and u00 . We know that there exist (x00 , a00 ) such that u00 = x00 + a00 e where x00 ∈ FU and x00 > 0, and a00 ≥ 0. Thus it follows that Θ = ωu0 + (1 − ω)x00 + a00 e. Because FU is convex (see Proposition C.1), we have that ωu0 + (1 − ω)x00 ∈ FU and Θ ∈ S(F). Therefore, following Taylor’s theorem, we can express J(u0 , F) by the quadratic expansion around u00 as follows: 1 J(u0 , F) = J(u00 , F) + ∇J(u00 , F)T (u0 − u00 ) + (u0 − u00 )T Hess(J(Θ, F))(u0 − u00 ) . 2

C.3

Proof of Proposition 4.1

Before the proof, we provide the value of the constant used in (16). Following this definition, we provide the proof of the proposition. Definition C.1. Define constants Fβ and uβ such that Fβ = 1 − uβ /E[v] and uβ = ξ(1 − β), in which scalar ξ is given by 12ν , (33) ξ, β¯ v3f 2 where

! 2  2 ¯ 2 f 4 v¯6 f¯ 2 f¯ 2 f v¯ 2 − E[v ] + E[v] , E[v] + E[v ] + (E[v] + v¯) , . ν , max 2 2 2 2 36

(34)

We determine the value of β such that Fβ ≥ 1/2 for all β ≥ β. Proof of Proposition 4.1. We prove this result in two steps. We defer the proofs of lemmas used in these steps to the end of this section. ˆ Step 1. In this step, we prove that w(v|u) ≥ 0 for all u ∈ Fβ U. For the fixed u, for simplicity, we use ˆ to represent w(v|u) ˆ ˆ = wL (v|u) = u and w ˆ is w given in (14). Suppose that for an i, ui ≤ uβ , then w clearly nonnegative because u ∈ Fβ U. Suppose that ui ≥ uβ for all i, i.e., u lies in the central region ˆ is less than uβ , thus w ˆ is always Uˆβ . We show that the largest jump from the initial state u to w nonnegative. The following lemma provides a bound on the largest jump.   1−β √ ˆ ˆ − uk2 ≤ Lemma C.2. For any u ∈ Uβ and β ≥ β, we have kw ν. β ˆ − uk2 for all u ∈ Uˆβ because it provides a uniform This lemma enables us to show that uβ ≥ kw v¯6 f 4 bound on this norm which is independent of u and v. Using the fact that ν ≥ and ξ = β¯12ν , we v3 f 2 36 get √ uβ ξ ν ν 6ν ˆ − uk2 ≤ (1 − β) ≤ (1 − β) = . (35) kw (1 − β) = √ (1 − β) ≤ β 2 2 β ν β¯ v3f 2 ˆ − uk2 ≥ uβ − kw ˆ − uk2 > 0 for all i. Therefore, it follows that w ˆi ≥ ui − kw ˆ ∈ Fβ U. For the case that u is in the boundary region of Fβ U, Step 2. Now we show that w ˆ ∈ Fβ U. Next, assume that u is in the central region Uˆβ . Consider ˆ = wL (v|u) = u, thus clearly w w the signed distance function J defined in (30). For simplicity, we use J(x) to represent J(x, Fβ ). ˆ ≤ 0 if and only if w ˆ ∈ Fβ U because w ˆ ≥ 0. In order to show Following Corollary C.1, we have J(w) 54

ˆ ≤ 0, we consider the quadratic expansion around u as in Proposition C.4 (with scalar F = Fβ in J(w) the proposition). We first prove that the necessary conditions for Proposition C.4 to hold. ˆ lies in S(Fβ ) for any u in Uˆβ . Lemma C.3. The future promise w ˆ and u because it is convex. This lemma implies that the set S(Fβ ) contains all Θ between w Following Proposition C.2, we have that α(Θ/Fβ ) > 0. Lemma C.4. The matrix Π(a) is positive definite for all a > 0. Because both u and Θ are in S(Fβ ), Lemma C.4 enables us to invoke Proposition C.4. Therefore, we next analyze each item in the quadratic expansion at a time. First, u ∈ Fβ U implies that J(u) ≤ 0. ˆ ≤ 0, it is sufficient to show that Thus, to show J(w) 1 ˆ − u) + (w ˆ − u)T Hess(J(Θ))(w ˆ − u) ≤ 0 . ∇J(u)T (w 2

(36)

ˆ − u), and an upper In order to show this inequality holds, we find a lower bound for −∇J (u)T (w ˆ − u)T Hess(J(Θ))(w ˆ − u). Then, we compare these bounds. We start by considering the bound for (w first-order term. The following lemma provides the lower bound. Lemma C.5. For any β ≥ β, the gradient of J(u) satisfies (1 − β)2 ξ ˆ − u) . ≤ −∇J (u)T (w 4βF2β This lemma mainly stems from the fact that ∇J(u) = α(u/Fβ )/Fβ (see Proposition C.3) and the future promises lie in a plane with normal α(u/Fβ ) (see Proposition 3.1). Following this lemma, it is 1 (1 − β)2 ξ ˆ − u)T Hess(J(Θ))(w ˆ − u) ≤ . Therefore, we next find an upper sufficient to show that (w 2 4βF2β bound for the term with the Hessian in the following lemma. Lemma C.6. For any β ≥ β, the Hessian of J(u) satisfies 1 ˆ − u)T Hess(J(Θ))(w ˆ − u) ≤ (w 2



1−β β

2

3ν f 2 v¯3 F2β

,

ˆ where Θ is an arbitrary point between u and w. T ˆ ˆ In the proof of this lemma, following the min-max theorem, we first bound (w−u) Hess(J(Θ))(w− 2 ˆ − uk2 . Then, we replace u) by the multiplication of the maximum eigenvalue of Hess(J(Θ)) and kw ˆ − uk22 , with its bound provided in Lemma C.2. the norm square, kw Combining the bounds provided by Lemmas C.5 and C.6, we obtain that (36) holds because 12ν ˆ ≤ 0 implying that w ˆ ∈ Fβ U for u such that ui ≥ uβ for ≤ ξ. Therefore, we prove J(w) βf 2 v¯3 all i.

C.4

Proof of Theorem 4.1

Proof. This result follows from Proposition 4.1 and Proposition 2.1. The set Fβ U characterized by the constant in (33) is a subset of Uβ by Proposition 2.1. Thus, the maximum achievable social welfare Jβ = Fβ J FB , is less than Jβ∗ . 55

C.5

Proofs of Lemmas C.2, C.3, C.4, C.5 and C.6

Proof of Lemma C.2. Proposition 3.1 states that future promises lie on a line for different v’s when n = 2. The extreme points of this line correspond to (0, v¯) and (¯ v , 0) because w ˆi (v|u) is non-increasing in vi and non-decreasing in vj , according to Proposition 5.2. Therefore, it follows that   ˆ ˆ v , 0)|u) − uk22 , kw((0, ˆ − uk22 ≤ max kw((¯ v¯)|u) − uk22 . kw Let γ = α(u/Fβ ) and suppose that γ1 ≤ γ2 without loss of generality. ˆ v , 0)|u) − uk22 ). In this step, using (13) and (14), we bound (w ˆ1 ((¯ v , 0)|u)−u1 )2 Step 1 (Bounding kw((¯ 2 and (w ˆ2 ((¯ v , 0)|u) − u2 ) separately. First, we obtain more compact expressions for these terms and using these expressions, we get the bounds. "Z     v¯ u1 1 − β γ1 y γ1 v¯ w ˆ1 ((¯ v , 0)|u) = + F (y)F dy − F v¯ β β γ2 γ2 0      # Z v 2  γ2 γ2 v2 γ2 y + Ev2 dy − F v2 F γ1 γ1 γ1 0 Changing the order of integrations, we rewrite w ˆ1 ((¯ v , 0)|u) as follows:  Z    u1 1 − β γ1 v¯ γ1 y w ˆ1 ((¯ v , 0)|u) = − f F (y)ydy + E[v] . β β γ2 0 γ2 We are now ready to bound (w ˆ1 ((¯ v , 0)|u) − u1 )2 . 

β 1−β

2



γ1 (w ˆ1 ((¯ v , 0)|u) − u1 ) = u1 − γ2 2

Z



 f

0

γ1 y γ2



2  ¯ 2 2 f v¯ f¯ 2 F (y)ydy − E[v] ≤ − E[v ] + E[v] . 2 2 | {z } ν1

This inequality follows from the fact that (i) γ1 /γ2 is less than 1, (ii) the p.d.f. is less than f¯ in its support, and (iii) we can remove u1 because E[v] ≥ u1 and they have different signs. Next, we derive w ˆ2 ((¯ v , 0)|u) following similar steps and bound (w ˆ2 ((¯ v , 0)|u) − u1 )2 . 2      2 Z Z v¯ γ1 y γ 2 v¯ γ2 u2 + 12 f yF (y)dy − F¯ (y)F y dy γ2 γ1 γ2 0 0  2       2 Z Z v¯ 1−β γ12 v¯ γ1 y γ2 ¯ ≤ max u2 + 2 f yF (y)dy, F (y)F y dy β γ2 γ1 γ2 0 0     2    2 1−β 2 f¯v¯2 f¯ 2 1−β 2 f¯v¯2 f¯ 2 ≤ max E[v] + − E[v ], E[v] = E[v] + − E[v ] . β 2 2 β 2 2 | {z }

(w ˆ2 ((¯ v , 0)|u) − u2 )2 =



1−β β

ν2

Here, we first group the terms with same sign inside the square brackets and bound them separately. We use the fact that γ1 /γ2 ≤ 1 and the p.d.f. is less than f¯ in its support to obtain the second inequality.   1−β 2 2 ˆ (ν1 +ν2 ). By using the bounds on w ˆi ((¯ v , 0)|u) for i = 1, 2, we obtain kw((¯ v , 0)|u) − uk2 ≤ β 56

ˆ ˆ1 ((0, v¯)|u)−u1 )2 Step 2 (Bounding kw((0, v¯)|u) − uk22 ). In this step, using (13) and (14), we bound (w and (w ˆ2 ((0, v¯, )|u) − u2 )2 separately, following similar steps as above. (Z "Z       v¯ v¯ u1 1 − β γ γ2 y γ2 v¯ γ y 2 1 ¯ dy + F dy − F v¯− w ˆ1 ((0, v¯)|u) = − F (y)F β β γ2 γ1 0 γ1 γ1 0 Z v2        #) γ2 y γ2 v2 F Ev2 dy + Ev2 F v2 γ1 γ1 0   Z u1 1 − β γ1 v¯ ¯ γ1 y = + F (y)yf dy . β β γ2 0 γ2 Because u1 ≤ E[v], γ1 /γ2 ≤ 1 and the p.d.f. is bounded by f¯ in its support, we obtain the following inequality: 2



(w ˆ1 ((0, v¯)|u) − u1 ) =

1−β β

2 

γ1 u1 + γ2

Z



F¯ (y)yf



0

γ1 y γ2

2

 dy

 ≤

1−β β

2 f¯ 2 E[v] + E[v ] . 2 {z } |

2 

ν3

Next, we derive a more compact expression for w ˆ2 ((0, v¯)|u). Z v¯        Z v¯ γ2 y γ2 v¯ γ2 y u2 1 − β F dy − F v¯ − F¯ (y)F dy w ˆ2 ((0, v¯)|u) = + β β γ1 γ1 γ1 0 0   Z   1 − β γ1 γ1 v¯ ¯ γ1 y − F (y)f ydy β γ2 γ2 0 γ2 Z v¯       Z v¯  γ2 y u2 1 − β γ2 v¯ γ2 y ¯ F (y)F = + dy − F v¯ − F f (y) ydy . β β γ1 γ1 γ1 0 0 Using a similar approach to previous steps, we now bound (w ˆ2 ((0, v¯)|u) − u2 )2 . 

2

(w ˆ2 ((0, v¯)|u) − u2 ) ≤  ≤

1−β β

2 "

1−β β

2

Z max u2 +



 F (y)F

0

γ2 y γ1



Z



dy, 0

yf (y)F¯



γ2 y γ1



 dy + F

 !#2 γ2 v¯ v¯ γ1

(E[v] + v¯)2 . | {z } ν4

 1−β 2 (ν3 + ν4 ). β ˆ v , 0)|u) − uk22 and kw((0, ˆ Combining the bounds on kw((¯ v¯)|u) − uk22 , we obtain the following bound   2  1−β 1−β 2 2 ˆ on the largest jump, i.e., kw(v|u) − uk2 ≤ max (ν1 + ν2 , ν3 + ν4 ) ≤ ν. β β

ˆ It follows that kw((0, v¯)|u) − uk22 ≤



Proof of Lemma C.3. First, when n = 2, it is obvious that S(Fβ ) = {z : |z1 − z2 | < Fβ E[v], z > 0} . Without loss of generality, assume w ˆ1 ≥ w ˆ2 . Because u ∈ Uˆβ , we know that u1 < Fβ E[v] and u2 ≥ uβ ,

57

which further implies ˆ − uk2 < kw ˆ − uk2 , and w ˆ − uk2 ≥ −kw ˆ − uk2 . w ˆ1 − Fβ E[v] ≤ u1 − Fβ E[v] + kw ˆ2 − uβ ≥ u2 − uβ − kw ˆ − uk2 . Equation (35) further Combining these two inequalities, we obtain w ˆ1 − w ˆ2 − Fβ E[v] + uβ < 2kw ˆ − uk2 , and, therefore, w ˆ1 − w ˆ2 < Fβ E[v]. implies that uβ ≥ 2kw Proof of Lemma C.4. The Hessian matrix of φ(a) is provided in Proposition 2.4 for a > 0. Denote     Z v¯ min(a1 ,a2 ) x x 2 x f f dx. Then, Π(a) is given as follows: z, a1 a2 0 " z # + 1 − a2za2 + 1 a31 a2 1 2 Π(a) = . − a2za2 + 1 a za3 + 1 1 2

1 2

Following Sylvester’s criterion, a matrix is positive definite if its leading principal minors are all positive. Because z/a31 a2 + 1 > 0, it is sufficient to show det(Π(a)) > 0. Thus, we next derive this determinant and show that it is positive. Because the p.d.f. f (·) is lower bounded in the support  3 z ≥ f 2 v¯ min(a1 , a2 ) /3. Thus, we have that

det(Π(a)) =

z ≥ 3 a1 a32

 3 f 2 v¯ min(a1 , a2 ) 3a31 a32

=

v¯3 f 2 > 0. 3 max(a31 , a32 )

Proof of Lemma C.5. Lemma C.4 implies we can invoke Proposition C.3 to show that the gradient of J is well defined and ∇J(u) = α(u/Fβ )/Fβ as given in (32). Moreover, using Proposition 3.1, we can ˆ as follows: alternatively express α(u/Fβ )T (u − w)

ˆ − u) = −∇J (u)T (w

  T ˆ α Fuβ (u − w)

. Fβ β  T  x u The first-order conditions for the optimization problem sup − φ(x) enable us to express Fβ kxk1 =1,x≥0 u as u = Fβ ∇φ (α (u/Fβ )) − µe , where µ is the dual variable corresponding to constraint kxk1 = 1 and e is the 2 dimensional vector of ones. Therefore, we get the following equation.   T ((1 − Fβ )∇φ (α(u/Fβ )) + µe)  1 − β  α Fuβ T −∇J (u) (w − u) = . Fβ β Fβ

=

  T      α Fuβ ∇φ α Fuβ − u 1 − β 

Note that xT ∇φ(x) = φ(x), and the dual variable µ is nonnegative because u ∈ Uˆβ and Fβ ∇φ(α(u/Fβ )) corresponds to a state in the efficient frontier of Uˆβ . Moreover Fβ ≥ 1/2 and φ(x) ≥ E[v]/2 for all x ∈ R2+ by definition. Thus, using these observations we obtain    (1 − Fβ ) (1 − β) (1 − β) (1 − Fβ ) E[v] u (1 − β)2 ξ ˆ − u) ≥ −∇J (u) (w φ α ≥ = . Fβ β Fβ 4βF2β 4βF2β T

58

Proof of Lemma C.6. Lemma C.4 enables us to use Proposition C.3 to obtain that   eeT Π(α(Θ/Fβ ))−1 1 −1 I− T . Hess (J(Θ)) = 2 Π(α(Θ/Fβ )) e Π(α(Θ/Fβ ))−1 e Fβ v¯ min(λ1 ,λ2 )



   x x x f Denote λ = α(Θ/Fβ ) and z , f dx, then Π(λ) = Hess(φ(λ)) + eeT by λ λ 1 2 0 definition. Therefore, we can evaluate the matrix multiplication operations using the definitions and we obtain   1 −1 1 λ31 λ32 Hess(J(Θ)) = . −1 1 F2β z   1 −1 The largest eigenvalue of matrix is 2. Because the p.d.f. f (·) is lower bounded in the support, −1 1  3 we have that z ≥ f 2 v¯ min(λ1 , λ2 ) /3. These observations and the fact that max(λ1 , λ2 ) ≤ 1 imply 6 that the largest eigenvalue of Hess(J(Θ)) is bounded by 2 3 2 . Finally, using Lemma C.2, we can f v¯ Fβ ˆ − uk22 and obtain the following inequality: also bound kw Z

2

1 3 ˆ − u)T Hess(J(Θ))(w ˆ − u) ≤ 2 3 2 kw ˆ − uk22 ≤ (w 2 f v¯ Fβ

59



1−β β

2

3ν . f 2 v¯3 F2β

D D.1

Appendix for Section 5 Proof of Proposition 5.1

Proof. Agent i’s allocation  T is given in (12) as pˆi (v|u) = 1{αi (u/Fβ )vi ≥ maxj6=i αj (u/Fβ )vj } where u x − φ(x) . α(u/Fβ ) = arg max Fβ kxk1 =1,x≥0 Step 1 (ˆ pi (v|u) is non-decreasing in vi ). Let v ≥ v 0 , and fix v−i ∈ [0, v¯]n−1 and u. If αi (u/Fβ )v 0 ≥ maxj6=i αj (u/Fβ )vj then αi (u/Fβ )v ≥ maxj6=i αj (u/Fβ )vj because α(u/Fβ ) ≥ 0. Therefore, whenever 1{αi (u/Fβ )v 0 ≥ maxj6=i αj (u/Fβ )vj } = 1, it follows that 1{αi (u/Fβ )v ≥ maxj6=i αj (u/Fβ )vj } = 1. Hence, pˆi (v, v−i |u) ≥ pˆi (v 0 , v−i |u). Step 2 (ˆ pi (v|u) is non-decreasing in ui ). Consider the following optimization problem,  T  u x sup − φ(x) . Fβ kxk1 =1,x≥0 Change variables  with a = x/xi , such that ai = 1, and, for any x satisfying kxk1 = 1, xi =  P 1/ 1 + j6=i xj . Consequently, the optimization problem above is equivalent to sup Ξ(ui , a−i ), a−i ≥0

in which Ξ(ui , a−i ) ,

1+

1 P

j6=i aj



ui + uT−i a−i Fβ

  − φ (a−i , 1) ,

where we use that φ(·) is homogeneous of degree one. We have ∂2Ξ 1 1. For simplicity, we use w(k) to (n) represent the future promises w(k) (v|u). For an inactive agent i (i.e., ui < uβ ), w ˆi (v|u) = ui ≥ 0, (k) (k) (k) thus we focus on w , and the bound on the jump from u to w which is provided by the following lemma.   1 − β (K1 (k))2 (k) (k) Lemma E.1. We have that kw − u k2 ≤ s(u). (n) β 3uβ

62

(n)

Following this lemma, we can argue that kw(k) − u(k) k2 < uβ 2

ˆ w(v|u) ≥ 0 . In particular, using the fact that (1 − β) < (1 − β) n+4 and s(u) ≤ 1 we have that

kw

(k)

−u

(k)

 k2 ≤

1−β β



2

(K1 (k)) (n)



(1 − β)

2 n+4

which implies w(k) > 0 and 2 2 for n ≥ 1, K1 (k) /β ≤ ξ (n) ,

2 ξ (n)

(n)

3uβ

 =

3uβ

 (n) 2



(n)

(n)



3uβ



3

.

(37)

(k,n)

U (k) . We consider the indicator function J   (k,n) (k,n) defined in (30) with scalar s(u)Fβ . For simplicity, we define J(x) = J x, s(u)Fβ in this proof.  (k,n) Corollary C.1 states that J w(k) ≤ 0 if and only if w(k) ∈ s(u)Fβ U (k) , because w(k) ≥ 0 as shown   earlier. In order to show J w(k) ≤ 0, we consider the quadratic expansion of J w(k) around u(k) provided in Proposition C.4. We next prove that the necessary conditions for Proposition C.4 to hold.   (k,n) Lemma E.2. The future promise w(k) is in S s(u)Fβ . Step 2.

In this step, we show that w(k) ∈ s(u)Fβ

  (k,n) Following this lemma, we obtain that the set S s(u)Fβ contains all Θ(k) between w(k) and   (k,n) u(k) because it is convex. Therefore, Proposition C.2 implies that α Θ(k) /s(u)Fβ > 0. Lemma E.3. The matrix Π(a) is positive definite for all a > 0, and its minimum eigenvalue is cH (k) (mini ai )k+1 . This lemma enables us to invoke Proposition C.4. Thus, we can analyze the terms in the quadratic   (k,n) expansion. We have that J u(k) ≤ 0 because u(k) ∈ s(u)Fβ U (k) . In order to show, J w(k) ≤ 0, it is sufficient to show the following inequality holds. 

∇J u

(k)

T

(w

(k)

−u

(k)

 T     1  (k) (k) (k) (k) (k) ≤ 0. w −u w −u Hess J Θ )+ 2

We first consider the first-order term. The following lemma provides a lower bound for −∇J u(k) u(k) ).

T

(w(k) −

Lemma E.4. The gradient of J(x) evaluated at u(k) satisfies   (k,n)  T (1 − β) 1 − Fβ E[v] ≤ −∇J u(k) (w(k) − u(k) ) .  2 (k,n) 2k Fβ We next consider the second-order term. Lemma E.5. We have that T      1 1  (k) w − u(k) Hess J Θ(k) w(k) − u(k) ≤  2 2

1  (k,n) 2 Fβ



1 k+3

(n)





1−β β

2

E[v]K2 (k) . k

 1 k+4 1 For n ≥ k, it follows that (1 − β) n+4 ≥ (1 − β), and ξ (n) n(k − 1)β 2 k+4 ≥ (E[v]K2 (k)) k+4 , thus   (k,n) (n) k+3 2 we have that (1 − Fβ ) uβ β ≥ (1 − β)K2 (k). Finally, we use this observation to replace 63

(1 − β)K2 (k) in the upper bound provided in Lemma E.5 and show that this upper bound is smaller than the lower bound on the term with gradient (negative term) given in Lemma E.1. Consequently, (k,n) it follows that w(k) ∈ s(u)Fβ U (k) . (k,n)

ˆ Note that w(k) ∈ s(u)Fβ U (k) does not necessarily guarantee that w(v|u) lies in the set Ωβ ˆ because w(v|u) could involve fewer active agents than u. That is, in the next round the number of 0 active agents may decrease to k 0 < k. Therefore, in the following step, we prove that w(k ) (v|u) ∈ 0 (k ,n) (k0 ) ˆ s(w(v|u))F U . β 0

0

Step 3. For simplicity, we use vector w(k ) to represent w(k ) (v|u). The support function of the set (k,n) (k,n) s(u)Fβ U (k) is s(u)Fβ φ(k) (·). According to Schneider (2013, p. 44), the support function satisfies (k,n)

that z ∈ s(u)Fβ

(k,n) (k) (k) φ (x )

U (k) if and only if z T x(k) ≤ s(u)Fβ (k,n)

fact that w(k) ∈ s(u)Fβ

for all x(k) ∈ Rk . Therefore, the

(k,n) (k) (k) φ (x )

U (k) implies that (w(k) )T x(k) ≤ s(u)Fβ (k0 ,n)

0

ˆ To prove that w(k ) ∈ s(w(v|u))F β 0

0

0

0

for all x(k) ∈ Rk . (k0 ,n) (k0 ) (k0 ) φ (x )

0

ˆ U (k ) , we show that (w(k ) )T x(k ) ≤ s(w(v|u))F β

0

(k0 )

0

for an arbitrary x(k ) ∈ Rk . Fix x(k ) ∈ Rk . Let x ∈ Rk be such that xi = xi for all i ≤ k 0 and 0 0 0 0 xi = 0 otherwise. Therefore, we obtain xT w(k) = (x(k ) )T w(k ) , and φ(k) (x) = φ(k ) (x(k ) ). Now, using 0 0 0 0 (k,n) the property of the support functions, we obtain (w(k ) )T x(k ) ≤ s(u)Fβ φ(k ) (x(k ) ). (k0 ,n)

(k,n)

≥ s(u)Fβ

ˆ We next prove that s(w(v|u))F β inequality for

(k,n) Fβ

(k0 ,n)

and Fβ

. Using the definitions, we get the following

: 

(n)

(k,n)



(k,n)

= Fβ

(k0 ,n)

− Fβ

(k,n)

+ Fβ

(k0 ,n)

= Fβ



n(k − k 0 )uβ

(k0 ,n)

≤ Fβ

E[v]

(n)

1 −

n(k − k 0 )uβ E[v]

 .

(n)

ˆ Recall that for an inactive agent i (i.e., ui < uβ ) our future promise function w(v|u) is such that w ˆi (v|u) = ui . If an agent is inactive for a given initial state u, then he remains to be inactive for a ˆ ˆ given future promise w(v|u). Therefore, we can bound s(w(v|u)) in terms of s(u) as follows: k P

ˆ s(w(v|u)) = s(u) −

w ˆi (v|u)

i=k0 +1

(n)

where (a) follows from the fact that uβ s(u) ≥ 1/n (since E[v] ≥

(k − k 0 )uβ s(u)E[v]



(b)



 ≥ s(u) 1 −

(n)

n(k − k 0 )uβ E[v]

 .

≥ w ˆi (v|u) for the inactive agents and (b) follows because (k0 ,n)

ˆ and k > 1). Therefore, it follows that s(w(v|u))F β

Finally, this observation implies that (k0 ,n) (k0 ) ˆ s(w(v|u))F U . β

(n)

≥ s(u) 1 −

E[v]

(n) nuβ



(a)

0 0 (w(k ) )T x(k )



(k0 ,n) (k0 ) (k0 ) ˆ s(w(v|u))F φ (x ), β

(k,n)

≥ s(u)Fβ

and

.

0 w(k ) (v|u)



Hence, we obtain that

n o 0 0 ¯0 (n) (n) (k0 ,n) (k0 ) ˆ w(v|u) ∈ u ∈ Rn | u(k ) ≥ uβ , u(k ) < uβ , and u(k ) ∈ s(u)Fβ U ⊆ Ωβ .

E.2

Proof of Theorem 6.1 (n)

Proof. The set Ωβ is a subset of Uβ Jβ =

(n,n) Fβ J FB ,

by Proposition 6.1. Thus, the maximum achievable social welfare

is less than Jβ∗ .

64

E.3

Proofs of Lemmas E.1, E.2, E.3, E.4 and E.5

In the following proofs, we consider u ∈ Ωβ with k active agents and the k dimensional subvector u(k) represent the promised utilities for the active agents. We use Θ(k) to represent an arbitrary k (n) dimensional point between u(k) and w(k) (v|u). Here the set Ωβ is characterized by constants uβ and n on (k,n) Fβ following Definition E.2. Further, define vectors k=1

 γ = α(k) 

u(k) (k,n) s(u)Fβ





 and λ = α(k) 

(k)

Θ

(k,n) s(u)Fβ

 .

(38)

Proof of Lemma E.1. For simplicity, we√use the short notation w(k) to represent the future promises w(k) (v|u). Because kw(k) − u(k) k2 ≤ kkw(k) − u(k) k∞ , we focus on an upper bound for kw(k) − (k) (k) u(k) k∞ = max |wi − ui |. We start with the following expansion. i

(k) wi



(k) ui

 Z vi Z v¯ i 1 − β h (k) (k) (k) (k) ui + Pi (y|u)dy − Pi (vi |u)vi − = F¯ (y)Pi (y|u)dy β 0 0 h i 1 X γj  (k) (k) vj |u) , Wj (vj |u) − Evˆj Wj (ˆ − k−1 γi 

j6=i

where

(k) Pi (y|u)

= s(u)

Y

 F

j6=i



1−β β

 Z 0

vj

(k)

γi y γj



h i (k) (k) vj |u) is given by and Wj (vj |u) − Evˆj Wj (ˆ vˆj

Z

(k)

Pj (y|u)dy − Pj (vj |u)vj − Evˆj

0

 h i (k) (k) Pj (y|u)dy + Evˆj Pj (ˆ vj |u)ˆ vj . (k)

(k)

We prove this result in three steps. In the first two steps, we consider two cases: |wi − ui | = (k) (k) (k) (k) (k) (k) wi − ui and |wi − ui | = ui − wi , and get a bound on the norm which depends on 1/ mini γi . (n) In the last step, we get an upper bound for 1/ mini γi that depends on uβ . (k)

(k)

wi

(k)

− ui

(k)

− ui ). Here, we remove negative terms to obtain the following bound.      Z vj  Z vi X γj 1 − β  (k) 1 (k) (k) (k) ui + ≤ Pi (y|u)dy + Pj (vj |u)vj + Evj Pj (y|u)dy  . β k − 1 γ i 0 0

Step 1 (Bounding wi

j6=i

(k)

(k)

Note that Pi (v|u) ≤ s(u) for all v by definition, and ui ≤ s(u)E[v]. Moreover, using the fact that the sum of γi ’s adds up to 1, and vi and vj are less than v¯. we get the following bound.         1−β (1 − γi ) 1 − β  E[v] + v¯  (k) (k) wi − ui ≤ s(u)(E[v] + v¯) 1 + ≤ s(u) . β (k − 1)γi β min γi i

65

(k)

(k)

− wi ). Similar to the previous step, we obtain  " Z v¯ 1 − β (k) (k) (k) (k) ui − wi ≤ Pi (vi |u)vi + F¯ (y)Pi (y|u)dy β 0 Z vj # 1 X γj (k) (k) Pj (y|u)dy + Evˆj [Pj (ˆ vj |u)ˆ vj ] , + k−1 γi 0 j6=i     1 − β  E[v] + v¯  ≤ s(u) . β min γi

Step 2 (Bounding ui

i

Summarizing the previous two steps, we obtain kw(k) − u(k) k∞ ≤ s(u) nizing

kw(k)



u(k) k





kkw(k)



u(k) k



1−β β







 E[v] + v¯ . Recogmin γi i

we obtain √        1 − β  k(E[v] + v¯)  1 − β  cN (k)  kw(k) − u(k) k2 ≤ s(u) ≤ s(u) . β min γi β min γi 2

∞,

i

i

Step 3 (Bounding 1/ mini γi ) In this step, we find an upper bound for 1/ mini γi as follows: (k)

ui

(a)

(k,n)

≤ s(u)Fβ

(b)

E[vi 1{γi vi ≥ max γj vj }] ≤ γi k f¯E[v 2 ] = cS (k)γi . j6=i

(k)

(k,n)

As discussed in Remark 3.1, ui = s(u)Fβ (∇φ(k) (γ))i − µ for some nonnegative scalar µ. Using the expression derived in Proposition 2.4 for (∇φ(k) (γ))i , we get (a). Because the p.d.f. f (·) is ¯ bounded in the support  2  by f and the c.d.f. F (·) is always less than one, E[vi 1{γi vi ≥ maxj6=i γj vj }] is bounded by γi f¯E v / maxj6=i γj . Together with this observation, using the fact that maxj6=i γj ≥ 1/k, (k,n)

and s(u) ≤ 1 and Fβ cS (k) mini γi ≥ kw(k)

≤ 1, we obtain (b). Taking the minimum over i’s in both sides, we get (n)

(k) mini ui

≥ uβ . Consequently, we have that

u(k) k



− s(u)

2



1−β β







 cN (k)  ≤ min γi



i

1−β β







 cS (k)cN (k)  = (n) uβ



1−β β



(K1 (k))2 (n)

.

3uβ

(n)

(n)

Proof of Lemma E.2. Equation (37) implies that kw(k) − u(k) k2 ≤ uβ /3. Because u(k) ≥ uβ , we (k,n)

must have w(k) > 0. If the point w(k) ∈ s(u)Fβ (k,n)

w(k) ∈ / s(u)Fβ

U (k) , the result holds immediately. Now suppose (k)

U (k) , and, therefore, there must exist a component j such that wj (k,n)

such that a ¯ = inf{a : w(k) − ae ≤ u(k) }, therefore w(k) − a ¯e ∈ S(s(u)Fβ

(k)

(k)

> uj . Select a ¯

) if w(k) − a ¯e > 0. The (k)

definition of a ¯ implies that there must exist a component i such that wi − a ¯ = ui > 0. We next (k) (k) (k) (k) (k) (k) focus on components j 6= i. Using the fact that a ¯ = wi − ui , we have wj − a ¯ = wj − wi + ui . (k)

Thus, we only need to show that wj

(k)

− wi

(k)

+ ui

66

(k)

> 0. Because ui

(k)

+ kw(k) − u(k) k2 ≥ wi

and

(k)

wj

(k)

(k)

≥ uj − kw(k) − u(k) k2 ≥ uβ − kw(k) − u(k) k2 , we have (k)

wj

(k)

− wi

(k)

+ ui

(n)

≥ uβ − 2kw(k) − u(k) k2 > 0 ,

(n)

where the last inequality follows because uβ ≥ 3kw(k) − u(k) k2 . Definition E.3. We define the weighted dot product h·, ·ix and the induced norm as follows. Let z and ˜ be arbitrary vectors in Rk . z ˜ix = hz, z

k X

zi z˜i xi and kzk2x = hz, zix =

i=1

k X

zi2 xi .

i=1

 Proof of Lemma E.3. Denote M = Hess φ(k) (a) . Proposition 2.4 shows that M is well defined for a > 0. Thus, Π (a) = M + ee T is also well defined. We identify a lower bound on the minimum eigenvalue of the matrix M + ee T which is positive and thus implying that M + ee T is positive definite. We show this result in three steps. Step 1. In this step, we provide a lower bound for the minimum eigenvalue of M + ee T . Define the following functions: Q y Z v¯ F at t and Φ , ω(y)dy , ω(y) , y2 0   1 y 2 f (y) η(y) , y 1 {y ≤ v¯} and gi (y) , η . F (y) ai ai Z v¯ Let G be a matrix whose entries are given by Gij = hai gi , aj gj iω , ai gi (y)aj gj (y)ω(y)dy. 0

Using the weighted norm notation in Definition E.3, we can equivalently express M as follows:   X M = diag  a2j hgi , gj iω  − G . j

X Here, the first term defines a diagonal matrix whose ith diagonal component is a2j hgi , gj iω . Define j Z v¯ X  2 M (y) = diag aj gi (y)gj (y) − G(y) to alternatively represent M , i.e., M = M (y)ω(y)dy. j

0

Next, consider the following optimization problem, whose objective value is the minimum eigenvalue of the matrix (M + ee T ), Z v¯ (xT M (y)x)ω(y)dy + (xT e)2 . (39) Ψ , min xT (M + ee T )x = min kxk2 ≥1

kxk2 ≥1 0

A straightforward lower bound for Ψ is obtained by taking the minimization to inside the integral. To do that, we also need to take the second term, (xT e)2 , to inside the integral by properly adjusting the weight as follows: e e˜ , √ . Φ

67

Therefore, we have Z

v¯ 

Ψ≥

T

T

min (x M (y)x) + (x e˜ )

0

2



kxk2 ≥1

ω(y)dy .

(40)

Step 2. Denote 4(y) to represent min (xT M (y)x)+(xT e˜ )2 . Then, the inequality (40) is represented kxk2 ≥1 Z v¯ 4(y)ω(y)dy. We continue by analyzing 4(y). as Ψ ≥ 0

4(y) = min (xT M (y)x) + (xT e˜ )2 kxk2 ≥1

    2  2 X X X X 1 = min  xj √  a2j gj (y)  x2j gj (y) −  xj gj (y)aj  +  kxk2 ≥1 Φ j j j j  2 X 1 xj gj √  . = min kak2g kxk2g − hx, ai2g +  kxk2 ≥1 gj Φ j Denote e g ,



√1 Φgi

 i

. Then, 4(y) is given as follows: 4(y) = min kak2g kxk2g − hx, ai2g + hx, e g i2g .

(41)

kxk2 ≥1

We next provide a lower bound for 4(y) by using the expression (41). We first consider a relaxation obtained by replacing the constraint kxk2 ≥ 1 with kxk2g ≥ min gi as follows: i

4(y) ≥

min

kxk2g ≥min gi

kak2g kxk2g − hx, ai2g + hx, e g i2g = min gi kak2g + i

i

min

kxk2g ≥min gi

hx, e g i2g − hx, ai2g ,

i

"

#

= min gi kak2g + min hx, e g i2g − hx, ai2g . kxk2g ≥1

i

In order to express this lower bound on 4(y), there is a need for a closed-form solution for the optimization problem over the differences of weighted dot products. The following lemma provides a closed-form solution for it. Lemma E.6. The optimal value of the optimization problem min hx, eg i2g − hx, ai2g is given by kxk2g ≥1

1 2

  q 2 2 2 2 2 2 keg kg − kakg − keg kg + kakg − (2heg , aig ) .

We defer the proof of this lemma to the supplementary appendix. Using the closed-form solution given in the lemma, the lower bound on 4(y) is updated as follows: min gi  4(y) ≥ ≥

i

2 min gi i

2

ke g k2g

+

kak2g

ke g k2g + kak2g





q

ke g k2g + kak2g

(2he g , aig )2 2 ke g k2g + kak2g 68

2

 − (2he g , aig )2

2 = min gi i

he g , ai2g . ke g k2g + kak2g

We obtain the second inequality by taking the common multiplier ke g k2g + kak2g outside the square p brackets because 1 − 1 − y 2 ≥ y 2 /2. We now consider each term separately to simplify the lower bound. X X 1 X 1 1 1X 1 he g , aig = aj √ gj = √ , ke g k2g = , and kak2g = a2j gj . gj = 2 Φ g g Φ g Φ Φ j j j j j j j Using these terms, we define the following lower bound. 1 ai

 2 y ai





y  ai  F ay i

f

f min 1{y ≤ ai v¯} min gi (y) y min a12 f¯1{y ≤ ai v¯} i i i 4(y) ≥ P 1 i P 2 = ≥ P 1 P 2 k + Φ a g (y) + Φ a g (y) g (y) j j j j gj (y) gj (y) g(y) + Φ¯ j



j

f y f¯1{y k g(y)

j

≤ mini ai v¯} + Φ¯ g (y)

j

,

where g and g¯ are lower and upper bounds for any gi , respectively, and given by g(y) ,

yf 1{y ≤ mini ai v¯} v¯2 f¯1{y ≤ v¯} . and g ¯ (y) , yf f¯

Replacing g(y) and g¯(y) in the right-hand side, we obtain the following lower bound for 4(y): y 2 f 2 1{y ≤ mini ai } 4(y) ≥ ¯2 . k f + Φ¯ v 2 f¯2 1{y ≤ v¯}1{y ≤ mini ai }

(42)

Step 3. In this step, we find an upper bound for Φ to obtain a lower bound of 4(y) which we denote by Γ(y). Then, we integrate Γ(y)ω(y) to bound Ψ. In particular, we use the upper bound f¯ on the p.d.f. f (·) in its support to get the first inequality.   Z v¯ mini ai Q f¯ y Z v¯ t at 1 (f¯)k (¯ v mini ai )k−1 1 (f¯v¯)k + (k − 1) Φ≤ dy + dy ≤ + . = 2 y2 (k − 1) v¯ mini ai v¯(mini ai )(k − 1) (mini ai )k 0 v¯ mini ai y When we replace the upper bound on Φ in the right-hand side of (42), we get another lower bound for 4(y). Define the piece-wise function  2  y (k+1)cH (k)(mini ai ) if y ≤ mini ai v¯ y 2 f 2 1{y ≤ mini ai } f k v¯k+1 = Γ(y) , k ¯ otherwise . k f¯2 + (f v¯) +(k−1) v¯2 f¯2 1{y ≤ v¯}1{y ≤ mini ai } 0 v¯(mini ai )(k−1)

Summarizing the previous steps, we obtain 4(y) ≥ Γ(y). Z Recall that in (40), we have the following inequality Ψ ≥

4(y)ω(y)dy. Because Γ(y) is less 0

69



than 4(y), we can lower bound Ψ as follows.   Z (k + 1)cH (k)(mini ai ) v¯ mini ai Y y Ψ≥ Γ(y)ω(y)dy = F dy k k+1 at f v¯ 0 0 t k+1  Z v¯ mini ai cH (k)(mini ai )k+2 (k + 1)cH (k)(mini ai ) 1 k Q Q . y dy = ≥ cH (k) min ai ≥ i v¯k+1 t at 0 t at Z



This lower bound on Ψ, at the same time, is a lower bound on the minimum eigenvalue of the matrix (M + ee T ).  Proof of Lemma E.4. Proposition C.3 provides ∇J u(k) because Lemma E.3 implies that Π (a) is (k,n)

positive definite for all a > 0 and u(k) ∈ S(s(u)Fβ ). Following Proposition G.1 which extends Proposition 3.1 to account the scaling factor, we obtain the following equations.    T γ T s(u)∇φ(k) (γ) − u(k) 1−β γ T (u(k) − w(k) ) (k) (k) (k) . (w − u ) = = −∇J u (k,n) (k,n) β s(u)F s(u)F β

(k,n)

Using the fact that u(k) + µe = s(u)Fβ

β

∇φ(k) (γ) with µ ≥ 0 (see Remark 3.1), it follows that

(k,n)

(k,n)

u(k) ≤ s(u)Fβ ∇φ(k) (γ) and xT ∇φ(k) (x) = φ(k) (x). Moreover Fβ ≥ 1/2, 1 ≥ β and φ(k) (x) ≥ k E[v]/k for all x ∈ R+ by definition. Thus, we obtain    (1 − β) 1 − F(k,n) T   E[v] β w(k) − u(k) ≥ −∇J u(k) .   (k,n) 2 2k Fβ (k,n)

Proof of Lemma E.5. We can invoke Proposition C.3 to get Hess(J(Θ(k) )) because Θ(k) ∈ S(s(u)Fβ ) and Lemma E.3 shows that Π (a) is positive definite for all a > 0. ! −1    T 1 ee Π (λ) −1 = I− . (43) Hess J Θ(k)  Π (λ) (k,n) 2 eT Π (λ)−1 e s(u)F β

     (k,n) 2 We prove this result in two steps. For simplicity, we use A to represent s(u)Fβ Hess J Θ(k) and H to represent Π (λ)−1 . Step 1. In this step, we find an upper bound for supkxk2 =1 xT Ax which depends on mini λi . Using (43), we can rewrite xT Ax as follows: xT Ax =

(e T He)xT Hx − xT Hee T Hx . e T He

Note that H is symmetric, thus eliminating the negative term −xT Hee T Hx yields the following bound, xT Ax ≤

(e T He)xT Hx = xT Hx = εH . e T He

Here, εH is the largest eigenvalue of H, and in the last equality we use that kxk22 = 1. In Lemma E.3, we further show that the minimum eigenvalue of Π (λ) is cH (k) (mini λi )k+1 . Therefore the largest 70

eigenvalue of H is

1 cH (k) (mini λi )k+1

. Therefore, we have that

     1 T 1  (k) w(k) − u(k) ≤  w − u(k) Hess J Θ(k) 2 2

1 (k,n) s(u)Fβ

2

kw(k) − u(k) k22 . cH (k)(mini λi )k+1

(44)

(n)

Step 2. In this step, we find an upper bound for 1/ mini λi that depends on uβ . Optimality of λ (k)

implies that Θi

(k,n)

= s(u)Fβ

(k,n)

(∇φ(k) (λ))i −µ. If we knew Θ(k) is in s(u)Fβ (k,n)

µ is nonnegative and Θ(k) ≤ s(u)Fβ

U (k) , then it would follow (k,n)

∇φ(k) (λ). However Θ(k) could lie outside of s(u)Fβ (k)

that case, µ becomes negative. Thus, it could be the case that Θi

(k,n)

> s(u)Fβ

U (k) . In

(∇φ(k) (λ))i for all

i. Despite this fact, we know −µ is less than ku(k) − w(k) k2 because Θ(k) is between u(k) and w(k) . Therefore, we have that (k)

Θi

(k,n)

≤ s(u)Fβ

(k,n)

(∇φ(k) (λ))i + ku(k) − w(k) k2 = s(u)Fβ

E[vi 1{λi vi ≥ max λj vj }] + ku(k) − w(k) k2 . j6=i

Because the p.d.f. f (·) is bounded by f¯ and the c.d.f. is always less than one, E[vi 1{λi vi ≥ maxj6=i λj vj }] can be bounded by λi f¯E[v 2 ]/ maxj6=i λj . Moreover, we have that maxj6=i λj ≥ 1/k, and (k,n) (k) s(u)Fβ ≤ 1. Thus, it follows that cS (k) mini λi ≥ mini Θi − ku(k) − w(k) k2 . (k)

(n)

We next derive a lower bound for mini Θi in terms of uβ . As shown in the first step of Proposi  (n) 2 tion 6.1, (1 − β) (K1 (k))2 is less than uβ β and we know β ≥ β. Together with these observations, (n)

Lemma E.1 implies that uβ ≥ 3kw(k) −u(k) k2 . Recognizing the fact that Θ(k) is between w(k) and u(k) , (k)

we have Θi

(k)

(k)

≥ uβ , it follows Θi

(k)

≥ uβ − uβ /3 = 2uβ /3 for all i, and so

≥ ui −kw(k) −u(k) k2 for all i. Because ui (n)

Using the fact that uβ

≥ 3kw(k) − u(k) k2 we get Θi

(n)

(k)

(n)

(n)

(n)

(n)

≥ uβ −kw(k) −u(k) k2 . (n)

(n)

mini Θi ≥ 2uβ /3. Combining these bounds we obtain that mini λi ≥ uβ /(3cS (k)). (n)

Finally, using Lemma E.1 to bound kw(k) − u(k) k22 and mini λi ≥ uβ /(3cS (k)), we can bound the right-hand side of (44), and have that  1 T     1  (k) w(k) − u(k) ≤  w − u(k) Hess J Θ(k) 2 2

71

1 (k,n)



2 

1 k+3

(n)





1−β β

2

E[v]K2 (k) . k

Supplementary Appendix F

Proof of Lemma E.6

Proof. The optimization problem in the statement of the lemma can be reformulated by the following √ √ √ change of variables and parameters. Let eg i gi = vi and ai gi = wi , and xi gi = zi for all i. Then it follows that min hx, e g i2g − hx, ai2g = min hz, vi2 − hz, wi2 = min zT (vvT − wwT )z .

kxk2g ≥1

kzk22 ≥1

kzk22 ≥1

Following the min-max theorem, the optimal value of this problem is given by the minimum eigenvalue of the matrix vvT −wwT . To find the eigenvalues, we express v and w with two orthonormal unit vectors v = c1 u1 and w = c2 u1 + c3 u2 , respectively. This implies that c1 = kvk2 and u1 = v/kvk2 , which further w − c2 u1 implies that c2 = uT1 w and c3 = uT2 w. Finally, we have u2 = . In an orthonormal basis kw − c2 u1 k2 starting with u1 and u2 , the matrix vvT − wwT has first two rows and columns  2  c1 − c22 −c2 c3 , −c2 c3 −c23 and everything else is 0. The minimum eigenvalue emerges as follows:     q q   1 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 T 2 c − c2 − c3 − (c3 + c1 + c2 ) − 4(c1 c2 ) = kvk2 − c2 − c3 − (kvk2 + c3 + c2 ) − 4(v w) . 2 1 2 Therefore, we have kvk22 = ke g k2g and vT w = ha, e g ig . To complete the proof, we show that c22 + c23 = kwk22 = kak2g . In fact, c22 + c23 =

(vT w)2 kvk42 kwk42 + (wT v)4 − 2kvk22 kwk22 (wT v)2 +

kvk2 w − (vT w)v 2 kvk22 2

2

he g , ai2g ke g k4g kak4g + he g , ai4g − 2ke g k2g kak2g he g , ai2g  = + ke g k2g ke g k2g ke g k2g kak2g − he g , ai2g  ke g k4g kak4g − ke g k2g kak2g he g , ai2g ke g k2g kak2g ke g k2g kak2g − he g , ai2g  =  = kak2g . = ke g k2g ke g k2g kak2g − he g , ai2g ke g k2g ke g k2g kak2g − he g , ai2g

G

Generalizations of Proposition 3.1 and Proposition 3.2

In this section, we provide generalizations of Proposition 3.1 and Proposition 3.2 to scaled settings. Specifically, we consider these propositions for the scaled main phase mechanism (p(k) , w(k) ) which is introduced in Section 6. Note that, Proposition 3.1 and Proposition 3.2 are special cases with k = n. n on (n) (k,n) . Proposition G.1. Suppose we are given a constant uβ ∈ [0, E[v]] and a sequence Fβ ∈ (0, 1) k=1 Let Ωβ is determined by those constants. For any given state u ∈ Ωβ with k active agents, the future promise vector w(k) (v|u) lies within a plane in Rk . Specifically, the plane is described by the following equation. T T 1−β u(k) − w(k) (v|u) a = s(u)∇φ(k) (a) − u(k) a ≥ 0 β App. 1

(k,n)

where a = α(k) (u(k) /(s(u)Fβ

)).

Proof. We first show that b such that aT w(k) (v|u)+b = 0. Let b =

k P

(k)

[(1−β)s(u)(∇φ(k) (a))i −ui ]/β.

i=1

Using the definition of w(k) (v|u), we obtain the following equation. T

a w

(k)

(v|u) =

k X

(k)

ai Evˆi [Wi (ˆ vi |u)] .

i=1

Moreover, (PK(u)) implies that h i (k) (k) βEvˆi [Wi (ˆ vi |u)] = ui − (1 − β)s(u)E[vi 1{ai vi ≥ max aj vj }] . j6=i

Recall that (∇φ(k) (a))i = E[vi 1{ai vi ≥ max aj vj }]. Combining these three observations, it follows that j6=i

aT w(k) (v|u) + b = 0. The second part of the proposition follows from the following properties of the support function φ(k) (·). Note that xT ∇φ(k) (x) = φ(k) (x) for all x by the definition of φ(k) (·). Furthermore, for a vector x the support function satisfies that φ(k) (x) ≥ xT z for all z ∈ U (k) (see Schneider, 2013). Because (k,n) u(k) ∈ s(u)Fβ U (k) , we obtain the following inequality, which concludes the proof. T T    T s(u)∇φ(k) (a − u(k) a = s(u)∇φ(k) (a)T a − u(k) a = s(u)φ(k) (a) − u(k) a ≥ 0 . n on (n) (k,n) Proposition G.2. Suppose we are given a constant uβ ∈ [0, E[v]] and a sequence Fβ ∈ (0, 1) . k=1 Let Ωβ is determined by those constants. Fix a state u ∈ Ωβ with k active agents. Then, the ex-post future promise w(k) (v|u) is an optimal solution of the following optimization problem: (k,n)

max min α(k) (u(k) /(s(u)Fβ ˜ w(·)

v

s.t. Ev−i [w ˜i (vi , v−i )] =

˜ ))T (u(k) − w(v)) (45)

(k) Wi (vi |u)

∀vi , i = 1, . . . , k (k,n)

Proof. For simplicity, we use a to represent a(k) (u(k) /(s(u)Fβ problem (45) as the following linear programming problem: max

)) in this proof. First, we reformulate

z

˜ w(·)

st.

(k)

E[w ˜i (vi , v−i )] = Wi (vi |u) ∀vi , i = 1, . . . , k z≤a

T

(u(k)

˜ − w(v))

(46)

∀v

(47)

Next, we find an upper bound for this problem by relaxing the constraints over z. (k,n) (k,n) The support function of set s(u)Fβ U (k) is s(u)Fβ φ(k) (·), where φ(k) (x) = E[maxi∈k xi vi ]. Be(k,n)

cause u(k) ∈ E(s(u)Fβ ∇φ(k) (a), i.e.,

(k,n)

U (k) ), we have u(k) /s(u)Fβ

(k) ui

maxj6=i aj vj }] +

(k,n) (k) = s(u)Fβ E[vi 1{ai vi ≥ maxj6=i aj vj }]. Moreover, ui = (1 − (k) βE[Wi (vi |u)], following (PK(u(k) )). These two observations

App. 2

(k,n)

∈ E(U (k) ), which implies u(k) /s(u)Fβ

=

β)s(u)E[vi 1{ai vi ≥ (k)

imply that ui

=

(k,n)

(k) τ E[Wi (vi |u)],

where τ =

βs(u)Fβ

.

(k,n)

s(u)Fβ − (1 − β) Therefore, the constraint (47) becomes z≤

k X

(k)

ai (τ E[Wi (vi |u)] − w ˜i (v)) for all v .

i=1

Because z has to satisfy this constraint for all v, we can relax it by replacing these constraints with a single constraint where the right hand side is the expectation over v. This operation corresponds to taking expectation of w ˜i (v). Following constraint (46), we obtain z≤

k X

(k)

ai (τ − 1)E[Wi (vi |u)]

(48)

i=1

P (k) Therefore, ki=1 ai (τ − 1)E[Wi (vi |u)] is an upper bound for the optimization problem (45). To show (k) w (v|u) is an optimal solution, we first show that w(k) (v|u) is feasible, and the objective function evaluated at w(k) (v|u) is equal to this upper bound. (k) (k) By its definition, the expectation of wi (v|u) with respect to v−i is Wi (vi |u), which implies P (k) feasibility. By Proposition G.1, we also know that aT (u(k) − w(k) (v|u)) = ki=1 ai (τ − 1)E[Wi (vi |u)] which, in turn, implies that w(k) (v|u) is an optimal solution for (45).

App. 3

Smile Life

When life gives you a hundred reasons to cry, show life that you have a thousand reasons to smile

Get in touch

© Copyright 2015 - 2024 PDFFOX.COM - All rights reserved.