Price-oriented, Rationing-free Protocol: Guideline for Designing Strategy/False-name Proof Auction Protocols

AAAI Conferences

A PORF protocol is automatically guaranteed to be strategy-proof, i.e., for each agent, declaring its true evaluation values is an optimal strategy regardless of the declarations of other agents. Furthermore, if a PORF protocol satisfies additional conditions, the protocol is also guaranteed to be false-name-proof, that is, it eliminates the benefits from using false-name bids, i.e., bids submitted under multiple fictitious name such as multiple email addresses. For Intemet auction protocols, being falsename-proof is important since identifying each participant on the Intemet is virtually impossible. The characteristics of a PORF protocol are as follows. For each agent, the price of each bundle of goods is presented. This price is determined based on the declared evaluation values of other agents, while it is independent of its own declaration. Then, each agent can choose the bundle that maximizes its utility independently of the allocations of other agents (i.e., mOoning-free). We show that an existing false-name-proof protocol can be represented as a PORF protocol. Furthermore, we develop a new false-name-proof PORF protocol.


Analyzing Complex Strategic Interactions in Multi-Agent Systems

AAAI Conferences

We develop a model for analyzing complex games with repeated interactions, for which a full game-theoretic analysis is intractable. Our approach treats exogenously specified, heuristic strategies, rather than the atomic actions, as primitive, and computes a heuristic-payoff table specifying the expected payoffs of the joint heuristic strategy space. We analyze two games based on (i) automated dynamic pricing and (ii) continuous double auction. For each game we compute Nash equilibria of previously published heuristic strategies. To determine the most plausible equilibria, we study the replicator dynamics of a large population playing the strategies. In order to account for errors in estimation of payoffs or improvements in strategies, we also analyze the dynamics and equilibria based on perturbed payoffs.



Representing von Neumann-Morgenstern Games in the Situation Calculus

AAAI Conferences

Definitions Sequential games are also known as extensive form games or game trees. The following definition is due to von Neumann, Morgenstem, and Kuhn; we adopt the formulation of (Osborne& Rubinstein 1994, Ch.ll.1). We begin with some notation for sequences. An infinite sequence is a function from the positive natural numbers to some set; we denote infinite sequences by the letter h and variants such as h I or hi. A finite sequence of length n is a function with domain 1,..., n, denoted by the letter s and variants. Almost all the sequences we consider in this paper are sequences of actions.


WhiteBear: An Empirical Study of Design Tradeoffs for Autonomous Trading Agents

AAAI Conferences

This paper presents WhiteBear, one of the top-scoring agents in the 2 "'i International Trading Agent Competition (TAC). TAC was designed as a realistic complex test-bed for designing agents trading in e-marketplaces. Our architecture is an adaptive, robust agent architecture combining principled methods and empirical knowledge. The agent faced several technical challenges. Deciding the optimal quantities to buy and sell, the desired prices and the time of bid placement was only part of its design. Other important issues that we resolved were balancing the aggressiveness of the agent's bids againsthe cost of obtaining increased flexibility and the integration of domain specific knowledge with general agent design techniques. Introduction The Trading Agent Competition (TAC) was designed and organized by a group of researchers at the University of Michigan, led by Michael Wellman (Wellman et al. 2001). Time was spent on the design and implementation of the market, but there was no common market scenario that researchers could focus on and use to compare strategies. TAC provides such a common framework. It is a challenging benchmark domain which incorporates several elements found in real marketplaces in the realistic setup of travel agents that organize trips for their clients.


En-Route Sector Metering using a Game-theoretic Approach

AAAI Conferences

Currently, Traffic Management Coordinators in the Air Route Traffic Control Centers establish flow constraints at various sector meter fixes, based on their best estimates of the predicted traffic demand into their sector. Sector flow rates are not coordinated between neighboring sectors or centers. Incorrect sector metering rates can lead often lead to a cascade effect resulting in delays in the schedules of aircraft several sectors away. In this paper we develop an approach for dynamic sector metering based on game theory. The approach is based on a Bayesian game with communication, wherein the sectors determine mutually beneficial metering rates (based on collaboration and exchange of metering rates and negotiated Scheduled Times of Arrival) chosen so as to optimize delay, controller workload and capacity. We formalize the model for a simplified scenario consisting of two sectors belonging to two different centers, attempting to set the flow rates at their boundaries. The simplified models for the two-player (sector) game capture the coupling of dynamics between the two sectors and possible interactions between incoming and outgoing traffic flows. The inbound aircraft from other sectors and outbound flow rate restriction to other sectors are generated from a stochastic time series model. To demonstrate feasibility we implement our approach on a simplified version of agent-based decision support to captures inter center/sector communication and decentralized decision-making Introduction As air traffic congestion and delay have increased in the post-deregulation era, the air transportation community has sought to identify more efficient methods of Traffic Flow Management (TFM) in order to best utilize existing capacity. Advanced TFM strategies have the potential to improve system throughput and reduce delay without requiting substantial rework of the National Airspace System (NAS) infrastructure (e.g., airspace redesign, Communication, Navigation and Surveillance (CNS) upgrades, etc.) and without imposing new aircraft equipage requirements. Currently, Traffic Management Coordinators (TMCs) the Air Route Traffic Conlrol Centers (ARTCC) establish flow constraints at various sector meter fixes, based on their best estimates of the predicted traffic demand, or sectors affected by adverse weather conditions. Arrival rates into a sector are usually determined for sectors close to airports with high demand, and these rates typically flow down (radially outward) to en route sectors. Typically controllers add a safety buffer to this rate to accommodate for any unforeseen circumstances. Sector flow rates are not coordinated between neighboring sectors or centers based on the estimated demand on their sectors. Furthermore, metering times at sectors are assigned based on miles-intrail restrictions (distance-based spacing).


Towards Computing Optimal Policies for Decentralized POMDPs

AAAI Conferences

The problem of deriving joint policies for a group of agents that maximze some joint reward function can be modelled as a decentralized partially observable Markov decision process (DEC-POMDP). Significant algorithms have been developed for single agent POMDPs however, with a few exceptions, effective algorithms for deriving policies for decentralized POMDPS have not been developed.



Miscomputing Ratio: The Social Cost of Selfish Computing Kate Larson and Tuomas Sandholm

AAAI Conferences

Auctions are useful mechanisms for allocating items (goods, tasks, resources, etc.) in multiagent systems. The bulk of auction theory assumes that the bidders' valuations for items are given a prior/. In many applications, however, the bidders need to expend significant effort to determine their valuations. This is the case, for example, when the bidders can gather information (Perisco 2000) when the bidders have the pertinent information in hand, but evaluating it is complex. There are a host of applications of the latter that are closely related to computer science and AI questions. For example, when a carrier company bids for a transportation task, evaluating the task requires solving the carrier's intractable vehicle routing problem (Sandholm 1993).