Say that MyPackage.deb depends on GTK 2.19, because it is based on functionality that was deprecated in 2.20.  What happens when when I want to apt-get install TheirProgram or dpkg -i TheirProgram.deb and GTK 2.21+ is a required dependency?  What should I do in situations such as these?
What happens when two apt packages depend on two different versions of the same package?
apt;package management
Generally speaking, new versions of libraries which introduce backwards incompatibilities should change their soname, and this will then result in a new package name for the runtime library (e.g. for GTK+, libgtk2.0-0 and libgtk2.1-0 or whatever is appropriate). It's usually considered a serious bug to introduce a breaking version upgrade without following this rule.This means that, in most cases, both runtime libraries can be installed simultaneously, and dependent packages too: your MyPackage.deb would pull in the old library, TheirProgram.deb would pull in the new one. This is used in Debian during library transitions: when a new, backwards-incompatible version of a library is uploaded, a transition is started, and until all the dependent packages have been rebuilt, both versions of the library are available in the archive.Of course as a general rule distributions try to only carry a single version of a library at a time, so the old library will disappear from the archives, but as long as you've got it installed, MyPackage should continue to work. You won't get any security support on the old version of the library though, and there are no guarantees that it will keep on working (or that no other package will break it), so for the long term you'd be better of fixing MyPackage so it works with newer versions of GTK+.If the new version of GTK+ is backwards-compatible, then the package name won't change, but (bugs excepted) the runtime library will still allow MyPackage to work  so installing TheirProgram will force the GTK+ upgrade, but MyPackage shouldn't be affected. (It might print more deprecation warnings during execution.)