Invited Session Mon.1.H 3008

Monday, 10:30 - 12:00 h, Room: H 3008

Cluster 2: Combinatorial optimization [...]

Rational convex programs and combinatorial algorithms for solving them


Chair: Vijay V. Vazirani



Monday, 10:30 - 10:55 h, Room: H 3008, Talk 1

Vijay V. Vazirani
Rational convex programs


A nonlinear convex program that always has a rational optimal solution will be called a rational convex program (RCP). The notion is analogous to that of an integral linear program (ILP), i.e., an LP that always has integral optimal solutions. The field of combinatorial optimization is built around problems whose LP-relaxations are ILPs.
Our contention is that in many ways, the situation with RCPs is similar to that of ILPs. In both cases, the existence of much higher quality solution is indicative of combinatorial structure that can not only lead to efficient algorithms but also deep insights that yield unexpected gains. This was certainly the case with ILPs, which led to a very rich theory that underlies not only combinatorics but also the theory of algorithms.



Monday, 11:00 - 11:25 h, Room: H 3008, Talk 2

Kamal Jain
Eisenberg-Gale markets: Algorithms and game theoretic properties

Coauthor: Vijay V. Vazirani



We define a new class of markets, the Eisenberg-Gale markets. This class contains Fisher's linear market, markets from the resource allocation framework of Kelly [1997], as well as numerous interesting new markets. We obtain combinatorial, strongly polynomial algorithms for several markets in this class. Our algorithms have a simple description as ascending price auctions. Our algorithms lead to insights into game-theoretic properties of these markets, such as efficiency, fairness, and competition monotonicity. They also help determine if these markets always have rational equilibria. A classification of Eisenberg-Gale markets w.r.t. these properties reveals a surprisingly rich set of possibilities.



Monday, 11:30 - 11:55 h, Room: H 3008, Talk 3

Gagan Goel
A perfect price discrimination market model, and a rational convex program for it

Coauthor: Vijay V. Vazirani


Motivated by the current market ecosystem of online display advertising, where buyers buy goods through intermediaries, we study a natural setting where intermediaries are allowed to price discriminate buyers based on their willingness to pay. We show that introducing perfect price discrimination via an intermediary into the Fisher model with piecewise-linear, concave (PLC) utilities renders its equilibrium polynomial time computable. Moreover, and surprisingly, its set of equilibria are captured by a convex program that generalizes the classical Eisenberg-Gale program, and always admits a rational solution. We also give a combinatorial, polynomial time algorithm for computing an equilibrium. We note that the problem of computing an equilibrium for the traditional Fisher market with PLC utilities is unlikely to be in P, since it is PPAD-complete.


  payday loan . Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.