Monday, December 17, 2012

Ziggie and Zack

A couple of weeks ago I went to a kickoff meeting of COST action IC1215 on computational social choice, and picked up a copy of the most colourful publication on display, “Ziggie and Zack: Your Lightning Heroes” (PDF), a final publication of an earlier COST action on the Physics of Lightning Flash and its Effects. I am now hopeful that the new COST action will produce a similar output featuring the hazards of voting paradoxes and computationally intractable solution concepts.

Thursday, December 13, 2012

WINE update

WINE 2012 (held here in Liverpool, UK) came to a successful conclusion yesterday; I should again thank the local organisers. On Tuesday we had a short business meeting to discuss renaming WINE from “workshop” to “conference”, which is a topic I was asked to raise by colleagues a few weeks ago. Since WINE is a conference in all but name, there was a clear consensus to do this, but retaining the acronym. The favoured name that retains the acronym is “Web Interaction and Network Economics”.

Here is a link to the Google Research blog article on WINE 2012.

We also discussed closer links with ACM, with David Parkes (chair of ACM SIGecom) suggesting some options. Currently WINE just has “in association” status with SIGecom. Being an ACM conference would represent some kind of badge of approval, and would provide some organisational support, such as links to ACM digital library and accounting/insurance/negotiation with venues. Being an ACM conference would cost money, but they would take the loss if an occurrence of WINE lost money, so it is a kind of insurance. ACM could alternatively share this status with another non-profit partner, e.g. maybe EATCS.

WINE 2013 will be at Harvard, and for WINE 2014 we had a very nice presentation by Tie-Yan Liu (at MSR Asia), for hosting WINE 2014 at either Beijing or Hong Kong (which one may depend on whether funding is forthcoming for a co-located winter school in Hong Kong). Finally, Martin Hoefer gave a presentation advertising SAGT 2013 to be held in Aachen, Germany (in the SuperC Building) (in October 2013).

Saturday, December 08, 2012

WINE 2012 web site

In case anyone gets here after having trouble reaching the WINE 2012 web site (due to server going down), here are links to some cached pages:

BTW the reception at the Athenaeum is at 6:00pm.

Monday, October 29, 2012

AGT/COMSOC program in Singapore

This winter, Institute for Mathematical Sciences (Singapore) will host a 2-month long program on algorithmic game theory and computational social choice, organized by Ning Chen (NTU) and Edith Elkind (NTU). The program includes three workshops - a mini-workshop on mechanism design (Jan 10-11), a week-long workshop on algorithmic game theory (Jan 14-18), and a week-long workshop on computational social choice (Jan 20-25) - as well as longer stays by some of the invited researchers.  A graduate winter school will be run in parallel with the workshops. Confirmed speakers include Rakesh Vohra, Tim Roughgarden, Jason Hartline, Kevin Leyton-Brown, Ulle Endriss, Jerome Lang and Jean-Francois Laslier; see http://www2.ims.nus.edu.sg/Programs/013game/gen_visitorlist.php#overseas
for the complete list.

The workshops are open to participation. There is no registration fee, but the prospective visitors are asked to fill out the registration form at http://www2.ims.nus.edu.sg/Programs/013game/register.php and drop an e-mail to Edith and Ning (eelkind, ningc at ntu.edu.sg). Thanks to generous support from the IMS and the AI Journal, we will be able to provide financial support (accommodation and/or travel) to a limited number of graduate students and young scientists who wish to attend the winter school; the applications for financial support can be filled out at http://www2.ims.nus.edu.sg/Programs/013game/onlineform/register.php

Wednesday, October 17, 2012

RA positions in Algorithmic Mechanism Design at the Universities of Liverpool and Glasgow

This article by the BBC’s economics editor celebrates the award of the Nobel Prize for economics to Alvin Roth and Lloyd Shapley. See also this article by The Guardian’s economics editor.

A forthcoming research project at the Universities of Liverpool and Glasgow addresses topics that are highly related to those that led to the above prize. Below is a copy of the ad that went to various mailing lists.

POSTDOCTORAL RESEARCH ASSOCIATE POSITIONS IN ALGORITHMIC MECHANISM DESIGN

UNIVERSITY OF LIVERPOOL, DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF GLASGOW, SCHOOL OF COMPUTING SCIENCE

Start date: 1 February 2013 or shortly thereafter
Post duration: 36 months
Salary: 31,948 - 35,938 pounds per annum

Ref.: R-580873 (Liverpool), 002834 (Glasgow)

We are seeking two Research Associates to be employed for 3 years on an EPSRC-funded research project entitled “Efficient Algorithms for Mechanism Design without Monetary Transfer”.

The aim of this project is to find new approximate and optimal, truthful mechanisms for combinatorial auctions, matching problems with preferences and facility location problems, in each case in the absence of monetary transfer. This will involve theoretical research, to include the design and analysis of new algorithms, and also practical implementation and experimental evaluation of these algorithms.

This is a multi-site research project which involves the Universities of Liverpool and Glasgow (EPSRC grant refs EP/K01000X/1 and EP/K010042/1).

One Research Associate will be based at the University of Liverpool and will be supervised by Dr Piotr Krysta. The other will be based at the University of Glasgow and will be supervised by Dr David Manlove. Other members of the project team include Prof Paul Goldberg and Dr Giorgos Christodoulou (co-investigators, based at the University of Liverpool), and identified overseas researchers.

Applicants should have a good first degree in Computing Science or a related discipline, a PhD in the area of Algorithms and Complexity, and typically two years of postdoctoral experience in this area, or equivalent research / industrial experience.

Research experience in one or more of the following areas is desirable:
- algorithmic mechanism design
- combinatorial optimisation
- approximation algorithms
- matching problems with preferences

Applications for each post should be directed to the University of Liverpool or Glasgow as appropriate. Applicants are welcome to apply for both positions.

For further details of the Liverpool post, see http://www.csc.liv.ac.uk/~piotr/EPSRC-postdoc.html. Informal enquiries may be made to Dr Piotr Krysta (email: pkrysta@liverpool.ac.uk). To apply, visit http://www.liv.ac.uk/working.

For further details of the Glasgow post, see http://www.dcs.gla.ac.uk/~davidm/postdoc.html. Informal enquiries may be made to Dr David Manlove (email david.manlove@glasgow.ac.uk). To apply, visit http://www.gla.ac.uk/jobs.

The closing date for both posts is 12 November 2012.

Monday, September 17, 2012

WINE 2012 accepted papers


The list of papers accepted to appear at WINE 2012 is below, also on the WINE 2012 web site.

Regular papers

Vasileios Tzoumas, Christos Amanatidis and Evangelos Markakis.
A Game-Theoretic Analysis of a Competitive Diffusion Process over Social Networks

Yoram Bachrach, Ian Kash and Nisarg Shah.
Agent Failures in Totally Balanced Games and Convex Games

Joan Feigenbaum, Michael Mitzenmacher and Georgios Zervas.
An Economic Analysis of User-Privacy Options in Ad-Supported Services

Paul Dütting, Monika Henzinger and Martin Starnberger.
Auctions with Heterogeneous Items and Budget Limits

Edward Lui and Samantha Leung.
Bayesian Mechanism Design with Efficiency, Privacy, and Truthfulness

Pranav Dandekar, Ashish Goel and David Lee.
Biased Assimilation, Homophily, and the Dynamics of Polarization

Davide Bilò, Luciano Gualà and Guido Proietti.
Bounded-Distance Network Creation Games

Nikolay Archak, Vahab Mirrokni and S Muthukrishnan.
Budget Optimization for Online Campaigns with Positive Carryover Effects

Sunil Easaw Simon and Krzysztof Apt.
Choosing Products in Social Networks

Morteza Zadimoghaddam and Aaron Roth.
Efficiently Learning from Revealed Preference

Amotz Bar-Noy, Yi Gai, Matthew P. Johnson, Bhaskar Krishnamachari and George Rabanca.
Funding Games: the Truth but not the Whole Truth

Pascal Lenzner.
Greedy Selfish Network Creation

Andreas Darmann, Edith Elkind, Sascha Kurz, Jérôme Lang, Joachim Schauer and Gerhard J. Woeginger.
Group Activity Selection Problem

Avishay Maya and Noam Nisan.
Incentive Compatible Two Player Cake Cutting

Georgios Piliouras, Tomas Valla and Laszlo Vegh.
LP-based Covering Games with Low Price of Anarchy

Anand Bhalgat, Tanmoy Chakraborty and Sanjeev Khanna.
Mechanism Design for a Risk Averse Seller

Swaprava Nath, Pankaj Dayama, Dinesh Garg, Narahari Yadati and James Zou.
Mechanism Design for Time Critical and Cost Critical Task Execution via Crowdsourcing

Bundit Laekhanukit, Guyslain Naves and Adrian Vetta.
Non-Redistributive Second Welfare Theorems

Nicole Immorlica and Emmanouil Pountourakis.
On Budget-Balanced Group-Strategyproof Cost-Sharing Mechanisms

Dvir Falik, Reshef Meir and Moshe Tenneholtz.
On Coalitions and Stable Winners in Plurality

Dimitris Fotakis and Paris Siminelakis.
On the Efficiency of Influence-and-Exploit Strategies for Revenue Maximization under Positive Externalities

Volodymyr Kuleshov and Gordon Wilfong.
On the efficiency of the simplest pricing mechanisms in two-sided markets

Constantinos Daskalakis, Alan Deckelbaum and Christos Tzamos.
Optimal Pricing is Hard

Pranav Dandekar, Nadia Fawaz and Stratis Ioannidis.
Privacy Auctions for Recommender Systems

Victor Naroditskiy, Mingyu Guo, Lachlan Dufton, Maria Polukarov and Nicholas R. Jennings.
Redistribution of VCG Payments in Public Project Problems

Kshipra Bhawalkar and Tim Roughgarden.
Simultaneous Single-Item Auctions

Johanne Cohen, Christoph Dürr and Kim Thang Nguyen.
Smooth Inequalities and Equilibrium Inefficiency in Scheduling Games

Martin Hoefer and Alexander Skopalik.
Social Context in Potential Games

Katrina Ligett and Aaron Roth.
Take it or Leave it: Running a Survey when Privacy Comes at a Cost

Avinatan Hassidim, Haim Kaplan, Yishay Mansour and Noam Nisan.
The AND-OR game: Equilibrium Characterization

Davide Bilò, Luciano Gualà, Stefano Leucci and Guido Proietti.
The Max-Distance Network Creation Game on General Host Graphs

Christian Borgs, Michael Brautbar, Jennifer Chayes, Sanjeev Khanna and Brendan Lucier.
The Power of Local Information in Social Networks

Xujin Chen, Benjamin Doerr, Xiaodong Hu, Weidong Ma, Rob van Stee and Carola Winzen.
The Price of Anarchy for Selfish Ring Routing is Two

Ashish Goel and David Lee.
Triadic Consensus: A Randomized Algorithm for Voting in a Crowd

Hadi Minooei and Chaitanya Swamy.
Truthful Mechanism Design for Multi-dimensional Covering Problems

Hamed Amini and Nikolaos Fountoulakis.
What I tell you three times is true: bootstrap percolation in small worlds


Short papers

Anand Bhalgat and Sreenivas Gollapudi.
Ad Allocation for Browse Sessions

Lirong Xia.
Generalized Weighted Model Counting: An Efficient Monte-Carlo Meta-Algorithm

Sayan Bhattacharya, Dmytro Korzhyk and Vincent Conitzer.
Computing a Profit-Maximizing Sequence of Offers to Agents in a Social Network

Lei Yao, Wei Chen and Tie-Yan Liu.
Convergence Analysis for Weighted Joint Strategy Fictitious Play in Generalized Second Price Auction

Michal Feldman and Tami Tamir.
Convergence of Best-Response Dynamics in Games with Conflicting Congestion Effects

Swapnil Dhamal and Narahari Yadati.
Forming Networks of Strategic Agents with Desired Topologies

Bassel Tarbush and Alexander Teytelboym.
Homophily in online social networks

Piotr Krysta and Orestis Telelis.
Limited Supply Online Auctions for Revenue Maximization

Balasubramanian Sivan, Vasilis Syrgkanis and Omer Tamuz.
Lower Bounds on Revenue of Approximately Optimal Auctions

Vahab Mirrokni, Mukund Sundurarajan and Sebastien Roch.
On Fixed-Price Marketing for Goods with Positive Network Externalities

Daniela Saban and Nicolas Stier-Moses.
The Competitive Facility Location Problem in a Duopoly: Connections to the 1-median Problem

Angelo Fanelli, Dariusz Leniowski, Gianpiero Monaco and Piotr Sankowski.
The ring design game with fair cost allocation

Amos Fiat and Ariel Levavi.
Tight Lower Bounds on Envy-Free Makespan Approximation

Thursday, August 16, 2012

RA position in game theory/computer security

A colleague (Carlos Cid, at Royal Holloway) asked me to help publicise the following job opportunity. The topic (game theory applied to cyber-security) is one that I don't know much about, but could be an interesting new direction in the Algorithmic Game Theory area.

The following is a quote from the advertisement.

The use of game theoretical techniques has recently become a popular and powerful method for the design and study of security of communications systems and protocols. The traditional approach of assuming honest parties following the protocol rules, whose security may be compromised by malicious players, can in this case be replaced by the scenario in which all parties are self-interested. The modelling of security systems and protocols as games, and the use of suitable game theoretical tools in their study and design, can offer several advantages, and present a further promising field of research in Information Security.

Monday, July 09, 2012

WINE 2012 Call for papers

A reminder about the 8th Workshop on Internet & Network Economics (WINE); which will take place in Liverpool during December 9-12. By now I hope that most people who may be interested will have seen a link to the call for papers in one of the messages I sent to various mailing lists. The submission deadline is the 1st of August, and the submission server will be added in a few days to the submission page.

This year the page limit is raised to 14 pages (for WINE 2011 it was 12 pages). I reckon that in these days of paperless papers one can be more generous with page limits. Against that, a higher page limit is more work for the PC. But so many CS conference submissions seem to use appendices, and when I review them I feel sort of obliged to check the appendix in any case, so I think there’s a case for a higher page limit. We still welcome papers whose page count is less than the limit, of course.

Invited speakers:
  • Kamal Jain, eBay Research Labs
  • Benny Moldovanu, University of Bonn
  • David C. Parkes, Harvard University

Program committee:
  • Paul Goldberg, Liverpool (chair)
  • Yoram Bachrach, Microsoft Research Cambridge
  • Nina Balcan, Georgia Tech
  • Ning Chen, NTU Singapore
  • Xi Chen, Columbia
  • Mohammad Taghi Hajiaghayi, University of Maryland
  • Yiling Chen, Harvard SEAS
  • Florin Constantin, A9.com
  • Shahar Dobzinski, Cornell
  • Amos Fiat, Tel-Aviv
  • Felix Fischer, University of Cambridge
  • Monika Henzinger, University of Vienna
  • Martin Hoefer, RWTH-Aachen
  • David Manlove, Glasgow
  • Evangelos Markakis, AUEB Athens
  • Peter Bro Miltersen, Aarhus
  • Vahab Mirrokni, Google
  • Georgios Piliouras, Georgia Institute of Technology
  • Maria Polukarov, Southampton
  • Heiko Roeglin, University of Bonn
  • Guido Schaefer, CWI Amsterdam / VU University Amsterdam
  • Grant Schoenebeck, Princeton
  • Yevgeniy Vorobeychik, Sandia Labs
  • Liad Wagman, Illinois Institute of Technology
  • Jean Walrand, UC Berkeley
  • Onno Zoeter, Xerox Research Centre Europe

Wednesday, May 09, 2012

SAGT and WINE 2012

The 8th Workshop on Internet and Network Economics (WINE 2012) will come to Liverpool in December. Please take a look at the web site for details! The 5th International Symposium on Algorithmic Game Theory (SAGT 2012) is in Barcelona in October; for SAGT the submission deadline is getting close, namely May 25th.

Tuesday, March 27, 2012

game theory programmers wanted

I received the following email, which may be of interest to some readers:

The GAMBIT project — Software Tools for Game Theory — has been accepted for the second time as a mentoring organization for the “Google Summer of Code 2012”. This means that Google pays students a stipend (5000 USD if the work is successful) to work on open-source code for this software project over the summer of 2012.

With this email, we would like to ask you to encourage students to contact us if they are interested in contributing to this project. It would involve the coding of algorithms and user interfaces for game-solving software.

The “mentors” for this project are Ted Turocy, Rahul Savani and Bernhard von Stengel, all with a long-standing interest in games and computation. Any enquiry should be directed to the three of us under the mail alias

gambit-mentors “at” nash.lse.ac.uk

The student application period is March 26 - April 6, with final deadline April 6, 2012, 19h UTC.

The webpage

http://www.google-melange.com/gsoc/org/show/google/gsoc2012/gambit

gives a summary of our project, and lists at the bottom under “Application Template” a number of questions an interested student should answer. He or she should definitely contact us before submitting an application to clarify his or her interest. The possible projects are listed under “Ideas” which is linked to

http://www.gambit-project.org/doc/ideas.html

and this list can be extended, for example if someone is interested in computing equilibrium refinements. We have kept this ideas list fairly non-academic but there is no real limit for more advanced projects related to equilibrium computation or game processing.

The timeline to the Google Summer of Code program is at

http://www.google-melange.com/document/show/gsoc_program/google/gsoc2012/faqs#timeline

and other frequently asked questions are at

http://www.google-melange.com/document/show/gsoc_program/google/gsoc2012/faqs

We expect something like 3-5 student stipends, and of course are interested in serious contributors with knowledge of game theory and coding experience.

Thank you for identifying possible contributors, and please do not hesitate to ask us any questions. We look forward to hearing from you and from your interested students!

With best wishes,

— Bernhard, Ted and Rahul

Sunday, March 04, 2012

fixing maths and CS education

Here are some links to news articles I’ve been reading recently. On the BBC News web site: Poor numeracy 'blights the economy and ruins lives'... maybe it does, but let’s be careful what we wish for; numeracy is to maths the way ICT (as used in the sense below) is to CS, and the wrong attempt to improve “numeracy” could backfire and create a new generation of schoolkids who hate maths even more than the present lot. The article has a link to a maths test, one that is frankly about as mind-numbing as any other maths test I’ve come across.

It’s in contrast to the situation regarding computer programming, where things looks much happier what with the arrival of Raspberry Pi and recent success on reforming computing at schools. In yesterday’s Guardian: The Raspberry Pi can help schools get with the program provides an update on the newly-released Raspberry Pi:
The Raspberry Pi project – a philanthropic effort to create the contemporary equivalent of the BBC Micro of yesteryear – has graduated from idealistic vapourware dreamed up in Cambridge to a finished, deliverable product manufactured in China.


Here’s a quote from the article
Second, we need to persuade Michael Gove and his colleagues that the subject that should be taught to all children is not ICT but something called computer science. The idea that there's a major body of knowledge in this field – complete with a stable and intellectually rigorous conceptual framework that is independent of today's or yesterday's gadgetry – is probably unfamiliar to residents of Whitehall, who think ICT is trivial because it's always becoming obsolete.
There’s another reason to be careful what you wish for: maybe it’s something you already have. Some links: The Guardian’s digital literacy campaign is a good resource for what’s going on with reform of ICT teaching. See Dept. of Education announcement: ‘Harmful’ ICT curriculum set to be dropped this September to make way for rigorous Computer Science; and a consultation; reported here and here; Royal Society report.

The Raspberry Pi is supposed to help to rekindle the excitement for programming that occurred during the ’80s, which I remember well. Mind you, at the same time, it was even then considered questionable to want to become a ‘programmer’; you were supposed to want to be a systems analyst, or some such job title. And of course, this remain an obstacle to programming in that it’s sometimes perceived to be low-level grunt work. Here’s a blog post that argues against that:
Still, competition for the few programmers out there looking for work is very steep. So few Americans know how to program that firms like Google and Facebook are actually buying whole companies just for their code-literate employees, in what are known as "talent acquisitions."

According to Calacanis, each employee who understands how to code is valued at about $500,000 to $1 million toward the total acquisition price. One million dollars just to get someone who learns code.

Firms' other strategy, of course, is to import Chinese and Indian programmers, through a costly and often only temporary visa. (That's because, unlike those countries, we don't teach programming to students in the United States. At best we teach kids how to use programs that are already on the shelves. But that's another article.)

I don’t know whether to be happy or unhappy to hear that the US has the same problem with programming that we have here. It seems like programmers are valuable due to their scarcity; maybe it’s against their interest to highlight the problem.

(added later:) some more links: Computing at School discussion forum; Information pack on teaching Computer Science at schools, distributed to head teachers, prepared by BCS and CAS

Tuesday, February 21, 2012

Reference letters

I’ve been writing quite a lot of references for students, mostly for places on MSc degree programmes. The system for supplying these letters has improved markedly in recent years, with most universities allowing PDFs to be uploaded to their web sites. There is variation in user-friendliness however...

Cambridge gets the prize for biggest selection of titles: here is a screen shot:


Exeter is best for country-of-origin selection: most drop-down menus that I use to select a nationality require me the find ‘United Kingdom’ somewhere between Uganda and Uruguay. Exeter’s menu had England right at the top of the list. (Ideally, they would also allow you to select ‘United Kingdom’ so you get to make some kind of political statement via your selection.)

The only annoying ones are those that require you to fill in a Word form on behalf of the student. Luckily there aren’t too many of those (I will not name names).

Tuesday, January 17, 2012

publishers versus openness

Academic publishers have become the enemies of science — the article explains how the US Research Works Act would “allow publishers to line their pockets by locking publicly funded research behind paywalls”.

A related issue is the Stop Online Piracy Act (Sopa) which has led to Wikipedia’s forthcoming protest (see the warning message on Wikipedia itself) in the form of a blackout that will take place on Wednesday. this article seems to provide hope that sanity will prevail; it’s reassuring to hear Rupert Murdoch accusing the Obama administration of bowing to “Silicon Valley paymasters”.

(added slightly later:) This new post at Tim Gowers' blog also comes out in favour of the one-day blackout.

(added 6.2.12: article in The Economist about the Elsevier boycott.)

Monday, January 09, 2012

heterogeneous prices for parking spaces

The following question occurred to me during a recent search for a car parking place. Maybe it’s been done to death somewhere in the economics literature; let me know if you’ve seen it.

So I’m having trouble finding a parking space, and being a good liberal my reaction is to throw money at the problem. Since the car park’s full, the people who run it should jack up the price, right? With any luck, it would rise to a point where some of these cheapskates would get priced out, and I would still be in the game. Actually, there’s a smarter trick possible: you should have some cheap parking spaces and some expensive ones. The first people to arrive at the car park are able to take the cheap spaces, and later arrivals who are desperate for a space have to buy the expensive ones.

To see that this can increase the revenue, suppose that you own 100 spaces and there are 200 potential users, 190 of whom would pay £1 for a space, but the other 10 would be prepared to pay £5. Clearly we should charge either £1 or £5 for spaces, and if we charge £1 for all of them we raise £100, while if we charge £5 for all of them we raise £50 (selling 10 spaces and leaving the other 90 idle). Suppose instead that 99 spaces cost £1 and the other one costs £5. Suppose further that car park users arrive in a random order. In that case you are very likely to sell all spaces and raise £104; there is probability of only 2-10 that the 10 high-value users will be amongst the first 100 users to arrive, which would lead to the £5 space ending up idle and a revenue of only £99.

This suggests the following computational problem. You have n parking spaces and there are N>n users, where each user has a known value that he assigns to receiving a parking space. Assuming they arrive in a random order, how should you price the parking spaces so as to maximize the expected revenue? (Whenever a user arrives, they buy the cheapest available space, unless their value is less that the cheapest space, in which case they leave.) Indeed, for a given set of n prices for the spaces, I don’t see how to efficiently compute that expected value, although it would be easy enough to approximate by simulation (repeatedly generate random orderings of the users and see what happens).

It seems like the effectiveness of heterogeneous prices is greater when N is quite a lot larger than n. In the case that n>N, I don’t know of any examples where revenue-maximization requires prices to be non-uniform.