Aaron Archer's Research Page

My research interests focus on discrete optimization, algorithmic game theory, and on applying the optimization techniques of operations research and theoretical computer science to both traditional domains such as network design, and non-traditional domains such as ecology and computer graphics. Other specific areas in which I have worked include algorithmic mechanism design, approximation algorithms, online algorithms, graph partitioning, facility location, graph algorithms and network flows. Look below for some of my publications.

I am currently a member of the Algorithms and Optimization group at the AT&T Shannon Research Laboratory in Florham Park, New Jersey. Before coming here, I completed my Ph.D. in Operations Research from Cornell University in August, 2003 (degree conferred in January, 2004). My thesis advisor was Eva Tardos, from the Computer Science department. During my graduate studies, I spent the spring 2000 semester visiting the Theory Group in the Computer Science department at UC Berkeley, and spent the summers of 2001 and 2002 working in the Computer Science Principles and Methodologies group at the IBM Almaden Research Center. Prior to these adventures, I earned a B.S. in mathematics from Harvey Mudd College.

Algorithmic mechanism design

• Aaron Archer and Robert Kleinberg, "Truthful germs are contagious: A local to global characterization of truthfulness" [pdf]
  • Bibliographic info: To appear in Proceedings of the 9th ACM Conference on Electronic Commerce (2009).
  • Quick summary: In mechanism design for agents with multi-dimensional type spaces, one of the big stumbling blocks has been the lack of an easily applicable characterization of truthful mechanisms that depends only on the allocation rule (i.e., social choice rule). Another large impediment has been that there was not a good understanding of how to combine different truthful mechanisms into a composite mechanism that is still truthful. We address both of these problems. We give a complementary pair of main results, which apply to allocation rules f on type spaces T of arbitrary (even infinite) dimension: (1) If T is convex, then f is truthful iff it satisfies two properties, called local weak monotonicity and vortex-freeness. (2) If T is not convex, then f is truthful iff it can be extended to a truthful allocation on the convex hull of T. Thus, the second result says that convex type spaces, where the first result applies, are in some sense the canonical ones. Our characterization theorem has a key feature that should make it easier to apply than Rochet's cyclic monotonicity condition: it requires checking the behavior of f only on local neighborhoods, so there is no need to understand the global structure of f. In fact, one surprising corollary is that f is truthful iff its restriction to an arbitrarily small 2-D neighborhood of each type in T is truthful, even if the dimension of T is uncountable! Restricting attention to local neighborhoods is very helpful when f is specified as the output of some algorithm, since it is usually much easier to analyze how the output changes when we make only small perturbations to the input. (For instance, think about how the optimal solution of a linear program changes as we perturb the objective coefficients.) We apply our theorem to provide an easy one-page proof of the Saks-Yu characterization for finite outcome spaces, and generalize this argument to provide a "truthful stitching" theorem: if f is defined by "stitching together" truthful allocations defined on various parts of the type space, then f is truthful iff it satisfies weak monotonicity at each of the "stitching" boundaries. We expect that this "truthful stitching" theorem could find application any time f is specified by an algorithm that contains branching points, which implicitly divide up the inputs into regions in which all inputs follow the same branches in the algorithm. Finally, we exhibit several revealing families of allocation functions that satisfy the k-cycle condition but are not truthful, dashing hopes that the Saks-Yu characterization involving the 2-cycle condition could be extended to a result for infinite outcome spaces using the k-cycle condition for some finite k. We are particularly fond of one of these examples, since it uses Chebyshev polynomials in the proof.

• Aaron Archer, Mechanisms for Discrete Optimization with Rational Agents [ps]
  • Bibliographic info: Ph.D. thesis, Cornell University, January 2004.
  • Quick summary: My dissertation is primarily a synthesis of the next four papers listed below. The unifying theme is to highlight and rectify four shortcomings of the Vickrey-Clarke-Groves (VCG) mechanism, which is widely seen as the gold standard in the field of mechanism design. We approach algorithmic mechanism design as "discrete optimization with a blindfold." Whereas traditional optimization problems assume that you are given the data as a starting point, we assume that different economic agents each hold part of the input data and report it to the decision-maker, who then decides on some outcome. Since these agents are self-interested, we assume that they will lie if they think it is to their advantage to do so. The field of mechanism design seeks to create "truthful" protocols, which means it is always in the agents' best interest to report their data truthfully. These usually involve the use of side payments to help induce truthtelling.
    The VCG framework is a general method for creating truthful mechanisms. We address the following four drawbacks: (1) VCG selects the outcome that maximizes the total social welfare, whereas often the decision-maker wants to maximize some other function. (2) In the case where the decision-maker is purchasing something, VCG must sometimes pay an unacceptably high premium to induce truthtelling. (3) Sometimes the decision-maker would like to use the VCG mechanism, but cannot because computing it is NP-hard. (4) VCG resists manipulation by single agents, but, in general, multiple agents could collude to cheat the mechanism.

• Aaron Archer, Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami and Scott Shenker, "Approximation and collusion in multicast cost sharing" [ps]
  • Bibliographic info:
    • An abstract by the last four authors appears in Proceedings of the 3rd ACM Conference on Electronic Commerce (2001) 253-255.
    • Full version appears in Games and Economic Behavior 47 (2004) 36-71.
  • Quick summary: We investigate two strategyproof methods for sharing the cost of transmission among recipients in a multicast tree: the Shapley value mechanism and the marginal cost mechanism. We construct a method that approximates the Shapley value mechanism, greatly reducing its communication complexity while maintaining its key property of group strategyproofness. The marginal cost mechanism (an instance of the Vickrey-Clarke-Groves family) is known to resist manipulation by single agents, but not by groups. We characterize which coalitions of agents can successfully manipulate the mechanism, how, and under what circumstances.

• Aaron Archer, Christos Papadimitriou, Kunal Talwar and Eva Tardos, "An approximate truthful mechanism for combinatorial auctions with single parameter agents" [ps]
  • Bibliographic info:
    • Conference version appears in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (2003) 205-214.
    • Full version appears in Internet Math 1 (2004) 129-150.
  • Quick summary: For most combinatorial auctions, even the simplest ones, it is NP-hard to compute the allocation of goods that maximizes the overall social welfare. Sadly, replacing an exact optimization routine with an approximation usually destroys the desirable incentive compatibility properties of auction mechanisms such as the famed Vickrey-Clarke-Groves (VCG) mechanism. We show how to adapt the powerful technique of rounding a linear program to create mechanisms that approximate the VCG mechanism while simultaneously attaining truthfulness in expectation and truthfulness with high probability. We illustrate this technique in the context of combinatorial auctions for single-minded bidders.
  • Note: This paper was invited to appear in the inaugural issue of Internet Math., but an editorial mishap delayed it to the second issue.

• Aaron Archer and Eva Tardos, "Frugal path mechanisms" [ps]
  • Bibliographic info:
    • Conference version appears inProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (2002) 991-999.
    • Full version appears in ACM Transactions on Algorithms 3(1): 1-22 (2007)
  • Quick summary: The Vickrey-Clarke-Groves (VCG) mechanism has been applied to the problem of buying the cheapest path in a graph, where the nodes or edges are owned by different economic agents. This mechanism induces truthful cost revelation as a dominant strategy for each agent, and selects the cheapest path in the graph, with respect to the actual costs incurred by the agents. However, since it must pay bonuses to each agent in order to induce truthtelling, it can sometimes be forced to overpay the actual cost by a factor of (k eps) (where k is the number of agents along the chosen path), even when there is tight competition in the market, in the form of a disjoint path costing only (1+eps) times the cost of the cheapest path. We prove that this drawback is intrinsic to the problem, in that every "reasonable" dominant strategy mechanism can be forced to overpay by just as much. The main part of our proof involves a characterization in terms of so-called min function mechanisms, which is of independent interest.
  • Note: This paper was invited to appear in a special issue of J. Algorithms devoted to the top papers from SODA '02. The special issue took forever, and eventually was moved to TALG. In the bibliographic reference for the full version above, don't trust the page numbers too much. There is something funny about the page numbering, since the online version of every article in this issue seems to be numbered starting at page 1. One of these days I need to take a look at the print version and see if it displays the same peculiarity.

• Aaron Archer and Eva Tardos, "Truthful mechanisms for one-parameter agents" [ps]
  • Bibliographic info:
    • Conference version appears in Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (2001) 482-491.
    • Full version in preparation.
  • Quick summary: We consider a range of classic discrete optimization problems in which the various components of the system under study are represented by distinct economic agents. In these problems, we are interested in optimizing some objective function other than the overall social welfare, so the Vickrey-Clarke-Groves mechanism is of no use to us. In the case where each agent's data can be naturally represented by a single real parameter, one can construct a truthful mechanism as long as the "load" allocated to each agent is monotone in her parameter. We apply this result to construct truthful polynomial-time mechanisms for a range of problems, including linear programming, facility location, max flow, and several basic scheduling problems. Some of these problems are NP-hard, in which case we derive truthful approximation algorithms. For one problem, we derive a lower bound on the approximation factor achievable by a truthful mechanism (without regard to its computational complexity).

Facility location

• Aaron Archer and Shankar Krishnan, "Importance sampling via load-balanced facility location" [pdf]
  • Bibliographic info: Appears in Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (2008) 316-330.
  • Quick summary: One of the recent movements in computer graphics has been towards the use of image-based lighting. One first captures a spherical intensity map of incident illumination in a real-life environment. Then one creates a virtual environment that includes objects not in the real-life scene, illuminated using the actual incident lighting. This virtual illumination is done using the spherical intensity map and ray-tracing. Since ray-tracing is computationally expensive, we need to sample only the "important" pixels from the intensity map, and trace the corresponding rays. So far, so good, but the devil is in the details of how this sampling is done. We propose a new method for sampling, based on a new type of facility location problem that we propose. This facility location model is NP-hard to solve, so we provide a primal-dual algorithm that runs quickly and gives provable approximation guarantees. We also report some preliminary results of applying our algorithm to real images. The use of discrete optimization techniques and the existence of any kind of provable guarantees on solution quality are both rare in computer graphics.
  • Note: Patents pending.

• Aaron Archer, Ranjithkumar Rajagopalan and David B. Shmoys, "Lagrangian relaxation for the k-median problem: new insights and continuity properties" [ps]
  • Bibliographic info: Appears in Proceedings of the 11th Annual European Symposium on Algorithms (2003) 31-42.
  • Quick summary: Good approximation algorithms for the k-median problem have been developed based on the fact that its Lagrangian relaxation is the much better-understood uncapacitated facility location problem. We make two contributions to this line of work. (1) We modify the Jain-Vazirani primal-dual algorithm for facility location in order to make it "continuous," meaning that the number of facilities opened by the algorithm never jumps by more than one as we vary the facility cost. This resolves an outstanding question posed by Jain and Vazirani, and establishes an upper bound of 3 on the integrality gap of the standard linear programming (LP) relaxation for k-median. (The previous best result was 4). This provides a rare example of an existential result proving an upper bound on an LP integrality gap without having an accompanying polynomial-time algorithm (since our algorithm involves finding a maximum independent set). (2) We give an LP-based analysis of a facility location algorithm by Mettu and Plaxton, which had previously been analyzed without any reference to an LP. One advantage of our analysis is that it leads immediately to a modification of Mettu-Plaxton that has the Lagrangian-preserving" property necessary for use in constructing an algorithm for k-median.

• Aaron F. Archer, "Two O(log*k)-approximation algorithms for the asymmetric k-center problem" [ps]
  • Bibliographic info: Appears in Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization (2001) 1-14.
  • Quick summary: Suppose there are n buildings that require protection from the fire department, but we have enough money to build only k fire stations. Where should we locate the fire stations in order to minimize the worst-case travel time to a fire? This is known as the k-center problem. For the case where the travel times are symmetric (i.e., time from A to B = time from B to A), there is a clever but simple 2-approximation algorithm (Hochbaum and Shmoys). When the times are asymmetric (possibly due to one-way streets or asymmetric traffic patterns), the problem becomes much harder. Panigrahy and Vishwanathan gave an O(log*n)-approximation based on a recursive greedy set cover procedure. We improve this result to O(log*k), using two completely different algorithms. (The log* function is the number of times we must iterate the log to bring the result below 1.)

• Aaron Archer, "Inapproximability of the asymmetric facility location and k-median problems" [ps]
  • Bibliographic info: unpublished manuscript (2000).
  • Quick summary: This paper gives lower bounds on the approximability of the facility location and k-median problems when the distance function is not symmetric, which essentially match the upper bounds given for these two problems by Hochbaum and by Lin and Vitter, respectively. We attain the bounds via a simple reduction from the set cover problem.

Network Design

• Steven J. Phillips, Paul Williams, Guy Midgley, and Aaron Archer, "Optimizing dispersal corridors for the cape proteaceae using network flow"
  • Bibliographic info: To appear in Ecological Applications in July or August, 2008.
  • Quick summary: See below.
  • Note: The customs in ecology are very different than in computer science. In order to comply with the journal's embargo policy, I will wait to post or describe the paper until after it has appeared.

• Aaron Archer, Asaf Levin and David P. Williamson, "A faster, better approximation algorithm for the minimum latency problem" [ps]
  • Bibliographic info:
    • Conference version by the first and third authors appears as "Faster approximation algorithms for the minimum latency problem," Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (2003) 88-96.
    • Improved version appears as Cornell ORIE Technical Report number 1362 (2003).
    • Journal version appears as "A faster, better approximation algorithm for the minimum latency problem," SIAM J. Comput. 37(5): 1472-1498 (2008).
  • Quick summary: The minimum latency problem (MLP), sometimes called the deliveryman or traveling repairman problem, is a customer-oriented version of the traveling salesman problem. Instead of a tour that minimizes the total travel time, we desire a tour that minimizes the average time at which we arrive at our customer locations. Blum et al. gave a method for using a beta-approximation algorithm for the rooted k-minimum spanning tree (k-MST) problem as a black box to produce an (8 beta)-approximation for MLP. Goemans and Kleinberg improved this factor to (3.59 beta). We show how to use Lagrangian relaxation to produce a 7.18-approximation for MLP (the same result one would obtain using a 2-approximation algorithm for k-MST), even though there is no 2-approximation algorithm known for the rooted k-MST problem. Our algorithm improves previous results both in approximation guarantee and running time. The analysis is clever: it involves "bluffing," along with a proof that the Goemans-Kleinberg algorithm will never call our bluff.

Graph partitioning

• Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar and Eva Tardos, "Approximate classification via earthmover metrics" [ps]
  • Bibliographic info: Appears inProceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (2004) 1072-1080.
  • Quick summary: The metric labeling problem and a special case, the 0-extension problem, ask us to label the nodes of a graph in such a way that neighboring nodes receive identical or similar labels (to the greatest extent possible). The so-called earthmover metric linear programming relaxation for the metric labeling problem is conjectured to have a small integrality gap, but attempts to use it to create approximation algorithms have so far met with limited success. We make progress in this direction by giving (1) an O(alpha)-approximation algorithm for the 0-extension problem in the case where the metric on labels is alpha-decomposable and (2) an O(log n)-approximation algorithm for the metric labeling problem, based on probabilistic tree embeddings and coordinated rounding along the tree.

Other

• Aaron F. Archer, "On the upper chromatic numbers of the reals" [ps] [pdf available from the publisher ]
  • Bibliographic info: Discrete Math., 214 (2000) 65-75.
  • Quick summary: The chromatic number of a metric space (X,d) is the minimum number of colors necessary to color every point in such a way that no two points at distance 1 get the same color. Now suppose we restrict different distances for each color, e.g., points at distance 2 cannot both be colored red, while points at distance 3 cannot both be colored blue. The upper chromatic number of X is the minimum number m of colors such that, no matter what list of m distances are restricted for the m colors, there is a legal coloring. The k^th upper chromatic number is the same, except that there are k distances restricted for each color. Our main results are: (1) For each k, the k^th upper chromatic number of the reals is at most the ceiling of 4ek, which improves the previous best upper bound of 32^k k! (2) For each k, the k^th upper chromatic number of the real numbers matches that of the integers, which is pretty astounding, since there are so many more reals to color. We generalize this to higher dimensions under the L₁ and L_infinity norms, and prove that these upper chromatic numbers are all finite. We also introduce a related quantity, the chromatic capacity of a graph, and prove some elementary results about it.
  • Addendum: I stated Theorem 14 without proof, since the proof is so similar to that of a similar theorem already in the literature. Since publication, some people have asked me for it, so here is the full proof.
  • Note: This paper came out of research I did at Joe Gallian's math REU at U. Minnesota, Duluth. Thanks for a fun summer and a fine introduction to research, Joe!

• Aaron F. Archer, Andrew D. Hutchings, and Brian Johnson, "A case for stricter grading" [ps]
  • Bibliographic info: UMAP J. 19.3 (1998) 299-313.
  • Quick summary: As a remedy for the epidemic of grade inflation, this paper proposes and investigates one scheme for adjusting students' GPAs according to the difficulty of the courses they have taken and the harshness or leniency of their professors in assigning grades for the course.
  • Note: This paper -- dreamed up and written in 89 hours -- won the SIAM award at the 1998 Mathematical Contest in Modeling. Adjacent articles in the journal explain the contest, and present the other two winning papers.

• Aaron Archer, Rick Cleary, Robin Lock and John Trono, "March Mathness: an analysis of a nonstandard basketball pool" [pdf]
  • Bibliographic info: Math Horizons (Feb. 2001) 17-21.
  • Quick summary: Office pools for the annual NCAA men's basketball tournament (nicknamed "March Madness") are a popular national diversion every March in the United States. In 2004, ESPN's online bracket challenge received about 2.4 million entries. Despite this popularity, many people are intimidated by the prospect of picking the winners in 63 games, many of them between colleges they may not have heard of, and whose basketball teams they certainly know nothing about. We suggest a different type of pool. Each team is assigned a price based on their seed -- the top seeds cost 25 cents apiece, while the bottom seeds cost only 1 cent apiece. To enter, you pay one dollar, and buy one dollar's worth of teams. Each player counts up the total number of games won by her teams, and the player with the highest total wins the jackpot. This leads to a lot of interesting mathematical questions, some of which we examine in this article.
  • Note: Co-author Rick Cleary was interviewed about this topic for the NPR show Science Friday on March 19, 2004 during the NCAA basketball tournament. Click here for the audio archive of the interview.

• Aaron F. Archer. "A modern treatment of the 15 puzzle" [ps][summary]
  • Bibliographic info: Amer. Math. Monthly, 106 (1999) 793-799.
  • Quick summary: The infamous puzzle maker Sam Loyd introduced his popular 15-puzzle in the 1870's, driving many people crazy by offering a prize of $1000 for the first person who could perform a feat that Loyd knew to be mathematically impossible. The puzzle consists of a tray that can hold a 4 by 4 grid of square pieces, which is filled by 15 squares with one square left blank. One can change the configuration by moving an adjacent square into the blank spot. The object is to obtain certain configurations of the pieces. It is easy to show that no odd permutations of the pieces are attainable, if the blank is to end up back where it started. This paper gives a particularly slick proof that all even permutations *are* attainable. It also includes many amusing historical notes about the puzzle.
  • Note: I figured out the main result while trying to avoid writing a paper for my film studies class in college. Ironically, more people have talked to me about this paper than about any of my serious research papers. I guess people really read the Monthly.

• Aaron Archer, book review of The 15 Puzzle: How It Drove the World Crazy (by Jerry Slocum and Dic Sonneveld) [pdf]
  • Bibliographic info: Appears in The Mathematical Intelligencer, 29(2): 83-85 (2007).
  • Quick summary: The book unmasks the most successful and enduring hoax ever perpetrated by renowned puzzle-maker and sometime prevaricator Sam Loyd. It is fascinating to see how the authors tease out that truth behind the invention of the 15-puzzle to set the record straight, 115 years after Loyd first committed his fraud. The book also includes numerous amusing anecdotes from newspapers and other writings published during the 15-puzzle craze of 1880, plus many beautiful photographs.

Back to Aaron's main page