Double implementation in a market for indivisible goods with a price constraint

I consider the problem of assigning agents to objects where each agent must pay the price of the object he gets and prices must sum to a given number. The objective is to select an assignment-price pair that is envy-free with respect to the true preferences. I prove that the proposed mechanism will implement both in Nash and strong Nash the set of envy-free allocations. The distinguishing feature of the mechanism is that it treats the announced preferences as the true ones and selects an envy-free allocation with respect to the announced preferences.

Bribe-proof rules in the division problem

The division problem consists of allocating an amount of a perfectly divisible good among a group of n agents with single-peaked preferences. A rule maps preference profiles into n shares of the amount to be allocated. A rule is bribe-proof if no group of agents can compensate another agent to misrepresent his preference and, after an appropriate redistribution of their shares, each obtain a strictly preferred share. We characterize all bribe-proof rules as the class of efficient, strategy-proof, and weak replacement monotonic rules. In addition, we identify the functional form of all bribe-proof and tops-only rules.

A maximal domain of preferences for tops-only rules in the division problem

The division problem consists of allocating an amount M of a perfectly divisible good among a group of n agents. Sprumont (1991) showed that if agents have single-peaked preferences over their shares, the uniform rule is the unique strategy-proof, efficient, and anonymous rule. Ching and Serizawa (1998) extended this result by showing that the set of single-plateaued preferences is the largest domain, for all possible values of M, admitting a rule (the extended uniform rule) satisfying strategy-proofness, efficiency and symmetry. We identify, for each M and n, a maximal domain of preferences under which the extended uniform rule also satisfies the properties of strategy-proofness, efficiency, continuity, and "tops-onlyness". These domains (called weakly single-plateaued) are strictly larger than the set of single-plateaued preferences. However, their intersection, when M varies from zero to infinity, coincides with the set of single-plateaued preferences.

Generalized property R and the Schoenflies Conjecture

There is a relation between the generalized Property R Conjecture and the Schoenflies Conjecture that suggests a new line of attack on the latter. The new approach gives a quick proof of the genus 2 Schoenflies Conjecture and suffices to prove the genus 3 case, even in the absence of new progress on the generalized Property R Conjecture.

Generalized backward doubly stochastic differential equations and SPDEs with nonlinear Neumann boundary conditions

In this paper, a new class of generalized backward doubly stochastic differential equations is investigated. This class involves an integral with respect to an adapted continuous increasing process. A probabilistic representation for viscosity solutions of semi-linear stochastic partial differential equations with a Neumann boundary condition is given.

Normal forms for rational difference equations with applications to the global periodicity problem

We propose a classification and derive the associated normal forms for rational difference equations with complex coefficients. As an application, we study the global periodicity problem for second order rational difference equations with complex coefficients. We find new necessary conditions as well as some new examples of globally periodic equations.

Generating trees for permutations avoiding generalized patterns

We construct generating trees with with one, two, and three labels for some classes of permutations avoiding generalized patterns of length 3 and 4. These trees are built by adding at each level an entry to the right end of the permutation, which allows us to incorporate the adjacency condition about some entries in an occurrence of a generalized pattern. We use these trees to find functional equations for the generating functions enumerating these classes of permutations with respect to different parameters. In several cases we solve them using the kernel method and some ideas of Bousquet-Mélou [2]. We obtain refinements of known enumerative results and find new ones.

Generalized factor models: a bayesian approach

There is recent interest in the generalization of classical factor models in which the idiosyncratic factors are assumed to be orthogonal and there are identification restrictions on cross-sectional and time dimensions. In this study, we describe and implement a Bayesian approach to generalized factor models. A flexible framework is developed to determine the variations attributed to common and idiosyncratic factors. We also propose a unique methodology to select the (generalized) factor model that best fits a given set of data. Applying the proposed methodology to the simulated data and the foreign exchange rate data, we provide a comparative analysis between the classical and generalized factor models. We find that when there is a shift from classical to generalized, there are significant changes in the estimates of the structures of the covariance and correlation matrices while there are less dramatic changes in the estimates of the factor loadings and the variation attributed to common factors.

The word problem distinguishes counter languages

Counter automata are more powerful versions of finite state automata where addition and subtraction operations are permitted on a set of n integer registers, called counters. We show that the word problem of Zn is accepted by a nondeterministic m-counter automaton if and only if m &= n.

On the complexity of the Whitehead minimization problem

The Whitehead minimization problem consists in finding a minimum size element in the automorphic orbit of a word, a cyclic word or a finitely generated subgroup in a finite rank free group. We give the first fully polynomial algorithm to solve this problem, that is, an algorithm that is polynomial both in the length of the input word and in the rank of the free group. Earlier algorithms had an exponential dependency in the rank of the free group. It follows that the primitivity problem – to decide whether a word is an element of some basis of the free group – and the free factor problem can also be solved in polynomial time.

Orbit decidability and the conjugacy problem for some extensions of groups

"Vegeu el resum a l'inici del document del fitxer adjunt."

The generic Hanna Neumann conjecture and post correspondence problem

"Vegeu el resum a l'inici del document del fitxer adjunt."

Generalized multiresolution analyses with given multiplicity functions

Generalized multiresolution analyses are increasing sequences of subspaces of a Hilbert space H that fail to be multiresolution analyses in the sense of wavelet theory because the core subspace does not have an orthonormal basis generated by a fixed scaling function. Previous authors have studied a multiplicity function m which, loosely speaking, measures the failure of the GMRA to be an MRA. When the Hilbert space H is L2(Rn), the possible multiplicity functions have been characterized by Baggett and Merrill. Here we start with a function m satisfying a consistency condition which is known to be necessary, and build a GMRA in an abstract Hilbert space with multiplicity function m.

Symmetry for a Dirichlet-Neumann problem arising in water waves

"Vegeu el resum a l'inici del document del fitxer adjunt."