Computer Science – Computer Science and Game Theory
Scientific paper
2010-10-20
Computer Science
Computer Science and Game Theory
Scientific paper
Over the last decade, combinatorial algorithms have been obtained for exactly solving several nonlinear convex programs. We first provide a formal context to this activity by introducing the notion of {\em rational convex programs} -- this also enables us to identify a number of questions for further study. So far, such algorithms were obtained for total problems only. Our main contribution is developing the methodology for handling non-total problems, i.e., their associated convex programs may be infeasible for certain settings of the parameters. The specific problem we study pertains to a Nash bargaining game, called ADNB, which is derived from the linear case of the Arrow-Debreu market model. We reduce this game to computing an equilibrium in a new market model called {\em flexible budget market}, and we obtain primal-dual algorithms for determining feasibility, as well as giving a proof of infeasibility and finding an equilibrium. We give an application of our combinatorial algorithm for ADNB to an important "fair" throughput allocation problem on a wireless channel.
No associations
LandOfFree
Rational Convex Programs, Their Feasibility, and the Arrow-Debreu Nash Bargaining Game does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Rational Convex Programs, Their Feasibility, and the Arrow-Debreu Nash Bargaining Game, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rational Convex Programs, Their Feasibility, and the Arrow-Debreu Nash Bargaining Game will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-717415