(The talk will be given in English)

Speaker:     Dr. Inbal Talgam Cohen
                   School of Computer Science & Engineering, Hebrew University

Monday, December 12^th, 2016
15:00 - 16:00

Room 011, Kitot Bldg., Faculty of Engineering

Computing with Strategic Agents and Uncertainty

Abstract

A centralized algorithm with perfect information can reach an efficient solution in engineering applications such as network routing, allocation of wireless spectrum, or matching jobs to machines on the cloud. Modern engineering and economic algorithms, though, face more demanding settings - algorithm input is not fully specified and the algorithm must interact with self-interested agents (for example, users with traffic demands in a communication network). In these cases, algorithm design faces new and fundamental challenges.
In this talk I will demonstrate how my research tackles these challenges, using ideas from combinatoric optimization, probability, game theory and economics. A particularly powerful idea for aligning agents’ incentives, which is heavily used in practice, is pricing (for example, consider for-profit cloud computing services). I will discuss algorithmic pricing questions that have been open for over three decades, and how these “reduce” to well-understood and classic resource allocation problems by applying a resource augmentation approach [Sleator-Tarjan’84].
 

Bio

Inbal Talgam-Cohen is a Marie Curie postdoctoral researcher at HUJI and a visiting postdoctoral researcher at TAU. She holds a PhD from Stanford (2015) supervised by Tim Roughgarden, an MSc from Weizmann and a BSc from TAU in computer science, as well as a law LLB. Her research is in algorithms and computational complexity with applications to game theory. Her awards include Best Doctoral Dissertation Award of ACM SIGecom, the Stanford Interdisciplinary Graduate Fellowship, and the Best Student Paper Award at EC’15.‏

Robust and Simple Market Design

Dr. Inbal Talgam Cohen – The Hebrew University

ABSTRACT:

Algorithms and the Internet are revolutionizing how society allocates its resources. Examples range from wireless spectrum and electricity to online advertising and carpooling opportunities. A fundamental question is how to allocate such resources efficiently by designing robust computational markets.

In this talk I will demonstrate recent progress on this question by considering a problem crucial for major industry players like Google: how to design revenue-maximizing allocation mechanisms. Most existing designs hinge on “getting the price right” – selling goods to buyers at prices low enough to encourage a sale, but high enough to garner non-trivial revenue. This approach is difficult to implement when the seller has little or no a priori information about buyers’ valuations, or when the setting is sufficiently complex, as in the case of markets with heterogeneous goods.

I will show a robust approach to designing auctions for revenue, which “lets the market do the work” by allowing prices to emerge from enhanced competition for scarce goods. This work provides guidelines for a seller in choosing among data acquisition and sophisticated pricing, and investment in drawing additional buyers.

Bio: Inbal Talgam-Cohen is a Marie Curie postdoctoral researcher at HUJI and a visiting postdoctoral researcher at TAU. She holds a PhD from Stanford (2015) supervised by Tim Roughgarden, an MSc from Weizmann and a BSc from TAU in computer science, as well as a law LLB.  Her research is in algorithmic game theory, including computational and data aspects of market design and applications to Internet economics. Her awards include Best Doctoral Dissertation Award of ACM SIGecom, the Stanford Interdisciplinary Graduate Fellowship, and the Best Student Paper Award at EC’15.

Speaker: Adam Mashiach,

M.Sc. student under the supervision of Prof. Ram Zamir.

Wednesday, December 7^th, 2016 at 15:00

Room 011, Kitot Bldg., Faculty of Engineering

Two Asymmetric Descriptions from Many Symmetric Descriptions

Abstract

Multiple descriptions provide a mechanism for graceful degradation in open-loop lossy source coding over a lossy-packet network. Existing solutions for the general asymmetric case are, however, cumbersome. We present a framework for designing an efficient asymmetric two-description scheme, based on dividing many symmetric descriptions into two groups, and encoding each group jointly.

In the first part, we present a multiple description coding scheme which is based on oversampling and dithered delta-sigma quantization that can generate large number of symmetric descriptions.  In the second part, we use this symmetric many description scheme to build an asymmetric sum-rate optimal two-description scheme. We further show that this idea can be extended to generate any number asymmetric descriptions (not only two), which are sum-rate optimal for an interesting specific case of the many description problem.