Society uses the following mechanism to decide on the supply of an experience good. Each agent can choose whether or not to contribute to the good. Contributions are collected, and the good is supplied whenever total contributions exceed a threshold. We study the case where the good is excludable, agents have a common value, and each agent receives a private signal about the common value. We study how such collective decisions perform in terms of information aggregation, social efficiency, and market traction.

We study the robustness of cheap-talk equilibria to infinitesimal private information of the receiver in a model with a binary state-space and state-independent sender-preferences.

Mean-preserving contractions are critical for studying Bayesian models of information design. We introduce the class of bi-pooling policies, and the class of bi-pooling distributions as their induced distributions over posteriors. We show that every extreme point in the set of all mean-preserving contractions of any given prior over an interval takes the form of a bi-pooling distribution. By implication, every Bayesian persuasion problem with an interval state space admits an optimal bi-pooling distribution as a solution, and conversely, for every bi-pooling distribution, there is a Bayesian persuasion problem for which that distribution is the unique solution.

Two firms produce substitute goods of unknown quality. At each stage the firms set prices and a consumer with private information and unit demand buys from one of the firms. Both firms and consumers see the entire history of prices and purchases. Will such markets aggregate information? Will the firm with the superior product necessarily prevail? We adapt the classic social-learning model by introducing strategic dynamic pricing. We provide necessary and sufficient conditions for asymptotic learning. In contrast to previous results, we show that asymptotic learning can occur when signals are bounded, namely, happens when the density of the consumers at the boundaries of the posterior belief distribution goes to zero. We refer to this property of the signal structure as the “vanishing margins” property.

The Bayesian persuasion paradigm of strategic communication models interaction between a privately informed sender and an ignorant but rational receiver. The goal is typically to design a (near-)optimal communication (or signaling) scheme for the sender. It enables the sender to disclose information to the receiver in a way as to incentivize her to take an action that is preferred by the sender. Finding the optimal signaling scheme is known to be computationally difficult in general. This hardness is further exacerbated when the message space is constrained, leading to NP-hardness of approximating the optimal sender utility within any constant factor. In this paper, we show that in several natural and prominent cases the optimization problem is tractable even when the message space is limited. In particular, we study signaling under a symmetry or an independence assumption on the distribution of utility values for the actions. For symmetric distributions, we provide a novel characterization of the optimal signaling scheme. It results in a polynomial-time algorithm to compute an optimal scheme for many compactly represented symmetric distributions. In the independent case, we design a constant-factor approximation algorithm, which stands in marked contrast to the hardness of approximation in the general case.

We revisit the basic variant of the classical secretary problem. We propose a new approach in which we separate between an agent (the sender) that evaluates the secretary performance and one (the receiver) that makes the hiring decision. The sender signals the quality of the candidate to the hiring agent. Whenever the two agents' interests are not fully aligned, this induces an information transmission (signaling) challenge for the sender. We study the sender's optimization problem subject to persuasiveness constraints for the receiver in several variants of the problem. Our results quantify the loss in performance for the sender due to online arrival. We provide optimal and near-optimal persuasive mechanisms. In most cases the sender can recover at least a constant fraction of the utility that he would have obtained had he been able to access all information at the outset.

The Bayesian persuasion model studies communication between an informed sender and a receiver with a payoff-relevant action, emphasizing the ability of a sender to extract maximal surplus from his informational advantage. In this paper, we study a setting with multiple senders in which the receiver is restricted to choosing, at the interim stage, one sender with whom to interact. Our main result is that whenever senders are uncertain about each other’s preferences and, in particular, cannot dismiss with certainty the possibility that others are aligned with the receiver, the receiver receives all the informational surplus in all equilibria.

A data curator would like to collect data from privacy-aware agents. The collected data will be used for the benefit of all agents. Can the curator incentivize the agents to share their data truthfully? Can he guarantee that truthful sharing will be the unique equilibrium? Can he provide some stability guarantees on such equilibrium? We study necessary and sufficient conditions for these questions to be answered positively and complement these results with corresponding data collection protocols for the curator. Our results account for a broad interpretation of the notion of privacy awareness. The full version of this paper is available at https://arxiv.org/abs/2207.06929.

We analyze repeated games in which players have private information about their levels of patience and in which they would like to maintain the privacy of this information vis-à-vis third parties. We show that privacy protection in the form of shielding players’ actions from outside observers is harmful, as it limits and sometimes eliminates the possibility of attaining Pareto-optimal payoffs.

The Bayesian persuasion paradigm of strategic communication models interaction between a privately-informed agent, called the sender, and an ignorant but rational agent, called the receiver. The goal is typically to design a (near-)optimal communication (or signaling) scheme for the sender. It enables the sender to disclose information to the receiver in a way as to incentivize her to take an action that is preferred by the sender. Finding the optimal signaling scheme is known to be computationally difficult in general. This hardness is further exacerbated when there is also a constraint on the size of the message space, leading to NP-hardness of approximating the optimal sender utility within any constant factor. In this paper, we show that in several natural and prominent cases the optimization problem is tractable even when the message space is limited. In particular, we study signaling under a symmetry or an independence assumption on the distribution of utility values for the actions. For symmetric distributions, we provide a novel characterization of the optimal signaling scheme. It results in a polynomial-time algorithm to compute an optimal scheme for many compactly represented symmetric distributions. In the independent case, we design a constant-factor approximation algorithm, which stands in marked contrast to the hardness of approximation in the general case.

Differential privacy is commonly used in the computer science literature as a mathematical definition of privacy for the purpose of quantifying and bounding privacy loss. It induces a preference order over the set of privacy-jeopardizing mechanisms which, in turn, adhere to some properties of this order. We show that a set of five such properties uniquely captures the ordinal implications of prioritizing the alternatives in agreement with differential privacy. The model can also be applied to evaluate the appropriateness of differential privacy in different settings.

We consider social learning where agents can only observe part of the population (modeled as neighbors on an undirected graph), face many decision problems, and arrival order of the agents is unknown. The central question we pose is whether there is a natural observability graph that prevents the information cascade phenomenon. We introduce the ‘celebrities graph’ and prove that indeed it allows for proper information aggregation in large populations even when the order at which agents decide is random and even when different issues are decided in different orders.

Consider a setting where many individuals forecast the (unknown) state of nature based on signals they receive independently. We refer to the joint distribution over the states and signals as an “information structure.” An information structure is deemed identifiable if the distribution of forecasts is sufficient to determine the state of nature, even without knowing the underlying information structure. We characterize the set of identifiable information structures and propose a scheme that uniquely identifies the state of nature for the finite case.

Privacy, in the sense of control over access to one's personal information, is a central concern in the context of online decision making, both in general and in relation to online platforms in particular. For at least some agents, a belief that one online platform jeopardizes users’ privacy more than another may tip the scales in favor of the latter. Thus, understanding how privacy considerations come into play is central for any economic or social analysis. To this end, we study how agents rank online platforms (or mechanisms, as we call them) from a privacy perspective. We propose a very simple model of privacy-jeopardizing mechanisms, along with a normative methodology for understanding how these mechanisms are ranked. Similarly to classic work in decision theory, we postulate several axioms that we believe a privacy order should satisfy, and then characterize the set of orders that comply with these axioms. These orders turn out to be related to the notion of f-divergence from information theory, one example of which is KL divergence. We test the usefulness of our theoretical result by using it to rank clustering models based on data provided by the Recommendation Team at Microsoft Research.

In various situations, decision makers face experts that may provide conflicting advice. This advice may be in the form of probabilistic forecasts over critical future events. We consider a setting where the two forecasters provide their advice repeatedly and ask whether the decision maker can learn to compare and rank the two forecasters based on past performance. We take an axiomatic approach and propose three natural axioms that a comparison test should comply with. We propose a test that complies with our axioms. Perhaps, not surprisingly, this test is closely related to the likelihood ratio of the two forecasts over the realized sequence of events. More surprisingly, this test is essentially unique. Furthermore, using results on the rate of convergence of supermartingales, we show that whenever the two experts’ advice are sufficiently distinct, the proposed test will detect the informed expert in any desired degree of precision in some fixed finite time.

We study an information-structure design problem (i.e., a Bayesian persuasion problem) in an online scenario. Inspired by the classic gambler's problem, consider a set of candidates who arrive sequentially and are evaluated by one agent (the sender). This agent learns the value from hiring the candidate to herself as well as the value to another agent, the receiver. The sender provides a signal to the receiver who, in turn, makes an irrevocable decision on whether or not to hire the candidate. A-priori, for each agent the distribution of valuation is independent across candidates but may not be identical. We design good online signaling schemes for the sender. To assess the performance, we compare the expected utility to that of an optimal offline scheme by a prophet sender who knows all candidate realizations in advance. We show an optimal prophet inequality for online Bayesian persuasion, with a 1/2-approximation when the instance satisfies a “satisfactory-status-quo” assumption. Without this assumption, there are instances without any finite approximation factor. We extend the results to combinatorial domains and obtain prophet inequalities for matching with multiple hires and multiple receivers.

A policy maker faces a sequence of unknown outcomes. At each stage two (self-proclaimed) experts provide probabilistic forecasts on the outcome in the next stage. A comparison test is a protocol for the policy maker to (eventually) decide which of the two experts is better informed. The protocol takes as input the sequence of pairs of forecasts and actual outcomes and (weakly) ranks the two experts. We focus on anonymous and non-counterfactual comparison tests and propose two natural properties to which such a comparison test must adhere. We show that these determine the test in an essentially unique way. The resulting test is a function of the derivative of the induced pair of measures at the realized outcomes.

In the classical secretary problem, multiple secretaries arrive one at a time to compete for a single position, and the goal is to choose the best secretary to the job while knowing the candidate’s quality only with respect to the preceding candidates. In this paper we define and study a new variant of the secretary problem, in which there are multiple jobs. The applicants are ranked relatively upon arrival as usual, and, in addition, we assume that the jobs are also ranked. The main conceptual novelty in our model is that we evaluate a matching using the notion of blocking pairs from Gale and Shapley’s stable matching theory. Specifically, our goal is to maximize the number of matched jobs (or applicants) that do not take part in a blocking pair. We study the cases where applicants arrive randomly or in adversarial order, and provide upper and lower bounds on the quality of the possible assignment assuming all jobs and applicants are totally ordered. Among other results, we show that when arrival is uniformly random, a constant fraction of the jobs can be satisfied in expectation, or a constant fraction of the applicants, but not a constant fraction of the matched pairs.

Technological evolution, so central to the progress of humanity in recent decades, is the process of constantly introducing new technologies to replace old ones. A new technology does not necessarily mean a better technology and so should not always be embraced. How can society learn which novelties present actual improvements over the existing technology? Whereas the quality of status-quo technology is well known, the new one is a pig in a poke. With sufficiently many individuals willing to explore the new technology society can learn whether it is indeed an improvement. However, self motivated agents, often, do not agree to explore. This is true, in particular, if agents observed some predecessors that were disappointed from the new technology. Inspired by the classical multi-armed bandit model we study a setting where agents arrive sequentially and must pull one of two arms in order to receive a reward - a risky arm (representing the new technology) and a safe arm (representing the existing one). A central planner must induce sufficiently many agents to experiment with the risky arm. The central planner observes the actions and rewards of all agents while the agents themselves have partial observation. For the setting where each agent observes his predecessor we provide the central planner with a recommendation algorithm that is (almost) incentive compatible and facilitates social learning.

Bayesian experts who are exposed to different evidence often make contradictory probabilistic forecasts. An aggregator, ignorant of the underlying model, uses this to calculate his or her own forecast. We use the notions of scoring rules and regret to propose a natural way to evaluate an aggregation scheme. We focus on a binary state space and construct low regret aggregation schemes whenever there are only two experts that either are Blackwell-ordered or receive conditionally independent and identically distributed (i.i.d.) signals. In contrast, if there are many experts with conditionally i.i.d. signals, then no scheme performs (asymptotically) better than a (0.5, 0.5) forecast.

We study the intersection signalling control problem for cars with heterogeneous valuations of time (VoT). We are interested in a control algorithm that has some desirable properties: (1) it induces cars to report their VoT truthfully, (2) it minimizes the value of time lost for cars waiting at the intersection, and (3) it is computationally efficient. We obtain three main results: (1) We describe a computationally efficient heuristic forward search approach to solve the static problem. (2) We extend the solution of the static problem to the dynamic case. We couple our algorithm with a carefully designed payment scheme which yields an incentive compatible mechanism. (3) We describe simulation results that compare the social welfare obtained by our scheduling algorithm, as measured by the total value of waiting time, to the social welfare obtained by other intersection signalling control methods.

Data-driven segmentation is the powerhouse behind the success of online advertising. Various underlying challenges for successful segmentation have been studied by the academic community, with one notable exception-consumers' incentives have been typically ignored. This lacuna is troubling, as consumers have much control over the data being collected. Missing or manipulated data could lead to inferior segmentation. The current work proposes a model of prior-free segmentation, inspired by models of facility location and, to the best of our knowledge, provides the first segmentation mechanism that addresses incentive compatibility, efficient market segmentation, and privacy in the absence of a common prior.

Players have privacy concerns that may affect their choice of actions in strategic settings. We use a variant of signaling games to model this effect and study its relation to pooling behavior, misrepresentation of information, and inefficiency.

Just the other day we were planning our weekend activities and looked at the forecast for the weather in Tel-Aviv on Friday, January 27. In particular what interested us was the probability for rain (precipitation). Accuweather's precipitation forecast was 77% while Yahoo! had a forecast of 60% and the Weather Channel was at 90% (all three screenshots are provided in the appendix). It was unclear to us how to aggregate these confliicting forecasts although we knew all three were reputable sources and were using sound weather models and reliable data. Our dilemma was not unique. In fact many of us face such con.icting sources of advice from experts on a daily basis. Forecasts from reliable pollsters on the outcome of the presidential elections, medical prognosis from trusted physicians, investment advice from experienced financial pundits and more. This challenge is in fact the crux of the working of many governing bodies. In the political arena we often see ministers and legislators that are chosen electives and must decide on critical issues and policies with any subject ma.er expertise. Such public electives dictate health care policies, decide on military development and deployment, financial regulation and so on without prior medical / military / financial background. To do so they reach out to experts advices whose information they should aggregate. We consider a model with three agents. .ere are two experts who provide a forecast about the probability over some given future event. .e experts agree on the prior probability, both receive some common information, however, one of them is be.er informed and has access to additional private information1. Both agents form posterior forecasts vis-A-vis Bayes rule. .e two forecasts are shared with the third player, the policy maker (PM), who now aggregates them to form his own subjective forecast. Unfortunately, the identity of the be.er informed expert is not known to the PM.

We study a two-sided matching market with a set of heterogeneous firms and workers in an environment where jobs are secured by regulation. Without job security Kelso and Crawford have shown that stable outcomes and efficiency prevail when all workers are gross substitutes to each firm. It turns out that by introducing job security, stability and efficiency may still prevail, and even for a significantly broader class of production functions.

In the on-line Explore & Exploit [E&E] literature, central to Machine Learning, a central planner is faced with a set of alternatives, each yielding some unknown reward. The planner's goal is to learn the optimal alternative as soon as possible, via experimentation. A typical assumption in this model is that the planner has full control over the experiment design and implementation. When experiments are implemented by a society of self-motivated agents the planner can only recommend experimentation but has no power to enforce it. The first paper to marry the social aspects with the challenge of E&E, a new research domain for which we coin the term 'social explore and exploit', is Kremer et. al. [Kremer et al. 2014]. In that work the authors introduce a naive setting (We use the notion of a 'naive setting' for settings where the optimal non-social explore and exploit scheme is trivial - try all actions sequentially, each once, and settle on the optimal one thereafter) and study optimal explore and exploit schemes that account for agents' incentives. To be more specific, [Kremer et al. 2014] identify an incentive compatible scheme with which a central planner can asymptotically steer the users towards taking the optimal action. Whereas [Kremer et al. 2014] account for agents' incentives and in particular the misalignment of incentives of the agents and the planner it ignore other societal aspects. In particular, [Kremer et al. 2014] make an implicit assumption that agents cannot see nor communicate with any other agent. It turns out that, when observability is factored in, the scheme proposed by Kremer et. al. is no longer incentive compatible, leading to market failure. In this work we introduce observability into the framework of social E&E. We study the design of recommendation systems when agents can (partly) observe each other. In particular, we investigate the conditions on the social network which allow for asymptotically optimal outcomes. Thus, we extend [Kremer et al. 2014] by adding the additional layer of a social network and show conditions under which the essence of their results, albeit with a different mechanism, can still be maintained even though agents may observe each other. Intuitively, the more agents can see each other the less power resides within the central planner. Formally, let a visibility graph over N agents be a graph where agents serve as the nodes, and an edge (a, b) implies that agents a and b can observe each other's action. A visibility graph is an (α, β)-graph if the number of nodes with degree greater than N^α is bounded by N^β·Our main result is that for a sufficiently large N, if the visibility graph is an (α,β)-graph, where 2α + β < 1, then there exists a deterministic incentive-compatible algorithm leading to approximately optimal outcome. On the other hand we show that for the complete graph asymptotically optimal outcome can not be obtained by any probabilistic incentive-compatible algorithm. As the complete graph is a (0, 1)-graph, our result is tight.

With the prevalence of cloud computing emerges the challenges of pricing cloud computing services. There are various characteristics of cloud computing which make the problem unique. We study an abstract model which focuses on one such aspect - the sale of a homogeneous and fully divisible good. We cast onto our model the idea of bundling, studied within the context of monopolist pricing of indivisible goods. We demonstrate how selling a divisible good as an indivisible one may increase seller revenues and characterize when this phenomenon occurs, and the corresponding gain factors.

Consider an abstract social choice setting with incomplete information, where the number of alternatives is large. Albeit natural, implementing VCG mechanisms is infeasible due to the prohibitive communication constraints. However, if players restrict attention to a subset of the alternatives, feasibility may be recovered. This article characterizes the class of subsets that induce an ex-post equilibrium in the original game. It turns out that a crucial condition for such subsets to exist is the availability of a type-independent optimal social alternative for each player. We further analyze the welfare implications of these restrictions. This work follows that of Holzman et al. [2004] and Holzman and Monderer [2004] where similar analysis is done for combinatorial auctions.

We consider an environment where sellers compete over buyers. All sellers are a-priori identical and strategically signal buyers about the product they sell. In a setting motivated by online advertising in display ad exchanges, where firms use second price auctions, a firm's strategy is a decision about its signaling scheme for a stream of goods (e.g., user impressions), and a buyer's strategy is a selection among the firms. In this setting, a single seller will typically provide partial information, and consequently, a product may be allocated inefficiently. Intuitively, competition among sellers may induce sellers to provide more information in order to attract buyers and thus increase efficiency. Surprisingly, we show that such a competition among firms may yield significant loss in consumers' social welfare with respect to the monopolistic setting. Although we also show that in some cases, the competitive setting yields gain in social welfare, we provide a tight bound on that gain, which is shown to be small with respect to the preceding possible loss. Our model is tightly connected with the literature on bundling in auctions.

The model of congestion games is widely used to analyze games related to traffic and communication. A central property of these games is that they are potential games and hence posses a pure Nash equilibrium. In reality, it is often the case that some players cooperatively decide on their joint action in order to maximize the coalition's total utility. This is modeled by Coalitional Congestion Games. Typical settings include truck drivers who work for the same shipping company, or routers that belong to the same ISP. The formation of coalitions will typically imply that the resulting coalitional congestion game will no longer posses a pure Nash equilibrium. In this paper, we provide conditions under which such games are potential games and posses a pure Nash equilibrium.

We study the class of congestion games for which the set of Nash equilibrium is equivalent to the set of strategy profiles played by greedy myopic players. We show these two coincide iff such games are played over extension-parallel graphs.

We study an incomplete information mechanism design problem with three peculiarities. First, access to agents' private information is costly and unobservable. Second, the mechanism may communicate sequentially with the agents. Third, the mechanism designer and all the agents share a common interest. As an example one can think of N geologists that study the potential oil reserves in some tract. The geologists agree on the right course of action, given their N studies. However, carrying out the study may be costly for a geologist and so he may opt to fabricate a study. The oil company that employs these geologists need not contract them simultaneously and may, furthermore, choose to provide some of the results of early studies to geologists employed later on. Finally, the geologists and the oil company would like the joint study to forecast the quantity of oil reserves as accurate as possible. It turns out that, in such settings, what may not be implementable without communication becomes implementable with communication. Clearly, the possibility for sequential communication introduces a lot of complexity to the design problem. However, we provide a result in the spirit of the revelation principle and argue that whenever implementation is possible with communication it is also possible with a simple communication mechanism. Formally, we extend the model and results in Smorodinsky and Tennenholtz (Games Econ Behav 55(2):385-406, 2006) who consider the similar problem but restrict attention to symmetric social choice functions and IID distributions over the private information.

Mechanism design deals with distributed algorithms that are executed with self-interested agents. The designer, whose objective is to optimize some function of the agents private types, needs to construct a computation that takes into account agent incentives which are not necessarily in alignment with the objective of the mechanism. Traditionally, mechanisms are designed for agents who only care about the utility they derive from the mechanism outcome, which often fully or partially discloses their (declared) types. Such mechanisms may become inadequate when agents are privacy-aware, i.e., when their loss of privacy adversely affects their utility. In such cases ignoring privacy-awareness in the design of a mechanism may render it not incentive compatible, and hence inefficient. Interestingly, and somewhat counter-intuitively, Xiao [eprint 2011] has recently showed that this can happen even when the mechanism preserves a strong notion of privacy. Towards constructing mechanisms for privacy-aware agents, we put forward and justify a model of privacy-aware mechanism design. We then show that privacy-aware mechanisms are feasible. The following is a summary of our contributions: - Modeling privacy-aware agents: We propose a new model of privacy-aware agents where agents need only have a conservative upper bound on how loss of privacy adversely affects their utility. This is in deviation from prior modeling which required full characterization. - Privacy of the privacy loss valuations: Agent privacy valuations are often sensitive on their own. Our model of privacy-aware mechanisms takes into account the loss of utility due to information leaked about these valuations. - Guarantees for agents with high privacy valuations: As it is impossible to guarantee incentive compatibility for agents that have arbitrarily high privacy valuations, we require a privacy-aware mechanism to set a threshold such that the mechanism is incentive compatible w.r.t. agents whose privacy valuations are below the threshold, and differential privacy is guaranteed for all other agents. - Constructing privacy-aware mechanisms: We first construct a privacy-aware mechanism for a simple polling problem, and then give a more general result, based on recent generic construction of approximately additive mechanisms by Nissim, Smorodinsky, and Tennenholtz [ITCS 2012]. We show that under a mild assumption on the distribution of privacy valuations (namely, that valuations are bounded for all but a vanishing fraction of the population) these constructions are incentive compatible w.r.t. almost all agents, and hence give an approximation of the optimum. Finally, we show how to apply our generic construction to get a mechanism for privacy-aware selling of digital goods.

We study the implementation challenge in an abstract interdependent values model and an arbitrary objective function. We design a generic mechanism that allows for approximate optimal implementation of insensitive objective functions in ex-post Nash equilibrium. If, furthermore, values are private then the same mechanism is strategy proof. We cast our results onto two specific models: pricing and facility location. The mechanism we design is optimal up to an additive factor of the order of magnitude of one over the square root of the number of agents and involves no utility transfers. Underlying our mechanism is a lottery between two auxiliary mechanisms - - with high probability we actuate a mechanism that reduces players influence on the choice of the social alternative, while choosing the optimal outcome with high probability. This is where differential privacy is employed. With the complementary probability we actuate a mechanism that may be typically far from optimal but is incentive compatible. The joint mechanism inherits the desired properties from both.

We study the problem of testing an expert whose theory has a learnable and predictive parametric representation, as do standard processes used in statistics. We design a test in which the expert is required to submit a date T by which he will have learned enough to deliver a sharp, testable prediction about future frequencies. We show that this test passes an expert who knows the data-generating process and cannot be manipulated by a uninformed one. Such a test is not possible if the theory is unrestricted.

We consider the efficiency properties of exchange economies where privately informed traders behave strategically. Specifically, a competitive mechanism is any mapping of traders' reports about their types to an equilibrium price vector and allocation of the reported economy. In our model, some traders may have non-vanishing impact on prices and allocations regardless of the size of the economy. Although truthful reporting by all traders cannot be achieved, we show that, given any desired level of approximation, there is over(N, -) such that any Bayesian-Nash equilibrium of any competitive mechanism of any private information economy with over(N, -) or more traders leads, with high probability, to prices and allocations that are close to a competitive equilibrium of the true economy. In particular, allocations are approximately efficient. A key assumption is that there is small probability that traders behave non-strategically.

This paper reports the results of a repeated all-pay auction game. The auction form used is the simplest possible, complete information, perfect recall and common value. Our main findings are that in such an auction, over-bidding is quite drastic, and the seller's revenue depends strongly on the number of bidders in early stages. However, after a few rounds of play, this dependence completely disappears and the seller's revenue becomes independent of the number of participants. The results are confronted with two solution concepts of economic theory, the Nash-equilibrium and the symmetric Logit equilibrium.

This paper addresses the question of multi-party computation in a model with asymmetric information. Each agent has a private value (secret), but in contrast to standard models, the agent incurs a cost when retrieving the secret. There is a social choice function the agents would like to compute and implement. All agents would like to perform a joint computation, which input is their vector of secrets. However, agents would like to free-ride on others' contribution. A mechanism which elicits players' secrets and performs the desired computation defines a game. A mechanism is 'appropriate' if it (weakly) implements the social choice function for all secret vectors. namely, if there exists an equilibrium in which it is able to elicit (sufficiently many) agents' secrets and perform the computation, for all possible secret vectors. We show that 'appropriate' mechanisms approach agents sequentially and that they have low communication complexity.

In his seminal work, Nash (1950) [Nash, J.F. (1950). "The Bargaining Problem", Econometrica, 18, 155-162.] derives a solution for two-person bargaining problems, within a cooperative setup. Nash assumes that the result of disagreement is known to both players and is not stochastic. We study the same problem, where the last assumption is relaxed. We provide a set of axioms which characterizes a natural generalization of the Nash solution to bargaining problems with a random point of disagreement.

This paper addresses the question of multi party computation in a model with asymmetric information. Each agent has a private value (secret), but in contrast to standard models, the agent incurs a cost when retrieving the secret. There is a social choice function the agents would like to compute and implement. All agents would like to perform a joint computation, which input is their vector of secrets. However, agents would like to free-ride on others’ contribution. A mechanism which elicits players’ secrets and performs the desired computation defines a game. A mechanism is ‘appropriate’ if it (weakly) implements the social choice function for all secret vectors. namely, if there exists an equilibrium in which it is able to elicit (sufficiently many) agents’ secrets and perform the computation, for all possible secret vectors. We show that ‘appropriate’ mechanisms approach agents sequentially and that they have low communication complexity.

The asymptotic value, introduced by Kannai in 1966, is an asymptotic approach to the notion of the Shapley value for games with infinitely many players. A vector measure game is a game v where the worth v(S) of a coalition S is a function f of μ(S) where μ is a vector measure. Special classes of vector measure games are the weighted majority games and the two-house weighted majority games, where a two-house weighted majority game is a game in which a coalition is winning if and only if it is winning in two given weighted majority games. All weighted majority games have an asymptotic value. However, not all two-house weighted majority games have an asymptotic value. In this paper, we prove that the existence of infinitely many atoms with sufficient variety suffice for the existence of the asymptotic value in a general class of nonsmooth vector measure games that includes in particular two-house weighted majority games.

We introduce a new solution concept for short-sighted players engaging in a repeated interaction: a Belief-based equilibrium (BBE). In a BBE, players optimize myopically given their beliefs which are not necessarily correct, but are not contradicted by the data. We show that, if the stage game has a unique correlated equilibrium then the play of a BBE resembles a Nash equilibrium play. However, a BBE may not be a Nash equilibrium. In particular, in a BBE players may play deterministically when the only Nash equilibrium is in mixed strategies.

Each period an outcome (out of finitely many possibilities) is observed. For simplicity assume two possible outcomes, a and b. Each period, a forecaster announces the probability of a occurring next period based on the past Consider an arbitrary subsequence of periods (e.g., odd periods, even periods, all periods in which b is observed, etc.). Given an integer n, divide any such subsequence into associated sub-subsequences in which the forecast for a is between (i/n, i + 1/n), i ∈ {0, 1,...,n}. We compare the forecasts and the outcomes (realized next period) separately in each of these subsubsequences. Given any countable partition of [0,1] and any countable collection of subsequences, we construct a forecasting scheme such that for all infinite strings of data, the long-run average forecast for a matches the long-run frequency of realized a's.

E. J. Green (1980, J. Econ. Theory 22, 155-182) and H. Sabourian (1990, J. Econ. Theory 51, 92-110) studied repeated games where a player's payoff depends on his actions and an anonymous aggregate outcome, and show that long-run players behave myopically in any equilibrium of such games. In this paper we extend these results to games where the aggregate outcome is not necessarily an anonymous function of players' actions, and where players' strategies may depend nonanonymously on signals of other players' behavior. Our argument also provides a conceptually simpler proof of Green and Sabourian's results, showing how their analysis is driven by general bounds on the number of pivotal players in a game.

Assume a decision maker has a preference relation over monetary lotteries. The reflection effect, first observed by Kahneman and Tversky, states that the preference order for two lotteries is reversed once they are multiplied by -1. The decision maker is constant risk averse (CRA) if adding the same constant to two distributions, or multiplying them by the same positive constant, will not change the preference relation between them. We combine these two axioms with the betweenness axiom and continuity, and prove a representation theorem. A technical curiosity is that the functions we get satisfy the betweenness axiom, yet are not necessarily Gâteaux (nor Fréchet) differentiable.

A player's influence relative to a mechanism and opponents' strategies is the maximum difference his action can make in the expected value of a collective outcome. A player is α-pivotal if his influence exceeds a threshold α. We provide tight bounds on the number of pivotal players and on average influence. These bounds are uniform over all mechanisms and action profiles and are achieved at mechanisms that take the form of a majority rule. We illustrate our analysis with an example of provision of a public good where each individual compares the private cost of his contribution with its influence on the collective outcome. Journal of Economic Literature Classification Numbers: D62, D89, H41.

We provide a sufficient condition for the expected aggregate contribution to a public good to be bounded, independently of the size of the population.

Consider an agent who faces a sequential decision problem. At each stage the agent takes an action and observes a stochastic outcome (e.g., daily prices, weather conditions, opponents' actions in a repeated game, etc.). The agent's stage-utility depends on his action, the observed outcome and on previous outcomes. We assume the agent is Bayesian and is endowed with a subjective belief over the distribution of outcomes. The agent's initial belief is typically inaccurate. Therefore, his subjectively optimal strategy is initially suboptimal. As time passes information about the true dynamics is accumulated and, depending on the compatibility of the belief with respect to the truth, the agent may eventually learn to optimize. We introduce the notion of relative entropy, which is a natural adaptation of the entropy of a stochastic process to the subjective set-up. We present conditions, expressed in terms of relative entropy, that determine whether the agent will eventually learn to optimize. It is shown that low entropy yields asymptotic optimal behavior. In addition, we present a notion of pointwise merging and link it with relative entropy.

Consider a finite-state stochastic process governed by an unknown objective probability distribution. Observing the system, a forecaster assigns subjective probabilities to future states. The resulting subjective forecast merges to the objective distribution if, with time, the forecasted probabilities converge to the correct (but unknown) probabilities. The forecast is calibrated if observed long-run empirical distributions coincide with the forecasted probabilities. This paper links unobserved reliability of forecasts to their observed empirical performance by demonstrating full equivalence between notions of merging and of calibration, and discusses implications of this equivalence for the literature of forecasting and learning. Journal of Economic Literature Classification Numbers: C5, C11, C73, D83.

A central result in the rational learning literature is that if the true measure is absolutely continuous with respect to the beliefs then, given enough data, the updated beliefs merge with the true distribution. In this paper, we show that, under absolute continuity, weak merging occurs fast (at the rate 1/√t) with density one. Moreover, if weak merging occurs fast enough (at the rate 1/t) then absolute continuity holds. These rates are sharp. We also show that, under some conditions, if weak merging occurs at the rate 1/√t then absolute continuity holds.

A probability distribution governing the evolution of a stochastic process has infinitely many Bayesian representations of the form μ = ∫Θμ_θdλ(θ). Among these, a natural representation is one whose components (μ_θ's) are "learnable" (one can approximate μ_θ by conditioning μ on observation of the process) and "sufficient for prediction" (μ_θ's predictions are not aided by conditioning on observation of the process). We show the existence and uniqueness of such a representation under a suitable asymptotic mixing condition on the process. This representation can be obtained by conditioning on the tail-field of the process, and any learnable representation that is sufficient for prediction is asymptotically like the tail-field representation. This result is related to the celebrated de Finetti theorem, but with exchangeability weakened to an asymptotic mixing condition, and with his conclusion of a decomposition into i.i.d. component distributions weakened to components that are learnable and sufficient for prediction.

We examine repeated games with incomplete information where the type spaces of the players may be large. It is shown that if the belief of each player, regarding future play of the game, accommodates the true play then a Nash equilibrium of the incomplete information game will evolve, with time, into an equilibrium of the complete information game, i.e., the realized game where the types of all players are common knowledge. We introduce the notion of accommodating beliefs which involves two requirements. The first is that the belief assigns positive probability to neighborhoods of the true distribution and the second is that what lies outside of a neighborhood is separated from the true distribution by sufficient incoming observations (this is the separation property defined in the paper).

Two measures, μ and μ, are updated as more information arrives. If with μ-probability 1, the predictions of future events according to both measures become close, as time passes, we say that μ merges to μ. Blackwell and Dubins (1962) showed that if μ is absolutely continuous with respect to μ then μ merges to μ. Restricting the definition to prediction of near future events and to a full sequence of times yields the new notion of almost weak merging (AWM), presented here. We introduce a necessary and sufficient condition and show many cases with no absolute continuity that exhibit AWM. We show, for instance, that the fact that μ is diffused around μ implies AWM.