7067374
Profit Sharing Auction
Auctions are a class of multi-party negotiation protocols. Classical auctions try to maximize social welfare by selecting the highest bidder as the winner. If bidders are rational, this ensures that the sum of profits for all bidders and the seller is maximized. In all such auctions, however, only the winner and the seller make any profit. We believe that "social welfare distribution" is a desired goal of any multiparty protocol. In the context of auctions, this goal translates into a rather radical proposal of profit sharing between all bidders and the seller. We propose a Profit Sharing Auction (PSA) where a part of the selling price paid by the winner is paid back to the bidders. The obvious criticism of this mechanism is the incentive for the seller to share its profit with nonwinning bidders. We claim that this loss can be compensated by attracting more bidders to such an auction, resulting in an associated increase in selling price. We run several sets of experiments where equivalent items are concurrently sold at a First Price Sealed Bid, a Vickrey, and a PSA auction. A population of learning bidders repeatedly choose to go to one of these auctions based on their valuation for the good being auctioned and their learned estimates of profits from these auctions. Results show that sellers make more or equivalent profits by using PSA as compared to the classical auctions. Additionally, PSA always attracts more bidders, which might create auxiliary revenue streams, and a desirable lower variability in selling prices. Interestingly then, a rational seller has the incentive to share profits and offer an auction like PSA which maximizes and distributes social welfare.
15974834
Learning Pareto-optimal Solutions in 2x2 Conflict Games
Multiagent learning literature has investigated iterated two-player games to develop mechanisms that allow agents to learn to converge on Nash Equilibrium strategy profiles. Such equilibrium configurations imply that no player has the motivation to unilaterally change its strategy. Often, in general sum games, a higher payoff can be obtained by both players if one chooses not to respond myopically to the other player. By developing mutual trust, agents can avoid immediate best responses that will lead to a Nash Equilibrium with lesser payoff. In this paper we experiment with agents who select actions based on expected utility calculations that incorporate the observed frequencies of the actions of the opponent(s). We augment these stochastically greedy agents with an interesting action revelation strategy that involves strategic declaration of one's commitment to an action to avoid worst-case, pessimistic moves. We argue that in certain situations, such apparently risky action revelation can indeed produce better payoffs than a non-revealing approach. In particular, it is possible to obtain Pareto-optimal Nash Equilibrium outcomes. We improve on the outcome efficiency of a previous algorithm and present results over the set of structurally distinct two-person two-action conflict games where the players' preferences form a total order over the possible outcomes. We also present results on a large number of randomly generated payoff matrices of varying sizes and compare the payoffs of strategically revealing learners to payoffs at Nash equilibrium.
482217
Believing others: pro and cons
Under the assumption that agents remain in the system for significant time periods, or that the agent composition changes only slowly Sen (1996) has previously presented a prescriptive strategy for promoting and sustaining cooperation among self-interested agents. The adaptive, probabilistic policy prescribed promotes reciprocative cooperation that improves both individual and group performance in the long run. In the short run, however, selfish agents could still exploit reciprocative agents. In this paper we evaluate the hypothesis that the exploitative tendencies of selfish agents can be effectively curbed if reciprocative agents share their "opinions" of other agents. Since the true nature of agents are not known a priori and is learned from experience, believing others can also pose other hazards. We provide a learned trust-based evaluation function that is shown to resist both individual and concerted deception on the part of selfish agents.
3526092
Selecting partners
1. I N T R O D U C T I O N In an open environment the goal of a self-interested agent would be to interact with or enter into partnership with those agents that will produce maximal local utility for this agent [5]. We assume that an agent can get one of several payoffs (utilities) for joining a particular coalition which is determined by a static probability distribution over the payoffs for each coalition. We consider choosing a single coalition to interact with repeatedly when the total number of interactions is known ahead of time.
43158386
Evolution and learning in multiagent systems
1062630
The Role of Commitment in Cooperative Negotiation
Cooperative information agents need mechanisms that enable them to work together effectively while solving common problems. We investigate the use of commitment by agents to proposed actions as a mechanism that allow agents to work concurrently on interdependent problems. Judicious use of commitment can not only increase the throughput of cooperative information systems, but also allow them to deal flexibly with dynamically changing environments. We use the domain of distributed scheduling to demonstrate that static commitment strategies are ineffective. Results from simulated experiments are used to identify the environmental features on which an adaptive commitment strategy should be predicated.
11397521
Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions
We present alternate reductions of the nearest neighbor searching problem to Point Location in Balls that reduces the space bound of Sariel Har-Peled's [S. Har-Peled, A replacement for Voronoi diagrams of near linear size, in: Proc. of IEEE FOCS, 2001, pp. 94-103, full version available from http://www.uiuc.edu/~sariel/papers] recent result on Approximate Voronoi Diagrams to linear while maintaining the logarithmic search time. We do this by simplifying the construction of [S. Har-Peled, A replacement for Voronoi diagrams of near linear size, in: Proc. of IEEE FOCS, 2001, pp. 94-103, full version available from http://www.uiuc. edu/~sariel/papers] that reduces the number of balls generated by algorithm by a logarithmic factor to O(n log n). We further reduce the number of balls by a new hierarchical decomposition scheme and a generalization of PLEBs to achieve linear space decomposition for nearest neighbor searching. The construction of our data structures takes O(n log n) time.
42428189
Lower Bounds for Parallel Algebraic Decision Trees, Complexity of Convex Hulls and Related Problems
We show that any parallel algorithm in the fixed degree algebraic decision tree model that answers membership queries in W ⊑ R n using p processors, requires Ω(¦W¦/n log(p/n)) rounds where ¦W¦ is the number of connected components of W. We further prove a similar result for the average case complexity. We give applications of this result to various fundamental problems in computational geometry like convex-hull construction and trapezoidal decomposition and also present algorithms with matching upper bounds.
13878075
Optimal sequencing of individually rational contracts
Multiagent researchers have worked on the problem of determining optimal contracts between self-interested agents. In particular, Sandholm et al. [1,8] have both theoretically and experimentally studied the necessity and usefulness of different contract types under the assumption of individually myopically rational contracting. We study a variant of sequential contracting where the goal is to maximize social welfare through a fixed-length sequence of individually rational contracts. The space of possible contract sequences is exponential. We compare a greedy deterministic heuristic with a stochastic genetic algorithm based approach for this optimal sequential contract selection problem. We focus on sub-additive domains where individually rational contracts are feasible with side payments. We show that the GA-based approach consistently outperforms the deterministic heuristic by generating larger social welfare.
5876633
Analysis of Communities of Interest in Data Networks
Communities of interest (COI) have been applied in a variety of environments ranging from characterizing the online buying behavior of individuals to detecting fraud in telephone networks. The common thread among these applications is that the historical COI of an individual can be used to predict future behavior as well as the behavior of other members of the COI. It would clearly be beneficial if COIs can be used in the same manner to characterize and predict the behavior of hosts within a data network. In this paper, we introduce a methodology for evaluating various aspects of COIs of hosts within an IP network. In the context of this study, we broadly define a COI as a collection of interacting hosts. We apply our methodology using data collected from a large enterprise network over a eleven week period. First, we study the distributions and stability of the size of COIs. Second, we evaluate multiple heuristics to determine a stable core set of COIs and determine the stability of these sets over time. Third, we evaluate how much of the communication is not captured by these core COI sets.
6303606
Class-of-service mapping for QoS: a statistical signature-based approach to IP traffic classification
The ability to provide different Quality of Service (QoS) guarantees to traffic from different applications is a highly desired feature for many IP network operators, particularly for enterprise networks. Although various mechanisms exist for providing QoS in the network, QoS is yet to be widely deployed. We believe that a key factor holding back widespread QoS adoption is the absence of suitable methodologies/processes for appropriately mapping the traffic from different applications to different QoS classes. This is a challenging task, because many enterprise network operators who are interested in QoS do not know all the applications running on their network, and furthermore, over recent years port-based application classification has become problematic. We argue that measurement based automated Class of Service (CoS) mapping is an important practical problem that needs to be studied.
 In this paper we describe the requirements and associated challenges, and outline a solution framework for measurement based classification of traffic for QoS based on statistical application signatures. In our approach the signatures are chosen in such as way as to make them insensitive to the particular application layer protocol, but rather to determine the way in which an application is used -- for instance is it used interactively, or for bulk-data transport. The resulting application signature can then be used to derive the network layer signatures required to determine the CoS class for individual IP datagrams. Our evaluations using traffic traces from a variety of network locations, demonstrate the feasibility and potential of the approach.