We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the cake. While it is known ...that no finite envy-free algorithm exists in this setting, we exhibit efficient algorithms that produce allocations with low envy among the agents. We then establish NP-hardness results for various decision problems on the existence of envy-free allocations, such as when we fix the ordering of the agents or constrain the positions of certain cuts. In addition, we consider a discretized setting where indivisible items lie on a line and show a number of hardness results extending and strengthening those from prior work. Finally, we investigate connections between approximate and exact envy-freeness, as well as between continuous and discrete cake cutting.
The Complexity of Computing a Nash Equilibrium Daskalakis, Constantinos; Goldberg, Paul W; Papadimitriou, Christos H
SIAM journal on computing,
01/2009, Letnik:
39, Številka:
1
Journal Article
Recenzirano
Odprti dostop
In 1951, John F. Nash proved that every game has a Nash equilibrium. Many algorithms have since been proposed for finding Nash equilibria, but none known to run in polynomial time. In 1991 the ...complexity class PPAD (polynomial parity arguments on directed graphs), for which Brouwer's problem is complete, was introduced, motivated largely by the classification problem for Nash equilibria; but whether the Nash problem is complete for this class remained open. In this paper the authors resolve these questions: They show that finding a Nash equilibrium in three-player games is indeed PPAD-complete; and they do so by a reduction from Brouwer's problem, thus establishing that the two problems are computationally equivalent. They then show how to simulate this graphical game by a three-player game, where each of the three players is essentially a color class in a coloring of the underlying graph. PUBLICATION ABSTRACT
Celotno besedilo
Dostopno za:
CEKLJ, DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, SIK, UILJ, UKNU, UL, UM, UPUK
Consensus Halving for Sets of Items Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi ...
Mathematics of operations research,
11/2022, Letnik:
47, Številka:
4
Journal Article
Recenzirano
Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work shows that, when the resource is represented by an interval, a ...consensus halving with at most
n
cuts always exists but is hard to compute even for agents with simple valuation functions. In this paper, we study consensus halving in a natural setting in which the resource consists of a set of items without a linear ordering. For agents with linear and additively separable utilities, we present a polynomial-time algorithm that computes a consensus halving with at most
n
cuts and show that
n
cuts are almost surely necessary when the agents’ utilities are randomly generated. On the other hand, we show that, for a simple class of monotonic utilities, the problem already becomes polynomial parity argument, directed version–hard. Furthermore, we compare and contrast consensus halving with the more general problem of consensus
k
-splitting, with which we wish to divide the resource into
k
parts in possibly unequal ratios and provide some consequences of our results on the problem of computing small agreeable sets.
Game theory studies situations in which strategic players can modify the state of a given system, in the absence of a central authority. Solution concepts, such as Nash equilibrium, have been defined ...in order to predict the outcome of such situations. In multi-player settings, it has been pointed out that to be realistic, a solution concept should be obtainable via processes that are decentralized and reasonably simple. Accordingly we look at the computation of solution concepts by means of decentralized dynamics. These are algorithms in which players move in turns to decrease their own cost and the hope is that the system reaches an “equilibrium” quickly.
We study these dynamics for the class of opinion games, recently introduced by Bindel et al. 10. These are games, important in economics and sociology, that model the formation of an opinion in a social network. We study best-response dynamics and show upper and lower bounds on the convergence to Nash equilibria. We also study a noisy version of best-response dynamics, called logit dynamics, and prove a host of results about its convergence rate as the noise in the system varies. To get these results, we use a variety of techniques developed to bound the mixing time of Markov chains, including coupling, spectral characterizations and bottleneck ratio.
The ability to control fire was a crucial turning point in human evolution, but the question when hominins first developed this ability still remains. Here we show that micromorphological and Fourier ...transform infrared microspectroscopy (mFTIR) analyses of intact sediments at the site of Wonderwerk Cave, Northern Cape province, South Africa, provide unambiguous evidence—in the form of burned bone and ashed plant remains—that burning took place in the cave during the early Acheulean occupation, approximately 1.0 Ma. To the best of our knowledge, this is the earliest secure evidence for burning in an archaeological context.
Various studies have presented clinical or in vitro evidence linking bacteria to colorectal cancer, but these bacteria have not previously been concurrently quantified by qPCR in a single cohort. We ...quantify these bacteria (Fusobacterium spp., Streptococcus gallolyticus, Enterococcus faecalis, Enterotoxigenic Bacteroides fragilis (ETBF), Enteropathogenic Escherichia coli (EPEC), and afaC- or pks-positive E. coli) in paired tumour and normal tissue samples from 55 colorectal cancer patients. We further investigate the relationship between a) the presence and b) the level of colonisation of each bacterial species with site and stage of disease, age, gender, ethnicity and MSI-status. With the exception of S. gallolyticus, we detected all bacteria profiled here in both tumour and normal samples at varying frequencies. ETBF (FDR = 0.001 and 0.002 for normal and tumour samples) and afaC-positive E. coli (FDR = 0.03, normal samples) were significantly enriched in the colon compared to the rectum. ETBF (FDR = 0.04 and 0.002 for normal and tumour samples, respectively) and Fusobacterium spp. (FDR = 0.03 tumour samples) levels were significantly higher in late stage (III/IV) colorectal cancers. Fusobacterium was by far the most common bacteria detected, occurring in 82% and 81% of paired tumour and normal samples. Fusobacterium was also the only bacterium that was significantly higher in tumour compared to normal samples (p = 6e-5). We also identified significant associations between high-level colonisation by Fusobacterium and MSI-H (FDR = 0.05), age (FDR = 0.03) or pks-positive E. coli (FDR = 0.01). Furthermore, we exclusively identified atypical EPEC in our cohort, which has not been previously reported in association with colorectal cancer. By quantifying colorectal cancer-associated bacteria across a single cohort, we uncovered inter- and intra-individual patterns of colonization not previously recognized, as well as important associations with clinicopathological features, especially in the case of Fusobacterium and ETBF.
Celotno besedilo
Dostopno za:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, SIK, UILJ, UKNU, UL, UM, UPUK
The National Cancer Act of 1971 instigated 50 years of momentum that raised the federal investment in cancer research from $500 million in 1972 to $6.5 billion in 2021. This investment has fueled ...basic, translational, and clinical research that has had a tremendous impact on our understanding of cancer and our ability to prevent, diagnose, and treat it. It has also affected many other diseases.
The National Cancer Act of 1971 instigated 50 years of momentum that raised the federal investment in cancer research from $500 million in 1972 to $6.5 billion in 2021. This investment has fueled basic, translational, and clinical research that has had a tremendous impact on our understanding of cancer and our ability to prevent, diagnose, and treat it. It has also affected many other diseases.
The Middle Stone Age (MSA) is associated with early behavioral innovations, expansions of modern humans within and out of Africa, and occasional population bottlenecks. Several innovations in the MSA ...are seen in an archaeological sequence in the rock shelter Sibudu (South Africa). At ~77,000 years ago, people constructed plant bedding from sedges and other monocotyledons topped with aromatic leaves containing insecticidal and larvicidal chemicals. Beginning at ~73,000 years ago, bedding was burned, presumably for site maintenance. By ~58,000 years ago, bedding construction, burning, and other forms of site use and maintenance intensified, suggesting that settlement strategies changed. Behavioral differences between ~77,000 and 58,000 years ago may coincide with population fluctuations in Africa.
The invention of pottery introduced fundamental shifts in human subsistence practices and sociosymbolic behaviors. Here, we describe the dating of the early pottery from Xianrendong Cave, Jiangxi ...Province, China, and the micromorphology of the stratigraphie contexts of the pottery sherds and radiocarbon samples. The radiocarbon ages of the archaeological contexts of the earliest sherds are 20,000 to 19,000 calendar years before the present, 2000 to 3000 years older than other pottery found in East Asia and elsewhere. The occupations in the cave demonstrate that pottery was produced by mobile foragers who hunted and gathered during the Late Glacial Maximum. These vessels may have served as cooking devices. The early date shows that pottery was first made and used 10 millennia or more before the emergence of agriculture.
Mutations in a recently identified gene HJV (also called HFE2, or repulsive guidance molecule C, RgmC) are the major cause of juvenile hemochromatosis (JH). The protein product of HJV, hemojuvelin, ...contains a C-terminal glycosylphosphatidylinositol anchor, suggesting that it can be present in either a soluble or a cell-associated form. Patients with HJV hemochromatosis have low urinary levels of hepcidin, the principal iron-regulatory hormone secreted by the liver. However, neither the specific role of hemojuvelin in maintaining iron homeostasis nor its relationship to hepcidin has been experimentally established. In this study we used hemojuvelin-specific siRNAs to vary hemojuvelin mRNA concentration and showed that cellular hemojuvelin positively regulated hepcidin mRNA expression, independently of the interleukin 6 pathway. We also showed that recombinant soluble hemojuvelin (rs-hemojuvelin) suppressed hepcidin mRNA expression in primary human hepatocytes in a log-linear dose-dependent manner, suggesting binding competition between soluble and cell-associated hemojuvelin. Soluble hemojuvelin was found in human sera at concentrations similar to those required to suppress hepcidin mRNA in vitro. In cells engineered to express hemojuvelin, soluble hemojuvelin release was progressively inhibited by increasing iron concentrations. We propose that soluble and cell-associated hemojuvelin reciprocally regulate hepcidin expression in response to changes in extracellular iron concentration. (Blood. 2005;106:2884-2889)
PDF
