{'fraction_non_alphanumeric': 0.04518532670997325, 'fraction_numerical': 0.010546427206725257, 'mean_word_length': 4.330040733197556, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Incomplete Information VCG Contracts for Common Agency

We study contract design for welfare maximization in the well known"common agency"model of [Bernheim and Whinston, 1986]. This model combines the challenges of coordinating multiple principals with the fundamental challenge of contract design: that principals have incomplete information of the agent's choice of action. Motivated by the significant social inefficiency of standard contracts for such settings (which we formally quantify using a price of anarchy/stability analysis), we investigate whether and how a recent toolbox developed for the first set of challenges under a complete-information assumption, VCG contracts [Lavi and Shamash, 2019], can be extended to incomplete information. We define and characterize the class of"incomplete information VCG contracts (IIVCG)", and show it is the unique class guaranteeing truthfulness of the principals and welfare maximization by the agent. Our results reveal an inherent tradeoff between two important properties required to ensure participation in the contract: individual rationality (for the principals) and limited liability (for the agent). We design a polynomial-time algorithm for determining whether a setting has an IIVCG contract with both properties. As our main result we design a polynomial-time"algorithmic IIVCG"contract: given valuation reports from the principals it returns, if possible for the setting, a payment scheme for the agent that constitutes an IIVCG contract with all desired properties. We also give a sufficient graph-theoretic condition on the population of principals that ensures the existence of such an IIVCG contract.


Introduction
Common agency. The principal-agent model is a fundamental area of microeconomic theory, capturing natural contractual relations with important practical implications [5,21,29,28]. At the heart of the model is a relationship between one entity (agent) who acts on behalf of another (principal); for example, corporate management and shareholders, a freelance worker and employers, the public regulator and citizens. In all of these examples, the agent (manager/freelancer/regulator) acts on behalf of multiple principals (shareholders/employers/citizens). The extension of the basic single-agent, single-principal setting to multiple principals mirrors the extension of the basic singleseller, single-buyer auction setting to multiple buyers. This extension was introduced in 1986 by Bernheim and Whinston [3], and is known as common agency. This fundamental theory has many additional applications to the study of markets, for example: a marketing agency that bids for ad space on behalf of multiple advertisers [8], a professional host on Booking.com who manages several properties for the owners, or platforms like Airbnb that have characteristics of an agent representing sellers (Airbnb works to promote listings of property owners). 1 The agency problem. The main challenge in the principal-agent model (with one or more principals) is the agency problem [32]: Actions that generate good outcomes for the principal(s) are costly for the agent, who rationally acts in his own self-interest. To align the interests of the principals with those of the agent, the principals compensate the agent depending on the outcome of his action. This compensation scheme, designed to incentivize the agent to choose a desirable action, is called a contract. The agency problem has two necessary ingredients (if one of these is missing, the problem is resolved): (i) Incomplete information of the agent's actions; (ii) Principals are better risk bearers than the agent.
Incomplete information means that the principals cannot directly observe the agent's choice of action, only its resulting (stochastic) outcome. The contractual payment scheme thus depends on the outcome, which serves as a noisy indicator of the action. This crucial feature of the model is known as hidden action or moral hazard. For example, employers of a freelancer are not aware of how much effort he invests, but do view the outcome of his efforts and compensate him accordingly.
The second crucial feature is the asymmetry between principals and agents in their attitude towards risk. The principal typically has "deeper pockets" and can bear the risk that the agent's actions will lead to losses. The way this is incorporated into our model follows classic works like [18,12,6]: we focus on contracts guaranteeing limited liability (LL) for the agent, i.e., payments in the contractual relationship flow only from the principals to the agent. Indeed, in our examples, a manager does not typically pay shareholders (even if he loses their investment), nor does a freelancer pay the employers to purchase projects. 2

Multiple Principals: Challenges and a Promising Approach
Having multiple principals raises intriguing new challenges: "The principal-agent problem here is intensified: not only is there still asymmetric information between the principals and agent that can bring moral hazard, but there is also asymmetric information between the principals themselves [... S]ince principals' interests often diverge, they face incentives to advance their individual interests instead of the joint interests by all principals[...] As a result, introducing governance to align the interests of the principals with those of the agent is much more difficult" [31].
Thus, misalignment among the principals combined with their private information (their types) requires novel contractual mechanisms. In this paper we focus on the design of welfare-maximizing contracts.
First price contracts. The classic literature on multiple principals has thoroughly explored one class of contracts, which can be referred to as first price. A first price contract is a simple mathematical object: it is a function t for every principal that maps an outcome generated by the agent's action to the principal's payment. The payment is simply the principal's (reported) value for this outcome, which can obviously be different than her true value. As we show in Theorem 1, first price contracts can be very socially inefficient (where social efficiency is considered in equilibrium, through the standard measures of price of anarchy/stability).
A solution designed for complete information. A possible solution arises from recent work of Lavi and Shamash [22]. Their work studies a model with complete information about the agent's choice of action, and thus no agency problem. To demonstrate how different the complete and incomplete information models are, consider a single principal and an agent choosing among two actions ("shirking" and "working"), the second costing him more effort. There are two possible outcomes ("failure" and "success"), and the principal's value for the second is higher. Shirking is more likely to produce failure than working. The precise costs, values and probabilities appear in Example 3.5, and are set up such that working maximizes the expected social welfare (the principal's expected value for the action's outcome, less the agent's cost for the action). With full information the principal can simply tell the agent to work and pay him his cost, thus maximizing welfare and extracting it fully as her expected utility. But in the incomplete information world where the agent's action is unknown, the socially-inefficient "null" contract, which pays nothing and incentivizes the agent to shirk, is preferable for the principal (see Example 3.5 for details).
Further evidence of the difference between the two models is the state of the literature in each. For complete information, the problem of welfare maximization with multiple principals and a single agent is largely settled by Bernheim and Whinston [4] (in a paper preceding their "Common Agency" paper [3]). Lavi and Shamash [22] address a generalization of this problem to would apply [6]. multiple agents (the generalization is due to [26]). They instantiate an abstract concept known as contractible contracts [25], and introduce a novel class of VCG contracts. In contrast, in the incomplete information world, the problem of welfare maximization with multiple principals has remained largely open even for a single agent in the three decades since the common agency model was introduced by [3]. Several works have considered the design of contracts with incomplete information from a computational point of view [2,16,19,20,10,9]; some of these works have multiple agents (e.g., [33,1]), or agent private types [15], but none to our knowledge consider multiple principals with private types.
VCG contracts and incomplete information. In the VGC contracts of Lavi and Shamash [22], principal 's payment for an outcome is no longer just her own (reported) value from this outcome (as in first price contracts), but is a function of the other principals' reported values as well. In this sense, the payment functions in VCG contracts are reminiscent of payments in VCG auctions [30,7,14]. 3 Such payments are indeed used in practice -for example, contracts with "price match guarantee" clauses. Moreover, computerized platforms (such as freelancing platforms) make VCG contracts easier to coordinate. Such platforms typically have a central intermediary who can serve as "mechanism designer". E.g., in online labor markets, the market platform serves as an intermediary between an agent (freelancer) and the principals who hire him. The platform has control over pricing structures and usually treats social welfare as a first-order concern [27, p. 55].
Other examples include marketing agencies (multiple advertisers and a single marketing agent), corporate management (multiple managers and shareholders, and a single lower-level manager), etc.
Our goal in this work is to import ideas from VCG contracts and auctions to the incomplete information world, towards making progress on the long-standing problem of welfare maximization in common agency settings. Our first challenge is that the class of VCG contracts is undefined for incomplete information settings. After devising an appropriate generalization of the definition (Section 3.4), we uncover a more serious challenge -the adaptation of VCG contracts to incomplete information introduces negative payments. In other words, under such contracts the agent is sometimes required to pay the principal, in violation of the LL property. Our results show this is no coincidence, and ultimately address the challenge through algorithmic methods (Section 4).
Our main result is a polynomial-time algorithm that implements a contract with all the desired properties, including LL, in all settings for which such a contract exists. We believe our contribution can be a first step in a potentially rich research area of utilizing contractible contracts to address agency problems: Indeed, it is as hopeless to solve all agency problems with first price contracts as it is to solve all mechanism design problems with first price auctions. More general contract classes are called for, and as with auctions, the computational viewpoint comes in handy.

Our Results
Design objectives. Motivated by the inefficiency of first price contracts, we seek new contracts that satisfy the following desiderata. (i) Incentives: Since principals' values are privately-known, we require that principals are incentivized to report their values truthfully in dominant strategies.
We also require individual rationality (IR) so that principals' participation is a dominant strategy, and as explained above, also the LL property so the agent faces no risk. 4 (ii) Objective: The payment schemes should incentivize the agent to choose a welfare maximizing action (we leave revenue maximization 5 for future work). (iii) Computational efficiency: Our contracts should be polynomial-time computable.
Beyond first price contracts. We begin with two examples showing that when the principals offer first price contracts to the agent, there can be a highly inefficient equilibrium (Example 1 shows the price of anarchy is O( 1 n ) for n principals), and it's even possible that all equilibria are inefficient (Example 2 shows the price of stability is 1 2 +O( 1 q−1 ) for q actions). As our first conceptual contribution, in Section 2 we formulate a game that allows us to consider more complex contract formats beyond first price: Every principal ∈ [n] reports a valuation b mapping outcomes to values. (The reports can be viewed as offers made to the agent, or as "bids" to a centralized computerized platform.) The agent then chooses an action which generates an outcome o. A contract t = (t 1 , ..., t n ) maps the reports b = (b 1 , ..., b n ) and the realized outcome o to a payment t (b, o) from every principal to the agent.
The IIVCG family and an impossibility. In Section 3 we define the Incomplete Information VCG (IIVCG) contract family, which is dominant strategy truthful and always induces welfare maximization. Dominant strategy truthfulness is a significant advantage of IIVCG over first price contracts: with the latter, a decades-old question is how the principals arrive at an equilibrium, since lacking coordination they face a bargaining-like problem of how to split the welfare. Building upon a classic result of Holmström [17], we show the IIVCG family is unique (note that all results stated in this section are informal): Theorem (Uniqueness of IIVCG, see Theorem 2). Every contract t such that (i) the agent is induced to maximize welfare, and (ii) the principals' dominant strategy is truthful, must belong to the IIVCG family.
Our definition of the IIVCG family (Definition 2) specifies only the expected payments to the agent for every action, where the expectation is over the action's stochastic outcome. This is not enough -a contract must determine the payments for every possible outcome realization. We 4 One could also consider relaxing the LL constraint by requiring not that every contractual payment is non-negative but rather that only the aggregate payment from the principals to the agent is non-negative for every outcome; this does not change our results (see Remark 7). 5 The concept of "revenue" in a multi-principal settings may require new definitions.
address this by characterizing the outcome-specific payments that incentivize welfare maximization on behalf of the agent: Lemma (Payment characterization, see Lemma 1). A contract t = (t 1 , . . . , t ) is IIVCG if and only if principal 's payment function t can be expressed using h (·) and w , where h (·) is a function of the other principals' reports b − , and w is a payment vector belonging to the polytope of payments incentivizing the socially efficient action.
This lemma is useful since it exactly defines our "design space", and in particular translates to linear constraints that are the cornerstone of our algorithmic constructions.
IIVCG contracts satisfy truthfulness and welfare maximization; what about the other desiderata of IR and LL? Whether or not these properties hold depends on the choices of h (·) and w that determine the payments for every principal . A natural starting point is to choose these to make principal 's expected payment equal to the externality she imposes on the others, as in VCG auctions with the Clarke pivot rule [7], as well as VCG contracts [22]. We refer to this instantiation of the IIVCG family as Auction-Inspired contracts. In Section 3.4 we show that while Auction-Inspired contracts are always IR, the LL property is not necessarily satisfied. This is no coincidence -there is in fact an inherent clash between the two properties: Theorem (LL-IR tradeoff, see Theorem 3). There are common agency settings for which no IIVCG contract is both LL and IR.
The above theorem can apply even to settings with a single principal. This impossibility result highlights how challenging it can be to design contracts under incomplete information, and how fundamentally different this model is from the complete information one.
An algorithmic approach and main results. In light of our impossibility result, we adopt an algorithmic approach that leverages our characterization of IIVCG contracts and uses it constructively. We give a polynomial-time algorithm (Algorithm 2) that determines for a given common agent setting whether or not there is an IIVCG contract for this setting that is both LL and IR.
If such a contract exists, we design another polynomial-time algorithm (Algorithm 1) that implements it, i.e., upon receiving reports b = (b 1 , ..., b n ) and an outcome o, it computes h (b − ) and w "on the fly" for every principal in order to determine the contractual payments. The algorithmic basis of this approach gives us flexibility that may not exist when trying to design a contract with a closed-form formula for payments.
Theorem (Main result, see Theorems 5-6). Consider a common agency setting. Algorithm 1 implements a (truthful and welfare maximizing) IIVCG contract that satisfies LL and IR whenever such a contract exists for the setting; Algorithm 2 determines existence of such a contract. Both algorithms run in polynomial time.
The next observation demonstrates that IIVCG contracts can achieve welfare maximization for settings in which first price contracts fail to achieve so even approximately.
Observation (The power of IIVCG beyond first price, see Appendix A.3). Algorithm 2 returns "Exists" (i.e., there exists an LL, IR IIVCG contract) when run on Examples 1 and 2, which have bad price of anarchy (respectively, stability) for first price contracts.
Finally, in Section 5 we give an instantiation of the IIVCG family called Weighted IIVCG.
Weighted IIVCG contracts are always LL, and we characterize the class of settings for which they are also IR -namely, settings that satisfy a graph-theoretic condition on the graph whose nodes are the principals. This completes the picture, showing the full range within IIVCG: IR and not LL (Auction-Inspired IIVCG), LL and not IR (Weighted IIVCG), and both LL and IR whenever possible (Algorithmic IIVCG). One avenue we do not explore in this paper but leave as an open question is contracts that guarantee LL and IR always, but only approximately achieve the optimal social welfare.

Model and Preliminaries
Common agency settings. We adopt the classic model of Bernheim and Whinston [3], in which there is a single agent who is common to n principals. The agent chooses an unobservable action that incurs a cost on the agent himself, and stochastically leads to an observable outcome that benefits the principals. This is formalized by a common agency setting as we now describe.
Every setting is a tuple (A, ψ, O, V, F ) as follows. A is a set of q actions available to the agent.
ψ maps an agent's action to its cost (we assume for simplicity no two actions have the same cost).
O is a set of m outcomes. Each principal ∈ [n] has a multiparameter valuation function v : O → R ≥0 , which maps an outcome to a non-negative value, and can also be thought of as a vector in R m

≥0
(valuations in our model are thus succinct objects). Valuation v belongs to a domain V , where for simplicity we assume V is a convex, polynomially-described polytope; all our results extend to general convex domains. 6 Valuation profile v is the tuple (v 1 , . . . , v n ), and V is the tuple of domains are privately known. This makes our model a hidden action, hidden type model (where the type is of the principals). 6 In the general case, the convex domains are represented by polynomial-time membership oracles. Convex valuation domains appear, e.g., as the main application in [17].

Contracts.
A contract profile t = (t 1 , ..., t n ) (contract for short) includes a payment rule t for each principal . We diverge from the classic model in that the payment rules depend not only on the outcome of the agent's action, but also on the reported valuations of all principals: t : V × O → R.
Such contracts are known as contractible. We denote principal 's report (a.k.a. bid ) by b ∈ V (the report need not be truthful, i.e., b is not necessarily v ).
Taken together, the n (publicly known) payment rules incentivize the agent when choosing an action. This introduces a tension among the n noncooperative principals to coordinate the agent's choice of action, on top of the usual tension between each principal and the self-interested agent. What constitutes a desirable action depends on the principals' valuations and on the design objective (welfare, revenue, etc.). In this work we focus on welfare, as detailed below.
The game. Fix a common agency setting. A contract t and valuation profile v define the following two-stage game. First, principals simultaneously report their bids b = (b 1 , ..., b n ). After perceiving the bids, the agent chooses a hidden action a, which imposes a distribution F |a over the outcomes.
An outcome o is realized according to this distribution, and each principal pays the agent t (b, o).
We assume quasi-linear utilities and risk neutrality for all parties. The utilities of the game are as follows: The agent's utility is the sum of payments less cost of chosen action, i.e., Thus, the agent's action x * (b) given bid profile b maximizes his expected utility: 7 We assume the principals know the agent is rational and can anticipate his action x * (b) given bid profile b. As for the utility of the principals, principal 's utility is her value less payment, i.e., Consider now the incomplete information game defined by contract t when the valuation profile v is not fixed. A strategy of principal in this game is a mapping from every possible valuation v to a bid b . A strategy is called dominant if it is guaranteed to maximize the principal's expected utility for every v no matter what the other principals bid, i.e., for every b − ∈ V − (and still 7 As is standard in the literature, we assume the agent tie-breaks in favor of the design objective (for an example in the context of revenue see [6]). In our case the objective is the (declared) social welfare. If among the utilitymaximizing actions there are several with highest (declared) welfare, we assume the agent chooses to invest maximum effort, i.e., takes the one with the maximum cost. (While we feel this kind of "eager" tie-breaking is in line with the standard tie-breaking assumption, our results do not rely on it and would hold for any consistent tie-breaking rule.) assuming the rationality of the agent). Principal is truthful as a dominant strategy if announcing her true valuation maximizes her expected utility, i.e., v ∈ arg max We say that contract t is truthful if every principal is truthful as a dominant strategy.
Design objectives. Our desiderata from a contract t concern (1) incentives, (2) social welfare, and (3) computational complexity. The first group of design objectives address incentives -principals' and agent's willingness to participate, and principals' willingness to provide private information.
For the latter, we focus on truthful contracts, in which every principal's dominant strategy is to simply report her valuation. To ensure principals' participation in such contracts, we require that every truthful principal has non-negative expected utility no matter how the others bid -this is known as the individual rationality (IR) property for principals. Formally, contract t satisfies IR if We now turn to the agent's incentives, for which we need the following central definition: The LL requirement guarantees that the agent never pays out-of-pocket. Under LL, to ensure the agent is guaranteed non-negative utility, we assume there exists an action with zero cost. 8 The second design objective is social welfare. Given a valuation profile v, the (expected) welfare of action a, denoted by Wel a (v), is the total expected value less cost, and a * (v) is a welfaremaximizing action: We seek contracts such that for every bid profile b, the agent's action choice x * (b) is "declared welfare maximizing"; we denote this by x * (b) = a * (b). 9 Since we focus on truthful contracts, when playing according to their dominant strategies the principals report b = v, and the agent's choice The last design objective is computational complexity: given a bid profile b and an outcome o, the payments t (b, o) should be computable in polynomial time for every ∈ [n]. To summarize our desiderata, we seek truthful, IR and LL contracts, which incentivize the agent to maximize welfare and whose payments are computable in polynomial time.

The IIVCG Family of Contracts
In this section we introduce IIVCG contracts. After giving motivation in Section 3.1, we define the IIVCG family and show it is (uniquely) truthful and welfare-maximizing in Section 3.2. In Section 3.3 we give the payment format and in Section 3.4 we instantiate this format such that payments capture externalities,à la VCG auctions. We show this instantiation is IR but not LL, and in Section 3.5 establish an inherent tradeoff between these two properties.

Motivation: The Social Inefficiency of First Price Contracts
A first price contract is a contract where each principal simply pays her bid, that is, As discussed in the introduction, this is the most common contract format in the literature. It satisfies the IR and LL properties. However, as we next show, it suffers from inefficiency in terms of social welfare. Since first price contracts are not truthful, we address their inefficiency through the measures of price of anarchy and price of stability. 10 Theorem 1. The price of anarchy of first price contracts tends to zero when the number of principals tends to infinity. The price of stability of first price contracts tends to 1 2 when the number of actions tends to infinity. 11 The proof relies on the following examples. where 0 < < γ < 1. There are n > 3 principals with the following valuation domains: In this example, the bid profile b 1 = (0, 0, 1 + γ), b 2 = (0, 1 + , 0), and b = (0, 0, 0) ∀ > 2 induces the agent to take action x * (b) = a 3 , and forms an equilibrium of the game. Note that Wel a 3 (v) = 1, while Wel a 1 (v) = n − 2. Hence, the price of anarchy tends to zero when n → ∞.
The full analysis appears in Appendix A.1.
Example 2 (Price of stability). There are q ≥ 2 actions a 1 , ..., a q and two outcomes o 1 , o 2 . Action There is one principal with valuation domain V 1 = R 2 ≥q and valuation v 1 = (q, q + γ 1−q ). 10 The price of anarchy is the ratio between the worst equilibrium welfare and the optimal welfare. The price of stability is the ratio between the best equilibrium welfare and the optimal welfare. For details see, e.g., [24,Chapter 17]. 11 We do not know whether 1 2 is tight.
In this example, Wel a i (v) = q + i − (i − 1)(γ + ). Thus, the socially efficient action is a q , while the action that minimizes welfare is a 1 . In Appendix A.2 we show that, when using a first price contract, the agent takes a 1 in all equilibria. The intuitive reason for this is that the principal bids to maximize her own utility rather than social welfare. Hence, the price of stability is . The last term tends to 1 2 when q → ∞. While the starting point of Example 2 is the "gap setting" construction of [10, p. 15], we must modify the construction in a nontrivial way and provide a new analysis (the gap in that construction is between the optimal welfare and revenue, whereas we seek a gap between the optimal welfare and equilibrium welfare).

Definition, Properties and Uniqueness of the IIVCG Family
As our main conceptual contribution, we propose to overcome the inefficiency of first price contracts by introducing the following family of contracts, which we show is (uniquely) truthful and welfaremaximizing.
following two properties hold: 1. Declared welfare maximization. Given contract t, for every bid profile b ∈ V, the agent chooses to maximize the declared social welfare, that is, The first property of IIVCG contracts requires that the agent maximizes the declared social welfare. Therefore, when principals bid truthfully, the agent takes a welfare-maximizing action, and social efficiency is achieved. The second property characterizes the expected payment from each principal to the agent for his action a * (b). The characterization for principal uses h , a function of the bids of the other principals besides , and Wel a * (b) (b − , 0), the part of the welfare from action a * (b) that is due to the other principals. 12 The characterization in Definition 2 determines only the payments in expectation (taken over the random outcome) for a certain action, not the payment rules themselves. We further develop the payment rules in Section 3.3. But Definition 2 suffices to establish truthfulness, and thus welfare maximization, for every IIVCG contract. We also show the other direction, i.e., a sense in which this family of contracts is uniquely truthful and welfare-maximizing. Proposition 1. Every IIVCG contract is truthful.
Proof. Let t be an IIVCG contract. Consider principal and fix the other principals' bids b − . We show that reporting truthfully maximizes principal 's expected utility. The key observation is that by Property 2 of Definition 2 of IIVCG contracts, principal 's expected utility As for the second term, h (b − ) does not depend on principal 's report b . We conclude that the total expected utility is maximized when b = v . Therefore, reporting truthfully is a dominant strategy for principal .
The next corollary follows immediately from Proposition 1 and from Property 1 of IIVCG contracts.
Corollary 1. In every IIVCG contract the agent maximizes social welfare.
We now show a uniqueness result for IIVCG: Whenever the agent maximizes declared welfare, IIVCG contracts are the only contracts that incentivize principals to bid truthfully as a dominant strategy. This result is reminiscent of the well-known result by Holmström [17], establishing uniqueness of VCG auctions for convex domains. 13 In fact, our proof makes use of a lemma from [17], in addition to the convexity of the valuation domains. We give here a sketch of the proof and defer the full proof to Appendix B.1.
Proof sketch. To prove t is IIVCG we must show existence of functions {h } that satisfy Property 2 in Definition 2 of IIVCG contracts. We first define h : V → R, i.e., as a function of the full bid profile. The definition is as follows: To do so, we fix b − and apply a key lemma from [17]. Roughly, this lemma states Thus, according to the key lemma,

A Characterization of the Outcome-Specific Payment Scheme
The definition of IIVCG contracts in the previous section includes a characterization of expected payments for action a * (b). In this section we complete the picture by characterizing the outcome-specific payments for all actions (Lemma 1). The characterization relies on Property 1 of IIVCG contracts -that the agent always maximizes the declared social welfare. Since the agent acts in his own self-interest, the payments must incentivize the agent to choose the welfare-maximizing action. We use this fact to deduce the format of the payments.
The characterization makes use of the following definition. For every action a define Note that the payment format is parameterized by functions {h } and vectors {w }, which must still be specified to get a concrete instance of an IIVCG contract, as we do in Section 3.4. , it follows that x * (b) = a * (b). 14 Thus Property 1 of IIVCG holds. Property 2 can also be verified, by observing that the 14 Recall that the agent tie-breaks in favor of the declared welfare-maximizing action a * (b).

IIVCG Instantiation: Auction-Inspired IIVCG
The payments developed in the previous section (Lemma 1) are parameterized by functions {h } and bid-dependent vectors {w }. In this section we give a first instantiation of the IIVCG family of contracts by specifying these functions and vectors. The instantiation is closely related to the VCG contracts of [22] as well as to VCG auctions, so we refer to the resulting contracts as "Auction- Since the IIVCG family is guaranteed to be truthful (Proposition 1) and welfare-maximizing (Corollary 1), our main concern in what follows is with the properties of IR and LL.
It is not hard to see that in Auction-Inspired IIVCG contracts, the expected payment of principal given bid profile b is her externality on the other principals: the difference between their (declared) expected welfare had she not participated, i.e., Wel a * (b − ,0) (b − , 0), and their (declared) expected welfare with her participation, i.e., Wel a * (b) (0, b ). This is exactly as in VCG auctions with the Clarke pivot rule. Interestingly, we now show that this natural instantiation of IIVCG does not satisfy all our desiderata -while it guarantees IR, it does not necessarily guarantee LL.
In Section 3.5 we show this is no coincidence -there is an inherent tradeoff among IR and LL. Proof Sketch. Consider a common agency setting with a valuation profile such that no principal has a positive externality on the others. Assume the principals are truthful (LL should hold for any bid profile, including truthful ones). As mentioned above, in any Auction-Inspired IIVCG, principal 's expected payment is her externality. The principals' expected payments are therefore all zero. The LL requirement that the agent is never paid a negative amount then means that he cannot be paid a positive amount either. When all payments are zero, the agent will not take any action with nonzero cost, in contradiction to the requirement that the agent maximizes welfare.
A specific setting that illustrates Proposition 2 appears in the next section (proof of Theorem 3).

The LL-IR Tradeoff
As we have seen, a natural IIVCG instantiation (namely Auction-Inspired IIVCG) is IR, but does not guarantee LL. In Section 5 we show a different instantiation that guarantees LL but not IR. We now show that the clash between LL and IR is unavoidable (see Appendix B.3 for the full proof): This implies that Since t also satisfies IR, the principal's expected value E o∼F |a 2 [v 1 (o)] = from her truthful bid is at least her expected payment E o∼F |a 2 [t 1 (v, o)], which by (1) is strictly positive. By Property 2 of 0). Putting everything together we get: Recall that Wel a 2 (v −1 , 0) = − , thus ≥ h 1 (v −1 ) + > 0. However, h 1 (·) is independent of v 1 and so cannot depend on . This is a contradiction.

Remark 4. With two or more principals, Theorem 3 is related to the classic result of Myerson and
Satterthwaite, by which there do not exist socially-efficient and budget-balanced mechanisms [23].
Indeed, the agent in our setting can be viewed as the mechanism designer in the classic result, and the principals in our setting can be viewed as the players. However, the impossibility result of Myerson and Satterthwaite crucially relies on the existence of two players, whereas Theorem 3 applies even to settings with a single principal.

Algorithmic IIVCG
Motivated by the LL-IR tradeoff (Theorem 3), in this section we formulate a necessary and sufficient condition on a common agency setting for the existence of an IIVCG contract that is both LL and IR (Lemma 2). Our characterization is constructive, yielding an IIVCG contract that satisfies both properties whenever such a contract exists. There is a conceptual difference between this contract design and Auction-Inspired IIVCG (presented in Section 3.4) or Weighted IIVCG (presented in Section 5). In the latter classes, the contract mapping t : V × O → R n is expressed using a short mathematical formula. We introduce Algorithmic IIVCG contracts, in which t is algorithm-based: To use contract ALG1, one must determine for a given setting whether there exists an IIVCG contract with both properties. Algorithm 2 leverages our necessary and sufficient condition and provides a procedure to do so. Formally: Theorem 6. Given a common agency setting, Algorithm 2 determines in polynomial time whether there exists an IIVCG contract that is both LL and IR for this setting.
Proof overview. The proofs of both theorems are given in Sections 4.1 and 4.2, respectively. At a high-level they proceed as follows. Given a common agency setting, we present two bounds on principals' payments: is an upper bound on principal 's expected payment in any IIVCG contract t that satisfies IR, i.e., 2. k a * (b) ∀b ∈ V, is a lower bound on the sum of principals' expected payments in any IIVCG contract t that satisfies LL, i.e., k a It follows that if there exists an IIVCG contract that is both LL and IR for the given setting, then Surprisingly, the reverse direction is also true, i.e., if the predicate in Eq. (3) holds, one can construct an IIVCG contract that is both LL and IR (Claim 3 and Algorithm 1). Section 4.2 shows that this predicate can be computed in polynomial time.

Proof of Theorem 5
In this section we explain Algorithm 1 and prove Theorem 5 step by step. As a first step, we provide the following upper bound on principals' payments.
Claim 1. Consider a common agency setting. Define:

An IIVCG-contract t satisfies IR if and only if
Proof. By definition, t satisfies IR if and only if each principal's expected payment when she bids truthfully is at most her expected value. That is, By Property 2 in the definition of IIVCG (Definition 2), the above holds if

both sides of the inequality, we have that t satisfies IR if and
Since the left-hand side is independent of v , the above is equivalent to the following condition (obtained by minimizing the right-hand side over all v ∈ V and dropping the ∀v ∈ V quanti- That is, by Property 2 in the definition of IIVCG, and by the definition of m (b), if and only if Proof. The linear program above is solvable in polynomial time since it consists of O(m) variables: 0 ≤ h ,ṽ ∈ V ⊆ R m ; and polynomially-many constraints: O(q) constraints in addition to the polynomially-many constraints ensuring that v ∈ V (recall that V is a convex, polynomiallydescribed polytope for every ). Note that Wel a j (b − ,ṽ ) = F |a j · (b − +ṽ ) − ψ(a j ). Thus, the jth constraint ensures that the welfare from action a j given (b − ,ṽ ) is at most h . Altogether we have that the optimal welfare Wel a * (b − ,ṽ ) (b − ,ṽ ) ≤ h at the feasible region. Minimizing h over allṽ ∈ V gives the first term in m (b). To complete m (b)'s computation, subtract Claim 2. Consider a common agency setting. Define: Proof. By linearity of expectation it suffices to show that ( ∈[n] t (b, o)) o∈O ∈ L a * (b) ∀b ∈ V. By definition of L a * (b) , we need to show that: Proof Proof. For the forward direction, suppose that there exists an IIVCG-contract t that satisfies both LL and IR. By claims 2, 1, we conclude that The backwards direction is constructive and relies on the following claim.
Claim 3. If a setting satisfies k a * (b) ≤ ∈[n] m (b) ∀b ∈ V, an IIVCG contract that satisfies LL and IR may be constructed by using Lemma 1, and and choose w 1 , ..., w n as follows: Proof of Claim 3. We first show that this contract is in IIVCG, by proving that Lemma 1 can be applied. Note that ∈[n] w = w b ∈ L a * (b) ∀b ∈ V, and that h is indeed independent of b . Thus, the constructed contract is an IIVCG contract. To show LL, we must show that to both sides of the inequality, we have that the above which holds by construction. IR follows from Claim 1, the choice of h (b − ), and IIVCG expected payment formula: Observation 3. The following linear program computes x from Claim 3 (2) in polynomial time. Remark 7. One may consider relaxing the LL constraint, by requiring that only the aggregate payment from all principals to the agent is non-negative. The proof of Claim 2 shows that requiring the payments from each individual principal to the agent to be non-negative is without loss of generality.

Proof of Theorem 6
In this section we prove Theorem 6, providing a method for determining when there exists an IIVCG contract that is both LL and IR. According to the characterization in Lemma 2, there exists such A key observation is that in order to test this predicate, it suffices to test only O(q) bid profiles as follows (where q is the number of actions).
Observation 4 follows directly from the definition of V a , and will be used in the proof of Theorem 6.
Proof. This linear program is similar to LP1, which computes the first term in m (b), and is referred to as h . We use the same set of constraints for each principal to ensure that Wel For each action a, line 2 uses LP4 to find arg min b∈Va ∈[n] m (b). Then, using Algorithm 1, we test if k a ≤ ∈[n] m (b). Thus, Algorithm 2 computes k a ≤ min b∈Va ∈[n] m (b) ∀a and determines whether a "good" IIVCG contract exists. Remark 8. When the principals have no private information (i.e., their types are fixed and publicly known so V i is a singleton), there are always contracts in IIVCG that satisfy LL and IR. I.e., our Algorithm 2 will return "Possible" and our Algorithm 1 will find the best such contract for the principals. As a concrete example, one LL and IR IIVCG contract is as follows. Take h = Wel a * (v) (v), and w = v in Lemma 1 of the IIVCG characterization. One can verify that a principal's payments in this contract are exactly her values. LL holds since the principal's values are non-negative, and IR holds since the principal's utility is zero. We mention that this contract favors the agent's utility over that of the principals'. At the other extreme, one can use Algorithmic IIVCG. Our LP approach to this class assures that the minimum payment required to incentivize the agent is charged from the principals, thus favoring their utility over the agent's.

IIVCG Instantiation: Weighted IIVCG Contracts
In this section we introduce a class within IIVCG which guarantees LL but not necessarily IR, and give a condition on common agency settings ("G-correlation") that suffices for the existence of IR as well. The high-level idea is as follows. By Proposition 2, in order to satisfy LL, principals' expected payment should be more than their externality on others. While increasing principals' payments may damage IR, a type of contract which we term Weighted IIVCG succeeds in providing IR for a wide family of common agency settings. The central idea is to approximate each principal's valuation according to other principals using the concept of a correlation graph, and use this to set the payments. Correlation graphs and G-correlated settings are defined in Section 5.1, and in Section 5.2 we use these to define Weighted IIVCG. We introduce the following "running example" for this section to demonstrate our definitions. Figure 1 depicts a correlation graph of the setting in the following example.

Correlation Graphs and G-Correlated Settings
In words, the G-weighted valuation of principal is a weighted average on other principals valuations, when their valuations are shifted downwards. We will demonstrate this for Example 3 and the correlation graph G in Figure 1: The G-weighted valuation of principal 1 isv 1

Definition 7. Given a correlation graph G, a setting is
That is, a setting is G-correlated if the welfare when principal 's valuation is replaced with her G-weighted valuation, is bounded by the actual welfare (for every valuation profile). We demonstrate this condition for the setting and the valuation profile in Example 3, and the correlation graph in Figure 1. Recall thatv 1 G = (0, 2.1). It can thus be verified that Wel a 1 (v) = 33, Wel a 2 (v) = 35.75 and that Wel a 1 (v − ,v G ) = 22, Wel a 2 (v − ,v G ) = 24.825. Thus, the welfare when principal 's valuation is replaced with her G-weighted valuation is bounded by the actual welfare (for v).
Examples of G-correlated settings. The following claims describe natural special cases for G-correlated settings.
Claim 5. Consider a common agency setting. If principals share the same expected value for each action, there exists a correlation graph G for which the setting is G-correlated. 16 Proof. Take G as any graph on [n] vertices that has a weighted in-degree and out-degree of 1 for all vertices. 17 Consider a valuation profile v and a principal . To satisfy the condi- . By the definition ofv and ofv k , ∀a as desired. This completes the proof. We mention that in this case, first price contracts may fail.
Proof. The proof proceeds as in Claim 5, but requires a different argument for proving that ∀a. This completes the proof.

G-Weighted IIVCG Contracts
We can now use the concepts introduced in the previous section to define Weighted IIVCG contracts and analyze their properties. 16 While this is natural, one can show that first price contracts do well in this case: Since principals have the same expected value for each action, and principals' domains are independent, the welfare of each action is fixed. Thus, the welfare maximizing action is unified for all valuation profiles (and bid profiles). In first price contracts, the agent maximizes declared welfare. Thus the socially efficient action is always chosen by the agent. 17 As two simple examples for such graphs, consider the graph defined by d( , + 1) = 1 ∀ ∈ [n], where + 1 is calculated modulo n, and the graph is defined by d( , k) = 1 n−1 ∀ , k ∈ [n].
Definition 8. Consider a correlation graph G. A G-Weighted IIVCG Contract is given by Proposition 5. Consider a correlation graph G. Every G-Weighted IIVCG contract is in IIVCG.
Proof. The proof relies on Lemma 1 when prove that the conditions of Lemma 1 are met. First, h is independent of b , sinceb G is independent ). Second, we show that ∈[n] w ∈ L a * (b) . To do so, we establish that ∈[n] w = ∈[n]b using the following chain of equalities: Equality (1) follows from the choice of w s above, and the definition ofb G (Definition 6). Equality (2) changes the order of summands, and Equality (3) this condition is equivalent to Definition 7 of the G-correlated setting. This completes the proof. In this section we prove that in Example 1, action a 3 and the bid profile b 1 = (0, 0, 1+γ), b 2 = (0, 1+ , 0) and b = (0, 0, 0) ∀ > 2 constitute an equilibrium. To do so, we show that the agent maximizes his utility, and that each principal cannot benefit from deviating and switching her bid. Note that Wel a 3 (v) = 1, while the action which maximizes social welfare is a 1 with Wel a 1 (v) = n − 2 > 1.
For the agent, the payoff from taking action a 3 or action a 2 is 1, while the payoff from action a 1 is 0. Recall that the tie-breaking rule is in favor of the declared welfare and then the cost (see footnote 7). Since a 2 and a 3 have the same declared welfare the agent takes action a 3 which incurs more cost. Therefore, x * (b) = a 3 . Principal 1 cannot raise her utility by changing the bid for o 3 . If she raises her bid, the agent still takes a 3 and her utility will strictly decrease since she pays more to the agent. If principal 1 lowers her bid, then the agent takes a 2 , and principal 1's utility will not vary. Principal 2 cannot raise her utility by changing the bid for o 2 . If she raises her bid, the agent takes a 2 and her utility will strictly decrease since she pays more then her value to the agent. If principal 2 lowers her bid, then the agent still takes a 3 , and principal 2's utility does not vary. As In this section we prove that in Example 2, the agent takes a 1 in all equilibria. The proof relies on the following Claim. Claim 7. Consider Example 2. For every bid profile that incentivizes the agent to take a i for i > 1, the principal's expected utility is at most 1 − /(1 − γ).
Observe that the smallest possible bid profile b 1 = (q, q) incentivizes the agent to take action a 1 .
Also, the principal's expected utility given b 1 is 1 > 1 − /(1 − γ). Thus, there is no equilibrium where the agent takes a i for i > 1.
Proof of Claim 7. Let b 1 be a bid profile that incentivizes a i for i > 1. It must hold that Since b 1 (o 1 ) must be at least q, it follows from the last inequality that 1) ). Using this, the following chain of inequalities shows that the principal's expected utility is at most 1 − /(1 − γ): A.3 Existence of IIVCG for Examples 1 and 2 Proposition 6. There exists an IIVCG contract for the setting in Example 1.

Proposition 7.
There exists an IIVCG contract for the setting in Example 2.
To prove this, we first state the following claims.
Proof of Proposition 7. As shown in Section 4.1, the setting is applicable if k a * (b) ≤ m 1 (b) ∀b ∈ V.
Equivalently, according to Claims 8 and 9, the setting is applicable if , since the left-hand side is at most (q − 1)(1 − γ − ) + 1 which, in turn, is at most q.
This completes the proof.
Proof of Claim 8. Recall that k a j = min w∈La E o∼F |a j [w(o)]. We show that one w which minimizes First, we prove that w ∈ L a j . To do so, we must show that . Replacing w and ψ, the last inequality holds if Reorganizing both sides, this is equal to Which, by subtracting γ 1−j − γ 1−j from both sides, holds if Observe the left-hand side in (4), by dividing the first term by γ q−j and multiplying the second The following case analysis shows the above inequality holds: 1. For j − j = 0,j − j = 1, this is immediate.
3. For 0 > j−j , (5) holds since 1−γ j −j = −( 1 where the first inequality follows from the fact that γ ≤ 1 q ≤ 1 2 . We have shown that w ∈ L a j . It is now left to show that w minimizes E o∼F |a j [w(o)]. Observe that for every w ∈ L a , it must hold that By reorganizing both sides, the last inequality equals to γ q−j (1 − γ)(w 2 − w 1 ) ≥ (γ 1−j − 1)(1 − γ) + . Dividing both sides by γ q−j (1 − γ), and since ). Since w meets these lower bounds, . This completes the proof.
Proof of Claim 9. Recall that m Since for every v 1 =ṽ 1 ∈ V 1 it holds thatṽ 1 ≤ v 1 (element wise). Thus, . This completes the proof.
To complete the picture, one IIVCG contract for Example 2 may be contracted using h 1 (b −1 ) = q That is,

This contract satisfies limited liability because
This contract also satisfies individual rationality since for a j = a * (v), it must hold that The inequality is immediate for j = 1, since ψ(a j ) = 0 and v ∈ V = R 2 ≥q . Suppose towards a contradiction that it does not hold for j > 1, then Wel ∀b ∈ V and fix an arbitrary b − ∈ V − . To show that t is an IIVCG contract, it suffices to show that h (b − , ·) is constant on b . We make the following observations: First, bidding truthfully is socially efficient, i.e., v ∈ arg max b ∈V Second, since principal is truthful, v ∈ arg max b ∈V E o∼F |a * After establishing (6) and (7) According to (10) and (11) g (b, o). With these notations, for every principal and every bid profile b, By IIVCG Definition, there exist {h } such that where h does not depend on b . Equalizing (12), (13) Since, ∈[n] w ∈ L a * (b) , a * (b) ∈ arg max a∈A E o∼F | [ ∈[n] w (o)] − ψ(a). Thus, and according to (15) we conclude that a * (b) maximizes the agent's utility. Furthermore, Property 2 in the definition of IIVCG (Definition 2) is also met. since principal 's expected payment is E o∼F |a * Wel a * (b) (b , 0) as desired. 18 If h (b − ) depends on the realised outcome, then it would also depend on principal 's bid (since 's bid influences the realised outcome indirectly by influencing the chosen action).

B.3 A Trade-off between LL and IR: Proof of Theorem 3
Here, we formally prove Theorem 3.
Proof of Theorem 3. Consider the common agency setting in Example 4 and the valuation profile v 1 = (3 , 0). Note that Wel a 1 (v) = 1.5 , and Wel a 2 (v) = 2 . Thus, the socially efficient action is a 2 . Suppose toward a contradiction that there exists an IIVCG contract t that satisfies LL and IR. Since t is an IIVCG contract, in a dominant strategy equilibrium the principal is truthful, and the agent takes the socially efficient action, i.e., a 2 . Since the agent maximizes the sum of payments minus cost, it must hold that By the assumption that t satisfies LL, t 1 (b, o 2 ) ≥ 0, so, t 1 (b, o 1 ) ≥ 2 .
That is, Since Wel a 2 (b −1 , 0) = − , we conclude that h 1 (b −1 ) ≥ . Now, consider the following valuation profile:ṽ 1 = (0, 0). Again, in a dominant strategy equilibrium the principal is truthfulb =ṽ and the agent takes the socially efficient action, which is now a 1 . By definition of IIVCG, h 1 is independent of b 1 . Thus, This is a contradiction to the fact that t satisfies IR.