- You are here:
- GT Home
- Home
- News & Events

Series: Other Talks

The rank of a bimatrix game (A, B) is defined as the rank of (A+B). For
zero-sum games, i.e., rank 0, Nash equilibrium computation reduces to
solving a linear program. We solve the open question of Kannan and
Theobald (2005) of designing an efficient algorithm for rank-1 games.
The main difficulty is that the set of equilibria can be disconnected.
We circumvent this by moving to a space of rank-1 games which contains
our game (A, B), and defining a quadratic program whose optimal
solutions are Nash equilibria of all games in this space. We then
isolate the Nash equilibrium of (A, B) as the fixed point of a single
variable function which can be found in polynomial time via an easy
binary search.
Based on a joint work with Bharat Adsul, Jugal Garg and Milind Sohoni.

Series: Other Talks

(algebraic statistics reading seminar)

Series: Other Talks

(algebraic statistics reading seminar)

Series: Other Talks

Algorithms and Randomness Center (ARC) Theory Day is an annual event that features hour-long lectures focusing on recent innovative results in theoretical computer science, spanning a wide array of topics several of which are inspired by practical problems.
See the complete list of titles and times of talks.

Series: Other Talks

Pricing and allocating goods to buyers with complex preferences in order to maximize some desired objective (e.g., social welfare or profit) is a central problem in Algorithmic Mechanism Design.
In this talk I will discuss some particularly simple algorithms that are able to achieve surprisingly strong guarantees for a range of problems of this type. As one example, for the problem of pricing resources, modeled as goods having an increasing marginal extraction cost to the seller, a simple approach of pricing the i-th unit of each good at a value equal to the anticipated extraction cost of the 2i-th unit gives a constant-factor approximation to social welfare for a wide range of cost curves and for arbitrary buyer valuation functions. I will also discuss simple algorithms with good approximation guarantees for revenue, as well as settings having an opposite character to resources, namely having economies of scale or decreasing marginal costs to the seller.

Series: Other Talks

Series: Other Talks

(algebraic statistics reading seminar)

Series: Other Talks

(algebraic statistics reading seminar)

Series: Other Talks

Series: Other Talks

(algebraic statistics reading seminar)