1,721,009 research outputs found
Quality of Equilibria in Resource Allocation Games
Get PDFIn situations where multiple parties are involved, individual selfish decisions result in outcomes that rarely align with what is best for society. In order to compare the quality of these outcomes with what is best for society, we need to predict which outcomes will occur. In game theory, the classic prediction is the Nash equilibrium, an outcome where no party can improve by deviating unilaterally. Nash equilibria are based on the assumption that parties choose their actions simultaneously. However, sequential decisions, where parties anticipate each other’s actions, are often considered more natural, and lead to different equilibria. We consider multiple equilibrium concepts for a variety of classes of games. The main class we consider, is the class of congestion games. Applications of congestion games include the allocation of scarce natural resources, the design of road networks in order to mitigate delays due to traffic jams, and the design of internet protocols that result in more efficient use of the available bandwidth
Smoothed analysis of belief propagation and minimum-cost flow algorithms
Get PDFAlgorithms that have good worst-case performance are not always the ones that perform best in practice. The smoothed analysis framework is a way of analyzing algorithms that usually matches practical performance of these algorithms much better than worst-case analysis. In this thesis we apply smoothed analysis to two classes of algorithms: minimum-cost flow algorithms and belief propagation algorithms. The minimum-cost flow problem is the problem of sending a prescribed amount of flow through a network in the cheapest possible way. It is very well known, and over the last half a century many algorithms have been developed to solve it. We analyze three of these algorithms (the successive shortest path algorithm, the minimum-mean cycle canceling algorithm, and the network simplex algorithm) in the framework of smoothed analysis and show lower and upper bounds on their smoothed running-times. The belief propagation algorithm is a message-passing algorithm for solving probabilistic inference problems. Because of its simplicity, it is very popular in practice. However, its theoretical behavior is not well understood. To obtain a better theoretical understanding of the belief propagation algorithm, we apply it to several well-studied optimization problems. We analyze under which conditions the belief propagation algorithm converges to the correct solution and we analyze its smoothed running-time
Complaint, compromise and solution concepts for cooperative games
Get PDFThis thesis mainly focuses on solution concepts for cooperative games. We investigate the solution concepts concerning the complaints of players. Motivated by the work the procedural values, we study the formation of the grand coalition and define a new kind of complaint for individual players. We then reveal that the solutions for both models coincide with the ENSC value either based on the lexicographic criterion or the least square criterion. We propose the so called alpha-ENSC value by considering the egoism of players. We implement the alpha-ENSC value by means of optimization and also the satisfier of a set of properties. Following the similar idea, we propose two kinds of complaints for coalitions and define the optimal compromise values based on the lexicographic criterion. It turns out that the optimal compromise values coincides with the ENSC value and the CIS value under corresponding complaint. We show an application of the previous mentioned method. We introduce and axiomatize a class of cost sharing methods for polluted river sharing systems that consists of the convex combinations of the known Local Responsibility Sharing (LR) method and the Upstream Equal Sharing (UES) method. We also deals with the solution concepts based on the compromise between the ideal and minimal payoffs for players, which is inspired by the definition of the tau value but in a more general way. We reveal the relations between the general compromise value with several well known solution concepts. Furthermore, we investigate the solution concepts for cooperative games with stochastic payoffs. We focus on a subset of all allocations and introduce the stochastic complaint for players. Under the least square criterion, the most stable solutions and the fairest solutions are proposed. Moreover, the optimal solution stays the same whether the optimization model depends on the coalitions or individual players
Fractional Programming in Cooperative Games
Get PDFCooperation of individuals or institutions is often coupled with benefits that can be regarded as the monetary worth or outcome of the cooperation. Therefore, the problem naturally arises how to allocate the total outcome among institutions or individuals in a fair way. Such allocation problems are studied within cooperative game theory. A general idea is to find an allocation which guarantees a payoff no less than the earning of these players working without cooperation. This motivates a classical concept for “fair‿ division, the “core‿ allocation (Chapter 2) for all individuals. However, such core allocations are not always guaranteed in many practical and theoretical cases. Even if there exists a core allocation, finding such an allocation is often hard. For example, the bin packing game (Chapter 3) does not always admit a nonempty core and finding a core allocation for the bin packing game is an NP-hard problem. In case the core is empty, in this thesis, we adopt the tax model, i.e., players can only keep a (1 − e) fraction of their total earning if they work on their own, where is called the taxation rate. This is the general idea behind sales and tax, which is quite natural and acceptable. Based on this model, we aim at finding an e-core allocation such that the taxation rate is as small as possible
Waarom wiskunde? Omdat je het spel strategisch wilt spelen
Get PDFIn een strategisch spel zijn alle spelers egoïsten. Iedereen speelt voor zichzelf. De uitkomst kan slecht zijn voor de maatschappij. Hoe slecht? Wiskundigen kunnen dat berekenen, doceert Marc Uetz
Matrix Approach to Cooperative Game Theory
Get PDFIn this monograph, the algebraic representation and the matrix approach are applied to study linear operators on the game space, more precisely, linear transformations on games and linear values. In terms of the essential notion of a coalitional matrix, these linear operators are represented algebraically by products of the corresponding coalitional matrix and the worth vector (representing the game). We perform a matrix analysis in the setting of cooperative game theory, to study axiomatizations of linear values, by investigating appropriate properties of these representation matrices. Particularly, the Shapley value is the most important representative. In summary, the concepts of eigenvalues, eigenvectors, null space, the diagonalization procedure and the similarity property for matrices, the system of linear equations and its solution set, the Moebius transformation and the complementary Moebius transformation, the basis for a linear space and so on, can be applied successfully to cooperative game theory. We conclude that the matrix analysis is a new and powerful technique for research in the field of cooperative game theory
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Copositive Programming and Related Problems
Get PDFFoundation of mathematical optimization relies on the urge to utilize available resources to their optimum. This leads to mathematical programs where an objective function is optimized over a set of constraints. The set of constraints can represent different structures, for example, a polyhedron, a box or a cone. Mathematical programs with cone constraints are called cone programs. A sub area of mathematical optimization is the one where the number of variables isfinite while the number of constraints is infinite, known as semi-infinite programming. In the first section of Chapter 1 we will start with a general introduction into the thesis. In the second section some basic definitions are given which are used throughout the thesis. The third and the fourth section provide a brief review of results on cone programming and semi-infinite programming, respectively. In section five we will briefly discuss cone programming relaxations. In the last section we shall give an overview over results presented in the thesis
Bipartite Graphs and the Decomposition of Systems of Equations
Get PDFSolving large systems of equations is a problem often encountered in engineering disciplines. However, as such systems grow, the effort required for finding a solution to them increases as well. In order to be able to cope with ever larger systems of equations, some form of decomposition is needed. By decomposing a large system into smaller subsystems, the total effort required for finding a solution may decrease. However, whether this is really the case of course depends on the additional effort required for obtaining the decomposition itself. In this thesis several aspects of the difficulty of obtaining such decompositions are explored
- …
