Report from SODA 2012: Part 2

Guest post by Ashwinkumar Badanidiyuru.

There has already been some info on the blogs on SODA here. The conference was well organized and the number of researchers attending the conference was also considerable. I really liked the cleanliness of Kyoto and the punctuality of trains.

The negative things were that the conference did not organize a breakfast and coffee was not available at all breaks. I and a couple of my friends also felt a terrible jet lag. Another problem which we faced while roaming around was the availability of vegetarian food.

There were two main sessions related to game theory and mechanism design. I will blog here about one of the sessions and my colleague Hu Fu has already blogged about the other.

1. The Notion of a Rational Convex Program, and An Algorithm for the Arrow-Debreu Nash Bargaining Game. (Vijay Vazirani):A nice blog post about this line of work has already been written here.  This paper introduces the notion of a rational convex program (RCP). RCP is a convex program that is guaranteed to have an optimal solution, which is rational and has polynomially non-zero bits given any setting of its parameters to rational numbers and the optimal solution is bounded. This paper defined a new Nash bargaining game and shows that it is logarithmic RCP (Objective function is a sum of logarithm of linear functions). It also gives a combinatorial algorithm to compute an equilibrium of such a game.
2. Beyond Myopic Best Response in Cournot Competition. (Svetlana Olonetsky, Amos Fiat, Elias Koutsoupias, Katrina Ligett, Yishay Mansour): This paper studies the best response strategies when the best response is non-myopic. (i.e. depends on how the other player could potentially choose the strategy in the next round). Consider the Cournot competition game where two firms produce oil, Firm1 at a cost of 0.3 dollars/barrel and Firm2 at a cost of 0.5 dollars/barrel. Let the price set by the market be 1-(number of barrels produced). In a Nash equilibrium Firm1 produces 0.3 barrels and Firm2 produces 0.1 barrels. But if Firm1 produced 0.5+ε barrels then Firm2 would drop out and Firm1gets a better return. This hints that Nash might not be the right solution concept.The solution concept proposed and studied in this paper is a delegation game where in the first round it is decided if each player is supposed to maximize his profit or revenue and in the second round the game is played. The part which confuses me is that this looks like something in between a one shot and a multi-round game.
3. Metastability of Logit Dynamics for Coordination Games. (Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Giuseppe Persiano): Usually in learning in games we study the stationary distribution of some noisy response strategy. This becomes not so interesting if the mixing time is very large. This paper studies the transient phase for Logit Dynamics for Coordination Games. It studies something called metastable distribution in which the game is present for a time-scale shorter than the mixing time. As an example it gives Ising’s game (similar to Ising’s model) where it takes exponential time to mix (under suitable parameters), while there are meta stable distributions. An interesting question would be computing a meta-stable distribution if the pseudo-mixing time is not polynomial.
4. Sketching Valuation Functions. (Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, Tim Roughgarden): We study the problem of storing an approximate version of different classes of valuation functions in polynomial space. The problem is motivated by sealed bid combinatorial auctions in which the bidders first write some version of their valuation and then send it to auctioneer. Then, the auctioneer uses this to allocate the items. This research is along the lines of a paper by Goemans, Harvey, Iwata and Mirrokni which gives an algorithm to find a -sketch for submodular functions using polynomially many value queries. There is also a lower bound of using arbitrary communication, stemming from the work of Balcan and Harveyon learning submodular functions in the PMAC model. Some of the interesting results in this paper are:
   • A tight sketch for subadditive functions using arbitrary
     communication and lower bound when the algorithm is restricted to use only value queries.
   • A surprising “PTAS” (i.e., (1+ε)-sketch) for coverage functions.
   • A generic reduction from sketching to learning in the PMAC model proposed by Balcan, Harvey.

   A very recent arXiv paper on learning valuation functions in the PMAC model, by Balcan, Constantin, Iwata, and Wang, contains a set of closely related (and in a few cases, overlapping) results that were independently discovered at the same time.

5. Voting with Limited Information and Many Alternatives. (Jon M. Kleinberg, Flavio Cherichetti): In this work an adversary first chooses an urn from a set of urns, each containing red and blue balls. Each voter knows the set of urns, but not the urn chosen by adversary. Then, each voter chooses a random ball from the chosen urn and votes for his/her guess for the right urn. The voters win if the chosen urn gets the maximum number of votes. The paper proves that voters are enough for this and surprisingly if each person gets to divide his vote among multiple urns then voters are enough to win with probability 1-δ. The second result is surprising since even a single person drawing random ball from the urn requires so many draws. The main motivation for this result is the problem where a set of jurors vote in a criminal trial. This is related to the Condorcet Jury Theorem.

There were some other interesting papers, a couple of which are described below.

• Popularity Vs Maximum Cardinality in the Stable Marriage Setting. (Telikepalli Kavitha).Extends Gale-Shapley algorithm to compute matching with small unpopularity. The algorithm is roughly a multi round GS algorithm where an unmatched boy re-proposes in the next round and any boy in round i gets preference over any boy in round j<i. The interesting feature of this algorithm is that at round i all augmenting paths of length i are avoided.
• Gathering Despite Mischief. (Yoann Dieudonne, Andrzej Pele and David Peleg).Consider a group of individuals, each moving synchronously in a network. The goal is for them to meet together at a node. There could be byzantine individuals which are either making incorrect moves or are sharing wrong information with other individuals. This paper gives upper and lower bounds (mostly not matching) for the total number of individuals necessary for a protocol to exist. An interesting result is a tight bound of f+2 in one of the models. Most bounds in this area do not seem to be of this form.
• Private Data Release Via Learning Thresholds. (Moritz Hardt, Guy Rothblum and Rocco A. Servedio).This paper gives a computationally efficient reduction from differentially private data release to learning thresholded sums of predicates.
• Matroidal Degree-Bounded Minimum Spanning Trees. (Rico Zenklusen).This paper generalizes the classic problem of degree bounded spanning tree to the case where we need to have a spanning tree with a matroid constraint for every node over which edges can be chosen. It gives an algorithm which returns a spanning tree of cost at most OPT and which violates each matroid constraint by at most eight elements. Seems to use similar techniques as Lau-Singh with non-trivial generalizations.
• Submodular Functions are Noise Stable. (Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin Lee).This paper is a simple observation that submodular functions are noise stable and hence can be agnostically learned.
• Random Walks, Electric Networks and The Transience Class Problem of Sandpiles. (Ayush Choure, Sundar Vishwananthan).In the sandpiles model you have a grid and sand particles are added one by one to some square in the grid. When the number of particles reaches a threshold they flip to adjacent squares. This paper studies and gives a bound for number of particles to be added to one corner of a square grid for the other corner to flip. I am curious if this model is also applicable to certain settings in social networks.
• Information Dissemination Via Random Walks in D-Dimensional Space. (Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiarui Sun, Yajun Wang).This paper considers the problem of m agents placed uniformly at random in a d-dimensional (d>2) hypercube and gives nearly tight bounds on the time required for information dissemination when one agent holds it. The interesting phenomenon for d>2 is a phase transition not seen when d=2. The asymptotic rate for time required follows different functions in two different ranges for m.
• Rumor Spreading and Vertex Expansion. (George Giakkoupis, Thomas Sauerwald).Gives nearly tight bounds on round complexity of rumor spreading in terms of vertex expansion. The lower bound for parameters such as vertex expansion only happen in specific class of graphs. It is interesting if there is a graph parameter which tightly bounds rumor spreading in every graph.
• Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation. (Shayan Oveis Gharan, Vahab Mirrokni, Morteza Zadimoghaddam).This paper analyses an existing algorithm for the online budgeted allocation and proves that it has a simultaneous approximation for adversarial as well as stochastic version of the problem.
• Improved Competitive Ratio for the Matroid Secretary Problem. (Oded Lachish, Sourav Chakraborty).This paper improves the competitive ratio of the matroid secretary problem to √log(rank). The surprising fact is that the paper is able to do so using some variant of binning.

Advertisement