An important issue in multi-agent systems is the exploitation of synergies via coalition formation. We initiate the formal study of fractional hedonic games. In fractional hedonic games, the utility of a player in a c...
详细信息
ISBN:
(纸本)9781634391313
An important issue in multi-agent systems is the exploitation of synergies via coalition formation. We initiate the formal study of fractional hedonic games. In fractional hedonic games, the utility of a player in a coalition structure is the average value he ascribes to the members of his coalition. Among other settings, this covers situations in which there are several types of agents and each agent desires to be in a coalition in which the fraction of agents of his own type is minimal. Fractional hedonic games not only constitute a natural class of succinctly representable coalition formation games, but also provide an interesting framework for network clustering. We propose a number of conditions under which the core of fractional hedonic games is non-empty and provide algorithms for computing a core stable outcome.
We consider the discrete assignment problem in which agents express ordinal preferences over objects and these objects are allocated to the agents in a fair manner. We use the stochastic dominance relation between fra...
详细信息
ISBN:
(纸本)9781634391313
We consider the discrete assignment problem in which agents express ordinal preferences over objects and these objects are allocated to the agents in a fair manner. We use the stochastic dominance relation between fractional or randomized allocations to systematically define varying notions of proportionality and envy-freeness for discrete assignments. The computational complexity of checking whether a fair assignment exists is studied systematically for the fairness notions. We characterize the conditions under which a fair assignment is guaranteed to exist. For a number of fairness concepts, polynomial-time algorithms are presented to check whether a fair assignment exists or not. Our algorithmic results also extend to the case of variable entitlements of agents. Our NP-hardness result, which holds for several variants of envy-freeness, answers an open problem posed by Bouveret, Endriss, and Lang (ECAI 2010).
Economic systems can often be modeled as games involving several agents or players who act according to their own individual interests. Our goal is to understand how various features of an economic system affect its o...
详细信息
Economic systems can often be modeled as games involving several agents or players who act according to their own individual interests. Our goal is to understand how various features of an economic system affect its outcomes, and what may be the best strategy for an individual agent. In this work, we model an economic system as a combination of many bilateral economic opportunities, such as that between a buyer and a seller. The transactions are complicated by the existence of many economic opportunities, and the influence they have on each other. For example, there may be several prospective sellers and buyers for the same item, with possibly differing costs and values. Such a system may be modeled by a network, where the nodes represent players and the edges represent opportunities. We study the effect of network structure on the outcome of bargaining among players, through theoretical modeling of rational agents as well as human subject experiments, when cost and values are public information. The interactions get much more complex when sellers’ cost and buyers’ valuations are private. We design and analyze revenue maximizing strategies for a seller in the presence of many buyers, when the seller has uncertain information or no information about the buyers’ valuations. We focus on developing pricing strategies, and compare their performance against truthful auctions. We also analyze trading strategies in financial markets, where a player quotes both buying and selling prices, again with uncertain or no information about future price evolution of the financial instrument.
The Monte Carlo method provides powerful geometric modeling capabilities for large problem domains in 3-D; therefore, the Monte Carlo method is becoming popular for 3-D fuel depletion analyses to compute quantities of...
详细信息
The Monte Carlo method provides powerful geometric modeling capabilities for large problem domains in 3-D; therefore, the Monte Carlo method is becoming popular for 3-D fuel depletion analyses to compute quantities of interest in spent nuclear fuel including isotopic compositions. The Monte Carlo approach has not been fully embraced due to unresolved issues concerning the effect of Monte Carlo uncertainties on the predicted results. Use of the Monte Carlo method to solve the neutron transport equation introduces stochastic uncertainty in the computed fluxes. These fluxes are used to collapse cross sections, estimate power distributions, and deplete the fuel within depletion calculations; therefore, the predicted number densities contain random uncertainties from the Monte Carlo solution. These uncertainties can be compounded in time because of the extrapolative nature of depletion and decay calculations. The objective of this research was to quantify the stochastic uncertainty propagation of the flux uncertainty, introduced by the Monte Carlo method, to the number densities for the different isotopes in spent nuclear fuel due to multiple depletion time steps. The research derived a formula that calculates the standard deviation in the nuclide number densities based on propagating the statistical uncertainty introduced when using coupled Monte Carlo depletion computer codes. The research was developed with the use of the TRITON/KENO sequence of the SCALE computer code. The linear uncertainty nuclide group approximation (LUNGA) method developed in this research approximated the variance of &psgr;N term, which is the variance in the flux shape due to uncertainty in the calculated nuclide number densities. Three different example problems were used in this research to calculate of the standard deviation in the nuclide number densities using the LUNGA method. The example problems showed that the LUNGA method is capable of calculating the standard deviation of the nuclide
A Hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process with unobserved (hidden) states. HMM is an extremely flexible tool and has been successfull...
详细信息
A Hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process with unobserved (hidden) states. HMM is an extremely flexible tool and has been successfully applied to a wide variety of stochastic modeling tasks. One of the first applications of HMM is speech recognition. Later they came to be known for their applicability in handwriting recognition, part-of-speech tagging and bio-informatics. In this thesis, we will explain the mathematics involved in HMMs and how to efficiently perform HMM computations using dynamic programming (DP) which makes it easy to implement HMM. We will also address the practical issues associated with the use of HMM like numerical scaling of conditional probabilities to model long sequences and smoothing of poor probability estimates caused by sparse training data.
In this thesis I demonstrate a novel application of chaotic dynamics to evolutionary algorithms, specifically in population size management. Typical evolutionary algorithms require a population size to be set as a par...
详细信息
In this thesis I demonstrate a novel application of chaotic dynamics to evolutionary algorithms, specifically in population size management. Typical evolutionary algorithms require a population size to be set as a parameter, which remains constant throughout execution. I created a new algorithm that can vary the population size chaotically or periodically, and do a series of performance tests comparing static, periodic, and chaotic population control. The problems targeted in these tests are chosen from both continuous and discrete multi-dimensional domains. I find that both chaotic and static population control perform well in certain situations; my evidence suggests that periodic population control is rarely a good choice. I also present additional analysis on the effects of the population dynamics and how they relate to mean population size and variance in the performance results
Many classification algorithms were originally designed for fixed-size vectors. Recent applications in text and speech processing and computational biology require however the analysis of variable-length sequences and...
详细信息
Many classification algorithms were originally designed for fixed-size vectors. Recent applications in text and speech processing and computational biology require however the analysis of variable-length sequences and more generally weighted automata. An approach widely used in statistical learning techniques such as Support Vector Machines (SVMs) is that of kernel methods, due to their computational efficiency in high-dimensional feature spaces. We introduce a general family of kernels based on weighted transducers or rational relations, rational kernels, that extend kernel methods to the analysis of variable-length sequences or more generally weighted automata. We show that rational kernels can be computed efficiently using a general algorithm of composition of weighted transducers and a general single-source shortest-distance algorithm. Not all rational kernels are positive definite and symmetric (PDS), or equivalently verify the Mercer condition, a condition that guarantees the convergence of training for discriminant classification algorithms such as SVMs. We present several theoretical results related to PDS rational kernels. We show that under some general conditions these kernels are closed under sum, product, or Kleene-closure and give a general method for constructing a PDS rational kernel from an arbitrary transducer defined on some non-idempotent semirings. We give the proof of several characterization results that can be used to guide the design of PDS rational kernels. We also show that some commonly used string kernels or similarity measures such as the edit-distance, the convolution kernels of Haussler, and some string kernels used in the context of computational biology are specific instances of rational kernels. Our results include the proof that the edit-distance over a non-trivial alphabet is not negative definite, which, to the best of our knowledge, was never stated or proved before. Rational kernels can be combined with SVMs to form efficient
暂无评论