Hard instances of algorithms and proof systems

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

A topological proof that surface relators are test words

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

A proof that all Seifert 3-manifold groups and all virtual surface groups are conjugacy separable

We prove that the fundamental group of any Seifert 3-manifold is conjugacy separable. That is, conjugates may be distinguished infinite quotients or, equivalently, conjugacy classes are closed in the pro-finite topology.

On group strategy-proof mechanisms for a many-to-one matching model

For the many-to-one matching model in which firms have substitutable and quota q-separable preferences over subsets of workers we show that the workers-optimal stable mechanism is group strategy-proof for the workers. In order to prove this result, we also show that under this domain of preferences (which contains the domain of responsive preferences of the college admissions problem) the workers-optimal stable matching is weakly Pareto optimal for the workers and the Blocking Lemma holds as well. We exhibit an example showing that none of these three results remain true if the preferences of firms are substitutable but not quota q-separable.

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.

Individual versus group strategy-proofness: when do they coincide?

A social choice function is group strategy-proof on a domain if no group of agents can manipulate its final outcome to their own benefit by declaring false preferences on that domain. Group strategy-proofness is a very attractive requirement of incentive compatibility. But in many cases it is hard or impossible to find nontrivial social choice functions satisfying even the weakest condition of individual strategy-proofness. However, there are a number of economically significant domains where interesting rules satisfying individual strategy-proofness can be defined, and for some of them, all these rules turn out to also satisfy the stronger requirement of group strategy-proofness. This is the case, for example, when preferences are single-peaked or single-dipped. In other cases, this equivalence does not hold. We provide sufficient conditions defining domains of preferences guaranteeing that individual and group strategy-proofness are equivalent for all rules defined on the

Strategy-proof social choice

This paper surveys the literature on strategy-proofness from a historical perspective. While I discuss the connections with other works on incentives in mechanism design, the main emphasis is on social choice models. This article has been prepared for the Handbook of Social Choice and Welfare, Volume 2, Edited by K. Arrow, A. Sen and K. Suzumura

Banning Obsolete Weapons or Reshaping Perceptions of Military Utility: Discursive Dynamics in Weapons Prohibitions

The paper focuses on the argumentative process through which new international norms prohibiting the use of weapons causing severe civilian harm emerge. It examines the debate surrounding the use and usefulness of landmines and cluster munitions and traces the process through which NGOs change conceptions of military utility and effectiveness of certain weapons by highlighting their humanitarian problems and questioning their military value. By challenging military thinking on these issues, NGOs redefine the terms of the debate – from a commonplace practice, the use of such weapons becomes controversial and military decisions need to be justified. The argument-counterargument dynamic shifts the burden of proof of the necessity and safety of the weapons to the users. The process witnesses the ability of NGOs to influence debates on military issues despite their disadvantaged position in hard security issue areas. It also challenges realist assumptions that only weapons that are obsolete or low-cost force equalizers for weak actors can be banned. To the contrary, the paper shows that in the case of landmines and cluster munitions, defining the military (in)effectiveness of the weapons is part and parcel of the struggle for their prohibition.

Group strategy-proof social choice functions with binary ranges and arbitrary domains: characterization results

We define different concepts of group strategy-proofness for social choice functions. We discuss the connections between the defined concepts under different assumptions on their domains of definition. We characterize the social choice functions that satisfy each one of them and whose ranges consist of two alternatives, in terms of two types of basic properties.

On p-optimal proof systems and logics for PTIME

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

On slicewise monotone parameterized problems and optimal proof systems for TAUT

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

Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs

In a seminal paper [10], Weitz gave a deterministic fully polynomial approximation scheme for counting exponentially weighted independent sets (which is the same as approximating the partition function of the hard-core model from statistical physics) in graphs of degree at most d, up to the critical activity for the uniqueness of the Gibbs measure on the innite d-regular tree. ore recently Sly [8] (see also [1]) showed that this is optimal in the sense that if here is an FPRAS for the hard-core partition function on graphs of maximum egree d for activities larger than the critical activity on the innite d-regular ree then NP = RP. In this paper we extend Weitz's approach to derive a deterministic fully polynomial approximation scheme for the partition function of general two-state anti-ferromagnetic spin systems on graphs of maximum degree d, up to the corresponding critical point on the d-regular tree. The main ingredient of our result is a proof that for two-state anti-ferromagnetic spin systems on the d-regular tree, weak spatial mixing implies strong spatial mixing. his in turn uses a message-decay argument which extends a similar approach proposed recently for the hard-core model by Restrepo et al [7] to the case of general two-state anti-ferromagnetic spin systems.

Political Competition in Hard Times

This paper analyzes a spatial model of political competition between two policy- motivated parties in hard times of crisis. Hard times are modeled in terms of policy- making costs carried by a newly elected party. The results predict policy divergence in equilibrium. If the ideological preferences of parties are quite diverse and extreme, there is a unique equilibrium in which the parties announce symmetric platforms and each party wins with probability one half. If one party is extreme while the other is more moderate, there is a unique equilibrium in which the parties announce asymmetric platforms. If the preferred policies of the parties are not very distinct, there are two equilibria with asymmetric platforms. An important property of equilibrium with asymmetric platforms is that a winning party necessarily announces its most preferred policy as a platform. JEL classification: D72. Keywords: Spatial model; Political competition; Two-party system; Policy-motivated parties; Hard times; Crisis.

Vertical Syndication-Proof Competitive Prices in Multilateral Markets

[eng] A multi-sided Böhm-Bawerk assignment game (Tejada, to appear) is a model for a multilateral market with a finite number of perfectly complementary indivisible commodities owned by different sellers, and inflexible demand and support functions. We show that for each such market game there is a unique vector of competitive prices for the commodities that is vertical syndication-proof, in the sense that, at those prices, syndication of sellers each owning a different commodity is neither beneficial nor detrimental for the buyers. Since, moreover, the benefits obtained by the agents at those prices correspond to the nucleolus of the market game, we provide a syndication-based foundation for the nucleolus as an appropriate solution concept for market games. For different solution concepts a syndicate can be disadvantageous and there is no escape to Aumman’s paradox (Aumann, 1973). We further show that vertical syndicationproofness and horizontal syndication-proofness – in which sellers of the same commodity collude – are incompatible requirements under some mild assumptions. Our results build on a self-interesting link between multi-sided Böhm-Bawerk assignment games and bankruptcy games (O’Neill, 1982). We identify a particular subset of Böhm-Bawerk assignment games and we show that it is isomorphic to the whole class of bankruptcy games. This isomorphism enables us to show the uniqueness of the vector of vertical syndication-proof prices for the whole class of Böhm-Bawerk assignment market using well-known results of bankruptcy problems.