Crowd innovation is an emerging technology where innovation is sourced out to the public through an open call. At the center of crowd innovation is a resource allocation problem: there is an abundance of workers but a scarcity of high skills, and an easy task assigned to a skilled worker is a waste of resources. This problem is complicated by the fact that the exact difficulties of innovation tasks may not be known in advance, so tasks that require high-skill labor cannot be identified and allocated ahead of time. More problematically, worker skills in a crowd environment are their own private information, and they may have an incentive to misrepresent that information. Taken together, these aspects imply that the firm has to solve the challenging problem of how to assign tasks to workers even though it knows neither the difficulties of the tasks nor the skills of the workers. We first relax the constraint that the firm does not know the skills of the workers (and that workers participate voluntarily) and examine the resulting assignment problem. We show that the solution to this problem takes the form of a skill hierarchy, where tasks are first attempted by low-skill labor, and high-skill workers only engage with a task if less skilled workers are unable to finish it. We derive this structure of the optimal matching by studying a dynamic programming formulation. The most distinctive property of the optimal matching is that it ensures that the heterogeneous skills of the available workers are efficiently utilized.

We study the simultaneous evolution of the opinion profile and network topology of a system of N agents. Based on the opinion profile at any given time, agents probabilistically decide which other agents to form links with. The probability of a link being formed with another agent depends on both similarity of their opinions and the popularity of that agent. Agents then average their opinion with the opinions of the agents they have formed links with, giving rise to a new opinion profile that determines-in a probabilistic fashion- the network topology for the next time step. Thus both opinions and network structure exhibit a strong correlation over time. Despite this correlation, we show that this system converges to a consensus in opinion. We provide simulations of convergence times and the limiting opinion profile as a function of the parameters of the system.

In this paper, we are interested in modeling diffusion of innovations on social networks. We focus on a scenario where innovation emerges at a small number of nodes in the society, and each individual needs certain portion of his neighbors (thresholds) to adopt the innovation before he does so. We analyze the dynamics of the diffusion process under deterministic topologies and threshold values. We show that the diffusion process depends on both the topology and threshold values through so called coherent sets. We investigate several interesting topologies, and utilize coherent set argument to determine the behavior of the process on these topologies.

We study revenue-maximizing pricing by a service provider in a communication network and compare revenues from simple pricing rules to the maximum revenues that are feasible. In particular, we focus on flat entry fees as the simplest pricing rule. We provide a lower bound for the ratio between the revenue from this pricing rule and maximum revenue, which we refer to as the Price of Simplicity. We characterize what types of environments lead to a low Price of Simplicity and show that in a range of environments, the loss of revenue from using simple entry fees is small. We then study the Price of Simplicity for a simple non-linear pricing (price discrimination) scheme based on the Paris Metro Pricing. The service provider creates different service classes and charges differential entry fees for these classes. We show that the gain from this type of price discrimination is small, particularly in environments in which the simple entry fee pricing leads to a low Price of Simplicity.

Most large-scale communication networks, such as the Internet, consist of interconnected administrative domains. While source (or selfish) routing, where transmission follows the least cost path for each source, is reasonable across domains, service providers typically engage in traffic engineering to improve operating performance within their own network. Motivated by this observation, we develop and analyze a model of partially optimal routing, where optimal routing within subnetworks is overlaid with selfish routing across domains. We demonstrate that optimal routing within a subnetwork does not necessarily improve the performance of the overall network. In particular, when Braess' paradox occurs in the network, partially optimal routing may lead to worse overall network performance. We provide bounds on the worst-case loss of efficiency that can occur due to partially optimal routing. For example, when all congestion costs can be represented by affine latency functions and all administrative domains have a single entry and exit point, the worst-case loss of efficiency is no worse than 25% relative to the optimal solution. In the presence of administrative domains incorporating multiple entry and/or exit points, however, the performance of partially optimal routing can be arbitrarily inefficient even with linear latencies. We also provide conditions for traffic engineering to be individually optimal for service providers.

We study the efficiency implications of competition among profit-maximizing service providers in communication networks. Service providers set prices for transmission of flows through their (sub)network. The central question is whether the presence of prices will help or hinder network performance. We investigate this question by considering the difference between users' willingness to pay and delay costs as the efficiency metric. Previous work has demonstrated that in networks consisting of parallel links, efficiency losses from competition are bounded. Nevertheless, parallel-link networks are special, and in most networks, traffic has to simultaneously traverse links (or subnetworks) operated by independent service providers. The simplest network topology allowing this feature is the parallel-serial structure, which we study in this paper. In contrast to existing results, we show that in the presence of serial links, the efficiency loss relative to the social optimum can be arbitrarily large. The reason for this degradation of performance is the double marginalization problem, whereby each serial provider charges high prices not taking into account the effect of this strategy on the profits of other providers along the same path. Nevertheless, when there are no delay costs without transmission (i.e., latencies at zero are equal to zero), irrespective of the number of serial and parallel providers, the efficiency of strong oligopoly equilibria can be bounded by 1/2, where strong oligopoly equilibria are equilibria in which each provider plays a strict best response and all of the traffic is transmitted. However, even with strong oligopoly equilibria, inefficiency can be arbitrarily large when the assumption of no delay costs without transmission is relaxed.

Abstract — We study the efficiency properties of oligopoly equilibria in congested networks. Our measure of efficiency is the difference between users ’ willingness to pay and delay costs. Previous work has demonstrated that in networks consisting of parallel links, efficiency losses from competition are bounded. In contrast, in this paper we show that in the presence of serial links, the efficiency loss relative to the social optimum can be arbitrarily large because of the double marginalization problem, whereby each serial provider charges high prices not taking into account the effect of this strategy on the profits of other providers along the same path. Nevertheless, when there are no delay costs without transmission (i.e., latencies at zero are equal to zero), irrespective of the number of serial and parallel providers, the efficiency of strong oligopoly equilibria can be bounded by 1/2, where strong oligopoly equilibria are equilibria in which each provider plays a strict best response and all of the traffic is transmitted. However, even with strong oligopoly equilibria, inefficiency can be arbitrarily large when the assumption of no delay costs without transmission is relaxed. I.

We study the flow control and routing decisions of self-interested users in a general congested network where a single profit-maximizing service provider sets prices for different paths in the network. We define an equilibrium of the user choices. We then define the monopoly equilibrium (ME) as the equilibrium prices set by the service provider and the corresponding user equilibrium. We analyze the networks containing different types of user utilities: elastic or inelastic. For a network containing inelastic user utilities, we show the flow allocations at the ME and the social optimum are the same. For a network containing elastic user utilities, we explicitly characterize the ME and study its performance relative to the user equilibrium at 0 prices and the social optimum that would result from centrally maximizing the aggregate system utility. We also define Braess' Paradox for a network involving pricing and show that Braess' Paradox does not occur under monopoly prices.