Algorithms, game theory, social choice, complexity, combinatorics, travel etc.

Matching in Practice

2012-01-18T12:50:00.000-08:00

The European network on “Matching in Practice” has launched its official website. The website mentions a resolve to arrange two workshops on matching theory every year. This augurs well for computer scientists and social scientists interested in the area. Future meetings include the following:

May 2012	Sunday 20 May 2012 - Wednesday 23 May 2012 09:00 Frontiers in Market Design: Matching Markets
July 2012	Thursday 19 July 2012 - Friday 20 July 2012 09:00 interdisciplinary MATCH-UP (Matching under Preferences) workshop

Salman Khan: on the art of teaching and more

2011-12-30T07:01:00.000-08:00

MATCH-UP 2012

2011-12-16T14:06:00.000-08:00

MATCH-UP 2012:

the Second International Workshop on Matching Under Preferences

19-20 July 2012

Budapest, Hungary

http://econ.core.hu/english/res/MATCH-UP_2012.html

co-located with SING8: The 8th Spain-Italy-Netherlands Meeting

on Game Theory (http://sing8.iehas.hu)

Celebrating the 50th anniversary of the seminal paper by Gale and Shapley,

and following the success of the first MATCH-UP workshop in Reykjavík in

2008 (http://www.optimalmatching.com/workshop), we are organising another

interdisciplinary workshop on stable matchings and related topics.

Background

----------

Matching problems with preferences occur in widespread applications such

as the assignment of school-leavers to universities, junior doctors to

hospitals, students to campus housing, children to schools, kidney

transplant patients to donors and so on. The common thread is that

individuals have preference lists over the possible outcomes and the task

is to find a matching of the participants that is in some sense optimal

with respect to these preferences.

The remit of this workshop is to explore matching problems with

preferences from the perspective of algorithms and complexity, discrete

mathematics, combinatorial optimization, game theory, mechanism design

and economics, and thus a key objective is to bring together the research

communities of the related areas.

Invited speakers

----------------

* Nicole Immorlica, Northwestern University

* Rob Irving, University of Glasgow

* Fuhito Kojima, Stanford University (on leave at Columbia University)

* Tayfun Sönmez, Boston College

List of topics

--------------

The matching problems under consideration include, but are not limited to:

* two-sided matchings involving agents on both sides (e.g. college

admissions, resident allocation, job markets, school choice, etc.)

* two-sided matchings involving agents and items (e.g. house allocation,

course allocation, project allocation, assigning papers to reviewers,

school choice, etc.)

* one-sided matchings (roommates problem, kidney exchanges, etc.)

* matching with payments (assignment game, auctions, etc.)

Submissions

-----------

We call for two types of contributed papers.

Format A: original contribution

* at most 12 pages

* accepted papers will be published in proceedings (however, this should

not prevent the simultaneous or subsequent submission of contributed

papers to other workshops, conferences or journals)

Format B: not necessarily original work

* no page limit

* only the abstract will be published in proceedings

Authors should indicate which format type their paper should be considered

under.

Important dates

---------------

* Deadline for submission of contributed papers: 19 March 2012

* Notification of acceptance: 20 April 2012

* Early registration deadline: 18 May 2012

* Workshop: 19-20 July 2012

Organising committee

--------------------

* Péter Biró (Institute of Economics, Hungarian Academy of Sciences)

* Tamás Fleiner (Budapest University of Technology and Economics)

* David Manlove (University of Glasgow)

* Tamás Solymosi (Corvinus University, Budapest)

Programme committee

-------------------

* Péter Biró (Chair, Institute of Economics, Hungarian Academy of Sciences)

* Estelle Cantillon (Université Libre de Bruxelles)

* Katarína Cechlárová (Univerzita Pavla Jozefa Safárika)

* Paul Dütting (EPFL, Lausanne)

* Aytek Erdil (University of Cambridge)

* Tamás Fleiner (Budapest University of Technology and Economics)

* Guillaume Haeringer (Universitat Autonoma de Barcelona)

* Elena Inarra (University of the Basque Country)

* Zoltán Király (Eötvös Loránd University, Budapest)

* Flip Klijn (Universitat Autonoma de Barcelona)

* David Manlove (University of Glasgow)

* Eric McDermid (21st Century Technologies)

* Shuichi Miyazaki(Kyoto University)

* Marina Nunez (Universitat de Barcelona)

* Ildikó Schlotter (Budapest University of Technology and Economics)

* Tamás Solymosi (Corvinus University, Budapest)

Further information

-------------------

See http://econ.core.hu/english/res/MATCH-UP_2012.html

Stanford Online Course on Game Theory

2011-11-21T01:42:00.000-08:00

An online course being taught by Yoav Shoham and Matthew Jackson:

(Hat tip to Nadeem Ahmed)

Security and Game Theory

2011-11-17T04:50:00.000-08:00

Milind Tambe who heads the Teamcore research group at USC has edited a book on Security and Game Theory which is soon due in the market. The book overviews recent research developments in the use of algorithmic game theory for security and surveillance. Here is a recent talk overviewing the topic.

James Gleick: "The Information: A History, A Theory, A Flood"

2011-11-15T08:50:00.000-08:00

James Gleick talks about his new book "The Information: A History, A Theory, A Flood".

Google X

2011-11-15T01:48:00.000-08:00

Interesting article by the NYT on Google's ideas and invention lab: Google X.

Simons Foundation featured articles

2011-11-14T01:16:00.000-08:00

The Simons Foundation is a NY-based foundation with the mission to advance basic sciences and mathematics. Their website has an interesting series of featured articles. The articles include one on matching theory and a recent one on Khot's unique games conjecture.

LogICCC: A Retrospective

2011-11-03T05:40:00.000-07:00

The ESF has published a report titled 'Modelling Intelligent Interaction (LogICCC): Logic in the Humanities, Social and Computational Sciences - A Retrospective' as the LogICCC program comes to a completion. The report gives an overview of the accomplishments of the constituent projects in the program and presents research highlights.

PROJECT ACRONYM	PROJECT TITLE
CFSC	Computational Foundations of Social Choice
DiFoS	Dialogical Foundations of Semantics
GASICS	Games for Analysis and Synthesis of Interactive Computational Systems
LcpR	The Logic of Causal and Probabilistic Reasoning in Uncertain Environments
LINT	Logic for Interaction
LoMoReVi	Logical Models of Reasoning with Vague Information
SSEAC	SOCIAL SOFTWARE for elections, the allocation of tenders and coalition/alliance formation
VAAG	Vagueness, Approximation and Granularity

Impressions from SAGT 2011

2011-11-02T06:05:00.000-07:00

Yair Dombb has a review of the recently concluded SAGT in the quant town of Amalfi.

Grand Pursuit: A Story of Economic Genius

2011-10-22T04:21:00.000-07:00

Sylvia Nasar, author of a 'A Beautiful Mind'--- the biography of John Nash--- has written a new book titled 'Grand Pursuit: A Story of Economic Genius'. In comparison to 'A Beautiful Mind', the new book

'is thus no longer the story of one man or one set of ideas, but of dozens of men and ideas, and covers not years but centuries, as Nasar tells us how modern economic theory emerged and then evolved, from Adam Smith in the late 18th century to Amartya Sen today' ---[The Globe and Mail].

This should be an interesting read.

Inferring information from social networks

2011-10-14T03:55:00.000-07:00

Jon Kleinberg's talks about how data from social networks 'offers a radically new perspective on fundamental questions in the social sciences.'

Prediction Games

2011-10-08T09:54:00.000-07:00

A short video by the Economist magazine...

Turing Award lecture

2011-10-05T04:41:00.000-07:00

The 2010 Turing Award lecture by Les Valiant is now online

Climate change: game theory to the rescue?

2011-09-07T04:09:00.000-07:00

The Guardian has an interesting report on how German academics at the Potsdam Institute for Climate Impact Research "have used the mathematics behind the strategic behaviour of countries to propose a way though the myriad impasses".

The relevant paper is available from here.

Recent Developments in Market Design

2011-08-27T08:38:00.000-07:00

There is an interesting mini workshop on 'Recent Developments in Market Design' on 14th September 2011 at Maastricht University. The abstract of the talks are available.

Supercooperators

2011-08-27T05:33:00.000-07:00

Mathematical biologist, Martin Nowak talks about his new book 'Supercooperators: Evolution, Altruism and Human Behaviour or, Why We Need Each Other to Succeed'.

Merits of Theory

2011-08-14T13:25:00.000-07:00

Hal Varian has a nice article on What Use is Economic Theory?
Varian views Economics as Policy Science and then gives a number of reasons why economic theory is helpful in this regard:

Theory as a substitute for data
Theory helps keep track of benefits and costs
Theory helps relate seemingly disparate problems
Theory can generate useful insights
A theory that is wrong can still yield insight
Theory provides a method for solving problems
Theory is an antidote to introspection
Verifying that something is obvious may show that it isn’t
Theory allows for quantification and calculation
Economics is amenable to experimental verification

Workshop: New Trends in Mechanism Design

2011-08-07T03:39:00.000-07:00

http://cfem.au.dk/newsevents/mechdesign/

The workshop will be held from September 6-9, 2011, at Copenhagen Business School, Denmark.

New Trends in Mechanism Design will bring together researchers from economics and computer science working on the design and analysis of economic mechanisms and on applications of such mechanism to solve real-life economic problems for companies, organizations and governments. The workshop will cover both the design of mechanisms using game theoretical analysis of incentives, and the calibration of mechanisms using experimental techniques.

Confirmed Speakers

Rick Antle, Yale School of Management, Yale University
Peter Cramton, University of Maryland
Uriel Feige, the Weizmann Institute
Jason Hartline, Northwestern University
Nicole Immorlica, Northwestern University
Hervé Moulin, Rice University
Tim Roughgarden, Stanford University

Time for a name change?

2011-08-04T19:24:00.000-07:00

Spain, Italy and Netherlands meeting on Game Theory (SING) was held this year in France and is being organized in Hungary in 2012. Perhaps, this is reason enough for having a more representative meaning for the word SING :-).

11th Meeting of Society for Social Choice and Welfare

2011-08-01T06:44:00.000-07:00

The Society for Social Choice and Welfare will organize its next biannual meeting in New Delhi from 17th August to 20th August, 2012.

------

Submission starts: 1st November, 2011

Submission deadline: 28th February, 2011

Notification of acceptance: 31st March, 2012

Early registration deadline: TBA

Late registration deadline: TBA

Conference dates: August 17 - 20, 2012

-----

Invited Speakers:

Matthew O. Jackson,

Claude d’Aspremont

Maurice Salles

International Conference on Game Theory

2011-07-14T15:32:00.000-07:00

The program is online: lot's of interesting talks.

SAGT 2011 papers

2011-06-29T23:28:00.001-07:00

The accepted papers list is now public.

Future of presentation slides?

2011-06-28T02:48:00.000-07:00

(Thanks to Markus Brill (Bibmaster general) for pointing out Prezi)

Dr. Adil Najam: New LUMS VC

2011-06-27T01:15:00.000-07:00

So it's doubly official now. Just received an email from the LUMS Alumni office that Dr. Adil Najam will be joining LUMS at the position of Vice Chancellor from July 2011. Adil Najam, more widely known for his blog Pakistaniat.com seems well-suited to take up the leadership role at LUMS. The following is an excerpt from his profile:

--------

Dr. Adil Najam will be joining LUMS at the position of Vice Chancellor from July 01, 2011. Dr. Najam is a leading authority on global public policy. He holds the Frederick S. Pardee Chair for Global Public Policy at Boston University. He also serves as the Director of the Pardee Centre for the study of the Longer-Range Future and is a tenured Professor of International Relations and of Geography and the Environment. Earlier he served as a Professor of Negotiations and Diplomacy (2002-2007) at the Fletcher School of Law and Diplomacy at Tufts University. He has also taught at the Massachusetts Institute for Technology (MIT) and the University of Massachusetts (UMass).

------

Funny: upcoming movie based on PhD Comics!

2011-06-23T13:03:00.000-07:00

PHD Movie Trailer from PHD Comics on Vimeo.

Barcelona

2011-06-09T04:45:00.000-07:00

For those attending IJCAI 2011(in Barcelona) AND also looking forward to exploring the city, The Guardian is focussing on Barcelona on their city guide website. Enjoy!

Algorithmic game theory lecture videos

2011-05-31T04:41:00.000-07:00

A while ago, the The innovations in Algorithmic Game Theory workshop was advertized. Considering the excellent speaker list, I was hopeful that the videos of the lectures would be put online.

The good news is that the lectures were videotaped and are online! Please click on the following links:

http://iasmac31.as.huji.ac.il:8080/groups/innovationsinalgorithmicgametheory/blog/

http://iasmac31.as.huji.ac.il:8080/groups/innovationsinalgorithmicgametheory/blog/?startIndex=20

The server is really slow but the videos should work.

[Hat tip to Paul Goldberg for pointing out the video links]

The demerits of Plurality voting

2011-05-20T05:34:00.000-07:00

A lot has been said about the pros and cons of using AV (Single Transferable Voting) as compared to First Past the Post (Plurality) in TV debates etc. What has been perplexing is that the opinions of specialists have hardly been sought. Or perhaps their voice got drowned amidst the political manouvering and lobbying.

Although the AV issue is dead for now, I wanted to highlight what the experts have to say about Plurality, the most widely used voting method, also in use in the UK elections:

http://www2.warwick.ac.uk/newsandevents/expertcomment/av/

The relevant portion is from 10.00 onwards where Prof. Dennis Leech, a specialist on voting theory (also one of my PhD advisors) talks about the issue. Prof. Leech refers to a meeting by the most renowned social choice theorists where Plurality was dismissed as a reasonable voting method. This is of course not the first time, people have voiced concern over Plurality.

Nicholas Christakis: The hidden influence of social networks

2011-05-18T07:03:00.000-07:00

(Hat tip to Simina Branzei for the link).

Interesting blog on game theory and social choice

2011-04-30T05:05:00.000-07:00

I recently noticed an interesting blog on game theory and social choice managed by László Á. Kóczy whose interests include 'cooperative game theory, voting games, as well as in scientometrics and industrial organisation.' Kóczy also manages the Ideas archive on game theory.

SAGT 2011 deadline

2011-04-29T01:52:00.000-07:00

As requested by the SAGT organizers: a reminder about the approaching deadline for paper submissions (May 9, 2011, 23:59 GMT).

The call for papers is available from here.

Working of the mind

2011-04-18T05:17:00.000-07:00

Josh Tenenbaum (Professor at MIT) researches on cognitive and neural mechanisms of the human mind and how can we use similar principles in AI. Recently, Tenenbaum and his coauthors have written an article in Science titled 'How to Grow a Mind: Statistics, Structure, and Abstraction'.

Here is a short talk Tenenbaum gave at Davos 2010 on the topic.

The strange case of Grigori Perelman

2011-04-15T02:52:00.000-07:00

Robin McKie from Guardian Books reviews a biography on Grigori Perelman, the mathematician who turned down a million dollars.

ICALP 2011 accepted papers

2011-04-13T07:57:00.001-07:00

ICALP 2011 papers: abstracts are also available.

IJCAI 2011 accepted papers

2011-04-04T14:05:00.000-07:00

IJCAI 2011 accepted papers are now public.

Boston Globe profiles Al Roth

2011-04-03T11:49:00.000-07:00

Boston Globe profiles Al Roth:

Academically speaking, Roth is a pioneer of so-called market design: finding situations where a market is failing — often, a place that most people wouldn’t even recognize as a market — and making it work better. Roth has influenced a cadre of young, energetic market designers, many of whom have taken up prominent positions at top universities. Inspired by Roth’s work, these rising economists are also setting their sights on real-world problems. Some are looking at dating websites; others are interested in how universities could do better at scheduling their students’ classes. Like Roth, all of them envision a world in which economists, as unlikely as it may seem, are recognized as society’s mechanics.

AAMAS 2011 program

2011-04-01T07:00:00.000-07:00

AAMAS 2011 program is now public: http://www.aamas2011.tw/DailyProgram.html

Les Valiant wins Turing Award

2011-03-09T07:00:00.000-08:00

Les Valiant has won the 2010 Turing Award.

(Citation from the ACM website)

Over the past 30 years, Leslie Valiant has made fundamental contributions to many aspects of theoretical computer science. His work has opened new frontiers, introduced ingenious new concepts, and presented results of great originality, depth, and beauty. Time and again, Valiant's work has literally defined or transformed the computer science research landscape.
Valiant's greatest single contribution may be his 1984 paper "A Theory of the Learnable," which laid the foundations of computational learning theory. He introduced a general framework as well as concrete computational models for studying the learning process, including the famous "probably approximately correct" (PAC) model of machine learning. This has developed into a vibrant research area and has had enormous influence on machine learning, artificial intelligence, and many areas of computing practice, such as natural language processing, handwriting recognition, and computer vision.

Valiant has made many seminal contributions to computational complexity. He introduced the notion of complexity of enumeration, in terms of the complexity class #P. The most surprising consequence of this study was that natural enumeration problems can be intractable even when the corresponding decision problem is tractable. Another fundamental contribution to computational complexity was Valiant's theory of algebraic computation, in which he established a framework for understanding which algebraic formulas can be evaluated efficiently. In analogy with the Boolean complexity classes P and NP, his theory characterizes the difficulty of computing fundamental functions in linear algebra, namely the determinant and permanent. Together with his work on #P, this set the stage for some of the most exciting subsequent developments in computational complexity, such as the development of interactive proofs for problems beyond NP.

A third broad area in which Valiant has made important contributions is the theory of parallel and distributed computing. His design of randomized routing strategies laid the groundwork for a rich body of research that exposed how randomization can be used to offset congestion effects in communication networks. He proposed the bulk synchronous model of parallel computation. He also posed a number of influential challenges leading to the construction of parallel algorithms for seemingly inherently sequential problems. Finally, the superconcentrators constructed by Valiant in the context of computational complexity established the fundamental role of expander graphs in computation.

AI in NYT

2011-03-08T11:52:00.000-08:00

NYT has an article on the use of AI in I.B.M.’s question-answering computer Watson and also Google ranking algorithms.

Dan Ariely on his new book

2011-03-07T02:33:00.000-08:00

Scott Aaronson - Physics in the 21st Century: Toiling in Feynman's Shadow

2011-03-06T07:36:00.000-08:00

Thank you to Felix Brandt for the link.

Sixth Pan-Pacific Conference on Game Theory

2011-03-04T13:45:00.000-08:00

The Sixth Pan-Pacific Conference on Game Theory just concluded. The technical program and the list of papers can be checked from here.

Matching: findings, flaws and future

2011-03-04T12:17:00.000-08:00

Al Roth points out an interesting conference on matching theory.

India invests heavily in higher education

2011-03-03T15:04:00.000-08:00

The BBC projects India's rise as a rapidly rising powerhouse in higher education and knowledge transfer.

The figures are staggering. India's government speaks of increasing the university enrolment rate from around 12% at present to 30% of the population by 2025 - approaching the levels of many Western countries.
It wants to expand its university system to meet the aspirations of a growing middle class, to widen access, and become a "knowledge powerhouse".
It will mean increasing the country's student population from 12 million to over 30 million, and will put it on course to becoming one of the world's largest education systems.
"We will very likely be number two if not number one in terms of numbers," says Pawan Agarwal, a former civil servant and author of Indian Higher Education: Envisioning the Future.
With US enrolment stagnating and the UK cutting back on university places, "Indian graduates will become more visible globally, particularly in technical and engineering fields", Mr Agarwal predicts.

New trends in Mechanism Design

2011-02-21T09:30:00.001-08:00

NEW TRENDS IN MECHANISM DESIGN

September 5-9, 2011
Copenhagen Business School
Denmark

Workshop and Summer School organized by
CFEM, Center for Research in the Foundations of Electronic Markets (cfem.dk)

New Trends in Mechanism Design will bring together researchers from economics and computer science working on the design and analysis of economic mechanisms and on applications of such mechanism to solve real-life economic problems for companies, organizations and governments. The workshop will cover both the design of mechanisms using game theoretical analysis of incentives, and the calibration of mechanisms using experimental techniques. A main focus of the workshop will be contributions from computer science to the field of mechanism design. Over the last decade, such contributions have intensified due to the challenges raised by new application domains in the age of the Internet, in some case leading to exciting new theoretical models. The applications considered at the workshop include (but are not restricted to) auctions, including procurement auctions, combinatorial auctions, sale of digital goods, online advertising, virtual sales of production and storage capacity, pricing and tariff schemes, cost allocation mechanisms, matching systems, regulatory mechanisms like yardstick competition, and benchmarking.

The workshop will be organized with only one stream of presentations. The presentations will include talks from leading invited scholars, a limited number of contributed long talks, as well as two sessions with contributed short (5-10 minutes) presentations of key ideas and findings and panel discussions on key challenges. A tutorial on mechanism design for students and other newcomers to the field is held in the beginning of the week. The program will allow for plenty of interaction between participants.

To submit a talk (long or short) for consideration, send an abstract or a full paper by email tocfem@cs.au.dk before May 1st, 2011. The notification date is July 1st, 2011.
- Hide quoted text -
Registration for the workshop begins June 1st, 2011, at www.cfem.dk.

Confirmed keynote speakers:
Peter Cramton, University of Maryland
Uriel Feige, the Weizmann Institute
Jason Hartline, Northwestern University
Nicole Immorlica, Northwestern University
HervMoulin, Rice University
Tim Roughgarden, Stanford University

Scientific organizers:
Peter Bogetoft, Copenhagen Business School
Peter Bro Miltersen, Aarhus University

AI and Final Jeopardy!

2011-02-17T04:49:00.000-08:00

Interesting course on game theory

2011-01-27T20:57:00.000-08:00

The Mathematics of Games: Strategies, Cooperation and Fair Division
March 14-26, 2011, Sevilla, Spain

-----

Topics and lecturers:

Mathematical Models in Economics.
Prof. Salvador Barberá. Universidad Autónoma de Barcelona.
Prof. Juan de Dios Moreno Ternero. Universidad Pablo de Olavide.
Non-cooperative Games.
Prof. Julio González Díaz. Universidad de Santiago de Compostela.
Profa. Gloria Fiestras Janeiro. Universidad de Vigo.
Profa. Luisa Monroy Berjillos. Universidad de Sevilla.

Cooperative Games.
Prof. Ignacio García Jurado. Universidad de la Coruña.
Prof. Andres Jiménez Losada. Universidad de Sevilla.
Prof. Miguel Angel Hinojosa. Universidad Pablo de Olavide.

Social Choice.
Prof. Antonio Villar. Universidad Pablo de Olavide.

Operations Research Games.
Prof. Henk Norde. Tilburg University (The Netherlands).

Computational Complexity in Game Theory.
Prof. Nimrod Megiddo. IBM Corporation. Almaden Research Center. California (USA).
Prof. Justo Puerto. Universidad de Sevilla.

Repeated Games.
Prof. Tristan Tomala. HEC Paris.

Bargaining.
Prof. Amparo Mármol. Universidad de Sevilla.
Prof. Clara Ponsatí. Institut d’ Anàlisi Econòmica. C.S.I.C.
Implementation of Cooperative Solutions
Prof. Gustavo Bergantiños. Universidad de Vigo.

Fair Division.
Prof. William Thomson. Rochester University (USA).
Prof. Carmen Herrero. Universidad de Alicante.

Inauguration of SSE and the 25th anniversary of LUMS

2011-01-25T08:42:00.000-08:00

You can watch a live stream of the inauguration of the School of Science and Engineering and the 25th anniversary celebration of LUMS, on January 26, 2011 at 4 p.m. (Pakistan Standard Time). The link of the event is http://anniversary.lums.edu.pk.

Having heard good things about SSE, it is great news that science and engineering is picking up at LUMS. The programme of the event is as follows:

5:45 p.m.
Ribbon-cutting ceremony
Live Transmission
6:00 p.m.
Addresses

Dr. Ahmad Jan Durrani, Vice-Chancellor, LUMS
Dr. Robert Jaffe, First Chair, SSE Advisory Board
Dr. Richard Larson, Chair, SSE Advisory Board
Syed Babar Ali, Pro-Chancellor, LUMS
Abdul Razzak Dawood, Rector, LUMS
Student from first batch of SSE
Alumnus from first batch of LUMS

7:30 p.m.
Screening of LUMS 25^th anniversary video
7:45 p.m.
Dinner

The Price of Anarchy

2011-01-07T06:51:00.000-08:00

Joseph Malkevitch revisits the concept of 'Price of Anarchy' in the latest AMS feature column.

Paul Milgrom:The Promise and Problems of Market Design

2011-01-04T13:51:00.000-08:00

Paul Milgrom Nemmers Prize Lecture from Steve Goldband on Vimeo.

Thanks to Prof. Martin Bichler for the link!

The Second Workshop on Cooperative Games in Multiagent Systems

2010-12-22T12:30:00.000-08:00

The Second Workshop on Cooperative Games in Multiagent Systems (CoopMAS-2011)
http://staff.science.uva.nl/~stephane/coopmas11/

Workshop co-located with AAMAS-2011 // Tapei, Taiwan
May 3rd, 2011
Foci:

* Cooperative game theory
* Coalition formation
* Joint decision making and voting
* Negotiation
* Collaborative filtering
* Market and economics based cooperation

Key dates
* Submission of contributions: January 30th 2011
* Acceptance notification: February 27th 2011
* Workshop: May 3rd, 2011

Workshop on Social Choice and AI

2010-12-21T13:44:00.000-08:00

After the success of COMSOC workshops, there is another workshop on a similar theme:

IJCAI Workshop on Social Choice and Artificial Intelligence

Barcelona, 16 July 2011

AI for war and peace

2010-11-29T07:54:00.000-08:00

The economist profiles the ALADDIN project which stands for 'Autonomous Learning Agents for Decentralised Data and Information Networks' and is a project whose collaboraters include BAE Systems, University Southampton, and my alma mater, University of Oxford. The research involves

...techniques that include game theory (in which agents have to overcome barriers to collaboration in order to get the best outcome), probabilistic modelling (which is employed to predict missing data and reduce uncertainty) and optimisation techniques (which can provide means of making decisions when communications between agents are limited). A number of the algorithms also employ auctions to allocate resources among competing users.

Algorithm finds kidneys

2010-11-26T08:56:00.000-08:00

Futurity covers algorithmic techniques for kidney matching markets.

How NOT to review a paper: funny:)

2010-11-18T10:14:00.000-08:00

Graham Cormode's take on how not to review a paper.

David Parkes: Incentive Engineering in the Internet Age

2010-11-06T16:21:00.000-07:00

16th Coalition Theory Network Workshop: Barcelona, February 4-5, 2011

2010-11-03T07:22:00.000-07:00

From the website:

The Center for the study of the Organizations and Decisions in Economics (CODE) of the Universitat Autònoma de Barcelona and MOVE will be organizing the 16th Coalition Theory Network Workshop in Barcelona, Spain, on February 4-5, 2011. We cordially invite you to attend. The Workshop will present the state of the art of theoretical, experimental and empirical research in:

Coalition formation;
Network formation;
Matching.

Confirmed invited speakers are:

Francis Bloch (École Polytechnique);
Lars Ehlers (Université de Montréal);
Andrea Galeotti (University of Essex).

How Markets Fail: The Logic of Economic Calamities

2010-10-18T07:01:00.000-07:00

The author of 'How Markets Fail: The Logic of Economic Calamities', John Cassidy talks about his book:

http://www.c-spanvideo.org/program/290952-1

Mining social networks: Untangling the social web

2010-09-20T02:16:00.000-07:00

The Economist discusses the importance of new algorithmic tools to analyse social networks.

The Social Network

2010-09-12T02:10:00.000-07:00

The Guardian profiles the upcoming movie 'The Social Network' which depicts how Facebook started.

Conference in town

2010-08-31T03:46:00.000-07:00

OR2010 is starting this week in Munich [map]. Game theory sessions include the following:

Contributions to Cooperative Game Theory [TA-14 Thursday, 8:30-10:00 3101]

A Value for Games with a Coalition Structure (Francesc Carreras)
On the Use of Generating Functions to Compute Power Indices based on Minimal Winning Coalitions (Josep Freixas)
Data Cost Games: The 1-Concavity and Core Properties (Theodorus S.H. Driessen)

Theoretical Contributions to Game Theory [TD-14 Thursday, 14:00-15:30 3101]

A Fresh Look on the Battle of Sexes Paradigm (Rudolf Avenhaus)
Non-negativity of Information Value in Games, Symmetry and Invariance (Sigifredo Laengle)
Algorithmic Aspects of Equilibria of Stable Marriage Model with Complete Preference Lists
(Tomomi Matsui)

COMSOC 2010 program

2010-08-27T02:06:00.000-07:00

The COMSOC 2010 program is up. PAMAS has a decent showing with four papers:

On the Fixed-Parameter Tractability of Composition-Consistent Tournament Solutions
Felix Brandt, Markus Brill, and Hans Georg Seedig
Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates
Felix Brandt, Markus Brill, Edith Hemaspaandra, and Lane A. Hemaspaandra
Optimal Partitions in Additively Separable Hedonic Games
Haris Aziz, Felix Brandt, and Hans Georg Seedig
Group-Strategyproof Irresolute Social Choice Functions
Felix Brandt

Web Alternative to Peer Review?

2010-08-24T01:40:00.000-07:00

The NYT looks at how the web may be changing the dynamics of how academic work is reviewed.

Daniel Spielman gets the Nevanlinna Prize

2010-08-19T03:24:00.000-07:00

Daniel Spielman of Yale University, USA, has been chosen for the 2010 Rolf Nevanlinna Prize for smoothed analysis of Linear Programming, algorithms for graph-based codes and applications of graph theory to Numerical Computing. More details on the website of ICM (International Congress of Mathematicians) where the prize will be awarded. Previous winners include Robert Tarjan, Leslie Valiant, Alexander Razborov, Avi Wigderson, Peter Shor, Madhu Sudan, and Jon Kleinberg.

Wired magazine profiles Prabhakar Raghavan

2010-08-18T05:56:00.000-07:00

Wired magazine profiles Prabhakar Raghavan who is not only the head of Yahoo Labs but is now the senior vice president of Yahoo. Raghavan is of course well-known in the theoretical computer science community.

P vs NP

2010-08-12T01:51:00.000-07:00

BBC coverage of the P vs NP question: http://www.bbc.co.uk/news/science-environment-10938302
Meanwhile, a more expert discussion on Deolalikar's ideas is live on Richard Lipton's blog and this wiki page.

The Vexing Mathematics of Democracy

2010-08-07T03:58:00.000-07:00

Donald Saari reviews a new book on mathematics of voting.

David H. Blackwell passes away

2010-08-04T06:08:00.000-07:00

http://www.washingtonpost.com/wp-dyn/content/article/2010/07/15/AR2010071506274.html

The practical power of game theory

2010-07-29T13:09:00.000-07:00

In the 2010 Nancy L. Schwartz Memorial Lecture, Harvard Professor Alvin Roth explains how market design can help save lives:
http://www.kellogg.northwestern.edu/news/video/opencontent/2010/Schwartz_Lecture.htm

Forbes profiles Al Roth

2010-07-26T06:03:00.000-07:00

http://www.forbes.com/forbes/2010/0809/opinions-harvard-alvin-roth-freakonomics-ideas-opinions.html

Recommendation Systems: wisdom of the crowd?

2010-07-19T07:23:00.000-07:00

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

Combinatorics of social choice

2010-07-17T05:04:00.000-07:00

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:

A plug for a TCS event

2010-07-10T01:41:00.000-07:00

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.

SAGT 2010 accepted papers

2010-06-28T12:43:00.000-07:00

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 Skopalik and Martin Hoefer. On the Complexity of Pareto-optimal Nash and Strong Equilibria
Noam Hazon and Edith Elkind. Complexity of Safe Strategic Voting
Constantinos Daskalakis , Rafael Frongillo, Christos Papadimitriou , George Pierrakos and Gregory Valiant. On Learning Algorithms for Nash Equilibria
Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum, Or Sheffet and Santosh Vempala. On Nash-Equilibria of Approximation-Stable Games
Uriel Feige and Inbal Talgam. A Direct Reduction from k-Player to 2-Player Approximate Nash
Martin Gairing and Rahul Savani. Computing stable outcomes in hedonic games
Uri Nadav and Georgios Piliouras. No Regret Learning in Oligopolies: Cournot vs Bertrand
Kristoffer Arnsfelt Hansen , Peter Bro Miltersen and Troels Bjerre Sørensen. The computational complexity of trembling hand perfection and other equilibrium refinements
Bharat Adsul , Sobhan Babu , Jugal Garg , Ruta Mehta and Milind Sohoni. A Simplex-like Algorithm for Fisher Markets
Matus Mihalak and Jan Christoph Schlegel. It's mostly constant in network creation games
Vijay Vazirani. 2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties
Volodymyr Kuleshov and Adrian Vetta. On the Efficiency of Markets with Two-Sided Proportional Allocation Mechanisms
Elliot Anshelevich , Bugra Caskurlu and Ameya Hate. Partition Equilibrium Always Exists in Resource Selection Games
Martin Macko, Kate Larson and Ľuboš Steskal. Braess's Paradox for Flows Over Time
Gagan Goel and Vijay Vazirani. A Perfect Price Discrimination Market Model with Production, and a Convex Program for it
Alex Fabrikant, Aaron D. Jaggard and Michael Schapira. On the Structure of Weakly Acyclic Games
Vittorio Bilo , Ioannis Caragiannis , Angelo Fanelli and Gianpiero Monaco. Improved lower bounds on the price of stability of undirected network design games
Bart de Keijzer , Guido Schaefer and Orestis Telelis. On the Inefficiency of Equilibria in Linear Bottleneck Congestion Games
Rajgopal Kannan and Costas Busch. Bottleneck Congestion Games with Logarithmic Price of Anarchy

AGT in CACM

2010-06-26T01:44:00.000-07:00

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?

COMSOC 2010

2010-06-21T10:53:00.000-07:00

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 the Coalitional Manipulation Problem under Maximin
Mirco Gelain, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable and Toby Walsh. Local search for stable marriage problems
Davide Grossi and Paolo Turrini. Dependence in Games and Dependence Games
Ning Chen and Arpita Ghosh. Algorithms for Pareto Stable Assignment
Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable and Toby Walsh. Stable marriage problems with quantitative preferences
Ronald L. Rivest and Emily Shen. An Optimal Single-Winner Preferential Voting System Based on Game Theory
Reshef Meir, Maria Polukarov, Jeffrey S. Rosenschein and Nicholas R. Jennings. Convergence to Equilibria in Plurality Voting
Victor Naroditskiy, Maria Polukarov and Nicholas R. Jennings. Linear Mechanisms for Single-Parameter Domains: Characterization, Existence, and Construction
Haris Aziz, Felix Brandt and Hans Georg Seedig. Optimal Partitions in Additively Separable Hedonic Games
Yonatan Aumann and Yair Dombb. The Efficiency of Fair Division with Connected Pieces
Sylvain Bouveret, Ulle Endriss and Jerome Lang. Fair Division under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods
Noam Hazon and Edith Elkind. Complexity of Safe Strategic Voting
Andreas Darmann, Christian Klamler and Ulrich Pferschy. A Maximin Approach to Finding Fair Spanning Trees
Felix Brandt. Group-Strategyproof Irresolute Social Choice Functions
Felix Brandt, Markus Brill and Hans Georg Seedig. On the Fixed-Parameter Tractability of Composition-Consistent Tournament Solutions
Ulle Endriss, Umberto Grandi and Daniele Porello. Complexity of Winner Determination and Strategic Manipulation in Judgment Aggregation
Ilan Nehama. Approximate Judgment Aggregation
Toby Walsh. Online Cake Cutting
Koji Takamiya. Complexity consideration on the existence of strategy-proof social choice functions
Tatyana Gvozdeva, Lane A. Hemaspaandra and Arkadii Slinko. Three Hierarchies of Simple Games Parameterized by "Resource'' Parameters
Arkadii Slinko, Piotr Faliszewski and Edith Elkind. Cloning in Elections
Péter Biró and Tamás Fleiner. Fractional solutions for NTU-games
Tyler Lu and Craig Boutilier. Budgeted Social Choice: A Framework for Multiple Recommendations in Consensus Decision Making
Nadja Betzler, Robert Bredereck and Rolf Niedermeier. Exact Rank Aggregation Based on Effective Data Reduction
Britta Dorn and Ildikó Schlotter. Multivariate Complexity Analysis of Swap Bribery
Ioannis Caragiannis, Dimitris Kalaitzis and Evangelos Markakis. Approximation algorithms and mechanism design for minimax approval voting
Lirong Xia, Jérôme Lang and Jérôme Monnot. Possible Winners When New Alternatives Join: New Results Coming Up!
Ioannis Caragiannis, Christos Kaklamanis, Nikos Karanikolas and Ariel Procaccia. Socially desirable approximations for Dodgson's voting rule
Daniel Eckert and Christian Klamler. A problem with strategy-proofness for abstract aggregation rules with metrically consistent preferences
Mark Wilson and Reyhaneh Reyhani. The probability of safe manipulation
Gabor Erdelyi and Michael Fellows. Parameterized Control Complexity in Bucklin Voting and in Fallback Voting
Jessica Davies, George Katsirelos, Nina Narodystka and Toby Walsh. An Empirical Study of Borda Manipulation

Amartya Sen: The Search For Justice

2010-06-16T06:09:00.000-07:00

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

Visions for Theoretical Computer Science

2010-06-15T13:53:00.000-07:00

Ever wondered how to sell or explain the importance of your favourite research topic to a lay-person?

The Visions for Theoretical Computer Science Team has put together a wonderful advertisement for what theoretical computer science is about and what it seeks to do. Check it out from here.

Martin Gardner

2010-06-13T13:19:00.000-07:00

The Economist has an obituary of Martin Gardner in a recent issue:

----------------------

WHERE literacy meets numeracy, enthusiasm meets scepticism and philosophy meets fun, there you find Martin Gardner. He earned his crust by writing, but his abiding interest was in maths, and his gift, or rather one of them, was to explain mathematical concepts in ways that made sense to non-mathematicians. Many of them not only understood what he wrote but also became infected with his love of maths, of its beauty and of its capacity to give satisfaction, if not delight, when its riddles were solved and its paradoxes explained. For 25 years he provided both the puzzlement and the demystification in a column in Scientific American.

Mr Gardner did not come to this task from MIT or Caltech. Indeed, he had no formal maths training after high school in Tulsa, Oklahoma. But he did come from a job in journalism, to be precise, from a post at Humpty Dumpty’s Magazine for Little Children, where among other tasks he helped with the designs, including all the cutouts. Cutouts also came his way when a conjuror introduced him to the hexaflexagon, a piece of paper folded into an almost flat six-sided shape that could be manipulated to reveal a series of different interiors one after another. This inspired him to write the article that launched his column, “Mathematical Games”, and with it a pastime now known as recreational maths.

Since this is a more benign, though almost equally addictive, version of its close relation, recreational drugs, it soon had a large following. Many were no doubt obsessive male teenagers and their fathers, epitomised perhaps by the followers of GeekDad, a blog that celebrates Geek Pride Day, nerdcore music and geek-chic fashion, as well as Mr Gardner. Some may have been sudoku, tredoku or futoshiki freaks, who buy daily newspapers, extract the puzzle pages and throw away the rest.

Others, however, were quite respectable. It is notable that Mr Gardner was one of the few popularisers of difficult subjects who earned the respect of serious thinkers, W.H. Auden, Noam Chomsky, Stephen Jay Gould and Douglas Hofstadter among them. Some, such as Roger Penrose (an Oxford mathematical physicist) and John Conway (a Princeton mathematician), owe some of their own celebrity to his writings about their work. No wonder it is sometimes said that Mr Gardner made mathematicians out of children and children out of mathematicians.

Maths, however, was far from being Mr Gardner’s only interest, even though it inevitably played a part in his most popular book, “The Annotated Alice”. This went through Lewis Carroll’s two Alice books, explaining the umpteen puns, jokes and allusions. He did the same for other works, including Coleridge’s “The Rime of the Ancient Mariner”, Chesterton’s “The Innocence of Father Brown”, Joyce’s “Ulysses”, Moore’s “The Night Before Christmas” and Baum’s “The Wonderful Wizard of Oz”.

This was micro stuff, but Mr Gardner did the big picture too. He could defend realism in the face of quantum physics, tackle infinity and nothing, venture into the realms beyond cultural relativism, test proofs of God and wonder whether Isaiah Berlin was a hedgehog or a fox. He wrote with lucidity about the works of computer scientists, philosophers and playwrights, always giving credit where it was due.

Logic conquers (almost) all

Yet he was far more than a synthesiser. Indeed, all his non-fiction—he also wrote novels, short stories and poetry—was rigorously analytical. And though he was shy, usually shunning his fans’ two-yearly “Gatherings for Gardner”, he was not afraid to speak his mind. Any beliefs he thought pseudoscientific, such as homeopathy, Scientology, creationism, anthroposophy, spoon-bending, astrology and flying saucers, he would dismiss with cool efficiency. Other ideas, such as Ronald Reagan’s beloved Laffer curve, were derided in spoof articles: Mr Gardner had a sense of humour, and used it to effect. But he was not malicious. Though he enjoyed hoaxes, he would sometimes turn them on himself, once writing, under a pseudonym, a withering review of one of his own works in the New York Review of Books.

Did he spread himself too thin? It is hard not to think that anyone who writes more books (70-plus) than many people have read, as well as numberless articles and essays, must be at the controls of a sausage machine, yet the sausages were usually good. The harder question is where it all came from, to which the only answer is himself—and reading.

Studying philosophy at the University of Chicago, and reading voraciously from Plato to Kant to H.G. Wells, he abandoned the Christian fundamentalism of his teenage years and acquired an enduring respect for rationalism and science. Along the way, he also came to love magic—not spells and sorcery, but the tricks and illusions of puzzlers and prestidigitators.

Perhaps this helps explain the belief in God that he came to in later life. His declaration of this belief caused, he admitted, profound shock to those who knew him only as a sceptic. But there was too much playfulness in Mr Gardner to make him yield entirely to reason. His faith, he said, was based on an “emotional turning of the will”, unsupported by logic or science. It was his way, perhaps, of recognising that mind and man are not synonyms.

University guide

2010-06-08T09:56:00.000-07:00

The Guardian has published its UK University Guide 2011. The guide has also ranked the UK universities according to 'teaching excellence'. The fact that Oxford and Cambridge occupy the top two spots is not surprising. Interestingly, Warwick has now made its way to number 3 in The Guardian's estimate.

Germans tend to be less ranking oriented in terms of higher education. However, in the last few years, the idea of elite universities has been put forward as part of the German Universities Excellence Initiative. The city of Munich is doing rather well in this list with the presence of both Munich universities, LMU and TUM.

Tim Harford: Logic of Life

2010-05-27T03:45:00.000-07:00

Federated Computer Research Conference (FCRC) 2011

2010-05-26T06:10:00.000-07:00

FCRC '11 will be held June 4-11, 2011 in San Jose. Meetings affiliated with FCRC include EC, STOC, NetEcon and Complexity.

AAAI accepted papers on multiagent systems

2010-05-24T13:41:00.000-07:00

(List from here)

210: Nonmanipulable Randomized Tournament Selections
Alon Altman, Robert Kleinberg

333: Competing Schedulers
Itai Ashlagi, Moshe Tennenholtz, Aviv Zohar

145: Probabilistic Possible Winner Determination
Yoram Bachrach, Nadja Betzler, Piotr Faliszewski

146: Coalitional Structure Generation in Skill Games
Yoram Bachrach, Reshef Meir, Kyomin Jung, Pushmeet Kohli

235: Transferable Utility Planning Games
Ronen I. Brafman, Carmel Domshlak, Yagil Engel, Moshe Tennenholtz

249: Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates - Felix Brandt, Markus Brill, Edith Hemaspaandra, Lane A. Hemaspaandra

972: Private and Third-Party Randomization in Risk-Sensitive Equilibrium Concepts
Mickey Brautbar, Michael Kearns, Umar Syed

581: An Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games
Andriy Burkov, Brahim Chaib-draa

75: Approximation Algorithms and Mechanism Design for Minimax Approval Voting
Ioannis Caragiannis, Dimitris Kalaitzis, Evangelos Markakis

23: Voting Almost Maximizes Social Welfare Despite Limited Communication
Ioannis Caragiannis, Ariel D. Procaccia

746: A Distributed Algorithm for Optimising over Pure Strategy Nash Equilibria
Archie C. Chapman, Alessandro Farinelli, Enrique Munoz de Cote, Alex Rogers, Nicholas R. Jennings

39: Truth, Justice, and Cake Cutting
Yiling Chen, John K. Lai, David C. Parkes, Ariel D. Procaccia

192: Possible Winners When New Candidates Are Added: The Case of Scoring Rules
Yann Chevaleyre, Jérôme Lang, Nicolas Maudet, Jérôme Monnot

177: Cloning in Elections
Edith Elkind, Piotr Faliszewski, Arkadii Slinko

521: Good Rationalizations of Voting Rules
Edith Elkind, Piotr Faliszewski, Arkadii Slinko

631: Lifting Rationality Assumptions in Binary Aggregation
Umberto Grandi, Ulle Endriss

606: Intentions in Equilibrium
John Grant, Sarit Kraus, Michael Wooldridge

212: Security Games with Arbitrary Schedules: A Branch and Price Approach
Manish Jain, Erim Kardes, Christopher Kiekintveld, Milind Tambe, Fernando Ordóñez

119: Algorithms for Finding Approximate Formations in Games
Patrick R. Jordan, Michael P. Wellman

682: Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games
Dmytro Korzhyk, Vincent Conitzer, Ronald Parr

885: Stability and Incentive Compatibility in a Kernel-Based Combinatorial Auction
Sébastien Lahaie

360: Facilitating the Evaluation of Automated Negotiators Using Peer Designed Agents
Raz Lin, Sarit Kraus, Yinon Oshrat, Ya'akov (Kobi) Gal

188: Convergence to Equilibria in Plurality Voting
Reshef Meir, Maria Polukarov, Jeffrey S. Rosenschein, Nicholas R. Jennings

205: Envy Quotes and the Iterated Core-Selecting Combinatorial Auction
Abraham Othman, Tuomas Sandholm

30: Can Approximation Circumvent Gibbard-Satterthwaite?
Ariel D. Procaccia

773: Trust Models and Con-Man Agents: From Mathematical to Empirical Analysis
Amirali Salehi-Abari, Tony White

617: Increasing Threshold Search for Best-Valued Agents
David Sarne, Simon Shamoun, Eli Rata

196: Approximate Coalition Structure Generation
Travis C. Service, Julie A. Adams

780: Accounting Mechanisms for Distributed Work Systems
Sven Seuken, Jie Tang, David C. Parkes

916: Asymmetric Spite in Auctions
Ankit Sharma, Tuomas Sandholm

732: A Decentralised Coordination Algorithm for Mobile Sensors
Ruben Stranders, Francesco Maria Delle Fave, Alex Rogers, Nicholas R. Jennings

151: Urban Security: Game-Theoretic Resource Allocation in Networked Physical Domains
Jason Tsai, Zhengyu Yin, Jun-young Kwak, David Kempe, Christopher Kiekintveld, Milind Tambe

852: Automated Channel Abstraction for Advertising Auctions
William E. Walsh, Craig Boutilier, Tuomas Sandholm, Rob Shields, George Nemhauser, David C. Parkes

642: Fixing a Tournament
Virginia Vassilevska Williams

950: Beyond Equilibrium: Predicting Human Behavior in Normal Form Games
James R. Wright, Kevin Leyton-Brown

149: Trial-Based Dynamic Programming for Multi-Agent Planning
Feng Wu, Shlomo Zilberstein, Xiaoping Chen

434: Compilation Complexity of Common Voting Rules
Lirong Xia, Vincent Conitzer

435: Stackelberg Voting Games: Computational Aspects and Paradoxes
Lirong Xia, Vincent Conitzer

195: Multi-Agent Learning with Policy Prediction
Chongjie Zhang, Victor Lesser

455: Dynamic Auction: A Tractable Auction Procedure
Dongmo Zhang, Wei Huang, Laurent Perrussel

525: Sequential Incremental-Value Auctions
Xiaoming Zheng, Sven Koenig

1084: Tolerable Manipulability in Dynamic Assignment without Money
James Zou, Sujit Gujar, David Parkes

Workshop on Multiagent Resource Allocation

2010-05-21T06:22:00.000-07:00

4th MARA Get-Together: Workshop on Multiagent Resource Allocation:

Paris, 17-18 June 2010

http://www.lamsade.dauphine.fr/~maudet/mara/

Innovations in Computer Science (ICS 2010)

2010-05-19T02:05:00.000-07:00

The slides of papers are presented in Innovations in Computer Science (ICS 2010) are available at
http://conference.itcs.tsinghua.edu.cn/ICS2010/

Workshop On Advances in Algorithmic Game Theory

2010-05-18T03:14:00.000-07:00

WORKSHOP ON ADVANCES IN ALGORITHMIC GAME THEORY

Center for Mathematics and Computer Science (CWI)
Amsterdam, The Netherlands
September 2-3, 2010

Workshop website: http://www.cwi.nl/~schaefer/agt10

The two-day workshop will be hosted at the Center for Mathematics and
Computer Science (CWI) in Amsterdam and will take place September 2-3,
2010. There will be four keynote talks and about 12 contributed talks.
The keynote speakers are:

* Ioannis Caragiannis (University of Patras, Greece)
* Michal Feldman (Hebrew University of Jerusalem, Israel)
* Jason Hartline (Nothwestern University, USA)
* Tim Roughgarden (Stanford University, USA)

Reiju Mihara: Video on social choice

2010-05-06T11:47:00.000-07:00

London Combinatorics Colloquia, London, England, UK, 19-20 May 2010

2010-05-02T07:07:00.000-07:00

London Combinatorics Colloquia, London, England, UK, 19-20 May 2010 :
http://www2.lse.ac.uk/maths/Seminars/Colloquia_in_Combinatorics.aspx

Workshop on Solution Concepts for Extensive Games

2010-05-02T05:53:00.000-07:00

Workshop on Solution Concepts for Extensive Games at Center for Algorithmic Game Theory, Aarhus University, Aarhus, Denmark from June 22 to June 25, 2010. http://www.cs.au.dk/cagt/sol.html

COST-ADT Doctoral School on Computational Social Choice

2010-04-29T05:13:00.000-07:00

The COST Action IC0602 ``ADT (Algorithmic Decision Theory)’’ is a collaborative project to build European-wide capability in algorithmic decision theory. A COST-ADT Doctoral School on Computational Social Choice was held in Estoril, Portugal from 9 to14 April 2010. There were more than 50 participants spanning more than twenty countries and the following research areas: computational social choice theory, multiple criteria decision analysis, decision under risk and uncertainty, algorithmic decision theory and welfare economics. The main local organizer of the school was José Rui Figueira. The school was based on a series of tutorials:

Christian Klamer (Institute of Public Economics at Graz University) lectured on the mathematical aspects of voting theory. In the first lecture he outlined the commonly used voting rules. In the second lecture, he was successful in his ambitious goal of explaining the proofs of three classic impossibility results in social choice theory: Arrow’s impossibility theorem Gibbard Sattherwaite theorem and Sen’s Liberal Paradox. His third lecture was based on Saari’s Geometry of voting.
Ulle Endriss (ILLC, University of Amsterdam) presented well organized lectures on fair division aspects of social choice theory. In his first lecture, he introduced social welfare theory. The second and third lectures were on fair division of divisible objects (cake cutting) and indivisible objects respectively.
Jerôme Lang (CNRS-LAMSADE, Paris) presented interactive lectures on computational and communication complexity aspects of social choice theory including complexity of computing winners, agenda control and voting insincerely.

The tutorial lecturers not only introduced the material but discussed recent results and future research directions. Apart from the three main tutorials, invited senior researchers also gave single lectures. José Rui Figueira presented the history of social choice theory and its contributors. Felix Brandt surveyed important axiomatic result in social choice theory and discussed three possible escape routes from Arrow’s impossibility theorem. Stefano Moretti presented the application of simple coalitional games and Shapley value to bioinformatics. Sébastien Konieczny and Thierry Marchant presented lectures on `Information Fusion and Social Choice’ and `From Social Choice to Multi-criteria Decision Analysis’ respectively.

During the event, participants also presented contributed talks. The highlights of the student talks were the following: Markus Brill’s presentation on the Tournament Equilibrium Set; Britta Dorn’s outline of the complexity aspect of scoring rules with incomplete preferences; Christian Geist’s impressive results on using SAT solvers and induction arguments to generate new and old impossibility results; and Paul Dütting’s talk on the state of the art of combinatorial auctions.

The school was organized in a relaxed manner with plenty of opportunities for participants to mingle and socialize. This included an enjoyable concert by a local band and an excurison. Apart from the COST Action and its relevant committees which were the driving force behind the school, the following sponsors of the school should also be acknowledged: CEG-IST, NANO-Risk Project, IST (TagusPark) and BPI (Banco Português de Investimentos). The talks and lectures are planned to be uploaded on the following website: http://cost-ic0602.org/.

DIMAP Summer School on Approximation and Randomized Algorithms, July 12 - 16, 2010

2010-04-17T13:20:00.000-07:00

A Summer School on Approximation and Randomized Algorithms is organized by the Centre for Discrete Mathematics and its Applications (DIMAP) at the University of Warwick, July 12 - 16, 2010.

The registration deadline is interesting: one day after England is eliminated from the 2010 FIFA World Cup (some time between June 26 and July 12).

Richard Thaler, "Using Behavioral Economics to Improve Decision Making"

2010-04-17T11:33:00.000-07:00

Polynomial Time Algorithm for Graph Isomorphism Testing?

2010-04-13T16:02:00.000-07:00

I just came across the following new report: http://arxiv.org/find/cs/1/au:+Trofimov_M/0/1/0/all/0/1.
The complexity of the graph isomoprphism problem is a longstanding open problem. Therefore, it will be interesting to check if the problem has finally been resolved.

ICALP accepted papers

2010-04-10T11:46:00.000-07:00

ICALP accepted paper list is now public: http://icalp10.inria.fr/index.php?n=Main.AcceptedPapers. Some papers which caught my eyes were:

Nikhil Bansal and Subhash Khot. Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems

MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Nicole Immorlica and Hamid Mahini. The cooperative game theory foundations of network bargaining games

Jian Li, Ke Yi and Qin Zhang. Clustering with Diversity

Tobias Harks and Max Klimm. On the Existence of Pure Nash Equilibria in Weighted Congestion Games

Anupam Gupta, Viswanath Nagarajan and R Ravi. Thresholded Covering Algorithms for Robust and Max-Min Optimization

Allan Borodin and Brendan Lucier. On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions

Loukas Georgiadis. Testing $2$-vertex connectivity and computing pairs of vertex-disjoint $s$-$t$ paths in digraphs

T-H. Hubert Chan, Elaine Shi and Dawn Song. Private and Continual Release of Statistics

Giorgos Christodoulou, Katrina Ligett and Evangelia Pyrga. Contention Resolution under Selfishness

John Fearnley. Exponential Lower Bounds For Policy Iteration

Dan Alistarh, Seth Gilbert, Rachid Guerraoui and Morteza Zadimoghaddam. How Efficient Can Gossip Be? (On the Message Complexity of Resilient Information Exchange)

Anna Blasiak and Robert Kleinberg. The Serializability of Network Codes

Nikhil Bansal, Kamal Jain, Anna Kazeykina and Joseph (Seffi) Naor. Approximation Algorithms for Diversified Search Ranking

Ning Chen and Xiaotie Deng. Envy-Free Pricing in Multi-Item Markets

Arend Rensink. Compositionality in Graph Transformation

Ron Graham, "Computers and Mathematics: Problems and Prospects"

2010-04-04T05:23:00.000-07:00

Mathematics and Sports

2010-04-04T05:16:00.000-07:00

In the latest AMS feature column, Joseph Malkevitch discusses mathematics involved in sports scheduling and related fairness and optimization questions in choosing rankings or winners.

ADFOCS 2010

2010-04-02T14:13:00.000-07:00

The 11th Max-Planck Summer School Advanced Course on the Foundations of Computer Science (ADFOCS 2010) will be held from August 2 - 6, 2010 in Saarbruecken, Germany.

The topic is `Approximation Algorithms and Algorithmic Game Theory’ and the invited speakers are Christos Papadimitriou,Vijay Vazirani and Guido Schaefer. Topics covered in the course will be `Computing Equilibria’, `Traditional to Novel Market Models: the Quest for the 'Right' One’ and `Cost Sharing and Approximation Algorithms’.

Bertinoro Workshop on Frontiers in Mechanism Design

2010-04-01T10:00:00.000-07:00

An interesting workshop on algorithmic mechanism design : http://econ.eecs.northwestern.edu/FMD2010/#schedule

Christos Papdimitriou discusses "Logicomix"

2010-03-20T13:21:00.000-07:00