Sunday, January 25, 2009

Computational social choice, social choice theory, and social choice mechanisms

Social choice mechanisms will no doubt be crucial to the operation of large and complex agent systems. Software agents will need to make choices and will need to affect outcomes in multi-agent interactions. Voting is one example. The emerging sub-field of computational social choice is an attempt to adapt the tools and techniques of social choice theory to the realm of computational entities.

I myself have not explored this area beyond the very superficial, but it does show promise.

Some of the specific topic areas are:

  • Algorithmic aspects of voting rules
  • Computational barriers to strategic behaviour
  • Collective decision-making in multi-agent systems
  • Preference elicitation and communication issues in voting
  • Fair division
  • Computational aspects of weighted voting games
  • Collective decision-making in combinatorial domains
  • Logic-based formalisms for social choice problems
  • Belief and judgement aggregation
  • Social software

The overall topic will be covered in a future special issue of Springer's Journal of Autonomous Agents and Multi-Agent Systems ("Special Issue on Computational Social Choice".)

Keywords: computational social choice, social choice theory, social choice mechanisms, social choice problems, collective decision-making.

-- Jack Krupansky

Saturday, January 17, 2009

Exploring New Interaction Designs Made Possible by the Semantic Web

The Journal of Web Semantics has issued a call for papers for a special issue on the topic of "Exploring New Interaction Designs Made Possible by the Semantic Web." They tell us that they:

... seek papers that look at the challenges and innovate possible solutions for everyday computer users to be able to produce, publish, integrate, represent and share, on demand, information from and to heterogeneous data sources. Challenges touch on interface designs to support end-user programming for discovery and manipulation of such sources, visualization and navigation approaches for capturing, gathering and displaying and annotating data from multiple sources, and user-oriented tools to support both data publication and data exchange. The common thread among accepted papers will be their focus on such user interaction designs/solutions oriented linked web of data challenges. Papers are expected to be motivated by a user focus and methods evaluated in terms of usability to support approaches pursued.

Offering some background, they inform us that:

The current personal computing paradigm of single applications with their associated data silos may finally be on its last legs as increasing numbers move their computing off the desktop and onto the Web. In this transition, we have a significant opportunity – and requirement – to reconsider how we design interactions that take advantage of this highly linked data system. Context of when, where, what, and whom, for instance, is increasingly available from mobile networked devices and is regularly if not automatically published to social information collectors like Facebook, LinkedIn, and Twitter. Intriguingly, little of the current rich sources of information are being harvested and integrated. The opportunities such information affords, however, as sources for compelling new applications would seem to be a goldmine of possibility. Imagine applications that, by looking at one's calendar on the net, and with awareness of whom one is with and where they are, can either confirm that a scheduled meeting is taking place, or log the current meeting as a new entry for reference later. Likewise, documents shared by these participants could automatically be retrieved and available in the background for rapid access. Furthermore, on the social side, mapping current location and shared interests between participants may also recommend a new nearby location for coffee or an art exhibition that may otherwise have been missed. Larger social applications may enable not only the movement of seasonal ills like colds or flus to be tracked, but more serious outbreaks to be isolated. The above examples may be considered opportunities for more proactive personal information management applications that, by awareness of context information, can better automatically support a person's goals. In an increasingly data rich environment, the tasks may themselves change. We have seen how mashups have made everything from house hunting to understanding correlations between location and government funding more rapidly accessible. If, rather than being dependent upon interested programmers to create these interactive representations, we simply had access to the semantic data from a variety of publishers, and the widgets to represent the data, then we could create our own on-demand mashups to explore heterogeneous data in any way we chose. For each of these types of applications, interaction with information -- be it personal, social or public -- provides richer, faster, and potentially lighter-touch ways to build knowledge than our current interaction metaphors allow.

Finally, they pose their crucial question:

What is the bottleneck to achieving these enriched forms of interaction?

For which they propose the answer:

Fundamentally, we see the main bottleneck as a lack of tools for easy data capture, publication, representation and manipulation.

They provide a list of challenges to be addressed in the issue, including but not restricted to:

  • approaches to support integrating data that is readily published, such as RSS feeds that are only lightly structured.
  • approaches to apply behaviors to these data sources.
  • approaches to make it as easy for someone to create and to publish structured data as it is to publish a blog.
  • approaches to support easy selection of items within resources for export into structured semantic forms like RDF.
  • facilities to support the pulling in of multiple sources; for instance, a person may wish to pull together data from three organizations. Where will they gather this data? What tools will be available to explore the various sources, align them where necessary and enable multiple visualizations to be explored?
  • methods to support fluidity and acceleration for each of the above: lowering the interaction cost for gathering data sources, exploring them and presenting them; designing lightweight and rapid techniques.
  • novel input mechanisms: most structured data capture requires the use of forms. The cost of form input can inhibit that data from being captured or shared. How can we reduce the barrier to data capture?
  • evaluation methods: how do we evaluate the degree to which these new approaches are effective, useful or empowering for knowledge builders?
  • user analysis and design methods: how do we understand context and goals at every stage of the design process? What is different about designing for a highly personal, contextual, and linked environment?

In addition to traditional, full-length papers, they are also soliciting shorter papers as well as one to two page short, forward-looking more speculative papers addressing the challenges outlined above. I am tempted to submit one of the latter, possibly based on my proposal for The Consumer-Centric Knowledge Web - A Vision of Consumer Applications of Software Agent Technology - Enabling Consumer-Centric Knowledge-Based Computing. Or, maybe a stripped-down version of that vision that is more in line with the "reach" of the current, RDF-based vision of the Semantic Web.

-- Jack Krupansky