Moshe Babaioff Reports from BAGT 6

Moshe Babaioff writes this guest blog post from the 6th Bay Algorithmic Game Theory Symposium (BAGT6) that was held last Friday in Berkeley:

The 6^th Bay Algorithmic Game Theory symposium (BAGT6) took place at UC Berkeley last Friday. The day started on the wrong foot for me. We arrived to the raining city of Berkeley and found out that the public parking we planned to use was closed to the public because of another event. We had to go around the campus looking for parking, getting to the auditorium not a minute  too early to find out that there is a problem with the projector. This was a beginning of a long saga of fighting the projector-computer compatibility issue, a saga that lasted the entire morning (it involved talks at 3 different rooms, 6 different laptops, 5 projectors (!) and restructuring of the schedule at real time). Clearly Fortuna had some unsettled business with BAGT. Alternative, it proved that the CS worst case approach is not paranoiac but rather realistic…

Michael Schapira gave the first talk, discussing the connection between VCG and VC Dimension. The presented paper belongs to the line of research that aims to understand the clash between incentive and computation feasibility. Combinatorial auction is probably the standard example for which such a clash exists. VCG achieves full efficiency but in intractable, while (for the studied problem) there are good approximation algorithms that are not truthful.  What is the best welfare approximation achievable by a polynomial-time truthful mechanism?   The paper presents new lower bounds for Maximal-in-Range (MIR) mechanisms, based on connections to the VC Dimension.

Michael Schwarz talked next, addressing the problem many of us ask ourselves every time we go to a mechanics to fix a small problem in our car: is it possible that the mechanics will honestly fix only what is broken and will not “find out” that we actually have a some major issues in our car that must be fixed immediately (“luckily I am able to give you a discount, if I fix it now it will only cost you $873+tax”). Michael presented a model of experts that need to diagnose the problem and also fix it. An expert might perform a minor or a major treatment (each with a different profit for him), and the costumer does not know which one should be taken.  Is it possible to have an equilibrium in which experts honestly perform the right treatment? It turn out that if all expert “have the same ability” that is the case, while it is not the case if they are heterogeneous.

After lunch we heard a talk by Jon Levin about early admission to Colleges. The early admission system allows students to apply early to at most one college, signaling their preference towards that college. Sometime the early admission is made a binding commitment. Jon presented a simple model of students and schools preferences and studied the equilibrium in that model.

Amin Saberi talked about noisy best respond dynamics in games played on networks. He asked how the spread of behavior depends on the structure of the graph and pointed out that the spread is very different than in the case of viral infection.

I talked about truthful multi-arm bandit mechanisms, mainly showing that such mechanisms must separate exploration and exploitation and have higher regret than the best non-truthful algorithms. We then had a mini-talks session with 4 short presentations. Nicolas Lambert followed with an overview of his results on the problem of eliciting probabilistic information, with an emphasize on new results regarding predicates on distributions. Assume that an expert knows some properties of a distribution (for example the mean or the variance), is it possible to truthfully extract that information? Payment depend on the expert report and the realized outcome. It turn out that it is possible to extract the mean, but not the variance by itself (yet one can truthfully extract both). Nicolas presented general characterization results for properties (and predicates) that can be truthfully extracted.

The last speaker for the day was Christos Papadimitriou talking about equilibria computation. Christos open his talk mentioning that this is the second time he gives a talk with this title at BAGT.  The talk started very similarly (Nash is PPAD complete…) but most of the talk was spend on a broad survey of many new results taken to address the likely intractability of the problem. Christos talked about 3 lines of attack: Approximate-Nash, special cases that can be solved in polynomial time and hardness results for restricted classes of algorithms.

Advertisement