Search

Sequential allocation is a simple allocation mechanism in which agents are given pre-specified turns in which they take one item among those that are still available. It has long been known that sequential allocation is not strategyproof. This raises the question of the complexity of computing a preference report that yields a higher utility than the truthful preference. We show that the problem is NP-complete for one manipulating agent with additive utilities and several non-manipulating agents. In doing so, we correct a wrong claim made in a previous paper. We then give two additional results. First, we present a polynomial-time algorithm for optimal manipulation when the manipulator has additive binary utilities. Second, we consider a stronger notion of manipulation whereby the untruthful outcome yields more utility than the truthful outcome for all utilities consistent with the ordinal preferences; for this notion, we show that a manipulation, if any, can be computed in polynomial time.

The global market in antiquities has been described as a grey market. We provide a breakdown of the meanings and implications of this greyness. Usually the term refers to the mixing of recently looted antiquities with those that can be sold legally, thus the antiquities market is grey because illicit objects are sold via a public and purportedly legitimate network of dealers and auction houses. This is supported by a second form of greyness: the ethically grey status of individual looted objects after time and their passage through jurisdictions via multiple trades obscures or overwrites their illicit origins. It is also supported by a greying of ethical judgment, achieved through a discourse that permits the purchase of illicit objects in constructed circumstances of “saving” or “preserving” artifacts.

In this thesis we consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from $n$ agents. The problem has received attention in computer science, mathematics, and economics. It has been a major open problem whether there exists a discrete and bounded envy-free protocol. First we show present a protocol for $4$ agents which solves the problem using $203$ cuts. We then generalise this by proposing a discrete and bounded envy-free protocol for any number of agents. The maximum number of queries required by the protocol is $n^{n^{n^{n^{n^n}}}}$. We additionally show that even if we do not run our protocol to completion, it can find in at most $n^3{(n^2)}^n$ queries a partial allocation of the cake that achieves proportionality (each agent gets at least $\frac{1}{n}$ of the value of the whole cake) and envy-freeness. We also show that an envy-free partial allocation can be computed in at most $n^3{(n^2)}^n$ queries such that each agent gets a connected piece that gives the agent at least $\frac{1}{3n}$ of the value of the whole cake. Finally we give a new lower bound of $\Omega(n^3)$ on the number of queries required to allocate cake in an envy-free way.

In this study, we aimed to analyze the global response to iron in the broad-range host pathogen Vibrio vulnificus under the hypothesis that iron is one of the main signals triggering survival mechanisms both inside and outside its hosts. To this end, we selected a strain from the main zoonotic clonal-complex, obtained a mutant in the ferric-uptake-regulator (Fur), and analyzed their transcriptomic profiles in both iron-excess and iron-poor conditions by using a strain-specific microarray platform. Among the genes differentially expressed, we identified around 250 as putatively involved in virulence and survival-related mechanisms. Then, we designed and performed a series of in vivo and in vitro tests to find out if the processes highlighted by the microarray experiments were in fact under iron and/or Fur control. Our results support the hypothesis that iron acts as a niche marker, not always through Fur, for V.vulnificus controlling its entire life cycle. This ranges from survival in the marine environment, including motility and chemotaxis, to survival in the blood of their hosts, including host-specific mechanisms of resistance to innate immunity. These mechanisms allow the bacterium to multiply and persist inside and between their hosts.

1.Environmental temperature gradients provide habitat structure in which fish orientate and individual thermal choice may reflect an essential integrated response to the environment. The use of subtle thermal gradients likely impacts upon specific physiological and behavioural processes reflected as a suite of traits described by animal personality. In this study we examine the relationship between thermal choice, animal personality and the impact of infection upon this interaction. 2.We predicted that thermal choice in Nile tilapiaOreochromis niloticusreflects distinct personality traits and that under a challenge individuals exhibit differential thermal distribution. 3.Nile Tilapia were screened following two different protocols: 1) a suite of individual behavioural tests to screen for personality and 2) thermal choice in a custom-built tank with a thermal gradient (TCHtank) ranging from 21 to 33 °C. A first set of fish were screened for behaviour and then thermal preference and a second set were tested in the opposite fashion; thermal then behaviour. The final thermal distribution of the fish after 48 h was assessed reflecting final thermal preferendum. Additionally, fish were then challenged using a bacterialStreptococcus iniaemodel infection to assess the behavioural fever response of proactive and reactive fish. 4.Results showed that individuals with preference for higher temperatures were also classified as proactive with behavioural tests and reactive contemporaries chose significantly lower water temperatures. All groups exhibited behavioural fever recovering personality-specific thermal preferences after 5 days. 5.Our results show that thermal preference can be used as a proxy to assess personality traits in Nile tilapia and it is a central factor to understand the adaptive meaning of animal personality within a population. Importantly, response to infection by expressing behavioural fever overrides personality related thermal choice.

A chapter exploring the nature and extent of organised crime in Scotland and charting developments and innovation in policing and criminal justice responses and policy.

14 pages, 4 figures, 1 table, Common carp Cyprinus carpio displaying proactive or reactive stress coping styles were acclimated to two environmental regimes (low oxygen and low temperature), and selected groups were tested for response to an inflammatory challenge (Escherichia coli lipopolysaccharide, LPS). Plasma glucose and lactate levels were measured, as were selected C. carpio-specific messenger (m)RNA transcript abundance, including cortisol receptor (CR), enolase (ENO), glyceraldehyde 3-phosphate dehydrogenase (GAPDH) and interleukin-1-beta (IL1β) was measured in individual whole brain samples. Basal levels (in sham injected fish held in normoxic conditions at 25° C) of plasma lactate and glucose differed between coping styles, being significantly lower in proactive individuals. Both variables increased in response to LPS challenge, with the exception of plasma glucose in reactive fish held in hypoxia. Baseline levels of gene expression under control conditions were significantly different for GAPDH between behavioural phenotypes. The responses to experimental challenge were sometimes diametrically opposed between stress-coping styles in a transcript-specific manner. For CR and GAPDH, for example, the response to LPS injection in hypoxia were opposite between proactive and reactive animals. Proactive fish showed decreased CR and increased GAPDH, whereas reactive showed the opposite response. These results further highlight that screening for stress-coping styles prior to experiments in adaptive physiology can significantly affect the interpretation of data obtained. Further, this leads to a more finely tuned analytical output providing an improved understanding of variation in individual responses to both environmental and inflammatory challenge., This study was partly supported by the Consolider-Ingenio Programme 2010, project CSD2007-0002 funded by the Spanish Ministry of Science and Education, Spain to S.M. F.A.H. and S.K. received financial support from the Commission of the European Communities, as part of SEAFOODPlus; project no. 506359. D.M.C. is funded by the Spanish Ministerio de Educación y Ciencia; Grant FPU; AP2006-02715

The probabilistic serial (PS) rule is one of the most prominent randomized rules for the assignment problem. It is well-known for its superior fairness and welfare properties. However, PS is not immune to manipulative behaviour by the agents. We initiate the study of the computational complexity of an agent manipulating the PS rule. We show that computing an expected utility better response is NP- hard. On the other hand, we present a polynomial-time algorithm to compute a lexicographic best response. For the case of two agents, we show that even an expected utility best response can be computed in polynomial time. Our result for the case of two agents relies on an interesting connection with sequential allocation of discrete objects., arXiv admin note: substantial text overlap with arXiv:1401.6523

The probabilistic serial (PS) rule is a prominent randomized rule for assigning indivisible goods to agents. Although it is well known for its good fairness and welfare properties, it is not strategyproof. In view of this, we address several fundamental questions regarding equilibria under PS. Firstly, we show that Nash deviations under the PS rule can cycle. Despite the possibilities of cycles, we prove that a pure Nash equilibrium is guaranteed to exist under the PS rule. We then show that verifying whether a given profile is a pure Nash equilibrium is coNP-complete, and computing a pure Nash equilibrium is NP-hard. For two agents, we present a linear-time algorithm to compute a pure Nash equilibrium which yields the same assignment as the truthful profile. Finally, we conduct experiments to evaluate the quality of the equilibria that exist under the PS rule, finding that the vast majority of pure Nash equilibria yield social welfare that is at least that of the truthful profile., Comment: arXiv admin note: text overlap with arXiv:1401.6523, this paper supersedes the equilibria section in our previous report arXiv:1401.6523

In the random assignment problem, objects are randomly assigned to agents keeping in view the agents' preferences over objects. A random assignment specifies the probability of an agent getting an object. We examine the structural and computational aspects of ex post efficiency of random assignments. We first show that whereas an ex post efficient assignment can be computed easily, checking whether a given random assignment is ex post efficient is NP-complete. Hence implementing a given random assignment via deterministic Pareto optimal assignments is NP-hard. We then formalize another concept of efficiency called robust ex post efficiency that is weaker than stochastic dominance efficiency but stronger than ex post efficiency. We present a characterization of robust ex post efficiency and show that it can be tested in polynomial time if there are a constant number of agent types. It is shown that the well-known random serial dictatorship rule is not robust ex post efficient. Finally, we show that whereas robust ex post efficiency depends solely on which entries of the assignment matrix are zero/non-zero, ex post efficiency of an assignment depends on the actual values.