Algorithmics, Social choice, Market Design, and Other Topics

The Scientific American discusses the issues of manipulation in online recommendation systems .

Noga Alon gave a plenary lecture at the recently concluded EURO 2010 conference . He presented six results in social choice theory, which included classic theorems and also some new work by Alon and his coauthors. The results are stated in an informal manner and therefore should be taken with a grain of salt: Majority can be irrational (Condorcet's Paradox)   Majority can be chaotic (McGarvey's Theorem) Only reasonable voting scheme is a dictatorship (Arrow's impossibility theorem) Any reasonable leader election scheme can be manipulated (Gibbard–Satterthwaite theorem) Bigger committees require bigger budgets. Cheating is inherent in 'reality show survivor games' .

FC College, Lahore is organizing a 10-day Summer Workshop in Theoretical Computer Science from 2-13 August 2010. there will lectures on the following theoretical computer science topics: Logic and Proofs  Combinatorics Algorithms Graph theory Discrete probability Computability theory  Complexity theory  Problems in graph theory If you are nearby, do attend.

http://sagt2010.cti.gr/ Elchanan Mossel and Omer Tamuz. Truthful Fair Division   Uriel Feige and Moshe Tennenholtz. Responsive Lotteries  Reshef meir, Yoram Bachrach and Jeffrey Rosenschein. Minimal Subsidies in Expense Sharing Games Vincenzo Auletta , Diodato Ferraioli, Francesco Pasquale and Giuseppe Persiano. Mixing Time and Stationary Expected Social Welfare of Logit Dynamics Felix Brandt, Felix Fischer and Paul Harrenstein. On the Rate of Convergence of Fictitious Play Dimitris Fotakis, George Karakostas and Stavros Kolliopoulos. On the Existence of Optimal Taxes for Network Congestion Games with Heterogeneous Users Chinmay Karande, Gagan Goel and Lei Wang. Single-Parameter Combinatorial Auctions with Partially Public Valuations Bharat Adsul, Sobhan Babu, Jugal Garg, Ruta Mehta and Milind Sohoni. Nash Equilibria in Fisher Market Yonatan Aumann and Yair Dombb. Pareto Efficiency and Approximate Pareto Efficiency in Routing and Load Balancing Games Alexander S...

Tim Roughgarden briefly reviews algorithmic game theory in the latest edition of the CACM . He frames algorithmic game theory as a field addressesing the follows basic questions: To what extent is "incentive-compatible" efficient computation fundamentally less powerful than "classical" efficient computation? When, and in what senses, are game-theoretic equilibria guaranteed to approximately optimize natural objective functions? When can the participants of a game quickly converge to an equilibrium? More modestly, when can a centralized algorithm quickly compute an equilibrium?

The accepted paper list is public : Sven Krumke and Clemens Thielen. Strong Implementation of Social Choice Functions in Dominant Strategies Clemens Thielen and Stephan Westphal. A Combinatorial Algorithm for Strong Implementation of Social Choice Functions Yiling Chen, John Lai, David Parkes and Ariel Procaccia. Truth, Justice, and Cake Cutting Ceyhun Coban and M. Remzi Sanver. Social Choice without the Pareto principle under weak independence Edith Elkind, Piotr Faliszewski and Arkadii Slinko. Distance Rationalization of Voting Rules Nadja Betzler. On Problem Kernels for Possible Winner Determination Under the k-Approval Protocol Felix Brandt, Markus Brill, Edith Hemaspaandra and Lane A. Hemaspaandra. Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates Noga Alon, Felix Fischer, Ariel Procaccia and Moshe Tennenholtz. Sum of Us: Strategyproof Selection from the Selectors Michael Zuckerman and Jeffrey S. Rosenschein. An Algorithm for th...

Amartya Sen takes a  philosophical angle on social choice and welfare theory as he discusses the idea of justice.