Sat, 26 Jul 2008 04:32:20 BST CiteULike: AbnerCYH's game http://www.citeulike.org/user/AbnerCYH/tag/game CiteULike.org en-gb Copyright © 2004-2008 citeulike.org http://www.citeulike.org/user/AbnerCYH/article/3038205 <i>(2002), pp. 389-395.</i> Market Equilibrium via a Primal-Dual-Type Algorithm Nikhil Devanur Christos Papadimitriou Amin Saberi Vijay Vazirani (2002), pp. 389-395. 2008-07-24T04:40:27-00:00 2002 389 395 IEEE Computer Society algorithms game graph optimization http://www.citeulike.org/user/AbnerCYH/article/2878470 <i>SIGACT News, Vol. 35, No. 4. (December 2004), pp. 23-37.</i> The computation of market equilibria Bruno Codenotti Sriram Pemmaraju Kasturi Varadarajan doi:10.1145/1054916.1054927 SIGACT News, Vol. 35, No. 4. (December 2004), pp. 23-37. 2008-06-10T02:59:35-00:00 2004 SIGACT News 0163-5700 35 4 23 37 ACM algorithms complexity game http://www.citeulike.org/user/AbnerCYH/article/2814729 <i>Theoretical Computer Science, Vol. 399, No. 3. (6 June 2008), pp. 236-245.</i><br /><br />Graph searching encompasses a wide variety of combinatorial problems related to the problem of capturing a fugitive residing in a graph using the minimum number of searchers. In this annotated bibliography, we give an elementary classification of problems and results related to graph searching and provide a source of bibliographical references on this field. An annotated bibliography on guaranteed graph searching Fedor Fomin Dimitrios Thilikos doi:10.1016/j.tcs.2008.02.040 Theoretical Computer Science, Vol. 399, No. 3. (6 June 2008), pp. 236-245. 2008-05-20T03:03:07-00:00 2008 Theoretical Computer Science 399 3 236 245 algorithms game graph http://www.citeulike.org/user/AbnerCYH/article/411634 <i>(2001)</i><br /><br />Boosting is a general method for improving the accuracy of any given learning algorithm. Focusing primarily on the AdaBoost algorithm, this chapter overviews some of the recent work on boosting including analyses of AdaBoost's training error and generalization error; boosting's connection to game theory and linear programming; the relationship between boosting and logistic regression; extensions of AdaBoost for multiclass classification problems; methods of incorporating human knowledge... The boosting approach to machine learning: An overview R Schapire (2001) 2005-11-30T08:57:07-00:00 2001 algorithms game kdd stochastic http://www.citeulike.org/user/AbnerCYH/article/2501046 <i>Operations Research Letters, Vol. 36, No. 2. (March 2008), pp. 173-176.</i><br /><br />The principal aim of this paper is to show that every weakly efficient solution of a lexicographic quasiconvex multicriteria optimization problem actually is an efficient (Pareto) solution of a reduced problem, obtained from the original one by selecting a certain number of criteria, not exceeding the Helly number of the solution space. Involving the Helly number in Pareto reducibility Nicolae Popovici doi:10.1016/j.orl.2007.09.002 Operations Research Letters, Vol. 36, No. 2. (March 2008), pp. 173-176. 2008-03-10T14:12:33-00:00 2008 Operations Research Letters 36 2 173 176 algorithms economic game http://www.citeulike.org/user/AbnerCYH/article/2197274 <i>Algorithmica</i><br /><br />Abstract   We develop an algorithm for computing the equilibrium price in the Fisher’s exchange market model with logarithmic utility functions. The algorithm is proved to converge to the equilibrium price in finite time and performs well in experimental tests. A Primal-Dual Algorithm for the Computation of Market Equilibrium with Logarithmic Utility Functions Li-Sha Huang doi:10.1007/s00453-007-9102-x Algorithmica 2008-01-05T15:53:58-00:00 Algorithmica algorithms game math http://www.citeulike.org/user/AbnerCYH/article/1847781 <i>(24 September 2007)</i><br /><br />In the last few years game theory has had a substantial impact on computer science, especially on Internet- and e-commerce-related issues. More than 40 of the top researchers in this field have written chapters that go from the foundations to the state of the art. Basic chapters on algorithmic methods for equilibria, mechanism design and combinatorial auctions are followed by chapters on incentives and pricing, cost sharing, information markets and cryptography and security. Students, researchers and practitioners alike need to learn more about these fascinating theoretical developments and their widespread practical application. Algorithmic Game Theory (24 September 2007) 2007-10-31T16:34:54-00:00 2007 Cambridge University Press algorithms game optimization http://www.citeulike.org/user/AbnerCYH/article/1778523 <i>Algorithmica</i><br /><br />Abstract   We study the complexity issues for Walrasian equilibrium in a special case of combinatorial auction, called single-minded auction, in which every participant is interested in only one subset of commodities. Chen et al. (J. Comput. Syst. Sci. 69(4): 675–687, 2004) showed that it is NP-hard to decide the existence of a Walrasian equilibrium for a single-minded auction and proposed a notion of approximate Walrasian equilibrium called relaxed Walrasian equilibrium. We show that every single-minded auction has a relaxed Walrasian equilibrium that satisfies at least two-thirds of the participants, proving a conjecture posed in Chen et al. (J. Comput. Syst. Sci. 69(4): 675–687, 2004). Motivated by practical considerations, we introduce another concept of approximate Walrasian equilibrium called weak Walrasian equilibrium. We show NP-completeness and hardness of approximation results for weak Walrasian equilibria. In search of positive results, we restrict our attention to the tollbooth problem (Guruswami et al. in Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 1164–1173, 2005), where every participant is interested in a single path in some underlying graph. We give a polynomial time algorithm to determine the existence of a Walrasian equilibrium and compute one (if it exists), when the graph is a tree. However, the problem is still NP-hard for general graphs. Walrasian Equilibrium: Hardness, Approximations and Tractable Instances Ning Chen Atri Rudra doi:10.1007/s00453-007-9103-9 Algorithmica 2007-10-17T06:35:38-00:00 Algorithmica algorithms complexity economic game optimization