8,717 research outputs found
Near-optimal no-regret algorithms for zero-sum
No full textWe propose a new no-regret learning algorithm. When used against an adversary, our algorithm achieves average regret that scales as O (1/√T) with the number T of rounds. This regret bound is optimal but not rare, as there are a multitude of learning algorithms with this regret guarantee. However, when our algorithm is used by both players of a zero-sum game, their average regret scales as O (ln T/T), guaranteeing a near-linear rate of convergence to the value of the game. This represents an almost-quadratic improvement on the rate of convergence to the value of a game known to be achieved by any no-regret learning algorithm, and is essentially optimal as we show a lower bound of Ω (1/T). Moreover, the dynamics produced by our algorithm in the game setting are strongly-uncoupled in that each player is oblivious to the payoff matrix of the game and the number of strategies of the other player, has limited private storage, and is not allowed funny bit arithmetic that can trivialize the problem; instead he only observes the performance of his strategies against the actions of the other player and can use private storage to remember past played strategies and observed payoffs, or cumulative information thereof. Here, too, our rate of convergence is nearly-optimal and represents an almost-quadratic improvement over the best previously known strongly-uncoupled dynamics.National Science Foundation (U.S.) (CAREER Award CCF-0953960
The Complexity of Optimal Mechanism Design
No full textMyerson's seminal work provides a computationally efficient revenue-optimal auction for selling one item to multiple bidders [18]. Generalizing this work to selling multiple items at once has been a central question in economics and algorithmic game theory, but its complexity has remained poorly understood. We answer this question by showing that a revenue-optimal auction in multi-item settings cannot be found and implemented computationally efficiently, unless zpp ⊇ P[superscript #P]. This is true even for a single additive bidder whose values for the items are independently distributed on two rational numbers with rational probabilities. Our result is very general: we show that it is hard to compute any encoding of an optimal auction of any format (direct or indirect, truthful or non-truthful) that can be implemented in expected polynomial time. In particular, under well-believed complexity-theoretic assumptions, revenue-optimization in very simple multi-item settings can only be tractably approximated.
We note that our hardness result applies to randomized mechanisms in a very simple setting, and is not an artifact of introducing combinatorial structure to the problem by allowing correlation among item values, introducing combinatorial valuations, or requiring the mechanism to be deterministic (whose structure is readily combinatorial). Our proof is enabled by a flow-interpretation of the solutions of an exponential-size linear program for revenue maximization with an additional supermodularity constraint.Alfred P. Sloan Foundation (Fellowship)Microsoft Research (Faculty Fellowship)National Science Foundation (U.S.) (CAREER Award CCF-0953960)National Science Foundation (U.S.) (Award CCF-1101491)Hertz Foundation (Daniel Stroock Fellowship
The structure of auctions : optimality and efficiency
No full textThesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2014.64Cataloged from PDF version of thesis.Includes bibliographical references (pages 183-187).The problem of constructing auctions to maximize expected revenue is central to mechanism design and to algorithmic game theory. While the special case of selling a single item has been well understood since the work of Myerson, progress on the multi-item case has been sporadic over the past three decades. In the first part of this thesis we develop a mathematical framework for finding and characterizing optimal single-bidder multi-item mechanisms by establishing that revenue maximization has a tight dual minimization problem. This approach reduces mechanism design to a measure-theoretic question involving transport maps and stochastic dominance relations. As an important application, we prove that a grand bundling mechanism is optimal if and only if two particular measure-theoretic inequalities are satisfied. We also provide several new examples of optimal mechanisms and we prove that the optimal mechanism design problem in general is computationally intractable, even in the most basic multi-item setting, unless ZPP contains P #p. Another key problem in mechanism design is how to efficiently allocate a collection of goods amongst multiple bidders. In the second part of the thesis, we study the problem of welfare maximization in the presence of unrestricted rational collusion. We generalize the notion of dominant-strategy mechanisms to collusive contexts, construct a highly practical such mechanism for multi-unit auctions, and prove that no such mechanism (practical or not) exists for unrestricted combinatorial auctions. Our results explore the power and limitations of enlarging strategy spaces to incentivize agents to reveal information about their collusive behavior.by Alan Deckelbaum.Ph. D
Alan Moore Comics as Performance, Fiction as Scalpel
No full textEclectic British author Alan Moore (b. 1953) is one of the most acclaimed and controversial comics writers to emerge since the late 1970s. He has produced a large number of well-regarded comic books and graphic novels while also making occasional forays into music, poetry, performance, and prose. In Alan Moore: Comics as Performance, Fiction as Scalpel , Annalisa Di Liddo argues that Moore employs the comics form to dissect the literary canon, the tradition of comics, contemporary society, and our understanding of history. The book considers Moore's narrative strategies and pinpoints the main thematic threads in his works: the subversion of genre and pulp fiction, the interrogation of superhero tropes, the manipulation of space and time, the uses of magic and mythology, the instability of gender and ethnic identity, and the accumulation of imagery to create satire that comments on politics and art history. Examining Moore's use of comics to scrutinize contemporary culture, Di Liddo analyzes his best-known works-- Swamp Thing, V for Vendetta, Watchmen, From Hell, Promethea , and Lost Girls . The study also highlights Moore?s lesser-known output, such as Halo Jones, Skizz , and Big Numbers , and his prose novel Voice of the Fire. Alan Moore: Comics as Performance, Fiction as Scalpel reveals Moore to be one of the most significant and distinctly postmodern comics creators of the last quarter-century.Intro -- Contents -- Preface and Acknowledgments -- Introduction -- CHAPTER 1. Formal Considerations on Alan Moore's Writing -- CHAPTER 2. Chronotopes: Outer Space, the Cityscape, and the Space of Comics -- CHAPTER 3. Moore and the Crisis of English Identity -- CHAPTER 4. Finding a Way into Lost Girls -- Conclusion -- Notes -- Bibliography -- Index -- A -- B -- C -- D -- E -- F -- G -- H -- I -- J -- K -- L -- M -- N -- O -- P -- Q -- R -- S -- T -- U -- V -- W -- Y -- ZEclectic British author Alan Moore (b. 1953) is one of the most acclaimed and controversial comics writers to emerge since the late 1970s. He has produced a large number of well-regarded comic books and graphic novels while also making occasional forays into music, poetry, performance, and prose. In Alan Moore: Comics as Performance, Fiction as Scalpel , Annalisa Di Liddo argues that Moore employs the comics form to dissect the literary canon, the tradition of comics, contemporary society, and our understanding of history. The book considers Moore's narrative strategies and pinpoints the main thematic threads in his works: the subversion of genre and pulp fiction, the interrogation of superhero tropes, the manipulation of space and time, the uses of magic and mythology, the instability of gender and ethnic identity, and the accumulation of imagery to create satire that comments on politics and art history. Examining Moore's use of comics to scrutinize contemporary culture, Di Liddo analyzes his best-known works-- Swamp Thing, V for Vendetta, Watchmen, From Hell, Promethea , and Lost Girls . The study also highlights Moore?s lesser-known output, such as Halo Jones, Skizz , and Big Numbers , and his prose novel Voice of the Fire. Alan Moore: Comics as Performance, Fiction as Scalpel reveals Moore to be one of the most significant and distinctly postmodern comics creators of the last quarter-century.Description based on publisher supplied metadata and other sources.Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, YYYY. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries
Mechanism Design via Optimal Transport
No full textOptimal mechanisms have been provided in quite general multi-item settings [Cai et al. 2012b, as long as each bidder's type distribution is given explicitly by listing every type in the support along with its associated probability. In the implicit setting, e.g. when the bidders have additive valuations with independent and/or continuous values for the items, these results do not apply, and it was recently shown that exact revenue optimization is intractable, even when there is only one bidder [Daskalakis et al. 2013]. Even for item distributions with special structure, optimal mechanisms have been surprisingly rare [Manelli and Vincent 2006] and the problem is challenging even in the two-item case [Hart and Nisan 2012]. In this paper, we provide a framework for designing optimal mechanisms using optimal transport theory and duality theory. We instantiate our framework to obtain conditions under which only pricing the grand bundle is optimal in multi-item settings (complementing the work of [Manelli and Vincent 2006]), as well as to characterize optimal two-item mechanisms. We use our results to derive closed-form descriptions of the optimal mechanism in several two-item settings, exhibiting also a setting where a continuum of lotteries is necessary for revenue optimization but a closed-form representation of the mechanism can still be found efficiently using our framework.Alfred P. Sloan Foundation (Fellowship)Microsoft Research (Faculty Fellowship)National Science Foundation (U.S.) (CAREER Award CCF-0953960)National Science Foundation (U.S.) (Award CCF-1101491)Hertz Foundation (Daniel Stroock Fellowship
Optimal Pricing Is Hard
No full textWe show that computing the revenue-optimal deterministic auction in unit-demand single-buyer Bayesian settings, i.e. the optimal item-pricing, is computationally hard even in single-item settings where the buyer’s value distribution is a sum of independently distributed attributes, or multi-item settings where the buyer’s values for the items are independent. We also show that it is intractable to optimally price the grand bundle of multiple items for an additive bidder whose values for the items are independent. These difficulties stem from implicit definitions of a value distribution. We provide three instances of how different properties of implicit distributions can lead to intractability: the first is a #P-hardness proof, while the remaining two are reductions from the SQRT-SUM problem of Garey, Graham, and Johnson [14]. While simple pricing schemes can oftentimes approximate the best scheme in revenue, they can have drastically different underlying structure. We argue therefore that either the specification of the input distribution must be highly restricted in format, or it is necessary for the goal to be mere approximation to the optimal scheme’s revenue instead of computing properties of the scheme itself.Microsoft Research (Fellowship)Alfred P. Sloan Foundation (Fellowship)National Science Foundation (U.S.) (CAREER Award CCF-0953960)National Science Foundation (U.S.) (Award CCF-1101491)Hertz Foundation (Daniel Stroock Fellowship
In Alan Turing’s Name: Pardoning the Dead, Forgetting the Living
No full textThis special panel discussion brought together authorities on Alan Turing and the statutory pardon legislation intended to honour him. Leading academics, in conversation with those who have unsuccessfully petitioned to have offences disregarded, were joined by the Turing Bill’s author
Bernard Williams
No full textAn edited multi-author volume assessing the moral philosophy of the late British philosopher Bernard Williams. Contributors: Adrian Moore, John Skorupski, Alan Thomas, Robert B Louden, Michael Stocker, A. A. Long, Edward Crai
Post-war British working-class fiction with special reference to the novels of John Braine, Alan Sillitoe, Stan Barstow, David Storey and Barry Hines
No full textThis study is about British working-class fiction in the post-war period.
It covers various authors such as Robert Tressell, George Orwell, Walter Greenwood, Lewis Grassic Gibbon and DH Lawrence from the early twentieth century; writers traditionally classified as 'Angry Young Men' like John Osborne, Arnold Wesker, Shelagh Delaney, John Wain and
Kingsley Amis; and working-class novelists like John Braine, Stan Barstow, David Storey, Alan Sillitoe and Barry Hines from the 1950s and 1960s.
Some of the main issues dealt with in the course of this study are language, form, community, self/identity/autobiography, sexuality and relationship with bourgeois art. The major argument centres on two questions: representation of working-class life, and the
relationship between working-class literary tradition and dominant ideologies.
We will be arguing that while working-class fiction succeeded in challenging and rupturing bourgeois literary tradition, on the level of language and linguistic medium of expression for example, it utterly failed to break away from dominant, bourgeois modes of literary production in relation to form, for instance.
Our argument is situated within Marxist approaches to literature, a political and aesthetic position from which we attempt an analysis and an evaluation of this working-class literary tradition. These critical approaches provide us also with the theoretical tool to define the political perspective of this tradition, and to judge whether it was confined to a descriptive mode of representation or
located in a radical, political outlook
- …
