File Download
Supplementary

Citations:
 Appears in Collections:
postgraduate thesis: Linear programming techniques for algorithms with applications in economics
Title  Linear programming techniques for algorithms with applications in economics 

Authors  
Advisors  Advisor(s):Chan, HTH 
Issue Date  2014 
Publisher  The University of Hong Kong (Pokfulam, Hong Kong) 
Citation  Chen, F. [陳飛]. (2014). Linear programming techniques for algorithms with applications in economics. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5312337 
Abstract  We study algorithms and models for several economicsrelated problems from the perspective of linear programming.
In network bargaining games, stable and balanced outcomes have been investigated in previous work. However, existence of such outcomes requires that the linear program relaxation of a certain maximum matching problem has integral optimal solution. We propose an alternative model for network bargaining games in which each edge acts as a player, who proposes how to split the weight of the edge among the two incident nodes. We show that the distributed protocol by Kanoria et. al can be modified to be run by the edge players such that the configuration of proposals will converge to a pure Nash Equilibrium, without the linear program integrality gap assumption. Moreover, ambiguous choices can be resolved in a way such that there exists a Nash Equilibrium that will not hurt the social welfare too much.
In the oblivious matching problem, an algorithm aims to find a maximum matching while it can only makes (random) decisions that are essentially oblivious to the input graph. Any greedy algorithm can achieve performance ratio 0:5, which is the expected number of matched nodes to the number of nodes in a maximum matching. We revisit the Ranking algorithm using the linear programming framework, where the constraints of the linear program are given by the structural properties of Ranking. We use continuous linear program relaxation to analyze the limiting behavior as the finite linear program grows. Of particular interest are new duality and complementary slackness characterizations that can handle monotone constraints and mixed evolving and boundary constraints in continuous linear program, which enable us to achieve a theoretical ratio of 0:523 on arbitrary graphs.
The Jchoice Kbest secretary problem, also known as the (J;K)secretary problem, is a generalization of the classical secretary problem. An algorithm for the (J;K)secretary problem is allowed to make J choices and the payoff to be maximized is the expected number of items chosen among the K best items. We use primaldual continuous linear program techniques to analyze a class of infinite algorithms, which are general enough to capture the asymptotic behavior of the finite model with large number of items. Our techniques allow us to prove that the optimal solution can be achieved by a (J;K)threshold algorithm, which has a nice \rational description" for the case K = 1. 
Degree  Doctor of Philosophy 
Subject  Linear programming Economics  Mathematical model Computer algorithms 
Dept/Program  Computer Science 
Persistent Identifier  http://hdl.handle.net/10722/206329 
DC Field  Value  Language 

dc.contributor.advisor  Chan, HTH   
dc.contributor.author  Chen, Fei   
dc.contributor.author  陳飛   
dc.date.accessioned  20141023T23:14:26Z   
dc.date.available  20141023T23:14:26Z   
dc.date.issued  2014   
dc.identifier.citation  Chen, F. [陳飛]. (2014). Linear programming techniques for algorithms with applications in economics. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5312337   
dc.identifier.uri  http://hdl.handle.net/10722/206329   
dc.description.abstract  We study algorithms and models for several economicsrelated problems from the perspective of linear programming. In network bargaining games, stable and balanced outcomes have been investigated in previous work. However, existence of such outcomes requires that the linear program relaxation of a certain maximum matching problem has integral optimal solution. We propose an alternative model for network bargaining games in which each edge acts as a player, who proposes how to split the weight of the edge among the two incident nodes. We show that the distributed protocol by Kanoria et. al can be modified to be run by the edge players such that the configuration of proposals will converge to a pure Nash Equilibrium, without the linear program integrality gap assumption. Moreover, ambiguous choices can be resolved in a way such that there exists a Nash Equilibrium that will not hurt the social welfare too much. In the oblivious matching problem, an algorithm aims to find a maximum matching while it can only makes (random) decisions that are essentially oblivious to the input graph. Any greedy algorithm can achieve performance ratio 0:5, which is the expected number of matched nodes to the number of nodes in a maximum matching. We revisit the Ranking algorithm using the linear programming framework, where the constraints of the linear program are given by the structural properties of Ranking. We use continuous linear program relaxation to analyze the limiting behavior as the finite linear program grows. Of particular interest are new duality and complementary slackness characterizations that can handle monotone constraints and mixed evolving and boundary constraints in continuous linear program, which enable us to achieve a theoretical ratio of 0:523 on arbitrary graphs. The Jchoice Kbest secretary problem, also known as the (J;K)secretary problem, is a generalization of the classical secretary problem. An algorithm for the (J;K)secretary problem is allowed to make J choices and the payoff to be maximized is the expected number of items chosen among the K best items. We use primaldual continuous linear program techniques to analyze a class of infinite algorithms, which are general enough to capture the asymptotic behavior of the finite model with large number of items. Our techniques allow us to prove that the optimal solution can be achieved by a (J;K)threshold algorithm, which has a nice \rational description" for the case K = 1.   
dc.language  eng   
dc.publisher  The University of Hong Kong (Pokfulam, Hong Kong)   
dc.relation.ispartof  HKU Theses Online (HKUTO)   
dc.rights  Creative Commons: Attribution 3.0 Hong Kong License   
dc.rights  The author retains all proprietary rights, (such as patent rights) and the right to use in future works.   
dc.subject.lcsh  Linear programming   
dc.subject.lcsh  Economics  Mathematical model   
dc.subject.lcsh  Computer algorithms   
dc.title  Linear programming techniques for algorithms with applications in economics   
dc.type  PG_Thesis   
dc.identifier.hkul  b5312337   
dc.description.thesisname  Doctor of Philosophy   
dc.description.thesislevel  Doctoral   
dc.description.thesisdiscipline  Computer Science   
dc.description.nature  published_or_final_version   
dc.identifier.doi  10.5353/th_b5312337   