Technical Summary: Shaping Human-AI Interactions to Provide Improvement Pathways and Balance Competing Objectives

Author: Keziah Naggita
Institution: Toyota Technological Institute at Chicago
Degree: Doctor of Philosophy in Computer Science (June 2026)

1. Problem Statement

The proliferation of AI systems in high-stakes decision-making (e.g., hiring, admissions) and home environments creates a feedback loop where individuals (agents) form beliefs about the system and act strategically to influence outcomes. These actions can be genuine improvements (enhancing underlying qualifications) or gaming (manipulating observable features without genuine improvement).

This thesis addresses three core challenges in shaping these interactions:

1. Developmental & Behavioral Dynamics: How do humans (specifically parents) perceive and respond to aggressive behavior by children toward AI-driven devices (robots, smart speakers, tablets), and how does the device's anthropomorphism influence these responses?
2. Incentivizing Improvement: How can decision-makers design targets and provide guidance to maximize genuine agent improvement while ensuring fairness and reachability?
3. Balancing Competing Objectives: How can AI systems be designed to maximize true positives (identifying qualified agents) and minimize false positives (rejecting unqualified agents) when agents can both improve and game the system?

2. Methodology

The thesis employs a multi-faceted methodological approach, integrating:

• Human-Subject Experiments: An online between-subjects study ($N=332$) investigating parental reactions to child aggression toward robots, smart speakers, and tablets.
• Algorithmic Design & Optimization: Development of polynomial-time and pseudo-polynomial algorithms for target placement, counterfactual explanation (CFE) generation, and role model selection.
• Theoretical Analysis: Application of learning theory (PAC learning), graph theory, and complexity theory (NP-hardness proofs) to analyze learnability, sample complexity, and classification bounds in strategic settings.
• Empirical Evaluation: Experiments on real-world datasets (Adult, OULAD, Law School) and semi-synthetic data to evaluate algorithmic performance under various risk-aversion strategies and geometric constraints.

3. Key Contributions and Results

Part I: Human-AI Interactions via Human-Subject Experiments

Focus: Parental responses to child aggression toward AI devices.

• Method: A 2 (aggression: aggressive vs. neutral) $\times$ 3 (device: robot, smart speaker, tablet) $\times$ 3 (modality: audio, physical, audio+physical) design.
• Key Findings:
  • Aggression Impact: Parents expressed significantly higher concern and were more likely to intervene (reprimand or remove the device) when their child exhibited aggressive behavior compared to neutral behavior.
  • Device Perception: While parents perceived robots and smart speakers as more anthropomorphic, animate, and warm than tablets, no significant difference was found in parental concern or intervention likelihood between robots and smart speakers. This contradicts the hypothesis that physical embodiment (robots) uniquely heightens concern compared to disembodied voice assistants.
  • Intervention Styles: Parents responded to neutral behavior with encouragement and assistance, whereas aggressive behavior triggered reprimands and the use of the situation as a learning opportunity.

Part II: Shaping Interactions to Provide Improvement Pathways

Focus: Designing mechanisms to incentivize genuine improvement.

3.1 Setting Reachable Targets (Chapter 3)

• Problem: Determining the optimal placement of $k$ target skill levels to maximize total agent improvement, considering that agents improve to the nearest reachable target.
• Challenges: Target placement is non-monotonic; adding a target can reduce total improvement by causing agents to switch from distant, high-value goals to closer, lower-value ones.
• Contributions:
  • Developed a polynomial-time dynamic programming algorithm to maximize total improvement.
  • Constructed the Pareto frontier for group social welfare to address fairness (max-min objectives).
  • Proved a structural result: A solution exists that is simultaneously $\Omega(1/g^3)$-approximately optimal for each of $g$ groups (under common improvement capacity).
  • Demonstrated that max-min fair solutions do not guarantee constant approximation for all groups simultaneously.

3.2 Generating Actionable Insights (Chapter 4)

• Problem: Generating Counterfactual Explanations (CFEs) that are actionable and resemble real-world actions in large state spaces.
• Contributions:
  • Proposed single-agent and data-driven CFE generators that bridge feature-based and action-based spaces.
  • Introduced "high-level" CFEs that modify fewer features but result in higher agent improvement compared to traditional low-level feature modifications.
  • Demonstrated that data-driven generators can efficiently produce valid CFEs by leveraging similarities between agent states, improving scalability and resource efficiency.

3.3 Selectively Revealing Role Models (Chapter 5)

• Problem: A social planner must reveal labels (positive/negative) of role models to maximize the number of agents emulating positive targets, subject to a limited budget.
• Contributions:
  • Showed that the social welfare function is submodular only when the planner is restricted to revealing positive targets (yielding a $(1-1/e)$-approximation via greedy algorithms).
  • Proved that allowing the revelation of negative targets breaks submodularity, potentially leading to arbitrarily poor performance.
  • Introduced a proxy welfare function that remains submodular even with negative targets, restoring approximation guarantees.
  • Established that the problem remains NP-Hard regardless of disclosure restrictions.

Part III: Jointly Optimizing Competing Objectives

Focus: Classification of agents who can both improve and game.

4.1 PAC Learning with Improvements (Chapter 6)

• Problem: How does the capacity for improvement affect learnability and sample complexity?
• Contributions:
  • Analyzed PAC learning in settings where agents can move within a neighborhood (graph model) to improve.
  • Zero-Error Learning: Proved that under uniform distributions, it is possible to achieve zero generalization error with a sample complexity of $O(\frac{n \log n}{d_{min}^+ + 1})$, where $d_{min}^+$ is the minimum degree of positive nodes. This contrasts with standard PAC models which often have constant error bounds.
  • Showed that risk-averse learning strategies (penalizing false positives heavily) are particularly effective in improvement settings.

4.2 Theory of Classification of Improving-and-Gaming Agents (Chapter 7)

• Problem: Designing classifiers to maximize true positives while minimizing false positives when agents can game (red edges) or improve (blue edges).
• Models:
  • General Discrete Model: Agents and criteria form a weighted, colored bipartite graph.
  • Linear Model: Agents move in $\mathbb{R}^d$; some dimensions are improvements, others are gaming.
• Contributions:
  • Algorithm: Developed an efficient algorithm (Algorithm 7.1) to find a set of criteria that maximizes true positives subject to zero false positives in the general discrete model.
  • Hardness: Proved that maximizing true positives subject to a non-zero bound on false positives is NP-hard, even in the linear model.
  • Linear Classification: Showed that finding a linear classifier that classifies all agents accurately and qualifies all improvable agents is possible, but maximizing true positives with minimal false positives in 2D space requires specific algorithmic constructions.

4.3 Empirical Study (Chapter 8)

• Problem: Evaluating improvement-gaming-aware algorithms on real-world data.
• Results:
  • Risk Aversion: Risk-averse strategies (e.g., weighted loss functions penalizing false positives) consistently outperform standard models in reducing error as improvement budgets increase.
  • Trade-offs: While increasing risk aversion reduces classification error, excessive risk aversion can lower overall utility scores.
  • Zero Error vs. Utility: Achieving zero classification error does not guarantee perfect utility; the ratio of true positives to false positives is critical.
  • Geometric Constraints: The choice of norm ($\ell_\infty$ vs. $\ell_2$) significantly shapes the direction and extent of feasible agent movements.

4. Significance and Claims

The thesis claims to advance human-centered machine learning by providing principles and methods for designing AI systems that align with human needs, values, and capabilities.

• Theoretical Advancement: It extends learning theory to "learning with improvements," demonstrating that agent agency can reduce sample complexity and enable zero-error learning under specific conditions, challenging standard PAC learning assumptions.
• Algorithmic Robustness: It provides structural results on the non-monotonicity of target placement and the hardness of balancing improvement and gaming, offering algorithms that are robust to strategic behavior.
• Practical Design: Through empirical and experimental work, it offers actionable insights for policymakers and system designers:
  • Child-AI Safety: Designers must consider that parents may not distinguish between robots and smart speakers regarding aggression, suggesting that safety features should be consistent across device types.
  • Recourse: Moving beyond feature-level explanations to action-based, data-driven guidance improves the scalability and fairness of algorithmic recourse.
  • Strategic Classification: Systems should employ risk-averse strategies and carefully balance the cost of false positives against the benefits of incentivizing genuine improvement.

The work integrates rigorous theoretical analysis with data-driven modeling and human-subject experimentation to bridge the gap between abstract algorithmic fairness and the practical realities of human-AI interaction.