The stability and efficiency of directed communication networks

Abstract. This paper analyzes the formation of directed networks where self-interested individuals choose with whom they communicate. The focus of the paper is on whether the incentives of individuals to add or sever links will lead them to form networks that are efficient from a societal viewpoint. It is shown that for some contexts, to reconcile efficiency with individual incentives, benefits must either be redistributed in ways depending on “outsiders” who do not contribute to the productive value of the network, or in ways that violate equity (i.e., anonymity). It is also shown that there are interesting contexts for which it is possible to ensure that efficient networks are individually stable via (re)distributions that are balanced across components of the network, anonymous, and independent of the connections of non-contributing outsiders.     

Stable and efficient bargaining networks

Abstract. We examine a bargaining game among players connected by a network, where successively potential partners negotiate over terms of a project. For any network structure and ordering of selection of bargaining partners, there is a unique subgame perfect equilibrium outcome which coincides with the standard Rubinstein split. Based on this, we derive expected payoffs for players as a function of the network. We the characterize the pairwise stable and efficient bargaining networks. These two sets do not always coincide and in many situations pairwise stable networks are over-connected. Received: 10 April 2001 / Accepted: 17 January 2002 I am indebted to Matthew Jackson for suggesting this paper. I also thank Bernard Caillaud, Sanjeev Goyal, and the seminar participants at Universidad de Alicante, Universidad Carlos III de Madrid, CEMFI (Madrid), Universitat Autònoma de Barcelona, Erasmus University of Rotterdam, Universitat Pompeu Fabra (Barcelona) and CERAS (Paris) for helpful comments. This paper was written while at Universitat Pompeu Fabra and CERAS. Financial support from the Spanish Ministry of Education through research grant DGESIC PB96-0302, and from the Ecole Nationale des Ponts et Chaussées, Paris is gratefully acknowledged. All errors are of course mine.     

Coalitional manipulations in a bankruptcy problem

In a bankruptcy problem framework we consider rules immune to possible manipulations by the creditors involved in the problem via merging or splitting of their individual claims. The paper provides characterization theorems for the non manipulable rules, the no advantageous merging parametric rules and the no advantageous splitting parametric rules. Received: 24 February 1998 / accepted: 9 March 1999     

A social choice function implementable via backward induction with values in the ultimate uncovered set

We prove the existence of a social choice function implementable via backward induction which always selects within the ultimate uncovered set. Whereas the uncovered set is the set of maximal elements of the covering relation, the ultimate uncovered set is the set obtained by iterative application of this covering operation. Dutta and Sen (1993) showed that any social choice function which is the solution of a generalized binary voting procedure is implementable via backward induction. Our result follows from Dutta and Sen's theorem, in that we construct a binary voting procedure always selecting within the ultimate uncovered set. We use the classical multistage elimination procedure, which always selects an alternative within the uncovered set. When this procedure is also used to select among all of the possible agendas or orderings of alternatives within the procedure, the alternative selected (from the agenda selected) will be within the uncovered set of the uncovered set. Our result follows from repeated application of this construction. Intuitively, the procedure constructed consists of requiring agents to vote on how they should vote and so on. Received: 7 April 1997 / Accepted: 15 October 1998     

On efficient trading mechanisms between one seller and n buyers

Myerson and Satterthwaite (1983) prove that if one seller and one buyer have independent private valuations for an indivisible object then no individually rational and incentive compatible trading mechanism can guarantee ex post efficiency when gains from trade are uncertain. Makowski and Mezzetti (1993) show that this is not the case when there are at least two buyers. In the latter context, if the highest possible seller's valuation is not too large, we provide an ex post efficient mechanism in which the mechanism designer and the agents are not required to know the probability distribution for the seller's valuation. Received: February 18, 1998 / Accepted: September 10, 1999     

Are serial Condorcet rules strategy-proof?

Abstract. This paper explores the extent to which majority rule is invulnerable to manipulation by individuals and coalitions, even when majority rule is used to select more than one alternative. The resulting rule may or may not be strategy-proof, depending on the size of the coalitions that can form, and on the nature of the individual preferences over sets of alternatives. No individual can manipulate with respect to a wide family of preferences over sets. The only restriction on the domain of true and revealed individual preferences is that the selection rule is always well defined. Received: 1 November 1999 / Accepted: 7 May 2001 We thank two anonymous referees for suggestions that have significantly improved the paper. We are also grateful to l'Université de Caen for sponsoring a Workshop on Social Choice Theory, where a first draft of this paper was presented in May, 1999, and to the workshop participants for helpful observations. Work on the final version of the paper was done while one of the authors was a guest of the Project on Intergenerational Equity supported by the Ministry of Education, Science, and Technology of Japan. We are grateful to the Ministry and to the project leader, Professor Kotaro Suzumura, for their support.     

Hierarchies and information-processing organizations

This paper analyzes organizational structures that minimize information processing costs for a specific organizational task. Organizations consist of agents of limited ability connected in a network. These agents collect and process information, and make decisions. Organizations implement strategies – mappings from environmental circumstances to decisions. The strategies are exogenously given from a class of “pie” problems to be defined in this paper. The notion of efficiency is lexicographic: the primary criterion is minimizing the number of agents, and the secondary criterion is minimizing the number of connections between the agents. In this modeling framework, efficient organizations are not hierarchical for a large number of problems. Hierarchies often fail to exploit fully the information processing capabilities of the agents because in a hierarchy, subordinates have a single superior. Received: 1 December 1995 / Accepted: 11 October 1998     

Stable matchings and the small core in Nash equilibrium in the college admissions problem

Both rematching proof and strong equilibrium outcomes are stable with respect to the true preferences in the marriage problem. We show that not all rematching proof or strong equilibrium outcomes are stable in the college admissions problem. But we show that both rematching proof and strong equilibrium outcomes in truncations at the match point are all stable in the college admissions problem. Further, all true stable matchings can be achieved in both rematching proof and strong equilibrium in truncations at the match point. We show that any Nash equilibrium in truncations admits one and only one matching, stable or not. Therefore, the core at a Nash equilibrium in truncations must be small. But examples exist such that the set of stable matchings with respect to a Nash equilibrium may contain more than one matching. Nevertheless, each Nash equilibrium can only admit at most one true stable matching. If, indeed, there is a true stable matching at a Nash equilibrium, then the only possible equilibrium outcome will be the true stable matching, no matter how different are players' equilibrium strategies from the true preferences and how many other unstable matchings are there at that Nash equilibrium. Thus, we show that a necessary and sufficient condition for the stable matching rule to be implemented in a subset of Nash equilibria by the direct revelation game induced by a stable mechanism is that every Nash equilibrium profile in that subset admits one and only one true stable matching. Received: 30 December 1998 / Accepted: 12 October 2001 This paper is a revision of the paper “Manipulation and Stability in a College Admissions Problem” circulated since 1994. I thank Rich McLean, Abraham Neyman, Mark Satterthwaite, Sang-Chul Suh, and Tetsuji Yamada for helpful discussions. I thank the associate editor and the two anonymous referees for their helpful comments that have greatly improved the paper. I am grateful to the Kellogg G.S.M. at the Northwestern University for the hospitality for my visit. Any errors are mine.     

Single-peakedness and coalition-proofness

We prove that multidimensional generalized median voter schemes are coalition-proof. Received: 16 July 1998 / Accepted 23 March 1999     

Multiprincipals multiagents incentive design

This paper studies a simple setting in which the contractual arrangements which determine the incentives for agents are not designed by a single central planner, but are themselves the outcome of a game among multiple noncooperatively acting principals. The notion of an Epsilon Contracting Equilibrium is introduced to predict the outcome of the contract-design game among principals. Symmetric pure strategy Epsilon Contracting Equlibria may not exist in perfectly symmetric environments. In a symmetric Epsilon Contracting Equilibrium in mixed strategies coordination failure may lead to a suboptimal institutional network in which the agents “cheat” their principals. Received: 14 June 1995 / Accepted: 09 August 1999     

Buyers' and sellers' cartels on markets with indivisible goods

This paper analyzes the formation of cartels of buyers and sellers in a simple model of trade inspired by Rubinstein and Wolinsky's (1990) bargaining model. When cartels are formed only on one side of the market, there is at most one stable cartel size. When cartels are formed sequentially on the two sides of the market, there is also at most one stable cartel configuration. Under bilateral collusion, buyers and sellers form cartels of equal sizes, and the cartels formed are smaller than under unilateral collusion. Both the buyers' and sellers' cartels choose to exclude only one trader from the market. This result suggests that there are limits to bilateral collusion, and that the threat of collusion on one side of the market does not lead to increased collusion on the other side.     

Implementation of optimal contracts under adverse selection

This paper studies a 2-agent, 2-type principal-multiagent model of adverse selection under the assumption that the agents each have complete information. We construct a mechanism implementing the first-best contracts in Nash equilibrium that: satisfies a condition related to individual rationality, is renegotiation-proof, has a small-sized message space, achieves unique implementation and satisfies undomination of Nash equilibrium strategies. Moreover, we prove that other requirements which relate to individual rationality (different from the one satisfied by our mechanism) are not compatible with implementation of the first-best contracts. Received: 27 July 1998 / Accepted: 26 May 2000     

Altruism, redistribution and social insurance

The paper examines the influence of altruism on voluntary transfers and government redistribution in a simple model: two jobs of different productivity are assigned by chance to two individuals. Ex ante the individuals are identical, ex post they have different incomes. The first part of the paper examines voluntary transfers determined ex post or agreed upon ex ante in the absence of altruism. In the second part, the influence of altruism is examined. Altruism is modelled as a pure public good: the minimum consumption (or income, since there is only one consumption good). Both individuals can contribute to its provision, one person by earning wage income, the other by voluntary transfers. The ex ante solutions generally lead to higher expected welfare but create several incentive problems. Only lump-sum transfers are considered. Received: 28 February 1997 / Accepted: 31 January 2000     

Identification of peer effects through social networks

We provide new results regarding the identification of peer effects. We consider an extended version of the linear-in-means model where interactions are structured through a social network. We assume that correlated unobservables are either absent, or treated as network fixed effects. We provide easy-to-check necessary and sufficient conditions for identification. We show that endogenous and exogenous effects are generally identified under network interaction, although identification may fail for some particular structures. We use data from the Add Health survey to provide an empirical application of our results on the consumption of recreational services (e.g., participation in artistic, sports and social activities) by secondary school students. Monte Carlo simulations calibrated on this application provide an analysis of the effects of some crucial characteristics of a network (i.e., density, intransitivity) on the estimates of peer effects. Our approach generalizes a number of previous results due to Manski [Manski, C., 1993. Identification of endogenous social effects: The reflection problem. Review of Economic Studies 60 (3), 531–542], Moffitt [Moffitt, R., 2001. Policy interventions low-level equilibria, and social interactions. In: Durlauf, Steven, Young, Peyton (Eds.), Social Dynamics. MIT Press] and Lee [Lee, L.F., 2007. Identification and estimation of econometric models with group interactions, contextual factors and fixed effects. Journal of Econometrics 140 (2), 333–374].     

The scheduling and organization of periodic associative computation: Efficient networks

This paper characterizes the efficient decentralized networks for calculating the associative aggregate of cohorts of data of a fixed size that arrive periodically. Radner (1993) proposed this problem of periodic parallel associative computation as a model of the ongoing information processing and communication by the administrative staff of a large organization. For a simpler model in which the organization processes a single cohort of data – which is equivalent to the periodic model when the agents are paid only when busy – he found that the efficient networks are hierarchical but quite irregular, even though the computation problem and technology are each symmetric. In the periodic model in which managers are paid even when idle, it becomes important to minimize idle time when scheduling managers to processing tasks. Such scheduling appears more difficult when each problem is processed by an irregular hierarchy, which suggest that hierarchies might be more regular in the periodic model. However, we show that in a class of efficient networks for periodic computation that spans the efficiency frontier, the processing of each cohort is similar to the efficient processing of a single cohort, and the overall organizational structure is not even hierarchical. Received: 15 October 1994 / Accepted: 6 March 1997     

The scheduling and organization of periodic associative computation: Essential networks

This paper defines and characterizes essential decentralized networks for calculating the associative aggregate of one or more cohorts of data. A network is essential if it is not possible to eliminate an instruction or manager and still calulate the aggregate of each cohort. We show that for essential networks, the graphs that depict the operations and data dependencies are trees or forests. These results assist in the characterization of efficient networks. Received: 15 October 1994 / Accepted: 6 March 1997     

The not-so-secret-agent: Professional monitors,hierarchies and implementation

Abstract. It is well-known that, when agents in an organization possess private information that is unverifiable by an outside party, games where agents simply announce their information can have multiple equilibria that may impede the successful implementation of the organization's objectives. We show that the introduction of a professional monitor (e.g. auditor, regulator, supervisor) can help to destroy the “bad' equilibria when agents have private information but have incomplete info rmation about others' information. Received: 21 May 1998 / Accepted: 26 May 2000     

Proportionally adjusted marginal pricing method to share joint costs

We consider the cost sharing problem with divisible demands of heterogeneous goods. We propose a cost sharing method called Proportionally Adjusted Marginal Pricing (PAMP) method. PAMP is a nonadditive (in the cost function) extension of average cost pricing. We introduce an axiom called Local Independence (LI) and use LI together with Continuity, Proportionality, and Scale Invariance to characterize PAMP. Received: 23 March 2001 / Accepted: 16 November 2001 I thank Yves Sprumont, Hervé Moulin, and Ahmet Alkan for discussions, comments and suggestions. Thanks also go to the associate editor and the referees, whose comments and suggestions greatly improve the paper.     

Achieving the first best in sequencing problems

Abstract. In a sequencing problem with linear time cost, Suijs (1996) proved that it is possible to achieve first best. By first best we mean that one can find mechanisms that satisfy efficiency of decision, dominant strategy incentive compatibility and budget balancedness. In this paper we show that among a more general and natural class of sequencing problems, sequencing problems with linear cost is the only class for which first best can be achieved. Received: 2 December 1999/Accepted: 9 May 2001     

Strategyproof multiple assignment using quotas

The allocation of heterogeneous and indivisible objects is considered where there is no medium of exchange. We characterize the set of strategyproof, nonbossy, Pareto-optimal, and neutral social choice functions when preferences are monotonic and quantity-monotonic. The characterized sets of social choice functions are sequential; agents are assigned their favorite objects among the objects not given to others before them, subject to a quota. Received: 5 January 1999 / Accepted: 14 June 1999