\documentclass[14pt]{article}

\usepackage{epsf}
\usepackage{epsfig}
\usepackage{color}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}  
\usepackage{amssymb}    
\usepackage{amsthm}
\usepackage{wrapfig}
\usepackage{subfigure}
\usepackage{hyperref}

%\usepackage{fancyheadings}
%\pagestyle{fancy}

\setlength{\parindent}{0pt}
\setlength{\parskip}{2ex}
\widowpenalty 10000

\usepackage{color}
\definecolor{MyDarkBlue}{rgb}{0.1,0,0.9}
\newcommand{\aside}[1]{\textcolor{MyDarkBlue}{#1}}

\usepackage{enumerate}


%\linenumbers

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\mybox}[1] {
\begin{center} {\small
\framebox[3in]{
\begin{minipage}[t]{4.5in} {\sf #1}
\end{minipage} } }
\end{center}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength\oddsidemargin{.25in}
\setlength{\textwidth}{6in}
\setlength{\textheight}{8.75in}
%\setlength{\textwidth}{4in}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\latex{latex }
\newcommand{\header}[1]{\section*{#1}}
\newcommand{\myquote}[1]{''{#1}''}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\thispagestyle{empty}

{\huge Detection Of Non-Human Agents}

{\it Richard J. Lipton and Kenneth W. Regan}

\vspace{.2in}
In modern complex distributed computing systems one of the recurring issues is: Are we interacting with a human? a computer? or a combination of a human aided by a computer? Determining which is the case is often of paramount importance in securing a system or understanding what is happening. 
%
% We are interested in vastly improving our understanding of this problem from the current state of the art.
%
All sources of improvements in the state of this art carry vital potential.

In {\bf active} interaction, one party, Alice, is able to challenge the other party, Bob, with questions.  This is essentially a type of Turing test, and is relatively well understood.  Accurate and powerful protocols have been developed, for instance CAPTCHA technology based on visual images.
%
% as in Captcha technology. It is reasoning accurate and powerful. 

We will study the {\bf inactive} case, where Alice is restricted to watch Bob's behavior and {\em detect passively} the event that Bob is (not) human.   This problem is fundamental and uniquely challenging.  A solution could advance security, social media data mining, and other basic technologies. 

The plan of research is novel in branching via a well-defined problem: Is a player of a chess game cheating---that is, using a computer to make his moves? Today even the world's best players are rated hundreds of points below chess engines that run on laptops. This state has led to many real-life cheating cases, where players in high-level tournaments have been accused and sometimes found to have cheated.  The second PI has developed a statistical model of human versus computer move choice in papers since 2011, and has been involved (as ``Alice'') in several such cases.  The model takes deep computer analysis of all move options and player skill parameters as inputs, and generates probabilities for each move and predictions for aggregate performance over sets of moves.

This adds a third detection category, since Bob is a {\em human using a computer tool}.  Special chess competitions called ``Freestyle'' allow human-computer collaboration.  This may seem hard to separate from ``human'' and ``computer,'' but a new joint paper by the second PI, to be presented at the M-PREF workshop associated to AAAI 2014, does exactly that in the case of chess.  This supplements move-choice statistics by measuring criteria by which humans tend to force games into earlier crises, while computers acting alone direct games into positions where they have more reasonable options and can play wait-and-see.  

Applications will also come from the correspondence, established by the second PI's joint paper at IEEE CIG 2013, between chess positions and multiple-choice test questions, and between the mathematics of rating chess players and theories of {\bf psychometrics} used for personnel assessment.  The important point is not cheating and chess {\em per se}, but rather the ability to leverage huge amounts of data---millions of moves from real competitions not simulations---in which mathematical tools such as the Elo rating system and logistic analysis are fully established.  This work has already led to discovering ``big-data'' style regularities of human behavior, including that human error scales up with the magnitude of either side's advantage in a position, and mass sensitivity to small differences in {\em post-hoc} move value.  

Thus we claim that using a real concrete problem---chess---to help develop a theory of passive detection of non-humans is important, with promising transfer potential to applications beyond chess.  The new proposed research will add Bob's decision {\bf depth} and {\bf time} as primary factors, ones apparently absent in Rasch or item-response psychometric theories, and thereby deepen all of the agent-discrimination, distributional performance-assessment, and test-difficulty rating components.  Anticipated project duration is 36 months at 10\% term, 50\% summer effort.








%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}


