1,720,983 research outputs found
Limits on Computationally Efficient VCG-Based Mechanisms for Combinatorial Auctions and Public Projects
Get PDFA natural goal in designing mechanisms for auctions and public projects is to maximize the social welfare while incentivizing players to bid truthfully. If these are the only concerns, the problem is easily solved by use of the VCG mechanism. Unfortunately, this mechanism is not computationally efficient in general and there are currently no other general methods for designing truthful mechanisms. However, it is possible to design computationally efficient VCG-based mechanisms which approximately maximize the social welfare.
We explore the design space of computationally efficient VCG-based mechanisms under submodular valuations and show that the achievable approximation guarantees are poor, even compared to efficient non-truthful algorithms. Some of these approximation hardness results stem from an asymmetry in the information available to the players versus that available to the mechanism. We develop an alternative Instance Oracle model which reduces this asymmetry by allowing the mechanism to access some computational capabilities of the players. By building assumptions about player computation into the model, a more realistic study of mechanism design can be undertaken.
Finally, we give VCG-based mechanisms for some problems in the Instance Oracle model which achieve provably better approximations than the best VCG-based mechanism in the standard model. However, for other problems we give reductions in the Instance Oracle model which prove inapproximability results as strong as those shown in the standard model. These provide more robust hardness results that are not simply artifacts of the asymmetry in the standard model.</p
Temporary equilibrium with learning: The stability of random walk beliefs
Get PDFThis paper examines the stability of deterministic steady-states with a one dimensional state-variable and a smooth, recursive updating rule. It is shown that the only possibly stable steady states are those associated with random walk beliefs, provided there is motion on a center manifold, which is the case when a key parameter is non-zero; In the extant literature, there is no motion on the center manifold (the parameter is zero), a consequence of the specific assumption that the expected value of the state variable next period determines its current value. The stability properties are seen to be robust with respect to small misspecifications in the agents fixed perception of the steady state.Learning, stability, random walk
TEMPORARY EQ'UILIBRIUM DYNAMICS WITH BAYESIAN LEARNING
Get PDFThis paper examines the stability of deterministic steady-states in a class of economies where the state -variable is one dimensional and where agents use Bayesian techniques to form expectations. Thr dynamics with learning are locally convergent if the prior mean is close to a stable perfect foresight root having modulus less than 1 and if the prior beliefs are held with enough confidence. Thr dynamics are however divergent if the prior mean or the variance of the prior distribution is sufficiently large.Stability, Bayesian learning.
The convergence of least squares learning in stochastic temporary equilibrium models
No full textThis paper provides conditions for the almost sure convergence of the least squares learning rule in a stochastic temporary equilibrium model, where regressions are performed on the past values of the endogenous state variable. In contrast to earlier studies, (Evans and Honkapohja, 1998; Marcent and Sargent, 1989), which were local analyses, the dynamics are studied from a global viewpoint, which allows one to obtain an almost sure convergence result without employing projection facilities.Least squares learning, Almost sure convergence.
Tops-Only Domains
No full textIn this paper we consider the standard voting model with a finite set of alternatives A and n voters and address the following question: what are the characteristics of domains D that induce the property that every strategy-proof social choice function f : Dn ! A satisfying unanimity, has the tops-only property? We first impose a minimal richness condition which ensures that for every alternative a, there exists an admissible ordering where a is maximal. We identify conditions on D that are sufficient for strategy-proofness and unanimity to imply tops onlyness in the general case of n voters and in the special case, n = 2. We provide an algorithm for constructing tops-only domains from connected graphs with elements of A as nodes. We provide several applications of our results. Finally, we relax the minimal richness assumption and partially extend our results.
Message Spaces for Perfect Correlated Equilibria
Get PDFWe show that a perfect correlated equilibrium distribution of an N-person game, as defined by Dhillon and Mertens (1996) can be achieved using a finite number of copies of the strategy space as the message space.
Transformations of the State Variable and Learning Dynamics
Get PDFThis article studies dynamics in a model where agents forecast a one dimensional variable via ordinary least squares regressions on the lagged values of the state variable. We study the stability properties of alternative transformations of the state variable that the agent can endogenously set forth. We study the consequences on the economy's stability of the typical transformations that an econometrician would attemp, such as differencing, detrending, or taking instantaneous concave transformations, such as logarithms. Surprinsingly, for the considered class of economies, we found that these transformations are destabilizing, whereas alternative transformations, which an econometrician would never consider, such as convex transformations, are stabilizing. Therefore, we ironically find that in our set-up. an active agent, who is concerned about learning the economy's dynamics and transforms the state variable, in an attempt to improve forecasting, is more likely to deviate from the steady state than a passive agent.Temporary equilibrium, Ordinary least squares learning, Globally stable formulations
FUNCTIONAL SUNSPOT EQUILIBRIA
Get PDFConsider a one step forward looking model where agents believe that the equilibrium values of the state variable are determined by a function whose domain is the current value of the state variable and whose range is the value for the subsequent period. An agent's forecast for the subsequent period uses the belief, where the function that is chosen is allowed to depend on the current realization of an extrinsic random process, and is made with knowledge of the past values of the state variable but not the current value. The paper provides (and characterizes) the conditions for the existence of sunspot equilibria for the model described.extrinsic uncertainty, stochastic equilibria
Functional Sunspot Equilibria
Get PDFConsider a one step forward looking self-referential model with a one dimensional state variable where the information set available to agents when they make their forecast for the next period includes the current realization of an extrinsic random process but does not include the current value of the state variable. Agents thus iterate twice on their beliefs about the law of motion of the system to generate their forecasts; this is as in models of learning and in contrast to the specification considered in the literature on sunspot equilibria where the extrinsic random process is the state variable. This paper demonstrates (and characterizes the conditions for) the existence of self-fulfilling stochastic equilibria with bounded fluctuations driven purely by extrinsic beliefs for the model described above; furthermore, the existence of these equilibria is shown to be independent of the determinacy properties of the perfect foresight dynamics of the model. (Traditional sunspot equilibria appear as a special case of the formulation of the paper). The paper indicates that the problem of multiplicity of rational expectations equilibria in these models is more severe than believed erstwhile.extrinsic uncertainty, stochastic equilibria
- …
