Algorithmics, Social choice, Market Design, and Other Topics

The latest issue is now available.

I reviewed a recently published book on algorithmic mechanism design: Game theoretic problems in network economics and mechanism design solutions Narahari Y. , Garg D. , Narayanam R. , Prakash H. , Springer Publishing Company, Incorporated, 2009. The review is available from here .

The Banzhaf vector measures the influence of a player in a monotonic simple game. I had been interested in the distribution of the Banzhaf vector is simple games and also weighted voting games (a subclass of simple games). Better knowledge of the distrbution helps to check whether an algorithm to design a game with the required Banzhaf vector has converged sufficiently. Alon and Edelman have published a recent paper where they investigate which non-negative vectors of sum 1 can be closely approximated by Banzhaf vectors of simple voting games with n players. Interestingly, they show that approximation is not necessarily easier for a larger n, and exhibit vectors in the standard n-simplex for all n that can not be well approximated.

This is a plug for the: 20 TH POSTGRADUATE COMBINATORIAL CONFERENCE Royal Holloway, University of London, UK 22-24 June, 2009 In addition to the talks contributed by students, the schedule will also include five one-hour talks from invited speakers. Prof. Andrew G. Thomason . Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge, England Talk title: 2-coloured graphs, multigraphs and hereditary properties Prof. Dave Cohen . Department of Computer Science, Royal Holloway University of London, England Talk title: Arrow's theorem showing that there is no fair voting system Dr. Anders Yeo . Department of Computer Science, Royal Holloway University of London, England. Talk title: Transversals in hypergraphs, total domination in graphs and other related problems Prof. Derek Smith . Faculty of Advanced Technology, University of Glamorgan, Pontypridd, Wales. Talk title:Old and new problems in coding theory ...

I am reproducing the information about an exciting workshop which will be held at UCL on 12 and 13th June. The workshop is hosted by ELSE at the Wellcome Collection Conference Centre in London. The focus is on algorithmic mechanism design, recommendation systems and social networks. Program: Friday, 12 June 2009 9:00 - 9:30 Gathering and registration 9:30 - 10:15 Preston McAfee : Allocating Guaranteed Display Advertising in an Exchange Environment 10:15 - 11:00 Michael Schwarz: Optimal Auction Design in a Multi-unit Environment: The Case of Sponsored Search Auctions 11:00 - 11:30 Coffee break 11:30 - 12:15 Sebastien Lahaie: An Expressive Auction Design for Online Display Advertising 12:15 - 13:00 Tim Roughgarden: Differential Privacy [ Relevant Readings ] 13:00 - 14:30 Lunch 14:30 - 15:15 Yongmin Chen: Equilibrium Price Dispersion with Heterogeneous Searchers 15:15 - 16:00 John Morgan: Shrouded Attributes and Information Suppression: Evidence from Fie...

Daskalakis , Paul Goldberg , and Papadimitriou have been instrumental in settling the complexity of computing the Nash equilibria of the normal form game. Similarly Chen , Deng and Teng have also been coming up with results to settle the complexity. Recently both groups of researchers published journal papers which describe in detail their results in the last few years: JACM paper and SIAM Journal of Computing .

The classical secretary problem involves n secretary job applicants who can be ranked by a total order. The applicants are interviewed one by one in some random order. After each interview, the applicant is accepted or rejected. The decision is based only on the relative ranks of the applicants interviewed so far. The game has payoff 1 if the best applicant is selected and 0 otherwise. The solution is to interview the first n/e candidates and then hire the first that is better than the first n/e candidates. For large enough n, the probability of success is 1/ e. Today, Nicholas Georgiou gave an interesting talk where a general partial order on candidates is considered instead of a linear order. He presented a strategy where the probability of success is 1/4. Check out the paper .