We consider the design of prediction market mechanisms known as automated market makers. We show that we can design these mechanisms via the mold of exponential family distributions, a popular and well-studied probability distribution template used in statistics. We give a full development of this relationship and explore a range of benefits. We draw connections between the information aggregation of market prices and the belief aggregation of learning agents that rely on exponential family distributions. We develop a natural analysis of the market behavior as well as the price equilibrium under the assumption that the traders exhibit risk aversion according to exponential utility. We also consider similar aspects under alternative models, such as budget-constrained traders.

We study information revelation in scoring rule and prediction market mechanisms in settings in which traders have conflicting incentives due to opportunities to profit from the market operator's subsequent actions. In our canonical model, an agent Alice is offered an incentive-compatible scoring rule to reveal her beliefs about a future event, but can also profit from misleading another trader Bob about her information and then making money off Bob's error in a subsequent market. We show that, in any weak Perfect Bayesian Equilibrium of this sequence of two markets, Alice and Bob earn payoffs that are consistent with a minimax strategy of a related game. We can then characterize the equilibria in terms of an information channel: the outcome of the first scoring rule is as if Alice had only observed a noisy version of her initial signal, with the degree of noise indicating the adverse effect of the second market on the first. We provide a partial constructive characterization of when this channel will be noiseless. We show that our results on the canonical model yield insights into other settings of information extraction with conflicting incentives.

We conduct laboratory experiments on variants of market scoring rules prediction markets, under different information distribution patterns, in order to evaluate the efficiency and speed of information aggregation, as well as test recent theoretical results on manipulative behavior by traders. We find that markets structured to have a fixed sequence of trades exhibit greater accuracy of information aggregation than the typical form that has unstructured trades. Prior theoretical predictions of differing strategic behavior under complementary information distributions and substitute information distributions are confirmed when the trading order is structured, but not in markets with an unstructured trading order. In the case of the market with a structured order, we find that the information aggregation is consequently slower when information is complementary, as traders more frequently engage in bluffing and delaying strategies. In comparing two commonly used mechanisms, we find no significant difference between the performance of the direct probability-report form and the indirect security-trading form of the market scoring rule.

The border gateway protocol (BGP) handles the task of establishing routes between the autonomous systems (ASes) that make up the Internet. It is known that it is possible for a group of ASes to define local BGP policies that lead to global BGP protocol oscillations. We close a long standing open question by showing that, for any network, if two stable routing outcomes exist then persistent BGP route oscillations are possible. This is the first non-trivial necessary condition for BGP safety. It shows that BGP safety must always come at the price of severe restrictions on ASes' expressiveness in their choice of routing policies. The technical tools used in our proof may be helpful in the detection of potential route oscillations and their debugging. We also address the question of how long it takes BGP to converge to a stable routing outcome. We analyze a formal measure of the convergence time of BGP for the policy class defined by Gao and Rexford, which is said to accurately depict the business structure underlying the Internet. We prove that, even for this restricted class of preferences, the convergence time might be linear in the size of the network. However, we show a much more reasonable bound if the network structure is similar to the current Internet: we prove that the number of phases required for convergence is bounded by approximately twice the depth of the customer-provider hierarchy.

We study protocols to enable one user (the principal) to make potentially profitable but risky interactions with another user (the agent), in the absence of direct trust between the two parties. In such situations, it is possible to enable the interaction indirectly through a chain of credit or "trust" links. We introduce a model that provides insight into many disparate applications, including open currency systems, network trust aggregation systems, and manipulation-resistant recommender systems. Each party maintains a trust account for each other party. When a principal's trust balance for an agent is high enough to cover potential losses from a bad interaction, direct trust is sufficient to enable the interaction. Allowing indirect trust opens up more interaction opportunities, but also expands the strategy space of an attacker seeking to exploit the community for its own ends. We show that with indirect trust exchange protocols, some friction is unavoidable: any protocol that satisfies a natural strategic safety property that we call sum-sybilproofness can sometimes lead to a reduction in expected overall trust balances even on interactions that are profitable in expectation. Thus, for long-term growth of trust accounts, which are assets enabling risky but valuable interactions, it may be necessary to limit the use of indirect trust. We present the hedged-transitive protocol and show that it achieves the optimal rate of expected growth in trust accounts, among all protocols satisfying the sum-sybilproofness condition.

Attackers may seek to manipulate recommender systems in order to promote or suppress certain items. Existing defenses based on analysis of ratings also discard useful information from honest raters. In this paper, we show that this is unavoidable and provide a lower bound on how much information must be discarded. We use an information-theoretic framework to exhibit a fundamental tradeoff between manipulation-resistance and optimal use of genuine ratings in recommender systems. We define a recommender system to be (n, c)-robust if an attacker with n sybil identities cannot cause more than a limited amount c units of damage to predictions. We prove that any robust recommender system must also discard Ω(log (n/c)) units of useful information from each genuine rater.

One attractive feature of market scoring rules [Hanson, Information Systems Frontiers, 2003] is that they are myopically strategyproof: It is optimal for a trader to report her true belief about the likelihood of an event provided that we ignore the impact of her report on the profit she might garner from future trades. This does not rule out the possibility that traders may profit by first misleading other traders through dishonest trades and then correcting the errors made by other traders. In this paper, we describe a new approach to analyzing non-myopic strategies and the existence of myopic equilibria. We first use a simple model with two partially informed traders in a single information market to gain insight into the conditions under which different equilibrium behavior emerges. We prove that, under generic conditions, the myopically optimal strategy profile is not a weak Perfect Bayesian Equilibrium (PBE) strategy for the logarithmic market scoring rule. We show that our results extend to multiple traders and signals. We propose a simple discounted market scoring rule that reduces the opportunity for bluffing strategies. We show that in any weak PBE, myopic or otherwise, the market price converges to the optimal price, and the rate of convergence can be bounded in terms of the discounting parameter.

An attacker can draw attention to items that don't deserve that attention by manipulating recommender systems. We describe an influence-limiting algorithm that can turn existing recommender systems into manipulation-resistant systems. Honest reporting is the optimal strategy for raters who wish to maximize their influence. If an attacker can create only a bounded number of shills, the attacker can mislead only a small amount. However, the system eventually makes full use of information from honest, informative raters. We describe both the influence limits and the information loss incurred due to those limits in terms of information-theoretic concepts of loss functions and entropies.

No abstract available.

Information markets, which are designed specifically to aggregate traders' information, are becoming increasingly popular as a means for predicting future events. Recent research in information markets has resulted in two new designs, market scoring rules and dynamic parimutuel markets. We develop an analytic method to guide the design and strategic analysis of information markets. Our central contribution is a new abstract betting game, the projection game, that serves as a useful model for information markets. We demonstrate that this game can serve as a strategic model of dynamic parimutuel markets, and also captures the essence of the strategies in market scoring rules. The projection game is tractable to analyze, and has an attractive geometric visualization that makes the strategic moves and interactions more transparent. We use it to prove several strategic properties about the dynamic parimutuel market. We also prove that a special form of the projection game is strategically equivalent to the spherical scoring rule, and it is strategically similar to other scoring rules. Finally, we illustrate two applications of the model to analysis of complex strategic scenarios: we analyze the precision of a market in which traders have inertia, and a market in which a trader can profit by manipulating another trader's beliefs.

Abstract — This paper studies multicast application overlay networks in a repeated-game framework. In these overlays, users have both the motivation and the means to alter their position in the overlay tree. We introduce a repeated-game model of user behavior that captures the practical tradeoff between a user’s short-term desire for quality and long-term desire for the network’s continued existence. We simulate overlay treeformation protocols with this model to study their robustness to selfish users. We show that this model can explain user cooperation and provide insight into how overlay systems scale in the absence of heavyweight mechanisms or identity systems. We also use the model to derive practical guidance on how to make multicast overlay protocols more robust to selfish users. I.

We study first-price auction mechanisms for auctioning flow between given nodes in a graph.We assume edges are independent agents with fixed capacities and costs, and their objective is to maximize their profit. We characterize all strong ffl-Nash equilibria of a first-price auction for this problem, and show that the total payment is never significantly more than, and often less than, the well known dominant strategy Vickrey-Clark-Groves (VCG) mechanism. We then present a randomized version of the first-price auction, for which the equilibrium condition can be relaxed to ffl-Nash equilibrium. We next consider a model in which the amount of demand is uncertain, but its probability distribution is known to the edges. For this model, we show that a simple ex ante first-price auction may not have any ffl-Nash equilibria. We then present a modified auction mechanism with 2-parameter bids, and show that it has an

The Border Gateway Protocol (BGP) for interdomain routing is designed to allow autonomous systems (ASes) to express policy preferences over alternative routes. We model these preferences as arising from an AS's underlying utility for each route and study the problem of finding a set of routes that maximizes the overall welfare (i.e., the sum of all ASes' utilities for their selected routes).We show that, if the utility functions are unrestricted, this problem is NP-hard even to approximate closely. We then study a natural class of restricted utilities that we call next-hop preferences. We present a strategyproof, polynomial-time computable mechanism for welfare-maximizing routing over this restricted domain. However, we show that, in contrast to earlier work on lowest-cost routing mechanism design, this mechanism appears to be incompatible with BGP and hence difficult to implement in the context of the current Internet. Our contributions include a new complexity measure for Internet algorithms, the dynamic stability, which may be useful in other problem domains.

According to economic theory supported by empirical and laboratory evidence, the equilibrium price of a financial security reflects all of the information regarding the security's value. We investigate the computational process on the path toward equilibrium, where information distributed among traders is revealed step-by-step over time and incorporated into the market price. We develop a simplified model of an information market, along with trading strategies, in order to formalize the computational properties of the process. We show that securities whose payoffs cannot be expressed as weighted threshold functions of distributed input bits are not guaranteed to converge to the proper equilibrium predicted by economic theory. On the other hand, securities whose payoffs are threshold functions are guaranteed to converge, for all prior probability distributions. Moreover, these threshold securities converge in at most $n$ rounds, where $n$ is the number of bits of distributed information. We also prove a lower bound, showing a type of threshold security that requires at least $n/2$ rounds to converge in the worst case.

No abstract available.

We show how to determine whether the edit distance between two given strings is small in sublinear time. Specifically, we present a test which, given two n-character strings A and B, runs in time o(n) and with high probability returns "CLOSE" if their edit distance is O(nΑ), and "FAR" if their edit distance is Ω(n), where Α is a fixed parameter less than 1. Our algorithm for testing the edit distance works by recursively subdividing the strings A and B into smaller substrings and looking for pairs of substrings in A, B with small edit distance. To do this, we query both strings at random places using a special technique for economizing on the samples which does not pick the samples independently and provides better query and overall complexity. As a result, our test runs in time Õ(nmax(Α/2, 2Α - 1\)) for any fixed Α < 1. Our algorithm thus provides a trade-off between accuracy and efficiency that is particularly useful when the input data is very large.We also show a lower bound of Ω(nΑ/2) on the query complexity of every algorithm that distinguishes pairs of strings with edit distance at most nΑ from those with edit distance at least n/6.

The routing of traffic between... this paper, we address the problem of interdomain routing from a mechanism-design point of view. The application of mechanism-design principles to the study of routing is the subject of earlier work by Nisan and Ronen [15] and Hershberger and Suri [11]. In this paper, we formulate and solve a version of the routing-mechanism design problem that is different from the previously studied version in three ways that make it more accurately reflective of real-world interdomain routing: (1) we treat the nodes as strategic agents, rather than the links; (2) our mechanism computes lowest-cost routes for all source-destination pairs and payments for transit nodes on all of the routes (rather than computing routes and payments for only one source-destination pair at a time, as is done in [15,11]); (3) we show how to compute our mechanism with a distributed algorithm that is a straightforward extension to BGP and causes only modest increases in routingtable size and convergence time (in contrast with the centralized algorithms used in [15,11]). This approach of using an existing protocol as a substrate for distributed computation may prove useful in future development of Internet algorithms generally, not only for routing or pricing problems. Our design and analysis of a strategyproof, BGP-based routing mechanism provides a new, promising direction in distributed algorithmic mechanism design, which has heretofore been focused mainly on multicast cost sharing.

Article Share on Approximation and collusion in multicast cost sharing (extended abstract) Authors: J. Feigenbaum Yale University, New Haven, CT Yale University, New Haven, CTView Profile , A. Krishnamurthy Yale University, New Haven, CT Yale University, New Haven, CTView Profile , R. Sami Yale University, New Haven, CT Yale University, New Haven, CTView Profile , S. Shenker ACIRI/ICSI, Berkeley, CA ACIRI/ICSI, Berkeley, CAView Profile Authors Info & Claims EC '01: Proceedings of the 3rd ACM conference on Electronic CommerceOctober 2001 Pages 253–255https://doi.org/10.1145/501158.501190Online:14 October 2001Publication History 9citation174DownloadsMetricsTotal Citations9Total Downloads174Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Our program benchmarks and simulations of novel circuits indicate that large-window processors are feasible. Using our redesigned superscalar components, a large-window processor implemented in today's technology can achieve an increase of 10-60% (geometric mean of 31%) in program speed compared to today's processors. The processor operates at clock speeds comparable to today's processors, but achieves significantly higher ILP.